Nine open problems for conjunctive and Boolean grammars

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:

  1. Are there any languages recognized by deterministic linear bounded automata working in time O(n2) that cannot be specified by Boolean grammars?
  2. Do conjunctive grammars over a one-letter alphabet generate only regular languages? (solved negatively by Artur Jeż in 2007; award presented on 3 July 2007 at the DLT 2007 conference in Turku, Finland)
  3. Are the languages generated by Boolean grammars contained in DTIME(n3-ε) for any ε>0? (solved positively by myself in 2009)
  4. Are the languages generated by Boolean grammars contained in DSPACE(n1-ε) for any ε>0?
  5. Is it true that for every Boolean grammar there exists a Boolean grammar in Greibach normal form that generates the same language?
  6. Is the family of conjunctive languages closed under complementation?
  7. Do there exist any inherently ambiguous languages with respect to Boolean grammars?
  8. Does there exist a number k0>0, such that, for all kk0, Boolean LL(k) grammars generate the same family of languages as Boolean LL(k0) grammars?
  9. Does there exist a number k≥0, such that every language generated by any Boolean grammar can be generated by a k-nonterminal Boolean grammar?

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.

Earlier publications and presentations of these problems are listed for historical reasons:

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.