Теорема Кука о двусторонних автоматах

Детерминированный двусторонний автомат с магазинной памятью может быть определён как набор ${\displaystyle P=(Q,\Sigma ,\Pi ,\delta ,s_{0},Z_{0},s_{t})}$, где[1]

• ${\displaystyle Q}$ — множество состояний автомата,
• ${\displaystyle \Sigma }$ — входной алфавит,
• ${\displaystyle \Pi }$ — стековый алфавит,
• ${\displaystyle \delta }$ — множество переходов автомата,
• ${\displaystyle q_{0}\in Q}$ — начальное состояние автомата,
• ${\displaystyle Z}$ — нижний символ стека,
• ${\displaystyle s_{t}}$ — финальное состояние.

• Andersen N., Jones N. D. Generalizing Cook's transformation to imperative stack programs (англ.) // Lect. Notes Comput. Sci. / G. Goos, J. Hartmanis, J. v. Leeuwen — Berlin, Heidelberg, New York, NY, London [etc.]: Springer, 1994. — P. 1—18. — ISSN 0302-9743; 1611-3349 — doi:10.1007/3-540-58131-6_33
• Mogensen T. Æ. WORM-2DPDAs: An extension to 2DPDAs that can be simulated in linear time (англ.) // Inform. Process. Lett. — Elsevier BV, 1994. — Vol. 52, Iss. 1. — P. 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. — С. 341—356. — doi:10.1007/978-3-642-82456-2_24
• Galil Z., Seiferas J. A Linear-Time On-Line Recognition Algorithm for ``Palstar (англ.) // J. ACM / D. J. Rosenkrantz — New York, N.Y.: Association for Computing Machinery, 1978. — Vol. 25, Iss. 1. — P. 102—111. — ISSN 0004-5411; 1557-735X — doi:10.1145/322047.322056
• Jones N. D. A note on linear time simulation of deterministic two-way pushdown automata (англ.) // Inform. Process. Lett. — Elsevier BV, 1977. — Vol. 6, Iss. 4. — P. 110—112. — ISSN 0020-0190; 1872-6119 — doi:10.1016/0020-0190(77)90022-9
• Manacher G. K. A new linear-time “on-line” algorithm for finding the smallest initial palindrome of a string (англ.) // J. ACM / D. J. Rosenkrantz — New York, N.Y.: Association for Computing Machinery, 1975. — Vol. 22, Iss. 3. — P. 346—351. — ISSN 0004-5411; 1557-735X — doi:10.1145/321892.321896
• Apostolico A., Breslauer D., Galil Z. Parallel detection of all palindromes in a string (англ.) // Theoretical Computer Science — Elsevier BV, 1995. — Vol. 141, Iss. 1-2. — P. 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 (англ.) — Boston: Addison-Wesley, 1974. — 480 p. — 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. — P. 323—350. — ISSN 0097-5397; 1095-7111 — doi:10.1137/0206024