It is arguable that most languages created to describe everyday problems are con

Question

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?

Explanation / Answer

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

To get a feeling of the situation, remember that SAT?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 PSpace will do (we need PSpace because problems like TQBF in NSpace(n) that are complete for 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 ExpSpace-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 NSpace(n2) which are not in 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 NSpace(n2) from NSpace(n)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.