# Explorability in Pushdown Automata

arXiv: https://arxiv.org/abs/2511.04048 · HTML: https://mlsanity.com/paper/2511.04048/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 15 references that are in the map.
- First posted on arXiv 6 Nov 2025.

## Builds on (most cited first, 1 of 1)

- [A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct](https://mlsanity.com/paper/2105.02611/) (2021)

## Abstract (arXiv)

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.