2026-07-20T05:25:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3146 2024-03-06T11:09:33Z ddc:004 open_access

Parsing Unary Boolean Grammars Using Online Convolution Okhotin, Alexander Reitwießner, Christian 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexander Okhotin and Christian Reitwießner 2011 Is Part Of Dagstuhl Seminar Proceedings, Volume 10501, Advances and Applications of Automata on Words and Trees (2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.10501.3 urn:nbn:de:0030-drops-31465 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10501.3 eng https://creativecommons.org/licenses/by/4.0/legalcode