DagSemProc.10501.3.pdf
- Filesize: 313 kB
- 11 pages
Document
Parsing Unary Boolean Grammars Using Online Convolution
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 10501
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2011-05-26
Cite AsGet BibTex
Alexander Okhotin and Christian Reitwießner. Parsing Unary Boolean Grammars Using Online Convolution. In Advances and Applications of Automata on Words and Trees. Dagstuhl Seminar Proceedings, Volume 10501, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
https://doi.org/10.4230/DagSemProc.10501.3
https://doi.org/10.4230/DagSemProc.10501.3
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.
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads