On Fri, Oct 14, 2016 at 3:08 AM, Ulrik Rasmussen <ul...@utr.dk> wrote:
> There is, as far as I know, no known examples of a CFL which cannot be > described by a PEG. The argument for "CF not-less-than PEG" instead relies > on a complexity result due to Lee[1] which says that a linear-time CFG > parser would imply the existence of an efficient O(m^2.333333...) algorithm > for boolean matrix multiplication. To the best of my knowledge, there is no > proof that such an algorithm cannot exist, but none has been found despite > a mountain of work on the subject. > > So, the question "CF < PEG?" is currently open: neither a formal proof nor > a counter-example has been found. > > [1] https://arxiv.org/abs/cs/0112018 > Thank you! -- Juancarlo *Añez*
_______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
