PPL 120 / 177 permanent IDsPrize Problem Ledger · PPLChecked 2026.07.27
Prize Problem LedgerOkhotin grammar problemsPPL 120Okhotin · Bounded nonterminal complexity of Boolean grammars

Permanent problem IDPPL 120

Reconfirm sponsorIndependentconjecture

Formal languages

Okhotin · Bounded nonterminal complexity of Boolean grammars

Is there a universal constant k such that every Boolean-grammar language has a Boolean grammar using at most k nonterminal symbols?

Boolean grammarsconjunctive grammarstheoretical computer science
01

The problem

Is there a universal constant k such that every Boolean-grammar language has a Boolean grammar using at most k nonterminal symbols?

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