I'm considering the problem of recognizing a language (over alphabet 0-9 and space) containing strings like "1 2 3 4 5 6" and "14 15 16 17" but not "1 3".
This came up while working on a common parsing task where elements needed to be in an ordered list. It struck me that while parsing the rest of that language was regular, this part was clearly irregular -- it can recognize, for example, the language A1A2 where A is an arbitrary string 0-9. In fact it seems to be content-sensitive (and not context-free by the pumping lemma).
My first question: is there a (reasonably well-known, i.e. not defined just for this problem) class of languages between context-sensitive and context-free that describes its expressive power better? I've read about Aho's indexed languages, but it's not obvious (to me!) that these are even in that class, powerful though it is.
My second question is informal. It seems that this language is easy to parse, and yet it is very high on the hierarchy. Is it common to come across similar examples and is there a standard way of dealing with them? Is there an alternate grouping of classes of languages that is incompatible with inclusion on the 'usual' ones?
My reason for thinking this is easy: the language can be parsed deterministically, by reading until you get to the end of the first number, checking if the next number follows, and so forth. In particular it can be parsed in O(n) time with O(n) space; the space can be reduced to $O(\sqrt n)$ without too much trouble, I think. But it's hard enough to get that kind of performance with regular languages, let alone context-free.
