6
$\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?

Improve this question
$\endgroup$
3
  • 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, 2011 at 3:15
  • $\begingroup$ @Michaël Cadilhac, I think you can post it as answer so the question becomes answered. $\endgroup$
    – Kaveh
    Feb 22, 2011 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, 2011 at 4:35

2 Answers 2

Reset to default
8
$\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.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Or more simply, any RE-complete problem, like the halting language. $\endgroup$
    – Mark Reitblatt
    Feb 22, 2011 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, 2011 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, 2013 at 16:48
3
$\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.

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.