---

---

Alexander Okhotin:
Nine Open Problems on Conjunctive and Boolean Grammars

ISBN: 952-12-1805-3

Techreport
Year: 2006
Month: Nov
Number: 794
Institution: TUCS
Keywords: Conjunctive grammars, Boolean grammars, language equations, parsing, complexity, automata
Address: Department of Mathematics, University of Turku
Laboratory: Discrete Mathematics for Information Technology

Abstract

Conjunctive grammars are context-free grammars with an explicit conjunction operation in the formalism of rules; Boolean grammars are further equipped with an explicit negation. The paper briefly reviews these grammars and proposes 9 most interesting and important research problems for them. An award of $240 Canadian is offered for the first correct solution of each of these problems.


Download full text