Wednesday, April 29, 2015

Is Logarithmic Space Closed Under Kleene Star?

A Georgia Tech student asked the title question in an introductory theory course. The instructor asked his TA, the TA asked me and I asked the oracle of all things log space, Eric Allender. Eric didn't disappoint and pointed me to Burkhard Monien’s 1975 theorem
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.
  1. Show that if A is in NL then A* is also in NL.
  2. Show that if A is in P then A* is also in P.
  3. Show that if A is c.e. (recognizable) then A* is also c.e.
Problem 1 above is equivalent to saying NL is closed under Kleene star and implies the “if” part of Monien’s result. Here is a simple proof of the other direction that L closed under Kleene star implies L = NL.

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 AC0 (constant-depth circuits) whose Kleene star is NL-complete. B above is one such set.

8 comments:

  1. 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!

    ReplyDelete
  2. WOW, This is by far the result that I learned at a much
    later 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 *?

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

    ReplyDelete
  4. Flajolet and Steyaert also had this result in a technical report:
    Complexity of classes of languages and operators, Rap. de Recherche 92,
    IRIA Laboria) in Nov. 1974.

    ReplyDelete
    Replies
    1. 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).

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

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

      Delete
  5. Hello, Professor Lance,

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

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

    ReplyDelete