HEXAGONbeta

Nonstabilization of the Predictive Boolean Lookahead Hierarchy

Primarily AI-generated textHuman understanding: all partscs.FL — Formal Languages and Automata Theory

Contributed by Will Howe, Grant Huffman, Jensen Kohlmeyer ↗, Liam Kruer

Version 1 / Nov 12, 2026 / CC BY 4.0

Abstract

We study the hierarchy of languages generated by predictive Boolean LL(k)\mathrm{LL}(k) grammars. The model uses a deterministic recursive-descent table, strongly non-left-recursive rules, and at least one positive conjunct per rule. For every integer r≥1r\geq1, we construct a language over a fixed eight-letter alphabet that has an ordinary LL(r+r2r+2)\mathrm{LL}(r+r2^r+2) grammar and establish that it has no predictive Boolean LL(r)\mathrm{LL}(r) grammar. The construction asks for a specified token in a uniquely decodable word. The lower bound represents parsing on a long unary prefix by finitely many forward-moving endpoint streams and a finite Boolean recurrence. Random binary blocks followed by homogeneous blocks separate streams with a persistent timing error from streams having an exact finite-state potential. A bounded-lookahead argument hides a token-count change from each remaining stream. An encoding of the resulting independent queries is then shorter than their arbitrary binary payload. This gives nonstabilization under the stated predictive convention. The conclusion is for the stated parser model, including positive-conjunct and strong non-left-recursion requirements. Path-dependent tables satisfying these requirements give the same language families.

Provenance statement

The mathematical draft and exposition were produced primarily with OpenAI Codex under the direction of the listed contributors. Lean was used to check parser correctness, semantic foundations, and endpoint-locality lemmas.

Tools used

OpenAI
Codex
Lean
Lean

References

  1. A. Okhotin, Nine open problems on conjunctive and Boolean grammars , Bulletin of the European Association for Theoretical Computer Science 91 (2007), 96--119. https://eatcs.org/images/bulletin/beatcs91.pdf.link
  2. A. Okhotin, Recursive descent parsing for Boolean grammars , Technical Report 2004--475, School of Computing, Queen's University, March 2004. https://research.cs.queensu.ca/TechReports/Reports/2004-475.pdf.link
  3. A. Okhotin, Recursive descent parsing for Boolean grammars , Acta Informatica 44 (2007), 167--189. doi:10.1007/s00236-007-0045-0 (https://doi.org/10.1007/s00236-007-0045-0).DOI
  4. A. Okhotin, Nine open problems on conjunctive and Boolean grammars: an update , manuscript, March 30, 2010. https://citeseerx.ist.psu.edu/document?doi=d0e62d472c289c617866fde28ff6dd32758a73c7&repid=rep1&type=pdf.link
  5. A. Okhotin, Expressive power of LL(kk) Boolean grammars , Theoretical Computer Science 412 (2011), no. 39, 5132--5155. doi:10.1016/j.tcs.2011.05.013 (https://doi.org/10.1016/j.tcs.2011.05.013).DOI
  6. I. Olkhovsky and A. Okhotin, On LL(kk) linear conjunctive grammars , 2021, arXiv:2112.08014 [cs.FL]. https://arxiv.org/abs/2112.08014.arXiv

Version history

  1. v1 · 14 pagesSubmitted by Jensen KohlmeyerInitial depositCurrentNov 11, 2026