Algoritmo di Markov

In logica matematica, un algoritmo di Markov è un sistema di riscrittura di stringhe (sistema semi-Thue) che si basa su regole analoghe a quelle grammaticali. È stato dimostrato che questi algoritmi sono Turing completi.

Definizione

Formalmente, un algoritmo di Markov è una quaterna ${\displaystyle {\mathcal {M}}=(\Sigma ,P,F,T)}$, dove:

• ${\displaystyle \Sigma }$ è un alfabeto
• ${\displaystyle (P,\leq )}$ è un insieme finito non vuoto di coppie di parole su ${\displaystyle \Sigma }$ munito di una relazione d'ordine
• ${\displaystyle F}$ è un sottoinsieme di ${\displaystyle P}$ i cui elementi sono detti regole finali
• ${\displaystyle T}$ è un sottoinsieme di ${\displaystyle \Sigma }$ detto l'alfabeto finale

Rispetto ad un generico sistema di riscrittura, un algoritmo di Markov ha in più la proprietà che, per ogni passo della sostituzione, deve essere applicata la prima (nel senso di elemento minimale) regola tra quelle possibili.

Bibliografia

• (EN) A. Caracciolo di Forino, String processing languages and generalized Markov algorithms. In: Symbol manipulation languages and techniques, D. G. Bobrow (Ed.), North-Holland Publ. Co., Amsterdam, 1968, pp. 191-206.

• (EN) Andrey Andreevich Markov, The Theory of Algorithms. American Mathematical Society Translations, series 2, 15, 1-14, 1960.

Collegamenti esterni

• Markov, algoritmo di, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) Markov algorithm, in PlanetMath.