A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct

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

zbMATH Keywords

synthesispushdown automatagood-for-gamessuccintness

Mathematics Subject Classification ID

Logic in computer science (03B70) Theory of computing (68Qxx) Computer science (68-XX)

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