A class of multitape automata with a decidable equivalence problem
From MaRDI portal
The equivalence problems for two-tape automata and multi-tape automata, each of which is contained in at most one cycle, were proved. The question of the decidability of the equivalence problem in the general case has remained open. This paper establishes the decidability of the equivalence problem for the class of multitape one-way automata admitting transitions to all except two of the tapes only a bounded number of times.
Recommendations
Cited in
(19)- Complete system of equivalent transformations for multitape automata
- Minimality and deadlockness of multitape automata
- Loops in automata and HDTOL relations
- LABELLING MULTI-TAPE AUTOMATA WITH CONSTRAINED SYMBOL CLASSES
- The Equivalence Problem of Deterministic Multitape Finite Automata: A New Proof of Solvability Using a Multidimensional Tape
- scientific article; zbMATH DE number 4037263 (Why is no real title available?)
- Formalization of the concept of multitape automaton
- scientific article; zbMATH DE number 4100618 (Why is no real title available?)
- scientific article; zbMATH DE number 4769 (Why is no real title available?)
- On the equivalence problem for deterministic multitape automata and transducers
- Revisiting the equivalence problem for finite multitape automata
- Implementation and Application of Automata
- On the Class of Predicates Decidable by Two-Way Multitape Finite Automata
- A new approach to solving equivalence problem
- Multi-tape Automata with Symbol Classes
- HDTOL matching of computations of multitape automata
- The equivalence problem of multitape finite automata
- Equivalence of two-dimensional multitape automata
- The equivalence problem of multidimensional multitape automata
This page was built for publication: A class of multitape automata with a decidable equivalence problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q794436)
