Boolean grammars

AbstractA new generalization of context-free grammars is introduced: Boolean grammars allow the use of all set-theoretic operations as an integral part of the formalism of rules. Rigorous semantics for these grammars is defined by language equations in a way that allows to generalize some techniques from the theory of context-free grammars, including Chomsky normal form, Cocke–Kasami–Younger cubic-time recognition algorithm and some limited extension of the notion of a parse tree, which together allow to conjecture practical applicability of the new concept