|
|
|
|
|
Markov AlgorithmA Markov algorithm is a string rewriting system that uses grammar-like rules to operate on strings of symbols. Markov algorithms have been shown to have sufficient power to be a general model of computation, and can thus be shown to be equivalent in power to a Turing machine. Since this model is Turing-complete, Markov algorithms can represent any mathematical expression from its simple notation. Example The following example shows the basic operation of a Markov algorithm. Rules - "A" -> "apple"
- "B" -> "bag"
- "S" -> "shop"
- "T" -> "the"
- "the shop" -> "my brother"
Symbol string "I bought a B of As from T S." Algorithm - Check the Rules in order from top to bottom to see whether any of the strings to the left of the arrow can be found in the Symbol string.
- If none are found, stop executing the Algorithm.
- If one or more is found, replace the leftmost matching text in the Symbol string with the text to the right of the arrow in the first corresponding Rule.
- Return to step 1 and carry on.
Execution of the algorithm If the algorithm is applied to the above example, the Symbol string will change in the following manner. - "I bought a B of apples from T S."
- "I bought a bag of apples from T S."
- "I bought a bag of apples from T shop."
- "I bought a bag of apples from the shop."
- "I bought a bag of apples from my brother."
The algorithm will then terminate. References: - Caracciolo di Forino, A. String processing languages and generalized Markov algorithms. In Symbol manipulation languages and techniques, D. G. Bobrow (Ed.), North-Holland Publ. Co., Amsterdam, The Netherlands, 1968, pp. 191-206.
- Markov, A.A. 1960. The Theory of Algorithms. American Mathematical Society Translations, series 2, 15, 1-14.
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|