License
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.10501.3
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: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 |
