7
$\begingroup$

I know $CSL\subset UL$ can be demonstrated by reduction to the absurd, but I've been trying to find a language that is in Type 0 ($UL$) and not in Context-Sensitive Languages ($CSL$).

Is there any language with such restrictions that isn't a Context-Sensitive language?

|cite|improve this question
$\endgroup$
  • 7
    $\begingroup$ As UL is the same as recursively enumerable and CSL the same as NSPACE[n] (see, e.g., Wikipedia), you may use your favorite version of the Space hierarchy theorem to get your language in UL \ CSL. $\endgroup$ – Michaël Cadilhac Feb 22 '11 at 3:15
  • $\begingroup$ @Michaël Cadilhac, I think you can post it as answer so the question becomes answered. $\endgroup$ – Kaveh Feb 22 '11 at 4:26
  • $\begingroup$ @Kaveh You're right. @Michaël, post it as an answer, and add something if you want, to mark is at the right answer ;) $\endgroup$ – Oscar Mederos Feb 22 '11 at 4:35
7
$\begingroup$

Type 0 grammars denote exactly recursively enumerable languages, and CSL = NSPACE[$n$] (e.g., Wikipedia). Thus, your favorite proof of the Space Hierarchy Theorem gives an explicit language in, say, NSPACE[$n^2$] \ NSPACE[$n$], thus in UL \ CSL.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ Or more simply, any RE-complete problem, like the halting language. $\endgroup$ – Mark Reitblatt Feb 22 '11 at 14:08
  • 1
    $\begingroup$ Of course ; that's indeed the "farthest" language from CSL to fit, and I proposed the "farthest" language from UL for the same job. $\endgroup$ – Michaël Cadilhac Feb 22 '11 at 15:16
  • $\begingroup$ to be more adequate with the statement "NSPACE[n2] \ NSPACE[n], thus in UL \ CSL", better to say it is so if P<>NP. $\endgroup$ – Charles Yu Apr 18 '13 at 16:48
2
$\begingroup$

Since deciding membership for a context-sensitive grammar is in $PSPACE$ ($NSPACE[n]$ even), any language not in $PSPACE$ is not expressable by a context-sensitive grammar. An example is therefore the language of all true propositions in Presburger arithmetic (en.wikipedia.org/wiki/Presburger_arithmetic).

Since we suspect that $PSPACE \neq EXPTIME$, we expect any $EXPTIME$-hard language to be sufficient. Alternatively, any $EXPSPACE$-hard problem is provably not context-sensitive by the space hierarchy theorem.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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