Conjunctive and Boolean grammars: The true general case of the context-free grammars

Conjunctive grammars extend the definition of a context-free grammar by allowing a conjunction operation in the rules; Boolean grammars are further equipped with an explicit negation. These grammars maintain the main principle of the context-free grammars, that of defining syntactically correct strings inductively from their substrings, but lift the restriction of using disjunction only. This paper surveys the results on conjunctive and Boolean grammars obtained over the last decade, comparing them to the corresponding results for ordinary context-free grammars and their main subfamilies. Much attention is given to parsing algorithms, most of which are inherited from the case of ordinary context-free grammars without increasing their computational complexity. The intended readership includes any computer scientists looking for a compact and accessible description of this formal model and its properties, as well as for a general outlook on formal grammars. The paper is also addressed to theoretical computer scientists seeking a subject for research; an account of pure theoretical research in the area presented in this paper is accompanied by a list of significant open problems, with an award offered for the first correct solution of each problem. Several directions for future investigation are proposed.