tag:blogger.com,1999:blog-3722233.post6356524135894160924..comments2021-09-21T04:14:03.225-05:00Comments on Computational Complexity: A limit on the DFA-CFG divide for finite setsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-882453770050938232016-01-18T08:52:32.538-06:002016-01-18T08:52:32.538-06:00(in the previous comment replace lower-bound with ...(in the previous comment replace lower-bound with upper-bound :-)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37365623499643427732016-01-18T08:34:35.604-06:002016-01-18T08:34:35.604-06:00Oh, I get it now. So what happens if you apply a ...Oh, I get it now. So what happens if you apply a simple regular operation to the language L_n that you found, like L_n^* or L_n concatenated with itself? That could possibly bump you up one exponential.Narad Rampersadnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85118164987261521492016-01-18T08:32:21.361-06:002016-01-18T08:32:21.361-06:00Isn't the diff lower bound ruled by the max &q...Isn't the diff lower bound ruled by the max "growing" that can be achieved by a CFG (i.e. k^n for some k; k=2 for grammars in Chomsky normal form) ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87233491183832207382016-01-15T14:32:53.354-06:002016-01-15T14:32:53.354-06:00That result gives you the following:
For all compu...That result gives you the following:<br />For all computable f, <br />For an INFINITE number of n there is a lang L_n such that<br />there is a CFG of size n but ANY DFA takes size f(n).<br /><br />In fact, this is even true for all f such that f\le_T HALT.<br />In fact, this is even true for all f such that INF \NOT\le_T HALT (thats a new result of mine, see http://arxiv.org/abs/1503.08847<br /><br />BUT what I am asking about is a FOR ALL result. I want <br />FOR ALL n there is a lang L_n such that the diff is large.<br />For that all I have manages is double-exp.<br /><br />GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58185025450321790692016-01-15T14:28:21.204-06:002016-01-15T14:28:21.204-06:00Isn't the (CFG,DFA) separation non-recursive (...Isn't the (CFG,DFA) separation non-recursive (Meyer and Fischer 1971)? I think this is mentioned in the paper of yours that you linked to.Narad Rampersadnoreply@blogger.com