The only logical operation expressible in context-free grammars is disjunction, which is represented by multiple rules for a single nonterminal. Conjunctive grammars are an extension of context-free grammars with explicit conjunction in the rules. Boolean grammars further extend them to support negation, and thus allow all propositional connectives. In other words, context-free grammars can be regarded as a particular case of Boolean grammars, in which only disjunction is allowed. This particular case has been studied quite well in the second half of 20th century, and now it is time to study the general case!
It has been shown that conjunctive and Boolean grammars give useful additional expressive power to conjunctive grammars. At the same time, they inherit efficient parsing algorithms, which makes them potentially useful in practice. However, many theoretical properties of these grammars remember unsolved. Believing that knowing these properties would be an important addition of our knowledge on formal languages, I, Alexander Okhotin, decided to promote their study by offering small awards for solving each of the following nine problems:
The award is $360 Canadian per problem, which is equally distributed between the authors of the solution. If two papers solving the same question appear simultaneously, the award is split between them. Each author receives a handwritten certificate and an award cheque. Every lady among the authors additionally receives a flower.
In most cases a solution must be published in a recognized journal or presented at a recognized conference to qualify for the award. The following survey of Boolean grammars contains full statements of the problems, and should be taken as the primary source of information.
History:
22 May 2006. First announcement of the problems (at a seminar in Tarragona).
21 November 2006. Written this page.
Award increased to $240 Canadian.
20 March 2007. Problem 2 solved by Artur Jeż.
2 April 2009. Problem 3 solved by Alexander Okhotin.
28 March 2010. Posted an update to the list of open problems.
Award increased to $360 Canadian.