A1 Refereed original research article in a scientific journal
Parsing Boolean grammars over a one-letter alphabet using online convolution
Authors: Okhotin A, Reitwiessner C
Publisher: ELSEVIER SCIENCE BV
Publication year: 2012
Journal: Theoretical Computer Science
Journal name in source: THEORETICAL COMPUTER SCIENCE
Journal acronym: THEOR COMPUT SCI
Volume: 457
First page : 149
Last page: 157
Number of pages: 9
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2012.06.032
Abstract
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(vertical bar G vertical bar . 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 vertical bar G vertical bar . n log(3) n . 2(O(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 vertical bar G vertical bar . n log(2) n . 2(O(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]. (C) 2012 Elsevier B.V. All rights reserved.
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(vertical bar G vertical bar . 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 vertical bar G vertical bar . n log(3) n . 2(O(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 vertical bar G vertical bar . n log(2) n . 2(O(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]. (C) 2012 Elsevier B.V. All rights reserved.
UTU Research Portal