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

详细信息    查看全文

• 作者：Alex ; er Okhotin ; Christian Reitwie?ner
• 关键词：Boolean grammars ; Conjunctive grammars ; Context-free grammars ; Unary languages ; Parsing ; Boolean convolution ; Integer multiplication
• 刊名：Theoretical Computer Science
• 出版年：2012
• 出版时间：26 October, 2012
• 年：2012
• 卷：457
• 期：Complete
• 页码：149-157
• 全文大小：274 K

文摘

Consider context-free grammars generating strings over a one-letter alphabet. For the membership problem for such grammars, stated as ¡°Given a grammar and a string , determine whether is generated by ¡±, only a na?ve -time algorithm is known. This paper develops a new algorithm solving this problem, which is based upon fast multiplication of integers, works in time , 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 . 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].