L is closed under Kleene star if and only if L = NL.L here is the set of problems solved in deterministic O(log n) space and NL is the nondeterministic counterpart. For a set of strings A, Kleene star, denoted A

^{*}is the set of all finite concatenations of strings of A. For example if A = {00,1} then A

^{*}= {ε, 1, 00, 11, 001, 100, 111, 0000, 0011, 1100, …} where ε is the zero-length string.

Kleene star comes up in regular expressions but also makes for many a good homework problem.

- Show that if A is in NL then A
^{*}is also in NL. - Show that if A is in P then A
^{*}is also in P. - Show that if A is c.e. (recognizable) then A
^{*}is also c.e.

Consider the following NL-complete problem: The set of triples (G,s,t) such that G is a directed graph with a restriction that all edges (i,j) have i<j and there is a path from node s to node t.

Define the following language

B = {G#i+1#G#i+2#...#G#j# | there is an edge (i,j) in G}B is computable in log space and the string G#s+1#G#s+2#…#G#t# is in B

^{*}if and only if there is a path from node s to node t. QED

Allender, Arvind and Mahajan give some generalizations to log-space counting classes and also notes that there are languages computable in AC

^{0}(constant-depth circuits) whose Kleene star is NL-complete. B above is one such set.

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!

ReplyDeleteWOW, This is by far the result that I learned at a much

ReplyDeletelater stage than I should have (I learned it from reading

this blog entry! 30 years after I took a grad course in complexity

theory!) I think I've even told my class

``I do not know of any class that is not closed under Star''

which is technically true (I didn't know! In fact its not known!)

but in any other sense is false.

When I teach complexity theory I DO cover all of the closure

properties for all of the classes. Well, apparently NOT all.

But now I will.

Are there any other natural classes that either are not closed

under * are not thought to be closed under *? Is AC_0 closed

under *?

Dspace(log^2 n) is closed under *. This gives you Savitch's result.

ReplyDeleteFlajolet and Steyaert also had this result in a technical report:

ReplyDeleteComplexity of classes of languages and operators, Rap. de Recherche 92,

IRIA Laboria) in Nov. 1974.

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).

DeleteLet 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*?

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)

DeleteHello, Professor Lance,

ReplyDeleteCould you answer me the following questions, please?

1- What would be the positive consequences of a POLYLOGTIME not equal to NLOGTIME proof?

2- Is not the POLYLOGTIME not equal to NLOGTIME proof proved yet (I mean published in a journal)?

Sincerely Professor Lance, I suspected I have proved the POLYLOGTIME not equal to NLOGTIME result in:

https://hal.archives-ouvertes.fr/hal-01147055

, but I don't really know whether it can be useful or not.

Thanks in advance,

Frank.

DCFL is not closed under star (while CFL is).

ReplyDelete