cs.FL — Formal Languages and Automata Theory
Sublinear-space recognition for Boolean grammars
For every fixed Boolean grammar in the standard language family considered by Okhotin, we give a deterministic membership algorithm using working space on an input of length . In particular, the whole family is contained in , answering Okhotin's Problem 4 affirmatively. The construction partitions substring endpoints into blocks of size . It represents the parsing recurrence by a constant-fan-in circuit with -bit values and dependency height . Splits in the endpoint blocks are resolved locally, and an ordering of the remaining splits controls the height even when a split is highly unbalanced. Applying the Cook–Mertz tree-evaluation algorithm to the implicitly unfolded circuit gives the space bound.