Boolean grammars

Boolean grammars were introduced by Okhotin in 2003 as an extension of context-free grammars, in which the rules may contain conjunction and negation. Besides these explicit operations, Boolean grammars allow implicit disjunction represented by multiple rules for a single nonterminal, which is the only logical operation expressible in context-free grammars. Conjunction and negation can be used, in particular, to specify intersection and complement of languages. An intermediate class of grammars known as conjunctive grammars allows conjunction and disjunction, but not negation.

The research carried out so far shows that the practical properties of the model are as good as in the case of the earlier studied conjunctive grammars, while the descriptional capabilities are further improved. In particular, some practically useful properties inherited from context-free grammars, such as efficient parsing algorithms, are still retained.

A Boolean grammar is defined as a quadruple (Σ, N, R, S), in which:

Informally, a rule of the above form asserts that every string w over Σ that satisfies each of the syntactical conditions represented by α1, ..., αm and none of the syntactical conditions represented by β1, ..., βn therefore satisfies the condition defined by A. Several formal definitions of a Boolean grammar have been proposed. They have one thing in common: the grammar can be represented as a system of language equations with union, intersection, complementation and concatenation, and the languages generated by the grammar must be its solution. The semantics differ in details, some define the languages using language equations, some draw upon ideas from the field of logic programming. However, these nontrivial issues of formal definition are mostly irrelevant for practical considerations, and one can construct grammars according to the given informal semantics.

(figure: Hierarchy of formal grammars) Boolean grammars were introduced in the following paper. A recent survey of the research on Boolean grammars is available. Awards are offered for solving some open problems.

Last updates:
9 October 2011. Written a new survey.
28 March 2010. Posted an update to the list of open problems.
15 March 2010. Updated the bibliography.
20 November 2006. Rewritten the introductory comments.
5 May 2006. Updated the bibliography.
16 October, 2004. Written “LR parsing for Boolean grammars”.