4
$\begingroup$

Actually I found that the set of context-sensitive Languages, $\mathbf{CSL}$ ($\mathbf{=NSPACE}(O(n))$ $= \mathbf{LBA}$ accepted languages) are not so widely discussed as $\mathbf{REG}$ (regular languages) or $\mathbf{CFL}$ (context-free languages).

And also the open problem $\mathbf{DSPACE}(O(n)) \stackrel?= \mathbf{NSPACE}(O(n))$ is not so famous as the "analogous" problem: $\mathbf{P} \stackrel?= \mathbf{NP}$.

So I have two questions:

  1. Is there a language in $\mathbf{CSL}$ which couldn't be proved to be in $\mathbf{DSPACE}(O(n))$?
  2. Moreover: Is there a language $L$ in $\mathbf{CSL}$ which is "complete" in the following sense: if we can prove that $L$ is in $\mathbf{DSPACE}(O(n))$ we get that $\mathbf{DSPACE}(O(n)) = \mathbf{CSL}$?

Notice: I have asked these questions in cs.stackexchange and got some interesting Answers but not a concrete (proven) example for such a language: https://cs.stackexchange.com/questions/79528/a-language-in-nspaceon-and-very-likely-not-in-dspaceon

|cite|improve this question
$\endgroup$
  • $\begingroup$ Neat question! :) $\endgroup$ – Michael Wehar Sep 6 '17 at 4:20
  • 5
    $\begingroup$ Just take any language complete for NSPACE(n) under linear-time reductions. $\endgroup$ – Emil Jeřábek Sep 6 '17 at 8:21
  • $\begingroup$ $NPSPACE=NSPACE(poly(n))=DSPACE(poly(n))=PSPACE$ So my prior is that $NSPACE(O(n))$ and $DSPACE(O(n))$ are fairly close and not analogous to $P$ versus $NP$. $\endgroup$ – Thomas Sep 6 '17 at 8:31
  • $\begingroup$ @Thomas, I already pointed that this is more analogous to $L$ vs. $NL$. $\endgroup$ – rus9384 Sep 7 '17 at 5:35
  • 2
    $\begingroup$ I don’t know what is many, but it’s certainly straightforward to construct examples of such languages: e.g., $L_1=\{\langle M,w\rangle:\text{$M$ is an NTM and accepts $w$ within space $|w|$}\}$, or $L_2={}$ succinct $s$-$t$-connectivity (i.e., the set of Boolean circuits $C$ in $2n$ variables such that there is a directed path from $\vec0$ to $\vec1$ in the directed graph on vertex set $\{0,1\}^n$ whose edge relation is computed by $C$). Surely some such have been given in the literature, but I can’t point you to a book. $\endgroup$ – Emil Jeřábek Sep 7 '17 at 14:10

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.