Finite Automata and Their Decision Problems

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

About this paperTiếng Việt中文

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.

English
日本語

Abstract: Finite automata are considered in this paper as instruments for classifying finite tapes. Each one-tape automaton defines a set of tapes, a two-tape automaton defines a set of pairs of tapes, et cetera. The structure of the defined sets is studied. Various generalizations of the notion of an automaton are introduced and their relation to the classical automata is determined. Some decision problems concerning automata are shown to be solvable by effective algorithms; others turn out to be unsolvable by algorithms.

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

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

Introduction

This section is missing here.

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.

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.