-2
$\begingroup$

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$) :

  1. $S \cap T$
  2. $S^*$ (kleene-star)
  3. $S.T$ (concat)
$\endgroup$

closed as off-topic by Emil Jeřábek supports Monica, Kaveh, Hsien-Chih Chang 張顯之, Jan Johannsen, Yuval Filmus Jul 31 '17 at 11:29

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Emil Jeřábek supports Monica, Kaveh, Hsien-Chih Chang 張顯之, Jan Johannsen, Yuval Filmus
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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 Rudoy Jul 30 '17 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 Klimpel Jul 30 '17 at 9:37
3
$\begingroup$

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.

  1. For $S\cap T$, you run both the machine for $S$ and for $T$, and accept if and only if both accepted.
  2. For $S^*$, see below for a proof that this is equivalent to the L=NL question.
  3. 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.

$\endgroup$
  • $\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$ – Thomas Klimpel Jul 27 '18 at 12:14

Not the answer you're looking for? Browse other questions tagged or ask your own question.