tag:blogger.com,1999:blog-3722233.post7166443596217832424..comments2024-03-18T23:13:09.570-05:00Comments on Computational Complexity: Is Logarithmic Space Closed Under Kleene Star?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-82267062777203537942015-05-20T07:46:44.096-05:002015-05-20T07:46:44.096-05:00DCFL is not closed under star (while CFL is).DCFL is not closed under star (while CFL is).Amir ben-Amramhttp://www2.mta.ac.il/~amirben/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60792289542151829682015-05-06T02:50:28.348-05:002015-05-06T02:50:28.348-05:00Allthough this question is decidable, I think ther...Allthough this question is decidable, I think there should be no direect way (by looking at the syntactic monoid of A) to decide this: to arbitrary regular set R Pin constructed a finite biprefix code (and thus aperiodic) A such that you "find" R in A* (Sur le monoide syntactique de L∗ lorsque L est un langage fini TCS 7 (1978), 211 - 215)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26947155239866864342015-05-05T05:56:28.621-05:002015-05-05T05:56:28.621-05:00Yes, you're right about Flajolet and Steyaert,...Yes, you're right about Flajolet and Steyaert, although I believe that Monien did his work earlier. We do cite Flajolet and Steyaert in our paper (and also give credit to Lange for noting that the language that they present is actually in AC^0).<br /><br />Let me highlight the following question, which we discuss in our paper, but which has received no attention since (unless there is some work that has been done in the formal language community that I have missed): For some FINITE sets A, A* is complete for NC^1. For other FINITE sets A, A* is in AC^0. Is there an informative way to classify FINITE sets A, that relates to the complexity of A*?Eric Allenderhttp://www.cs.rutgers.edu/~allender/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49017119384860877692015-05-04T11:49:33.056-05:002015-05-04T11:49:33.056-05:00Hello, Professor Lance,
Could you answer me the f...Hello, Professor Lance,<br /><br />Could you answer me the following questions, please?<br /><br />1- What would be the positive consequences of a POLYLOGTIME not equal to NLOGTIME proof?<br /><br />2- Is not the POLYLOGTIME not equal to NLOGTIME proof proved yet (I mean published in a journal)?<br /><br />Sincerely Professor Lance, I suspected I have proved the POLYLOGTIME not equal to NLOGTIME result in:<br /><br />https://hal.archives-ouvertes.fr/hal-01147055<br /><br />, but I don't really know whether it can be useful or not.<br /><br />Thanks in advance,<br />Frank.Anonymoushttps://www.blogger.com/profile/01550125963313485816noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79867193946683864932015-04-30T14:44:21.806-05:002015-04-30T14:44:21.806-05:00Flajolet and Steyaert also had this result in a te...Flajolet and Steyaert also had this result in a technical report:<br />Complexity of classes of languages and operators, Rap. de Recherche 92,<br />IRIA Laboria) in Nov. 1974.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72501390898364606252015-04-30T14:32:52.770-05:002015-04-30T14:32:52.770-05:00Dspace(log^2 n) is closed under *. This gives you ...Dspace(log^2 n) is closed under *. This gives you Savitch's result. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52579816433145261462015-04-30T11:19:35.892-05:002015-04-30T11:19:35.892-05:00WOW, This is by far the result that I learned at a...WOW, This is by far the result that I learned at a much<br />later stage than I should have (I learned it from reading<br />this blog entry! 30 years after I took a grad course in complexity<br />theory!) I think I've even told my class<br />``I do not know of any class that is not closed under Star''<br />which is technically true (I didn't know! In fact its not known!)<br />but in any other sense is false.<br /><br />When I teach complexity theory I DO cover all of the closure<br />properties for all of the classes. Well, apparently NOT all.<br />But now I will.<br /><br />Are there any other natural classes that either are not closed<br />under * are not thought to be closed under *? Is AC_0 closed<br />under *?<br />GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35479571470977661962015-04-29T20:59:59.227-05:002015-04-29T20:59:59.227-05:00Once I reached this result on my own. I was pretty...Once I reached this result on my own. I was pretty proud of myself, but it looked very obvious that this cannot be a new result, so I didn't do anything with it. I didn't know that it's by Burkhard Monien until now, thanks!Anonymousnoreply@blogger.com