PPL 125 / 177 permanent IDsPrize Problem Ledger · PPLChecked 2026.07.27
Prize Problem LedgerOkhotin grammar problemsPPL 125Okhotin · Limitations of Boolean grammars

Permanent problem IDPPL 125

Reconfirm sponsorIndependentconjecture

Formal languages

Okhotin · Limitations of Boolean grammars

Are there languages recognized in O(n²) time by deterministic linear-bounded automata that cannot be specified by Boolean grammars?

Boolean grammarsconjunctive grammarstheoretical computer science
01

The problem

Are there languages recognized in O(n²) time by deterministic linear-bounded automata that cannot be specified by Boolean grammars?

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