On Büchi one-counter automata
From MaRDI portal
Publication:4636612
DOI10.4230/LIPICS.STACS.2017.14zbMATH Open1402.68114MaRDI QIDQ4636612FDOQ4636612
Authors: Stanislav Böhm, Stefan Göller, Piotr Hofman, Simon Halfon
Publication date: 19 April 2018
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
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)
Cited In (8)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Equivalence of deterministic one-counter automata is NL-complete
- Title not available (Why is that?)
- Büchi VASS recognise \(\mathbf{\Sigma}^{1}_{1}\)-complete \({\omega}\)-languages
- Language equivalence of deterministic real-time one-counter automata is NL-complete
- One-counter automata for parsing and language approximation
- 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)