tag:blogger.com,1999:blog-3722233.post4857864447576414386..comments2023-03-20T21:49:52.361-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-05T01:29:03.891-05:002015-06-05T01:29:03.891-05: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