1959/04/01 by M. O. Rabin, D. Scott · 21 citations
Computer Science · #Advanced Algebra and Logic #Machine Learning and Algorithms #semigroups and automata theory
paper · doi:10.1147/rd.32.0114
crossref issued 1959/04/01 · crossref published 1959/04/01 · crossref published-print 1959/04/01 · openalex publication_date 1959/04/01 · crossref created 2010/04/05 · openalex created_date 2025/10/10 · crossref deposited 2025/10/27 · crossref indexed 2026/07/31 · openalex updated_date 2026/07/31
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.