Finite Automata and Their Decision Problems

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

About this paper中文日本語

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
Tiếng Việt

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.

Ôtômat hữu hạn và các bài toán quyết định của chúng†

Tóm tắt: Các ôtômat hữu hạn được xem xét trong bài báo này như những công cụ để phân loại các băng hữu hạn. Mỗi ôtômat một băng xác định một tập các băng, một ôtômat hai băng xác định một tập các cặp băng, v.v. Cấu trúc của các tập được xác định được nghiên cứu. Nhiều khái quát hóa khác nhau của khái niệm ôtômat được đưa ra và mối quan hệ của chúng với các ôtômat cổ điển được xác định. Một số bài toán quyết định liên quan đến ôtômat được chứng minh là có thể giải được bằng các thuật toán hữu hiệu; các bài toán khác hóa ra không thể giải được bằng thuật toán.

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 Tiếng Việt by gpt-5, against glossary version 7. Translated from the English.