arXiv:2611.12315 · v1

Beating Rytter's Bound: All-Pairs CFL Reachability in $O(n^3(\log\log n)^2/(\log n)^2)$ Time

首次提交 2026-11-09 20:40

版本更新 2026-11-09 20:40

雷达观测 2026-11-10 15:22

摘要

Context-free reachability and 2NPDA recognition are fundamental problems in program analysis and language theory. Despite years of effort, the best algorithms for these problems run in time $O(n^3/\log n)$ on a word RAM model; they are based on an observation of Rytter in 1985 for 2NPDA which was adapted for CFL reachability by Chaudhuri in 2008. No better algorithm has been designed since. We give the first improvement to Rytter's algorithm. For both all-pairs context-free reachability and 2NPDA recognition, we show a deterministic algorithm running in $O(n^3(\log\log n)^2/(\log n)^2)$ time and $O(n^{2+ε})$ words of space for every fixed $0<ε<1$ on a word RAM. Our improvement is based on a new data structure that reports set differences using batched maintenance of exact intersection counts, allowing saturation to skip regions that contain no new reachability information.

作者备注：25 pages