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

Теорема Кука — результат теории автоматов, демонстрирующий, что выполнение двустороннего детерминированного автомата с магазинной памятью может быть смоделировано за линейное время на машине с произвольным доступом к памяти. Открыта в 1970 году учёным из торонтского университета Стивеном Куком. Теорема послужила теоретическим фундаментом для множества линейных алгоритмов обработки текста, таких как алгоритм Манакера, алгоритм Кнута — Морриса — Пратта и алгоритм Вайнера.

Постановка

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

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

Литература

• Andersen N., Jones N. D. Generalizing Cook's transformation to imperative stack programs (англ.) // Lecture notes in computer science / G. Goos, J. Hartmanis, J. v. Leeuwen — Berlin, Heidelberg, New York City, London: 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 (англ.) // Information Processing Letters — 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 (англ.) // Journal of the ACM / D. J. Rosenkrantz — New York City: 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 (англ.) // Information Processing Letters — 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 (англ.) // Journal of the ACM / D. J. Rosenkrantz — New York City: 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 Journal on Computing / M. Sudan — SIAM, 1977. — Vol. 6, Iss. 2. — P. 323—350. — ISSN 0097-5397; 1095-7111 — doi:10.1137/0206024