The equivalence problem of multitape finite automata

DOI10.1016/0304-3975(91)90356-7zbMath0727.68063OpenAlexW2111270089WikidataQ60162917 ScholiaQ60162917MaRDI QIDQ804302

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

zbMATH Keywords

multiplicity multitape automata multiplicity equivalent

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

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

Cites Work