Paper Info
Title
Fast Stochastic Context-Free Parsing: A Stochastic Version of the Valiant Algorithm
Abstract
In this work, we present a fast stochastic context-free parsing algorithm that is based on a stochastic version of the Valiant algorithm. First, the problem of computing the string probability is reduced to a transitive closure problem. Then, the closure problem is reduced to a matrix multiplication problem of matrices of a special type. Afterwards, some fast algorithm can be used to solve the matrix multiplication problem. Preliminary experiments show that, in practice, an important time savings can be obtained.
Year
DOI
Venue
2007
10.1007/978-3-540-72847-4_12
IbPRIA (1)
Keywords
Field
DocType
important time saving,valiant algorithm,stochastic version,fast stochastic context-free parsing,special type,preliminary experiment,fast stochastic context-free,fast algorithm,closure problem,transitive closure problem,matrix multiplication problem,matrix multiplication,transitive closure
Closure problem,Computer science,Matrix (mathematics),Algorithm,Parsing,Freivalds' algorithm,Transitive closure,Matrix multiplication
Conference
Volume
ISSN
Citations 
4477
0302-9743
6
PageRank 
References 
Authors
0.49
9
2
Name
Order
Citations
PageRank
José-Miguel Benedí131829.43
Joan-Andreu Sánchez219829.00