• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Fast Parsing for Boolean Grammars: A Generalization of Valiant's Algorithm

Alexander Okhotin, Fast Parsing for Boolean Grammars: A Generalization of Valiant's Algorithm. TUCS Technical Reports 953, Turku Centre for Computer Science, 2010.

Abstract:

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 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 $\Theta(BM(n))$, where $BM(n)$ is the number of operations needed to multiply two Boolean matrices of size $n \times n$, which is $O(n^{2.376})$ as per the current knowledge.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tOkhotin09b,
  title = {Fast Parsing for Boolean Grammars: A Generalization of Valiant's Algorithm},
  author = {Okhotin, Alexander},
  number = {953},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2010},
  keywords = {Boolean grammars, conjunctive grammars, context-free grammars, matrix multiplication, parsing, recognition},
  ISBN = {978-952-12-2330-3},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication