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.

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

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

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.