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

DOI10.1016/0020-0190(81)90105-8MaRDI QIDQ1152220zbMATH OpenOpenAlexFDO

Authors 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)

Cites work

• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• A representation of trees by languages. I
• A result on the equivalence problem for deterministic pushdown automata
• The decidability of equivalence for deterministic stateless pushdown automata
• The equivalence problem for deterministic finite-turn pushdown automata
• The equivalence problem for real-time strict deterministic languages
• Transductions des langages de Chomsky

Cited in

(2)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1152220)