The simultaneous accessibility of two configurations of two equivalent DPDA's

DOI10.1016/0020-0190(81)90105-8zbMath0459.68019OpenAlexW1996465692MaRDI QIDQ1152220

Bruno Courcelle

Publication date: 1981

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(81)90105-8

zbMATH Keywords

deterministic pushdown automataequivalence problemrational transductionalternate stacking methodsimultaneous accessibility

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (max. 100)

Some results on subclass containment problems for special classes of dpda's related to nonsingular machines ⋮ An extended direct branching algorithm for checking equivalence of deterministic pushdown automata

Cites Work

• Unnamed Item
• Transductions des langages de Chomsky
• A result on the equivalence problem for deterministic pushdown automata
• A representation of trees by languages. I
• The equivalence problem for real-time strict deterministic languages
• The decidability of equivalence for deterministic stateless pushdown automata
• The equivalence problem for deterministic finite-turn pushdown automata

This page was built for publication: The simultaneous accessibility of two configurations of two equivalent DPDA's