2 ms·
OK. I thought you meant that a non-constructive proof existed that there is such a CFG. That's how I interpreted "Finally, since PEG can be parsed in linear tim
by versteegen 10y ago
OK. I thought you meant that a non-constructive proof existed that there is such a CFG. That's how I interpreted "Finally, since PEG can be parsed in linear time, there must also be some CFG which cannot be recognized by any PEG". But I see that on cstheory you wrote instead (being more precise?) "most probably ... PEG does not contain CFG".
- ulrikrasmussen 10y agoAh, yes, that's because the non-linear complexity of binary matrix multiplication (which CFG parsing can be reduced to) is strongly suspected to be a lower bound, but I don't think that there is a formal proof of it (I am not an expert in complexity theory, so I am just basing this on what some authors seem to suggest). So, the non-constructive argument is a "proof" in the same sense that some results can be proved by first assuming that P /= NP.