The decidability of equivalence for deterministic stateless pushdown automata
From MaRDI portal
Publication:4174788
DOI10.1016/S0019-9958(78)90139-0zbMath0393.68078MaRDI QIDQ4174788
Michio Oyamaguchi, Namio Honda
Publication date: 1978
Published in: Information and Control (Search for Journal in Brave)
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)
Related Items (17)
A fast algorithm to decide on the equivalence of stateless DPDA ⋮ On some decision questions concerning pushdown machines ⋮ Superdeterministic DPDAs: The method of accepting does affect decision problems ⋮ A representation of trees by languages. II ⋮ Decidable subcases of the equivalence problem for recursive program schemes ⋮ The simultaneous accessibility of two configurations of two equivalent DPDA's ⋮ The equivalence problem for two dpda's, one of which is a finite-turn or one-counter machine ⋮ On the decidability of equivalence for deterministic pushdown transducers ⋮ DPDA's in 'Atomic normal form' and applications to equivalence problems ⋮ New techniques for proving the decidability of equivalence problem ⋮ On jump-deterministic pushdown automata ⋮ A representation of trees by languages. I ⋮ Synchronizable deterministic pushdown automata and the decidability of their equivalence ⋮ A direct branching algorithm for checking equivalence of strict deterministic vs. LL(k) grammars ⋮ Fundamental properties of infinite trees ⋮ New families of non real time dpda's and their decidability results ⋮ An extended direct branching algorithm for checking equivalence of deterministic pushdown automata
This page was built for publication: The decidability of equivalence for deterministic stateless pushdown automata
