Finite Automata and Their Decision Problems

Michael O. Rabin, Dana Scott, 1959, IBM Journal of Research and Development

About this paperEnglishTiếng Việt日本語beside Englishbeside Tiếng Việtbeside 日本語

This paper is under a licence that does not allow it to be reproduced, so what is here is its front matter and a short abstract. Read it at the publisher's page.

有限自动机及其判定问题†

摘要：本文将有限自动机视为对有限带进行分类的工具。每个单带自动机定义一个带集合，双带自动机定义一个带对集合，依此类推。我们研究所定义集合的结构。本文引入了自动机概念的各种推广，并确定了它们与经典自动机之间的关系。我们证明了一些关于自动机的判定问题可以通过有效算法求解；另一些问题则无法通过算法求解。

References

  1. A. W. Burks and Hao Wang, "The logic of automata," Journal of the Association for Computing Machinery, 4, 193-218 and 279-297 (1957).
  2. S. C. Kleene, "Representation of events in nerve nets and finite automata," Automata Studies, Princeton, pp. 3-41, (1956).
  3. W. S. McCulloch and E. Pitts, "A logical calculus of the ideas imminent in nervous activity," Bulletin of Mathematical Biophysics, 5, 115-133 (1943).
  4. E. F. Moore, "Gedanken-experiments on sequential machines," Automata Studies, Princeton, pp. 129-153 (1956).
  5. A. Nerode, "Linear automaton transformations," Proceedings of the American Mathematical Society, 9, 541-544 (1958).
  6. E. Post, "A variant of a recursively unsolvable problem," Bulletin of the American Mathematical Society, 52, 264-268 (1946).
  7. J. C. Shepherdson, "The reduction of two-way automata to one-way automata," IBM Journal, 3, 198-200 (1959). Revised manuscript received August 8, 1958

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8. Translated into 中文 by gpt-5, against glossary version 6. Translated from the English.