2011/01/01 by Alexander Okhotin, Okhotin, Alexander, Christian Reitwießner +1
Computer Science · #Algorithms and Data Compression #semigroups and automata theory #Complexity and Algorithms in Graphs
paper · doi:10.4230/dagsemproc.10501.3
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| log2(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.