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)

Awards are offered for solving some open problems. A recent survey of the research on Boolean grammars is available:

Some research papers on Boolean grammars are listed below (this bibliography is somewhat outdated; an up-to-date bibliography is included in the cited survey).

Theoretical foundations:
  1. A. Okhotin, “Boolean grammars” (pdf), Information and Computation, 194 (2004) 19-48.
  2. V. Kountouriotis, Ch. Nomikos, P. Rondogiannis, “Well-founded semantics for Boolean grammars”, Information and Computation, 207:9 (2009), 945--967.
Parsing for Boolean grammars:
  1. A. Okhotin, “LR parsing for Boolean grammars” (pdf), International Journal of Foundations of Computer Science 17:3 (2006), 629--664.
  2. A. Megacz, “sbp: a scannerless Boolean parser”, LDTA 2006, Electronic Notes in Theoretical Computer Science, 164:2 (2006), 97--102.
  3. A. Okhotin, “Recursive descent parsing for Boolean grammars” (pdf), Acta Informatica, 44:3--4 (2007), 167--189.
  4. A. Okhotin, “Fast parsing for Boolean grammars: a generalization of Valiant's algorithm” (pdf), submitted.
Subclasses of Boolean grammars:
  1. A. Okhotin, “Conjunctive grammars” (pdf), Journal of Automata, Languages and Combinatorics, 6 (2001), 519-535.
  2. M. Wrona, “Stratified Boolean grammars”, MFCS 2005.
  3. Ch. Nomikos, P. Rondogiannis, “Locally stratified Boolean grammars”, LATA 2007.
  4. A. Okhotin, “Unambiguous Boolean grammars” (pdf), Information and Computation, 206:9--10 (2008), 1234--1247.
Theoretical characterizations and normal forms:
  1. A. Okhotin, “The dual of concatenation” (pdf), Theoretical Computer Science, 345 (2005), 425-447.
  2. A. Okhotin, C. Reitwie{\ss}ner, “Conjunctive grammars with restricted disjunction” , Theoretical Computer Science, to appear.
Extensions of conjunctive and Boolean grammars:
  1. D. Zook, “Multi-conjunctive grammars”, TALE 2007
  2. V. Kountouriotis, Ch. Nomikos, P. Rondogiannis, “Conjunctive macro grammars”, TALE 2007
Applications:
  1. A. Okhotin, “On the existence of a Boolean grammar for a simple programming language”, AFL 2005.

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”.