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

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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.