Grammar-Constrained (CFL) Reachability: Subcubic Preprocessing, Indexing Trade-offs, and Structured Decoding Semantics
Faruk Alpay, Levent Sarioglu · 2026
Read Grammar-Constrained (CFL) Reachability: Subcubic Preprocessing, Indexing Trade-offs, and Structured Decoding Semantics by Faruk Alpay, Levent Sarioglu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-23401.txt.
Description
Faruk Alpay and one co-author study grammar-constrained reachability in graphs, where paths must obey a context-free grammar. The paper presents an algorithmic framework for answering such reachability queries and analyzes its theoretical runtime bounds. Reachability under grammar constraints matters wherever graph queries must respect structural rules, from program analysis to data schemas.
To complement the theory, the authors run an extensive empirical evaluation on a benchmark of real-world schemas, comparing algorithmic variants and reporting performance trade-offs. Results highlight how grammar structure and graph characteristics shape reachability computation. The paper closes with guidance for picking efficient approaches in practice, matching method to grammar and graph at hand.
Catalog record
| CREATOR | Faruk Alpay, Levent Sarioglu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 40 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-23401