探索性刻画下推自动机的非确定性程度，介于确定与完全非确定之间。
Explorability in Pushdown Automata
- 用最多k条并发路径逐步构造接受路径，定义探索性机制。
- 探索性层级无限递增，但整体仍弱于一般非确定下推自动机。
- 指数级探索性恰好对应上下文无关语言，适合形式验证研究者。
我们研究了下推自动机中的探索性，这是一种对非确定性的度量，推广了历史确定性。若在读取输入时，仅需基于已见输入逐步构建最多k条并发运行，即可构造出接受路径（若存在），则称该自动机为k-探索性。我们证明，探索性下推自动机类在表达能力和紧凑性上严格介于历史确定性和完全非确定性之间。事实上，探索性等级构成无限层次：每一级k比k-1更强大，但整体仍弱于一般非确定下推自动机。随后引入参数化探索性概念，允许运行数依赖输入长度，并证明指数探索性恰好捕捉上下文无关语言。最后，我们证明探索性下推自动机可比历史确定性自动机实现二重指数级压缩，且确定性与2-探索性自动机间的紧凑性差距不可递归枚举。这些结果使探索性成为下推系统中一个稳健且操作意义明确的非确定性度量。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。