<p>It sounds like what you are looking for are multihead automata (in your case, 1-way 2-head deterministic finite automata should suffice). I'm not really an expert on these, but google turns up some interesting surveys on this language hierarchy, such as</p>

<p>Marek Chrobak: Hierarchies of one-way multihead automata, <a href="http://www.sciencedirect.com/science/article/pii/0304397586900939" rel="nofollow">http://www.sciencedirect.com/science/article/pii/0304397586900939</a></p>

<p>This also gives one answer to your second question: The hierarchy of n-head automata lies "across" the Chomsky hierarchy.</p>

CC BY-SA 3.0
2011-06-30T16:21:23.243Z
That's really fantastic.  I'm surprised -- and pleased -- to see the existence of such a class.
Charles
CC BY-SA 3.0
2011-06-30T21:39:37.460Z
@Marek is on this site: maybe he will weigh in :)
Suresh Venkat
CC BY-SA 3.0
2011-07-03T08:02:47.187Z
That paper was written in my previous life ;-) Yes, if I understand the problem, this language can be accepted by a one-way 2-head automaton. So it's also in LOGSPACE.
Marek Chrobak
CC BY-SA 3.0
2011-06-30T11:19:15.700Z
2011-06-30T11:19:15.700Z
Klaus Draeger
<p>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". </p>

<p>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).</p>

<p>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.</p>

<p>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?</p>

<p>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.</p>

CC BY-SA 3.0
2011-06-30T02:20:00.033Z
The pumping lemma is used to discriminate context-free languages from regular languages and not from context-sensitive languages. So it is sure that your language is not regular, but I think it could be context-free...
Benoît Fraikin
CC BY-SA 3.0
2011-06-30T02:26:27.830Z
@Benoît Fraikin: I'm using 'the other' pumping lemma.
Charles
CC BY-SA 3.0
2011-07-03T17:29:23.723Z
The Bar-Hillel lemma... this is my misunderstanding ^_^
Benoît Fraikin
<fl.formal-languages>
What kind of language is needed to recognize an ordered list? [multihead automata, apparently]
Charles
# What kind of language is needed to recognize an ordered list? [multihead automata, apparently]

(Asked by: username_0 on 2011-06-30)

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.

**Tags:** fl.formal-languages
> **Comments:**
> **username_1**: The pumping lemma is used to discriminate context-free languages from regular languages and not from context-sensitive languages. So it is sure that your language is not regular, but I think it could be context-free...  
> **username_0**: @Benoît Fraikin: I'm using 'the other' pumping lemma.  
> **username_1**: The Bar-Hillel lemma... this is my misunderstanding ^_^  

---

## 1 answers

### Answer by username_2 on 2011-06-30. Score: 7 | Accepted answer

It sounds like what you are looking for are multihead automata (in your case, 1-way 2-head deterministic finite automata should suffice). I'm not really an expert on these, but google turns up some interesting surveys on this language hierarchy, such as

Marek Chrobak: Hierarchies of one-way multihead automata, <http://www.sciencedirect.com/science/article/pii/0304397586900939>

This also gives one answer to your second question: The hierarchy of n-head automata lies "across" the Chomsky hierarchy.

> **Comments:**
> **username_0**: That's really fantastic.  I'm surprised -- and pleased -- to see the existence of such a class.  
> **username_3**: @Marek is on this site: maybe he will weigh in :)  
> **username_4**: That paper was written in my previous life ;-) Yes, if I understand the problem, this language can be accepted by a one-way 2-head automaton. So it's also in LOGSPACE.  

---

