Synchronizable deterministic pushdown automata and the decidability of their equivalence
From MaRDI portal
Publication:1822521
DOI10.1007/BF00288472zbMath0617.68075MaRDI QIDQ1822521
Juhani Karhumäki, Karel II Culik
Publication date: 1986
Published in: Acta Informatica (Search for Journal in Brave)
68Q45: Formal languages and automata
Related Items
New techniques for proving the decidability of equivalence problem, A direct branching algorithm for checking the equivalence of two deterministic pushdown transducers, one of which is real-time strict, \(L(A)=L(B)\)? decidability results from complete formal systems, The extended equivalence problem for a class of non-real-time deterministic pushdown automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Systems of equations over a free monoid and Ehrenfeucht's conjecture
- Superdeterministic DPDAs: The method of accepting does affect decision problems
- On the decidability of equivalence for deterministic pushdown transducers
- Deterministic one-counter automata
- A result on the equivalence problem for deterministic pushdown automata
- A direct algorithm for checking equivalence of LL(k) grammars
- An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
- On the decidability of homomorphism equivalence for languages
- Two decidability results for deterministic pushdown automata
- On equivalence of grammars through transformation trees
- A direct branching algorithm for checking equivalence of strict deterministic vs. LL(k) grammars
- A direct branching algorithm for checking equivalence of some classes of deterministic pushdown automata
- Test sets for context free languages and algebraic systems of equations over a free monoid
- The equivalence problem for real-time strict deterministic languages
- Some remarks on the KH algorithm fors-grammars
- The decidability of equivalence for deterministic stateless pushdown automata
- The equivalence problem for deterministic finite-turn pushdown automata
- Properties of deterministic top-down grammars
- Real-Time Strict Deterministic Languages
