Cookeova věta o dvoustranných automatech

Cookeův teorém  je výsledkem teorie automatů demonstrující, že provádění dvoucestného deterministického zásobníkového automatu lze simulovat v lineárním čase na stroji s pamětí s náhodným přístupem . Objevil ho v roce 1970 vědec Stephen Cook z University of Toronto . Věta sloužila jako teoretický základ pro mnoho lineárních algoritmů zpracování textu, jako je Manakerův algoritmus , Knuth-Morris-Prattův algoritmus a Weinerův algoritmus .

Inscenace

Deterministický zásobníkový automat lze definovat jako množinu , kde [1]

•  je množina stavů automatu,
•  - vstupní abeceda,
•  - zásobníková abeceda,
•  - mnoho přechodů automatu,
•  je výchozí stav stroje,
•  je spodní symbol hromádky,
•  - konečný stav.

Poznámky

1. ↑ Aho, Hopcroft, Ullman, 1974 , str. 337

Literatura

• Andersen N., Jones N. D. Generalizing Cookova transformace na imperativní zásobníkové programy  // Lect . Poznámka Výpočet. sci. / G. Goos , J. Hartmanis , J. v. Leeuwen - Berlín , Heidelberg , New York, NY , Londýn [atd.] : Springer , 1994. - S. 1-18. — ISSN 0302-9743 ; 1611-3349 – doi:10.1007/3-540-58131-6_33
• Mogensen T. Æ. WORM-2DPDA: Rozšíření 2DPDA, které lze simulovat v lineárním čase  // Inform . proces. Lett. - Elsevier BV , 1994. - Sv. 52, Iss. 1. - S. 15-22. — ISSN 0020-0190 ; 1872-6119 – doi:10.1016/0020-0190(94)90134-1
• Rytter W. The Complexity of Two-Way Pushdown Automata and Recursive Programs - 1985. - S. 341-356. doi:10.1007/ 978-3-642-82456-2_24
• Galil Z., Seiferas J. Algoritmus on-line rozpoznávání v lineárním čase pro ``Palstar (anglicky) // J. ACM / D. J. Rosenkrantz - New York, NY : Association for Computing Machinery , 1978. - Vol. 25, Iss. 1. - S. 102-111. — ISSN 0004-5411 ; 1557-735X – doi:10.1145/322047.322056
• Jones N. D. Poznámka k lineární časové simulaci deterministických dvoucestných zásobníkových automatů  // Inform . proces. Lett. - Elsevier BV , 1977. - Sv. 6, Iss. 4. - S. 110-112. — ISSN 0020-0190 ; 1872-6119 – doi:10.1016/0020-0190(77)90022-9
• Manacher G. K. Nový „on-line“ algoritmus s lineárním časem pro nalezení nejmenšího počátečního palindromu řetězce  // J. ACM / D. J. Rosenkrantz - New York, NY : Association for Computing Machinery , 1975. - Vol. 22, Iss. 3. - S. 346-351. — ISSN 0004-5411 ; 1557-735X – doi:10.1145/321892.321896
• Apostolico A. , Breslauer D., Galil Z. Paralelní detekce všech palindromů v řetězci  (anglicky) // Theoretical Computer Science - Elsevier BV , 1995. - Vol. 141, Iss. 1-2. - S. 163-173. — ISSN 0304-3975 ; 1879-2294 – doi:10.1016/0304-3975(94)00083-U
• Aho A. , Hopcroft J.E. , Ullman J.D. The Design and Analysis of Computer Algorithms  (anglicky) - Boston : Addison-Wesley , 1974. - 480 s. — ISBN 978-0-201-00029-0
• Knuth D. E. , James H. Morris, Jr. , Pratt V. R. Fast Pattern Matching in Strings  // SIAM J. Compput. / M. Súdán - SIAM , 1977. - Sv. 6, Iss. 2. - S. 323-350. — ISSN 0097-5397 ; 1095-7111 – doi:10.1137/0206024