The Decidability and Complexity of Interleaved Bidirected Dyck Reachability
summary
Proves D1⟂D1 reachability runs in O(n^3 α(n)) time, improving on the prior O(n^7) bound; shows Dk⟂D1 reachability is decidable and its linearly bounded variant runs in O(n^2 α(n)) with a matching quadratic lower bound; proves full Dk⟂Dk reachability is undecidable. Provides a constructive reduction and layered-graph algorithm, and an implementation that speeds standard benchmarks from days to minutes (example: five minutes vs two days).
AI-written summary · about