Nine open problems on conjunctive and Boolean grammars: an update
Alexander Okhotin · 2010
Conjunctive grammars are context-free grammars with an explicit conjunction operation in the formalism of rules; Boolean grammars are further equipped with an explicit negation. Three years have passed since the publication of the last survey of these grammars and their open research questions (A. Okhotin,“Nine open problems on conjunctive and Boolean grammars”, Bulletin of the EATCS, 91 (2007), 96‐119). While an updated survey is under preparation, this note is aimed to report on the two solved problems, as well as to correct a couple of small errors. In addition, the award for solving each of the problems is raised to $360 Canadian.