The equivalence problem of multitape finite automata

DOI10.1016/0304-3975(91)90356-7zbMATH Open0727.68063OpenAlexW2111270089WikidataQ60162917 ScholiaQ60162917MaRDI QIDQ804302FDOQ804302

Tero Harju, Juhani Karhumäki

Publication date: 1991

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90356-7

Recommendations

Revisiting the equivalence problem for finite multitape automata
A class of multitape automata with a decidable equivalence problem
The equivalence problem of multidimensional multitape automata
scientific article; zbMATH DE number 4769
On the equivalence problem for deterministic multitape automata and transducers

zbMATH Keywords

multiplicity multitape automata multiplicity equivalent

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

Cited In (72)

LABELLING MULTI-TAPE AUTOMATA WITH CONSTRAINED SYMBOL CLASSES
On Power Series over a Graded Monoid
Why We Need Semirings in Automata Theory (Extended Abstract)
Title not available (Why is that?)
Decidability and syntactic control of interference
An iteration property of Lindenmayerian power series
On Synchronized Multitape and Multihead Automata
Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines
On the multiplicity equivalence problem for context-free grammars
Systems of equations over a finite set of words and automata theory
Reversibility of computations in graph-walking automata
Complete system of equivalent transformations for two-tape automata with disjoint loops
A note on the equivalence problem of rational formal power series
On equality of multiplicity sets of regular languages
Equations over finite sets of words and equivalence problems in automata theory
On Lindenmayerian algebraic sequences
Some decisional problems on rational relations
Weighted automata with discounting
On morphically generated formal power series
On the Ambiguity and Finite-Valuedness Problems in Acceptors and Transducers
Title not available (Why is that?)
The problem of equivalent transformations for homogeneous multitape automata
Automaton semigroup models of programs
Synchronized rational relations of finite and infinite words
Direct and dual laws for automata with multiplicities
Using algebraic models of programs for detecting metamorphic malwares
Title not available (Why is that?)
Highly Undecidable Problems For Infinite Computations
On Lindenmayerian algebraic power series
\(L(A)=L(B)\)? decidability results from complete formal systems
SOME DECISION QUESTIONS CONCERNING THE TIME COMPLEXITY OF LANGUAGE ACCEPTORS
On size reduction techniques for multitape automata
Many aspects of defect theorems
HDTOL matching of computations of multitape automata
Modelization of deterministic rational relations
A polynomial algorithm testing partial confluence of basic semi-Thue systems
A polynomial algorithm testing partial confluence of basic semi-Thue systems
The Equivalence Problem of Deterministic Multitape Finite Automata: A New Proof of Solvability Using a Multidimensional Tape
Another approach to the equivalence of measure-many one-way quantum finite automata and its application
Finite transducers and rational transductions
Synchronized tree automata
Multiplicities: A deterministic view of nondeterminism
Decidability of equivalence for deterministic synchronized tree automata
Rational and Recognisable Power Series
The equivalence problem of multidimensional multitape automata
Automata, Languages and Programming
Solution of the generalized minimization problem for two-tape automata with one fixed tape
On the Class of Predicates Decidable by Two-Way Multitape Finite Automata
Equivalence checking of prefix-free transducers and deterministic two-tape automata
Title not available (Why is that?)
Symmetries of knowledge bases
Title not available (Why is that?)
On decision problems for parameterized machines
Iterative pairs and multitape automata
On the representation of finite deterministic 2-tape automata
Algorithm for establishing the equivalence of deterministic multitape automata
Minimality and deadlockness of multitape automata
Program equivalence checking by two-tape automata
On synchronized multi-tape and multi-head automata
The ``equal last letter predicate for words on infinite alphabets and classes of multitape automata
The validity of weighted automata
Weighted automata
Polynomial algorithm for equivalence problem of deterministic multitape finite automata
Inclusion is undecidable for pattern languages
On the decidability of the equivalence problem for partially commutative rational power series
On D0L power series
Reflections on the phenomenon of Aleksej Andreevich Lyapunov
A class of multitape automata with a decidable equivalence problem
Equivalence of two-dimensional multitape automata
Decidability of equivalence for deterministic synchronized tree automata
On the Decidability of the Equivalence Problem for Monadic Recursive Programs
On the equivalence problem of context-free and DT0L languages

This page was built for publication: The equivalence problem of multitape finite automata

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