Beating Rytter's Bound: All-Pairs CFL Reachability in O(n 3(n) 2/(n) 2) Time
cs.PL, cs.FL
Submitted: 2026-11-09
Updated: 2026-11-09
Terminology
Sources
- Efficient Exact Paths For Dyck and semi-Dyck Labeled Path Reachability
- The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds
- Subcubic Certificates for CFL Reachability
- Simulation of Two-Way Pushdown Automata Revisited
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
- Faster Online Matrix-Vector Multiplication
- On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication
Related papers
- The Best of Times, the Worst of Times: Moment-Based Analysis of Probabilistic Cost Structures
- Formal Verification of an Out-of-Order Multiprocessor against an In-Order Weak-Memory ISA
- Fuss-free cumulative universes: theory and practice
- High-Level Synthesis of Efficient Pipelines with Visibility Control
- Model Checking Probabilistic Multiparty Session Types
- A Type System for Communication-Safe Hardware Design