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