License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-31465
URL: https://drops.dagstuhl.de/opus/volltexte/2011/3146/
Go to the corresponding Portal

Okhotin, Alexander ; Reitwießner, Christian

Parsing Unary Boolean Grammars Using Online Convolution

pdf-format:
10501.ReitwiessnerChristian.Paper.3146.pdf (0.3 MB)

Abstract

In contrast to context-free grammars, the extension of these grammars by explicit conjunction, the so-called conjunctive grammars can generate (quite complicated) non-regular languages over a single-letter alphabet (DLT 2007). Given these expressibility results, we study the parsability of Boolean grammars, an extension of context-free grammars by conjunction and negation, over a unary alphabet and show that they can be parsed in time O(|G| log^2(n) M(n)) where M(n) is the time to multiply two n-bit integers. This multiplication algorithm is transformed into a convolution algorithm which in turn is converted to an online convolution algorithm which is used for the parsing.

BibTeX - Entry

@InProceedings{okhotin_et_al:DSP:2011:3146,
  author =	{Alexander Okhotin and Christian Reitwie{\"s}ner},
  title =	{{Parsing Unary Boolean Grammars Using Online Convolution}},
  booktitle =	{Advances and Applications of Automata on Words and Trees},
  year =	{2011},
  editor =	{Christian Glasser and Jean-Eric Pin and Nicole Schweikardt and Victor Selivanov and Wolfgang Thomas},
  number =	{10501},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3146},
  annote =	{Keywords: }
}

Collection: 10501 - Advances and Applications of Automata on Words and Trees
Issue Date: 2011
Date of publication: 26.05.2011

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI