Where academic tradition
meets the exciting future

Nine Open Problems on Conjunctive and Boolean Grammars

Alexander Okhotin, Nine Open Problems on Conjunctive and Boolean Grammars. TUCS Technical Reports 794, Turku Centre for Computer Science, 2006.


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. The paper briefly reviews these grammars and proposes 9 most interesting and important research problems for them. An award of $240 Canadian is offered for the first correct solution of each of these problems.


Full publication in PDF-format

BibTeX entry:

  title = {Nine Open Problems on Conjunctive and Boolean Grammars},
  author = {Okhotin, Alexander},
  number = {794},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2006},
  keywords = {Conjunctive grammars, Boolean grammars, language equations, parsing, complexity, automata},
  ISBN = {952-12-1805-3},

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication