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)
$\begingroup$
$\endgroup$
2
-
$\begingroup$ I'm pretty sure that one can construct a logspace language $S$ such that $S^*$ is NL-complete. Then if L $\ne$ NL, we can immediately conclude that L is not closed under kleene-star. $\endgroup$– Mikhail RudoyCommented Jul 30, 2017 at 3:04
-
$\begingroup$ @MikhailRudoy Thanks for the hint, I now constructed such a logspace language $S$ in my answer below. Don't worry about the fact that it will soon be deleted together with this question, I locally saved a copy of my answer. I know that it is problematic to answer non-research level questions here, since we should not encourage such questions on this side. But I just wanted to know the answer before the question gets deleted, since it is still a nice little challenge. $\endgroup$– Thomas KlimpelCommented Jul 30, 2017 at 9:37
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
- For $S\cap T$, you run both the machine for $S$ and for $T$, and accept if and only if both accepted.
- For $S^*$, see below for a proof that this is equivalent to the L=NL question.
- For $S.T$, you run a counter separating $S$ from $T$, and accept if there is a counter position for which the first part is accepted by the machine for $S$, and the second part is accepted by the machine for $T$.
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.
-
$\begingroup$ Turns out this was first shown by Burkhard Monien in 1975 as the theorem "L is closed under Kleene star if and only if L = NL.", see blog.computationalcomplexity.org/2015/04/…. I still think this is not research level, even so one also has to prove the easier results sooner or later, and there will always be a huge number of such results. $\endgroup$ Commented Jul 27, 2018 at 12:14