On the Class of Predicates Decidable by Two-Way Multitape Finite Automata

DOI10.1145/321328.321335MaRDI QIDQ5514601zbMATH OpenOpenAlexFDO

Authors Kojiro Kobayashi, Shigeru Sekiguchi

Publication date 1966

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/321328.321335

zbMATH Keywords

mathematical logic

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX) Formal languages and automata (68Q45)

Recommendations

• A class of multitape automata with a decidable equivalence problem
• scientific article; zbMATH DE number 4769
• Publication:4939597
• The equivalence problem of multitape finite automata
• Equivalence of two-dimensional multitape automata

Cites work

• Decision Problems of Finite Automata Design and Related Arithmetics
• scientific article; zbMATH DE number 3131080 (Why is no real title available?)
• scientific article; zbMATH DE number 7354705 (Why is no real title available?)
• scientific article; zbMATH DE number 3254906 (Why is no real title available?)
• Operations Which Preserve Definability in Languages
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Two Families of Languages Related to ALGOL
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(3)

• On the determinacy problem for two-way pushdown automata
• Multitape finite automata with rewind instructions
• A Fast Parallel Algorithm for the Robust Prediction of the Two-Dimensional Strict Majority Automaton

This page was built for publication: On the Class of Predicates Decidable by Two-Way Multitape Finite Automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5514601)