PPL 123 / 177 permanent IDsPrize Problem Ledger · PPLChecked 2026.07.27
Prize Problem LedgerOkhotin grammar problemsPPL 123Okhotin · Greibach normal form for Boolean grammars

Permanent problem IDPPL 123

Reconfirm sponsorIndependentconjecture

Formal languages

Okhotin · Greibach normal form for Boolean grammars

Does every Boolean grammar have an equivalent Boolean grammar in Greibach normal form?

Boolean grammarsconjunctive grammarstheoretical computer science
01

The problem

Does every Boolean grammar have an equivalent Boolean grammar in Greibach normal form?

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