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
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 |