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)

Full work available at URL https://doi.org/10.1016/0304-3975(90)90189-O

zbMATH Keywords

decidabilityDPDAEhrenfeucht conjectureequivalencepushdown automatatest sets

Mathematics Subject Classification ID

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

Cites work

• 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
• 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?)
• 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 decidability results about regular and pushdown translations
• Some Recursively Unsolvable Problems in ALGOL-Like Languages
• Synchronizable deterministic pushdown automata and the decidability of their equivalence
• Systems of equations over a free monoid and Ehrenfeucht's conjecture
• 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 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 Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids
• The Ehrenfeucht conjecture: An algebra-framework for its proof
• 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 Deterministic Two-Way Sequential Transducers is Decidable
• The equivalence problem for real-time DPDAs
• The equivalence problem for real-time strict deterministic languages
• The Equivalence Problem for Single-Valued Two-Way Transducers (on NPDTOL Languages) is Decidable
• The inclusion problem for simple languages
• The inclusion problem for some classes of deterministic multitape automata
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
• The Unsolvability of the Equivalence Problem for \varepsilon -Free NGSM’s with Unary Input (Output) Alphabet and Applications
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines

Cited in

(3)

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

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)