A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct

DOI10.46298/LMCS-20(1:3)2024arXiv2105.02611MaRDI QIDQ6137877FDOQ6137877

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)

Abstract: We study the expressiveness and succinctness of history-deterministic pushdown automata (HD-PDA) over finite words, that is, pushdown automata whose nondeterminism can be resolved based on the run constructed so far, but independently of the remainder of the input word. These are also known as good-for-games pushdown automata. We prove that HD-PDA recognise more languages than deterministic PDA (DPDA) but not all context-free languages (CFL). This class is orthogonal to unambiguous CFL. We further show that HD-PDA can be exponentially more succinct than DPDA, while PDA can be double-exponentially more succinct than HD-PDA. We also study HDness in visibly pushdown automata (VPA), which enjoy better closure properties than PDA, and for which we show that deciding HDness is ExpTime-complete. HD-VPA can be exponentially more succinct than deterministic VPA, while VPA can be exponentially more succinct than HD-VPA. Both of these lower bounds are tight. We then compare HD-PDA with PDA for which composition with games is well-behaved, i.e. good-for-games automata. We show that these two notions coincide, but only if we consider potentially infinitely branching games. Finally, we study the complexity of resolving nondeterminism in HD-PDA. Every HDPDA has a positional resolver, a function that resolves nondeterminism and that is only dependant on the current configuration. Pushdown transducers are sufficient to implement the resolvers of HD-VPA, but not those of HD-PDA. HD-PDA with finite-state resolvers are determinisable.

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)

Cites Work

• Pushdown automata with bounded nondeterminism and bounded ambiguity
• Title not available (Why is that?)
• Borel determinacy
• Visibly pushdown languages
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
• The Theory of Stabilisation Monoids and Regular Cost Functions
• On the Succinctness of Different Representations of Languages
• A note on the succinctness of descriptions of deterministic languages
• The tractability frontier for NFA minimization
• Minimal NFA Problems are Hard
• A Direct Proof of the Inherent Ambiguity of a Simple Context-Free Language
• Pushdown processes: Games and model-checking
• The determinacy of context-free games
• The Smallest Grammar Problem
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• \(L(A)=L(B)\)? decidability results from complete formal systems
• Solving Games Without Determinization
• Descriptional Complexity of (Un)ambiguous Finite State Machines and Pushdown Automata
• Descriptional complexity of unambiguous input-driven pushdown automata
• Regular canonical systems
• Topological properties of omega context-free languages
• Measuring nondeterminism in pushdown automata
• Title not available (Why is that?)
• Height-Deterministic Pushdown Automata
• Good-enough synthesis
• Title not available (Why is that?)
• Active context-free games
• Title not available (Why is that?)
• Relating word and tree automata
• Title not available (Why is that?)
• On Determinisation of Good-for-Games Automata
• Title not available (Why is that?)
• How Deterministic are Good-For-Games Automata?
• Title not available (Why is that?)
• Büchi Good-for-Games Automata Are Efficiently Recognizable
• Minimizing GFG Transition-Based Automata
• A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct
• Title not available (Why is that?)

Cited In (6)

• Token Games and History-Deterministic Quantitative-Automata
• History-deterministic timed automata
• Checking history-determinism is NP-hard for parity automata
• On history-deterministic one-counter nets
• A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct
• History-deterministic timed automata are not determinizable

This page was built for publication: A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct

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