A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct
From MaRDI portal
Publication:6137877
DOI10.46298/lmcs-20(1:3)2024arXiv2105.02611MaRDI QIDQ6137877
Shibashis Guha, Karoliina Lehtinen, Ismaël Jecker, Martin Zimmermann
Publication date: 16 January 2024
Published in: Logical Methods in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2105.02611
Related Items (4)
On history-deterministic one-counter nets ⋮ A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct ⋮ History-deterministic timed automata are not determinizable ⋮ Token Games and History-Deterministic Quantitative-Automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The tractability frontier for NFA minimization
- Descriptional complexity of unambiguous input-driven pushdown automata
- Borel determinacy
- Pushdown automata with bounded nondeterminism and bounded ambiguity
- \(L(A)=L(B)\)? decidability results from complete formal systems
- Pushdown processes: Games and model-checking
- Good-enough synthesis
- Active context-free games
- Measuring nondeterminism in pushdown automata
- Relating word and tree automata
- The Determinacy of Context-Free Games
- On Determinisation of Good-for-Games Automata
- Height-Deterministic Pushdown Automata
- The Smallest Grammar Problem
- Visibly pushdown languages
- Descriptional Complexity of (Un)ambiguous Finite State Machines and Pushdown Automata
- Solving Games Without Determinization
- The Theory of Stabilisation Monoids and Regular Cost Functions
- On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
- On the Succinctness of Different Representations of Languages
- A note on the succinctness of descriptions of deterministic languages
- Minimal NFA Problems are Hard
- Büchi Good-for-Games Automata Are Efficiently Recognizable
- Minimizing GFG Transition-Based Automata
- How Deterministic are Good-For-Games Automata?
- Regular canonical systems
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- A Direct Proof of the Inherent Ambiguity of a Simple Context-Free Language
- Topological properties of omega context-free languages
- A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct
This page was built for publication: A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct
