PPL 122 / 177 permanent IDsPrize Problem Ledger · PPLChecked 2026.07.27
Prize Problem LedgerOkhotin grammar problemsPPL 122Okhotin · Complement closure of conjunctive languages

Permanent problem IDPPL 122

Reconfirm sponsorIndependentconjecture

Formal languages

Okhotin · Complement closure of conjunctive languages

Is the family of languages generated by conjunctive grammars closed under complementation?

Boolean grammarsconjunctive grammarstheoretical computer science
01

The problem

Is the family of languages generated by conjunctive grammars closed under complementation?

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