tag:blogger.com,1999:blog-3722233.post4857864447576414386..comments2020-01-20T07:37:42.239-05:00Comments on Computational Complexity: Langs with provably bigger CFG's then CSG'sLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-3722233.post-23595852526677922912015-06-05T02:29:03.891-04:002015-06-05T02:29:03.891-04:00Nice results! There is a slight problem with (3), ...Nice results! There is a slight problem with (3), since Sn actually has CFGs of size O(n^3) using "dynamic programming". Perhaps you got confused due to a typo in my paper (in Theorem 9, n should be t).<br /><br />On the other hand, I think that Wn has a CSG of size O(log n), so you get a similar separation using the lower bound you quote in (2), which does hold.<br /><br />Finally, let me mention that the lower bounds in Ellul et al. and my paper use exactly the same technique, which is a bit surprising since I didn't know of their paper while writing mine.Yuval Filmushttps://www.blogger.com/profile/08450062297306341505noreply@blogger.com