up vote 6 down vote favorite
2

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?

share|cite|improve this question
  • 6
    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. – Michaël Cadilhac Feb 22 '11 at 3:15
  • @Michaël Cadilhac, I think you can post it as answer so the question becomes answered. – Kaveh Feb 22 '11 at 4:26
  • @Kaveh You're right. @Michaël, post it as an answer, and add something if you want, to mark is at the right answer ;) – Oscar Mederos Feb 22 '11 at 4:35
up vote 6 down vote accepted

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.

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

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.

share|cite|improve this answer

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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