4 ms·
CFG parsing can be done better than O(n^3), reducing to Boolean matrix multiplication, which is about O(n^2.37). http://theory.stanford.edu/~virgi/cs367/papers
by pacala 10y ago
CFG parsing can be done better than O(n^3), reducing to Boolean matrix multiplication, which is about O(n^2.37).
http://theory.stanford.edu/~virgi/cs367/papers/valiantcfg.pdf http://theory.stanford.edu/~virgi/cs367/papers/valiantcfg.pd...
https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_a...
Agreed that CYK and Earley are rather simple to implement. Though Earley has an edge, as its best case is O(n), whereas CYK is O(n^2) best case.
- justinpombrio 10y ago> CFG parsing can be done better than O(n^3), reducing to Boolean matrix multiplication, which is about O(n^2.37). Is there a known lower bound on running time to parse CFGs, like O(n^2)?
- DannyBee 10y agoIt is known that any fast CFG parsing algorithm can be turned into a fast boolean matrix multiplication algorithm. So if CFG parsing was n^2, so is boolean matrix multiplication :) See http://arxiv.org/abs/cs/0112018 http://arxiv.org/abs/cs/0112018
- yxhuvud 10y agoOne important note is that this holds for general grammars that can contain everything. If the grammar is restricted somehow, for example to lr(k) then the best complexity is linear (there are even parsers that manage both LR(n) in linear time and general parsing in cubic).
- moefh 10y agoI'm confused by this argument. To show that > if CFG parsing was n^2, so is boolean matrix multiplication wouldn't you need to show that any boolean matrix multiplication can be turned into CFG parsing (and not the converse)?
- deleted 10y ago[deleted]
- justinpombrio 10y agoGreat question, I just learned something. A boolean matrix multiplication problem can be turned into a CFG problem. Therefore, an algorithm that solves CFG problems can be turned into an algorithm that solves boolean matrix multiplication.
- DannyBee 10y agoSorry, yes, i deleted a line accidentally, but it turns out you can show both directions, and to prove a tight bound, you need to show they reduce to each other without changing the complexity class.