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