2026-07-26T15:56:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25092 2026-02-09T08:06:06Z ddc:004 open_access

Explorability in Pushdown Automata Bedi, Ayaan Lehtinen, Karoliina Pushdown automata nondeterminism explorability history-determinism We study explorability, a measure of nondeterminism in pushdown automata, which generalises history-determinism. An automaton is k-explorable if, while reading the input, it suffices to follow k concurrent runs, built step-by-step based only on the input seen so far, to construct an accepting one, if it exists. We show that the class of explorable PDAs lies strictly between history-deterministic and fully nondeterministic PDAs in terms of both expressiveness and succinctness. In fact increasing explorability induces an infinite hierarchy: each level k defines a strictly more expressive class than level k-1, yet the entire class remains less expressive than general nondeterministic PDAs. We then introduce a parameterized notion of explorability, where the number of runs may depend on input length, and show that exponential explorability precisely captures the context-free languages. Finally, we prove that explorable PDAs can be doubly exponentially more succinct than history-deterministic ones, and that the succinctness gap between deterministic and 2-explorable PDAs is not recursively enumerable. These results position explorability as a robust and operationally meaningful measure of nondeterminism for pushdown systems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ayaan Bedi and Karoliina Lehtinen 2025 Is Part Of LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2025.12 urn:nbn:de:0030-drops-250921 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.12 eng https://creativecommons.org/licenses/by/4.0/legalcode