Id: hexagon/2611.00269 Pdf: https://hexagonmath.org/pdf/2611.00269v1 Url: https://hexagonmath.org/abs/2611.00269v1 Tags: msc:68Q45, Boolean grammars, parsing, space complexity, tree evaluation Score: 0 Title: Sublinear-space recognition for Boolean grammars Domain: cs.FL Origin: ai-generated Source: hexagon Authors: Will Howe, Grant Huffman, Jensen Kohlmeyer, Liam Kruer Reviews: 0 Subject: cs.FL Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Ai-models: Codex Discussed: 0 Published: 2026-11-11 Withdrawn: false Authorship: no-human-author-claimed Formalized: false Human-understanding: all Page: https://delphi.science/r/hexagon/2611.00269 For every fixed Boolean grammar in the standard language family considered by Okhotin, we give a deterministic membership algorithm using $O_G(n^{2/3}(\log(n+2))^{2/3})$ working space on an input of length $n$. In particular, the whole family is contained in $\operatorname{DSPACE}(n^{3/4})$, answering Okhotin's Problem 4 affirmatively. The construction partitions substring endpoints into blocks of size $b$. It represents the parsing recurrence by a constant-fan-in circuit with $O_G(b^2)$-bit values and dependency height $O(n/b+1)$. Splits in the endpoint blocks are resolved locally, and an…