License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.10501.3
URN: urn:nbn:de:0030-drops-31465
URL: http://dagstuhl.sunsite.rwth-aachen.de/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:DagSemProc.10501.3,
  author =	{Okhotin, Alexander and Reitwie{\ss}ner, Christian},
  title =	{{Parsing Unary Boolean Grammars Using Online Convolution}},
  booktitle =	{Advances and Applications of Automata on Words and Trees},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10501},
  editor =	{Christian Glasser and Jean-Eric Pin and Nicole Schweikardt and Victor Selivanov and Wolfgang Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2011/3146},
  URN =		{urn:nbn:de:0030-drops-31465},
  doi =		{10.4230/DagSemProc.10501.3},
  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