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

equivalence; decidability; DPDA; test sets; pushdown automata; Ehrenfeucht conjecture

Mathematics Subject Classification ID

68Q45: Formal languages and automata

03B25: Decidability of theories and sets of sentences

68Q42: Grammars and rewriting systems

Related Items

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

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