New techniques for proving the decidability of equivalence problem

DOI10.1016/0304-3975(90)90189-OzbMath0699.68092MaRDI QIDQ913523

Karel II Culik

Publication date: 1990

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

zbMATH Keywords

equivalencedecidabilityDPDAtest setspushdown automataEhrenfeucht conjecture

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Decidability of theories and sets of sentences (03B25) Grammars and rewriting systems (68Q42)

Related Items

Decomposing a $k$-valued transducer into $k$ unambiguous ones ⋮ On the lengths of values in a finite transducer

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The decidability of equivalence for deterministic finite transducers
• The equivalence problem for deterministic two-tape automata
• Systems of equations over a free monoid and Ehrenfeucht's conjecture
• The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids
• The inclusion problem for some classes of deterministic multitape automata
• Test sets for finite substitutions
• The Ehrenfeucht conjecture: An algebra-framework for its proof
• A proof of Ehrenfeucht's conjecture
• Finiteness properties of matrix representations
• The equivalence of finite valued transducers (on HDT0L languages) is decidable
• Test sets and checking words for homomorphism equivalence
• On the decidability of equivalence for deterministic pushdown transducers
• Deterministic one-counter automata
• The inclusion problem for simple languages
• Complete problems for deterministic polynomial time
• Equivalence problems for deterministic context-free languages and monadic recursion schemes
• Single-valued a-transducers
• On the decidability of homomorphism equivalence for languages
• Some decidability results about regular and pushdown translations
• On equivalence of grammars through transformation trees
• Synchronizable deterministic pushdown automata and the decidability of their equivalence
• A direct branching algorithm for checking equivalence of strict deterministic vs. LL(k) grammars
• Multitape one-way nonwriting automata
• Loops in automata and HDTOL relations
• Test sets for context free languages and algebraic systems of equations over a free monoid
• The Equivalence Problem for Single-Valued Two-Way Transducers (on NPDTOL Languages) is Decidable
• The equivalence problem for real-time DPDAs
• The equivalence problem for real-time strict deterministic languages
• The Equivalence Problem for Deterministic Two-Way Sequential Transducers is Decidable
• The decidability of the equivalence problem for DOL-systems
• The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and Applications
• The decidability of equivalence for deterministic stateless pushdown automata
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
• The equivalence problem for deterministic finite-turn pushdown automata
• Some Recursively Unsolvable Problems in ALGOL-Like Languages
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
• Properties of deterministic top-down grammars
• On the translation of languages from left to right