The well-known parsing algorithm for the context-free grammars due to Valiant ("General context-free recognition in less than cubic time", Journal of Computer and System Sciences, 10:2 (1975), 308-314) is refactored and generalized to handle the more general Boolean grammars. The algorithm reduces construction of the parsing table to computing multiple products of Boolean matrices of various size. Its time complexity on an input string of length n is , where is the number of operations needed to multiply two Boolean matrices of size n ×n, which is O(n 2.376) as per the current knowledge.
| Original language | English |
|---|---|
| Title of host publication | Developments in Language Theory - 14th International Conference, DLT 2010, Proceedings |
| Pages | 340-351 |
| Number of pages | 12 |
| DOIs | |
| State | Published - 4 Nov 2010 |
| Externally published | Yes |
| Event | 14th International Conference on Developments in Language Theory, DLT 2010 - London, ON, Canada Duration: 17 Aug 2010 → 20 Aug 2010 |
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 6224 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
| Conference | 14th International Conference on Developments in Language Theory, DLT 2010 |
|---|---|
| Country/Territory | Canada |
| City | London, ON |
| Period | 17/08/10 → 20/08/10 |
ID: 41142259