On Büchi one-counter automata

DOI10.4230/LIPICS.STACS.2017.14MaRDI QIDQ4636612zbMATH OpenFDO

Authors Stanislav Böhm, Stefan Göller, Piotr Hofman, Simon Halfon

Publication date 19 April 2018

zbMATH Keywords

deterministic pushdown automatainfinite words

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Recommendations

• Equivalence of deterministic one-counter automata is NL-complete
• Language equivalence of deterministic real-time one-counter automata is NL-complete
• Decidability of the equivalence problem for deterministic pushdown automata
• Bisimulation equivalence and regularity for real-time one-counter automata
• Highly Undecidable Problems For Infinite Computations

Cited in

(8)

• scientific article; zbMATH DE number 7447732 (Why is no real title available?)
• scientific article; zbMATH DE number 7559503 (Why is no real title available?)
• Equivalence of deterministic one-counter automata is NL-complete
• scientific article; zbMATH DE number 7471692 (Why is no real title available?)
• Büchi VASS recognise \(\mathbf{\Sigma}^{1}_{1}\)-complete \({\omega}\)-languages
• One-counter automata for parsing and language approximation
• Language equivalence of deterministic real-time one-counter automata is NL-complete
• On the expressive power of non-deterministic and unambiguous Petri nets over infinite words

This page was built for publication: On Büchi one-counter automata

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