7
$\begingroup$

Hopcroft & Ullman 1979, Intro to Automata Theory, Languages, & Computation states (p. 224) that "almost any language one can think of is CSL; the only known proofs that certain languages are not CSLs are ultimately based on diagonalization." They give for example the universal Turing machine. I presume this statement is still true today more than three decades later but wonder anyway.

Are there any non-CSLs known that are not "ultimately based on diagonalization"?

I agree that this question is not necessarily strictly defined. I would also be willing to accept examples in the form where an algorithm was initially/originally built or constructed for some purpose and had unknown complexity and later the algorithm was proved to be non-CSL.

Note non CSLs are also the Exp-space hard problems. Wikipedia mentions without reference "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." I would like to know a reference for this if anyone has it.

Improve this question
$\endgroup$
2
  • 6
    $\begingroup$ For the question in the note in the last paragraph, check the fact that all context-sensitive languages are in PSPACE. The claim follows by combining it with the space hierarchy theorem. $\endgroup$
    – Tsuyoshi Ito
    Commented Apr 28, 2012 at 17:13
  • $\begingroup$ If you agree that proving uncomputability of the Busy Beaver function (en.wikipedia.org/wiki/Busy_beaver) does not ultimately base on diagonalization, then one can prove undecidability of the HALTING problem without diagonalization. The HALTING problem is non-CSL. $\endgroup$
    – David G
    Commented Jul 23, 2013 at 21:29

0

Reset to default

Your Answer

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