Algoritmo di Markov

sistema di riscrittura di stringhe (sistema semi-Thue) che si basa su regole analoghe a quelle grammaticali

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.

DefinizioneModifica

Formalmente, un algoritmo di Markov è una quaterna  , dove:

  •   è un alfabeto
  •   è un insieme finito non vuoto di coppie di parole su   munito di una relazione d'ordine
  •   è un sottoinsieme di   i cui elementi sono detti regole finali
  •   è un sottoinsieme di   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.

BibliografiaModifica

  • (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 esterniModifica

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