18
$\begingroup$

It is arguable that most languages created to describe everyday problems are context-sensitives. In the other hand, it is possible and not hard to find some languages that are not recursive or even not recursively-enumerable.

Between these two types are the recursive non-context-sensitive languages. Wikipedia gives one example here:

An example of recursive language that is not context-sensitive is any recursive language whose decision is an EXPSPACE-hard problem, say, the set of pairs of equivalent regular expressions with exponentiation.

So the question: What others problems exists that are decidable but yet non-context-sensitive? Is this class of problems the same as decidable EXPSPACE-hard?

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ Lots of (arguably natural) verification problems are (if decidable) at least PSPACE-complete. I am not sure wether this is sufficient for non-context-sensitivity, but there are plenty of problems with an EXPSPACE lower bound, too. $\endgroup$
    – Raphael
    Commented Mar 13, 2012 at 7:14

3 Answers 3

Reset to default
11
$\begingroup$

CSL is the same as $\mathsf{NSpace}(n)$ (non-deterministic linear space). Any language which is outside $\mathsf{NSpace}(n)$ is not CSL.

To get a feeling of the situation, remember that $SAT \in \mathsf{NSpace}(n)$ and even TQBF.

What others problems exists that are decidable but yet non-context-sensitive?

The are many problems. Any problem that is complete for a complexity class larger than $\mathsf{PSpace}$ will do (we need $\mathsf{PSpace}$ because problems like TQBF in $\mathsf{NSpace}(n)$ that are complete for $\mathsf{PSpace}$ because a (polynomial time) reduction can blow up the size of an input by a polynomial). Giving an example will mean proving a lowerbound for the complexity class containing the problem and that is very very difficult task. The only major way we know so far to do this is diagonalization which intuitively means that the larger class should be able to simulate the smaller class.

So $\mathsf{ExpSpace\text{-}hard}$ seems a natural place to start to look for natural examples of language which are not CSL.

Is this class of problems the same as decidable EXPSPACE-hard?

No. By the space hierarchy theorem, there are languages which are in $\mathsf{NSpace}(n^2)$ which are not in $\mathsf{NSpace}(n)$. If you are asking for nice examples, that is going to be difficult because the theorem works using diagonalization and therefore the language it proves to satisfy these conditions is very artificial.

I suggest that you ask a separate question for a natural problem that separates $\mathsf{NSpace}(n^2)$ from $\mathsf{NSpace}(n)$.

Improve this answer
$\endgroup$
0
3
$\begingroup$

Just like $\{a^nb^n:n\geq 0\}$ is context-free but not regular, the language $L=\{a^nb^nc^n:n\geq 0\}$ is decidable but not context-free. However, $L$ can be solved using logarithmic space (you just need a counter for each of the symbols $a$, $b$ and $c$), so it is not EXSPACE-hard.

Also, the language $\{(r_1,r_2):L(r_1)=L(r_2)\}$, where $r_1$ and $r_2$ are regular expressions, is PSPACE-complete. I'm almost sure it's not context-sensitive, but I don't remember a proof and I'm writing from my phone, so it's not easy to go looking for references.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Duh. Sorry. In the end I had ended asking the wrong question! What I am intended was non-context-sensitive instead of non-context-free. I changed the question (which unfortunately invalidates your answer). $\endgroup$
    – Victor Stafusa
    Commented Mar 13, 2012 at 1:46
  • $\begingroup$ BTW, can you answer that in the way it is now? $\endgroup$
    – Victor Stafusa
    Commented Mar 13, 2012 at 1:48
  • $\begingroup$ @Victor what about now? $\endgroup$
    – Janoma
    Commented Mar 13, 2012 at 2:06
  • $\begingroup$ Way better. But still needs improvement. I personally is a bit skeptical about non-context-sensitivity of your example. $\endgroup$
    – Victor Stafusa
    Commented Mar 13, 2012 at 2:07
  • 1
    $\begingroup$ The problem given is correct, but its class was wrong. It is EXPSPACE-complete, not PSPACE-complete. Now I am convinced: en.wikipedia.org/wiki/EXPSPACE $\endgroup$
    – Victor Stafusa
    Commented Mar 13, 2012 at 2:40
0
$\begingroup$

intersection operator\to the syntax of regular expressions, deciding whethertwo such expressions describe the same language is EXPSPACE-hardcheck here hence this language is not context sensitive but recursive https://jeffe.cs.illinois.edu/teaching/algorithms/book/12-nphard.pdf

Improve this answer
$\endgroup$
1
  • $\begingroup$ Please don't copy-paste from external sources without attribution. We require that you indicate all copied material following the guidelines in cs.stackexchange.com/help/referencing, including using quotes to indicate which portion is copied. $\endgroup$
    – D.W. ♦
    Commented Oct 25, 2021 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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