Parsing Boolean grammars over a one-letter alphabet using online convolution

摘要

Consider context-free grammars generating strings over a one-letter alphabet. For the membership problem for such grammars, stated as "Given a grammar G and a string a~n, determine whether a~n is generated by G", only a naive O(|G| · n~2)-time algorithm is known. This paper develops a new algorithm solving this problem, which is based upon fast multiplication of integers, works in time |G| · n log~3 n · 2~(0(log~*n)), and is applicable to context-free grammars augmented with Boolean operations, known as Boolean grammars. For unambiguous grammars, the running time of the algorithm is reduced to |G| · n log~2 n · 2~(0(log~* n)). The algorithm is based upon (a simplification of) the online integer multiplication algorithm by Fischer and Stockmeyer [M.J. Fischer, L.J. Stockmeyer, Fast on-line integer multiplication, Journal of Computer and System Sciences 9 (3) (1974) 317-331].