Algoritmo di Markov

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica wikitesto]

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

  • \Sigma è un alfabeto
  • (P, \leq) è un insieme finito non vuoto di coppie di parole su \Sigma munito di una relazione d'ordine
  • F è un sottoinsieme di P i cui elementi sono detti regole finali
  • T è un sottoinsieme di \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[modifica | modifica wikitesto]

  • (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[modifica | modifica wikitesto]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica