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

CREATORFaruk Alpay, Levent Sarioglu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-23401

Browse the full library · About the Tower of Babel