New techniques for proving the decidability of equivalence problem

DOI10.1016/0304-3975(90)90189-OMaRDI QIDQ913523zbMATH OpenFDO

Authors Karel II Culik

Publication date 1990

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

zbMATH Keywords

equivalencedecidabilitypushdown automatatest setsEhrenfeucht conjectureDPDA

Mathematics Subject Classification ID

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

Cites work

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

Cited in

(3)

• scientific article; zbMATH DE number 4083010 (Why is no real title available?)
• On the lengths of values in a finite transducer
• Decomposing a $k$-valued transducer into $k$ unambiguous ones

Describes a project that uses

Uses Software

• ALGOL 60

This page was built for publication: New techniques for proving the decidability of equivalence problem

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