PPL 126 / 177 permanent IDsPrize Problem Ledger · PPLChecked 2026.07.27
Prize Problem LedgerOkhotin grammar problemsPPL 126Okhotin · Sublinear space for Boolean-grammar languages

Permanent problem IDPPL 126

Reconfirm sponsorIndependentconjecture

Formal languages

Okhotin · Sublinear space for Boolean-grammar languages

Are the languages generated by Boolean grammars contained in deterministic space O(n^(1−ε)) for some ε>0?

Boolean grammarsconjunctive grammarstheoretical computer science
01

The problem

Are the languages generated by Boolean grammars contained in deterministic space O(n^(1−ε)) for some ε>0?

Open since2007original problem survey
Last checked2026.07.27Catalog verification
02

Reward offers

Offer 01C$360Alexander Okhotin
Personal offer

Okhotin’s 2010 author update raises the award for the first correct solution of each remaining problem to C$360 and says the original terms remain in force. Because the primary terms page has not been refreshed since 2010, confirm claim procedure with the sponsor.

03

Sources & reading