Cookes sats om tvåsidiga automater

Cookes teorem  är ett resultat av automatteori som visar att exekveringen av en tvåvägs deterministisk pushdown- automat kan simuleras i linjär tid på en direktminnesmaskin . Upptäcktes 1970 av forskaren Stephen Cook vid University of Toronto . Satsen har tjänat som den teoretiska grunden för många linjära textbehandlingsalgoritmer, såsom Manaker- algoritmen , Knuth-Morris-Pratt- algoritmen och Weiner-algoritmen .

Staging

En deterministisk pushdown-automat kan definieras som en uppsättning , där [1]

•  är uppsättningen av automattillstånd,
•  - mata in alfabet,
•  - stapla alfabetet,
•  - många övergångar av automaten,
•  är maskinens initiala tillstånd,
•  är den nedersta symbolen för stacken,
•  - sluttillstånd.

Anteckningar

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

Litteratur

• Andersen N., Jones N. D. Generalizing Cooks transformation till imperativa stackprogram  // Lect . Obs Comput. sci. / G. Goos , J. Hartmanis , J. v. Leeuwen - Berlin , Heidelberg , New York, NY , London [etc.] : Springer , 1994. - S. 1-18. — ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-58131-6_33
• Mogensen T. Æ. WORM-2DPDA: En förlängning till 2DPDA som kan simuleras i linjär tid  // Inform . bearbeta. Lett. - Elsevier BV , 1994. - Vol. 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 och rekursiva program - 1985. - S. 341-356. doi:10.1007/ 978-3-642-82456-2_24
• Galil Z., Seiferas J. A Linear-Time On-Line Recognition Algorithm for ``Palstar (engelska) // 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. En anteckning om linjär tidssimulering av deterministiska tvåvägs pushdown-automater  // Inform . bearbeta. Lett. - Elsevier BV , 1977. - Vol. 6, Iss. 4. - S. 110-112. — ISSN 0020-0190 ; 1872-6119 - doi:10.1016/0020-0190(77)90022-9
• Manacher G. K. En ny linjär-tid "on-line" algoritm för att hitta den minsta initiala palindromen av en sträng  // 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. Parallell detektering av alla palindromer i en sträng  (engelska) // 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  (engelska) - 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. Comput. / M. Sudan - SIAM , 1977. - Vol. 6, Iss. 2. - S. 323-350. — ISSN 0097-5397 ; 1095-7111 - doi:10.1137/0206024