What are the closure properties of $L$ (DLOGSPACE)? I'm not only intrested in these properties (if of course $S$ and $T$ are in $L$) :
- $S \cap T$
- $S^*$ (kleene-star)
- $S.T$ (concat)
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.Sign up to join this community
This question is not research level, even so showing the equivalence of closure under kleene-star to the well known open problem L=NL was a nice challenge. Obviously $S\cap T$ and $S.T$ are in DLOGSPACE, if $S$ and $T$ are in DLOGSPACE.
Obviously $S^*$ is in NL, if $S$ is in NL. One guesses the separation between the first part and the rest and check that the first part is in $S$, then one guesses the next separation and so on.
Since DLOGSPACE is a subclass of NL, it is sufficient to find a $S$ in DLOGSPACE for which $S^*$ is NL-complete, as suggested by Mikhail Rudoy in his comment. A suitable variant of DAG-reachability can be used as NL-complete problem here, and a suitable encoding of single-level DAG reachability as language $S$ in DLOGSPACE.
The encoding of single-level DAG reachability goes as follows: The number of leading zero specifies the node of the input layer, then comes a description of the single-level DAG by the number of input nodes, the number of output nodes, and the connections between those nodes. The trailing number of zeros specifies the node of the output layer, where the complementary scheme "number of output nodes" - "number of trailing zeros" is used.
The variant of DAG-reachability which reduces to $S^*$ is the one with a given separation into levels such that connections only exist between consecutive levels.
We now only look at the words for which the number of output nodes matches the number of input nodes of the next single-level DAG, and where the number of zeros between two descriptions also matches that number. The information about the splitting of the input word into the different parts now provides the nondeterministic guess for how to traverse that DAG.