On the Class of Predicates Decidable by Two-Way Multitape Finite Automata
- 1 April 1966
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 13 (2) , 236-261
- https://doi.org/10.1145/321328.321335
Abstract
The problem of deciding predicates concerned with m -tuples of words by means of 2-way multitape finite automata is considered. In general, more than m tapes are used to decide a predicate concerned with m -tuples of words. In such a way, a necessary and sufficient condition for a predicate to be decidable by a 2-way multitape finite automaton is obtained. The relation between the ability of Turing machines and that of 2-way multitape finite automata is also discussed.Keywords
This publication has 7 references indexed in Scilit:
- Operations Which Preserve Definability in LanguagesJournal of the ACM, 1963
- Two Families of Languages Related to ALGOLJournal of the ACM, 1962
- Recursive Unsolvability of Post's Problem of "Tag" and other Topics in Theory of Turing MachinesAnnals of Mathematics, 1961
- Decision problems of finite automata design and related arithmeticsTransactions of the American Mathematical Society, 1961
- Weak Second‐Order Arithmetic and Finite AutomataMathematical Logic Quarterly, 1960
- Finite Automata and Their Decision ProblemsIBM Journal of Research and Development, 1959
- The Reduction of Two-Way Automata to One-Way AutomataIBM Journal of Research and Development, 1959