Sublinear-space recognition for Boolean grammars
Source: hexagonmath.org/abs/2611.00269v1
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2611.00269
curl -X POST /api/v1/records/hexagon/2611.00269/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2611.00269/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'