• Science • People
Non User
 • Locations • Timeline
Index: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Home > Markov algorithm

 Contents
1 Example
1.1 Rules
1.2 Symbol string
1.3 Algorithm
1.4 Execution of the algorithm
A 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.

1 Example

The following example shows the basic operation of a Markov algorithm.

1.1 Rules

  1. "A" -> "apple"
  2. "B" -> "bag"
  3. "S" -> "shop"
  4. "T" -> "the"
  5. "the shop" -> "my brother"

1.2 Symbol string

"I bought a B of As from T S."

1.3 Algorithm

  1. 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.
  2. If none are found, stop executing the Algorithm.
  3. 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.
  4. Return to step 1 and carry on.

1.4 Execution of the algorithm

If the algorithm is applied to the above example, the Symbol string will change in the following manner.

  1. "I bought a B of apples from T S."
  2. "I bought a bag of apples from T S."
  3. "I bought a bag of apples from T shop."
  4. "I bought a bag of apples from the shop."
  5. "I bought a bag of apples from my brother."

The algorithm will then terminate.

References:


computer science

Read more »

Topics: Markov Algorithm, Example, Rules, Symbol String, Algorithm...

Markov chainIn mathematics, a (discrete-time) Markov chain is a discrete-time stochastic process with the Markov property. In such a process, the distant past is irrelevant given knowledge of the recent past. There are also continuous-time Markov chains. A Markov chaMarkov 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 powerMarkov's inequalityIn probability theory, Markov's inequality gives an upper bound for the probability that a non-negative function of a random variable is greater than or equal to some positive constant. It is named after the Russian mathematician Andrey Markov. Markov's i
Markovnikov's ruleIn chemistry, Markovnikov's rule is an observation based on Zaitsev's Rule. It was formulated by the Russian chemist Vladimir Vasilevich Markovnikov. It states that, in chemical reactions found particularly in organic chemistry, when a hydrogen halide reaMarkov propertyIn probability theory, a stochastic process has the Markov property if the conditional probability distribution of future states of the process, given the present state, depends only upon the current state, i. it is conditionally independent of the past sMarkovThe name Markov can refer to Andrey Markov, mathematician. Georgi Markov, dissident. In probability theory, the Markov property.
MarkovianMarkovian Parallax DenigrateMarkov decision process
Markov blanket  
Non User