4 ms·
> 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
by 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.