Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Unambiguous Boolean Grammars

Unambiguous Boolean Grammars

Alexander Okhotin, Unambiguous Boolean Grammars. TUCS Technical Reports 802, Turku Centre for Computer Science, 2007.

Abstract:

Boolean grammars are an extension of context-free grammars, in which all propositional connectives can 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 <i>O</i>(<i>n</i>^2). Linear conjunctive languages are shown to be unambiguous, while the existence of languages inherently ambiguous with respect to Boolean grammars is left open.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tOkhotin07a,
  title = {Unambiguous Boolean Grammars},
  author = {Okhotin, Alexander},
  number = {802},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2007},
  keywords = {ambiguity, parsing, Boolean grammars, conjunctive grammars, language equations},
  ISBN = {978-952-12-1846-0},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication