Log in
Enquire now
Markov algorithm

Markov algorithm

In theoretical computer science, a Markov algorithm is a string rewriting system that uses grammar-like rules to operate on strings of symbols.

OverviewStructured DataIssuesContributors

Contents

TimelineTable: Further ResourcesReferences

Markov algorithms have been shown to be Turing-complete, which means that they are suitable as a general model of computation and can represent any mathematical expression from its simple notation. Markov algorithms are named after the Soviet mathematician Andrey Markov, Jr.

Refal is a programming language based on Markov algorithms.

Here is an example of a normal algorithm scheme in the five-letter alphabet |*abc:

Algorithm

The Rules are a sequence of pairs of strings, usually presented in the form of pattern → replacement. Each rule may be either ordinary or terminating.

Given an input string:

1. Check the Rules in order from top to bottom to see whether any of the patterns can be found in the input string.

2. If none is found, the algorithm stops.

3. If one (or more) is found, use the first of them to replace the leftmost occurrence of matched text in the input string with its replacement.

4. If the rule just applied was a terminating one, the algorithm stops.

5. Go to step 1.

Note that after each rule application the search starts over from the first rule.

Timeline

No Timeline data yet.

Further Resources

Title
Author
Link
Type
Date
No Further Resources data yet.

References

Find more entities like Markov algorithm

Use the Golden Query Tool to find similar entities by any field in the Knowledge Graph, including industry, location, and more.
Open Query Tool
Access by API
Golden Query Tool
Golden logo

Company

  • Home
  • Press & Media
  • Blog
  • Careers
  • WE'RE HIRING

Products

  • Knowledge Graph
  • Query Tool
  • Data Requests
  • Knowledge Storage
  • API
  • Pricing
  • Enterprise
  • ChatGPT Plugin

Legal

  • Terms of Service
  • Enterprise Terms of Service
  • Privacy Policy

Help

  • Help center
  • API Documentation
  • Contact Us
By using this site, you agree to our Terms of Service.