Conjunctive grammars

Conjunctive grammars, introduced by Okhotin in 2000, are an extension of context-free grammars, in which the rules may contain a conjunction operation. Besides explicit conjunction, conjunctive grammars allow implicit disjunction represented by multiple rules for a single nonterminal, which is the only logical operation expressible in context-free grammars. Conjunction can be used, in particular, to specify intersection of languages. A further extension of conjunctive grammars known as Boolean grammars additionally allows explicit negation.

Though the expressive means of conjunctive grammars are greater than those of context-free grammars, they retain some practically useful properties of the latter, such as efficient parsing algorithms.

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

Σ is the alphabet;
N is the set of nonterminal symbols;
P is the set of rules, each of the form
A -> α₁ & ... & α_m,
where A is a nonterminal and α₁, ..., α_m are strings formed of symbols in Σ and N;
S ∈ N is the start symbol.

Informally, a rule of the above form asserts that every string w over Σ that satisfies each of the syntactical conditions represented by α₁, ..., α_m therefore satisfies the condition defined by A. Two equivalent formal definitions of the language specified by a conjunctive grammar exist. One definition is based upon representing the grammar as a system of language equations with union, intersection and concatenation and considering its least solution. The other definition generalizes Chomskian derivation to term rewriting of the following form:

Terms are formed of symbols in Σ and N connected using concatenation and conjunction;
For each rule in P, a subterm A can be rewritten with the term (α₁ & ... & α_m)
A subterm (w & ... & w), for any string w over Σ, can be rewritten with the term w.

The set of strings over Σ derivable from S in this way is the language generated by the grammar.

These definitions, some examples and some basic properties can be found in the following journal paper, in which conjunctive grammars were first introduced:

A. Okhotin, “Conjunctive grammars” (pdf), Journal of Automata, Languages and Combinatorics, 6:4 (2001), 519-535.

An incomplete bibliography on conjunctive grammars is given in the following early survey:

A. Okhotin, “An overview of conjunctive grammars” (pdf), in: Paun, Rozenberg, Salomaa (Eds.), Current Trends in Theoretical Computer Science: The Challenge of the New Century, Vol. 2, World Scientific, 2004, 545--566.
- Earlier version in: Bulletin of the EATCS, 79 (2003), 145-163.

There are awards offered for solving a few theoretical problems on conjunctive grammars.

A. Okhotin, “Nine open problems on conjunctive and Boolean grammars”, TUCS Technical Report No 794, Turku Centre for Computer Science, Turku, Finland, November 2006.

Last updated: 17 November, 2006. Rewritten the entire page.