A class of multitape automata with a decidable equivalence problem

MaRDI QIDQ794436zbMATH OpenFDO

Authors Efim Kinber

Publication date 1983

Published in Programming and Computer Software (Search for Journal in Brave)

zbMATH Keywords

decidabilityequivalence problemsmulti-tape automataone-way automatatwo-tape automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Review text

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

• Equivalence of two-dimensional multitape automata
• The equivalence problem of multidimensional multitape automata
• Revisiting the equivalence problem for finite multitape automata
• scientific article; zbMATH DE number 4037263
• The equivalence problem of multitape finite automata

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)