PPL 124 / 177 permanent IDsPrize Problem Ledger · PPLChecked 2026.07.27
Prize Problem LedgerOkhotin grammar problemsPPL 124Okhotin · Inherent ambiguity for Boolean grammars

Permanent problem IDPPL 124

Reconfirm sponsorIndependentconjecture

Formal languages

Okhotin · Inherent ambiguity for Boolean grammars

Does any language exist that is inherently ambiguous with respect to Boolean grammars?

Boolean grammarsconjunctive grammarstheoretical computer science
01

The problem

Does any language exist that is inherently ambiguous with respect to 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