We study explorability, a measure of nondeterminism in pushdown automata that generalizes history-determinism. An automaton is said to be k-explorable if, while reading the input, it suffices to track only k concurrent runs constructed step by step based solely on the input seen so far to ensure that an accepting run can be found whenever one exists. We show that the class of explorable PDAs lies strictly between history-deterministic and fully nondeterministic PDAs, both in terms of expressiveness and succinctness.  We establish an infinite hierarchy within the class of explorable PDAs: k-explorable PDAs are strictly less expressive than (k + 1)-explorable ones, while the entire hierarchy remains less expressive than unrestricted nondeterministic PDAs. We further introduce a parameterized notion of explorability, where the number of tracked runs may depend on the input length, and demonstrate that exponential explorability captures precisely the class of context-free languages. Finally, we prove that explorable PDAs can be doubly exponentially more succinct than history-deterministic ones. Moreover, we establish that a similar doubly exponential gap persists even when explorability is restricted to a fixed constant k, and that the succinctness gap between deterministic and 2-explorable PDAs is not recursively enumerable. Altogether, these results establish explorability as a robust and operationally meaningful measure of nondeterminism for pushdown systems.

Ayaan Bedi, an alumnus of Krea, is a second-year M.Sc. Computer Science student at the Chennai Mathematical Institute. He focuses on automata and games for synthesis, particularly their connections to logic and language theory. His recent work includes projects on the explorability of pushdown automata (FSTTCS 2025) and the logical characterization of Multiple Context-Free Grammars.

This talk is mandatory for fourth year Computer Science students