TY - JOUR

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

AU - Okhotin, Alexander

AU - Reitwießner, Christian

PY - 2012/10/26

Y1 - 2012/10/26

N2 - 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 an, determine whether an is generated by G", only a nave O(|G|·n2)-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|·nlog3n·2O(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|·nlog2n·2O(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) 317331].

AB - 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 an, determine whether an is generated by G", only a nave O(|G|·n2)-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|·nlog3n·2O(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|·nlog2n·2O(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) 317331].

KW - Boolean convolution

KW - Boolean grammars

KW - Conjunctive grammars

KW - Context-free grammars

KW - Integer multiplication

KW - Parsing

KW - Unary languages

UR - http://www.scopus.com/inward/record.url?scp=84865459916&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2012.06.032

DO - 10.1016/j.tcs.2012.06.032

M3 - Article

AN - SCOPUS:84865459916

VL - 457

SP - 149

EP - 157

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -