A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct

A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct

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-...

Full description

Bibliographic Details
Main Authors: Shibashis Guha, Ismaël Jecker, Karoliina Lehtinen, Martin Zimmermann
Format: Article
Language:English
Published: Logical Methods in Computer Science e.V. 2024-01-01
Series:Logical Methods in Computer Science
Subjects:
computer science - formal languages and automata theory
computer science - logic in computer science
Online Access:https://lmcs.episciences.org/10156/pdf

Similar Items

Similar Items