Algoritmul Markov

În logica matematică , un algoritm Markov este un sistem de rescriere a șirurilor ( sistem semi-Thue ) care se bazează pe reguli similare gramaticii. S-a dovedit că acești algoritmi sunt Turing complet .

Definiție

În mod formal, un algoritm Markov este un cuatern ${\mathcal {M}}=(\Sigma ,P,F,T)$ ${\ displaystyle {\ mathcal {M}} = (\ Sigma, P, F, T)}$ ${\ displaystyle {\ mathcal {M}} = (\ Sigma, P, F, T)}$ , unde este:

$\Sigma$ ${\ displaystyle \ Sigma}$ $\ Sigma$ este un alfabet
$(P,\leq )$ ${\ displaystyle (P, \ leq)}$ ${\ displaystyle (P, \ leq)}$ este un set finit non-gol de perechi de cuvinte pe $\Sigma$ ${\ displaystyle \ Sigma}$ $\ Sigma$ cu un raport de comandă
$F.$ ${\ displaystyle F}$ $F.$ este un subset de $P.$ ${\ displaystyle P}$ $P.$ ale cărui elemente se numesc reguli finale
$T.$ ${\ displaystyle T}$ $T.$ este un subset de $\Sigma$ ${\ displaystyle \ Sigma}$ $\ Sigma$ a spus alfabetul final

Comparativ cu un sistem generic de rescriere, un algoritm Markov are proprietatea suplimentară că, pentru fiecare etapă a substituției, trebuie aplicată prima regulă (în sensul elementului minim) dintre cele posibile.

Bibliografie

( EN ) A. Caracciolo di Forino, Limbaje de procesare șir și algoritmi Markov generalizați. În: Limbaje și tehnici de manipulare a simbolurilor, DG Bobrow (Ed.), North-Holland Publ. Co., Amsterdam, 1968, pp. 191-206.

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

linkuri externe

( EN ) Algoritmul Markov , în PlanetMath .

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică