Back to Search
Start Over
Parsing Boolean grammars over a one-letter alphabet using online convolution
- Source :
-
Theoretical Computer Science . Oct2012, Vol. 457, p149-157. 9p. - Publication Year :
- 2012
-
Abstract
- Abstract: 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]. [Copyright &y& Elsevier]
- Subjects :
- *STRING
*MULTIPLICATION
*BOOLEAN functions
*ALGORITHMS
*PROBLEM solving
*INTEGERS
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 457
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 79485319
- Full Text :
- https://doi.org/10.1016/j.tcs.2012.06.032