The decidability of equivalence for deterministic stateless pushdown automata

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)

zbMATH Keywords

DecidabilityEquivalence ProblemContext-Free LanguageDeterministic Pushdown Automata

Mathematics Subject Classification ID

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