TY - JOUR

T1 - Conjunctive and boolean grammars

T2 - The true general case of the context-free grammars

AU - Okhotin, Alexander

PY - 2013/8/1

Y1 - 2013/8/1

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

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

KW - Boolean grammars

KW - Conjunctive grammars

KW - Context-free grammars

KW - Formal languages

KW - Language equations

KW - Parsing

UR - http://www.scopus.com/inward/record.url?scp=84880701745&partnerID=8YFLogxK

U2 - 10.1016/j.cosrev.2013.06.001

DO - 10.1016/j.cosrev.2013.06.001

M3 - Review article

AN - SCOPUS:84880701745

VL - 9

SP - 27

EP - 59

JO - Computer Science Review

JF - Computer Science Review

SN - 1574-0137

ER -