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.

有限オートマトンとその決定問題†

要旨：本論文では、有限オートマトンを有限テープを分類するための道具として考察する。各1テープ・オートマトンはテープの集合を定義し、2テープ・オートマトンはテープの対の集合を定義する、その他も同様である。定義された集合の構造を研究する。オートマトンの概念のさまざまな一般化を導入し、それらと古典的オートマトンとの関係を明らかにする。オートマトンに関するいくつかの決定問題は有効なアルゴリズムによって解けることを示し、他の問題はアルゴリズムによって解けないことを示す。

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.