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.


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.

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.