arXiv
Open Access
2026
Grammar-Constrained (CFL) Reachability: Subcubic Preprocessing, Indexing Trade-offs, and Structured Decoding Semantics
Faruk Alpay
Levent Sarioglu
Abstrak
We study the problem of grammar-constrained context-free language reachability in graphs, focusing on complexity and empirical performance. We present an algorithmic framework for evaluating reachability queries constrained by context-free grammars, and analyze its theoretical runtime bounds. To complement our theoretical results, we conduct an extensive empirical evaluation on a comprehensive benchmark of real-world schemas, comparing different algorithmic variants and reporting performance trade-offs. Our results highlight the impact of grammar structure and graph characteristics on reachability computation, and provide guidance for selecting efficient approaches in practice.
Penulis (2)
F
Faruk Alpay
L
Levent Sarioglu
Akses Cepat
Informasi Jurnal
- Tahun Terbit
- 2026
- Bahasa
- en
- Sumber Database
- arXiv
- Akses
- Open Access ✓