Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there a language actually in use that can't be recognized by a linear bounded automaton? I only know of ones that don't have a practical use, like "the set of pairs of equivalent regular expressions with exponentiation" (Wikipedia). Or would any such language be too slow to recognize to be useful?

share|cite|improve this question
In use by whom? For what? Would "English" count? – Qiaochu Yuan Feb 25 '12 at 22:37
Does something PSPACE-complete count as useful? Because those certainly can't. – Harry Altman Feb 25 '12 at 22:48
Automated proof checkers are computer programs that recognize the language of all valid proofs in some system. I don't think this language can be recognized by a linear bounded automaton, but I don't actually know. – Tanner Swett Feb 25 '12 at 22:49

The set of true statements in Presburger Arithmetic is not context sensitive (as it has been shown that it is not $\text{NPSPACE}(n)$ decideable).

As for being in actual use, don't know.

Got from:

share|cite|improve this answer

I think any problem with non-elementary complexity should do, e.g. "correctly typed programs" for some complex type theories might be just an example you look for ;-)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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