DOI

Boolean grammars are an extension of context-free grammars, in which conjunction and negation may be explicitly used in the rules. In this paper, the notion of ambiguity in Boolean grammars is defined. It is shown that the known transformation of a Boolean grammar to the binary normal form preserves unambiguity, and that every unambiguous Boolean language can be parsed in time O(n2). Linear conjunctive languages are shown to be unambiguous, while the existence of languages inherently ambiguous with respect to Boolean grammars is left open.

Original languageEnglish
Pages (from-to)1234-1247
Number of pages14
JournalInformation and Computation
Volume206
Issue number9-10
DOIs
StatePublished - 1 Sep 2008

    Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

    Research areas

  • Ambiguity, Boolean grammars, Conjunctive grammars, Parsing

ID: 41141675