<p>For tree automata, you have the Mostowski hierarchy, which is about the complexity of acceptance condition: each level is of the form $(i,j)$ with $i\in\{0,1\}$ and $i\leq j$. Being at level $(i,j)$ means that there is a parity automaton using parities from $i$ to $j$ recognizing the language. For more on parity condition, see here: <a href="https://en.wikipedia.org/wiki/%CE%A9-automaton" rel="nofollow">https://en.wikipedia.org/wiki/%CE%A9-automaton</a>. This hierarchy exists in 3 versions: deterministic, nondeterministic, or alternating, depending on the model of automaton you are looking at (although the deterministic hierarchy does not cover all regular languages).</p>

<p>There is an other hierarchy called Wadge hierarchy, with a more topological flavour, but it is getting further from complexity of acceptors: <a href="http://en.wikipedia.org/wiki/Wadge_hierarchy" rel="nofollow">http://en.wikipedia.org/wiki/Wadge_hierarchy</a></p>

CC BY-SA 3.0
2013-05-21T09:58:25.897Z
Thanks for your answer.  Could you please clarify the relation between the Wadge hierarchy (which seems to me as a classification of sets) and trees?  Also, as far as I can tell by reading about ω-automata, they accept/reject infinite words.  Does the Mostowski hierarchy also apply to finite trees?
Bruno Le Floch
CC BY-SA 3.0
2013-05-22T11:51:10.243Z
Languages of infinite trees are sets, and you can apply the Wadge hierarchy over them.
Mostowski hierarchy is also applied on trees. The nondeterministic one collapses on [1,2]-level on words, but all 3 (det,ND, alt) are strict on trees.
The two hierarchy are rather independant, for instance you can arbitrarily high in the Wadge hierarchy, while staying at the [1,2]-level of Mostowski.
Denis
CC BY-SA 3.0
2013-05-31T12:55:27.910Z
The Mostowski hierarchy is only defined for infinite trees, because the parity condition does not make sense on finite trees.
Denis
CC BY-SA 3.0
2013-05-20T17:00:57.910Z
2013-05-20T17:00:57.910Z
Denis
<p>The Mostowski hierarchy is about parity automata, thus infinite trees. I believe, it is beyond the question.</p>

<p>Best work I can think of about automata on finite trees is TATA <a href="http://tata.gforge.inria.fr/" rel="nofollow">http://tata.gforge.inria.fr/</a> . But it is mostly about finite state ones, and rather concerned about using them as a framework for satisfiability problems.</p>

<p>Few years ago, during my studies, I also developed some construction to describe more proper ASTs for order-independent constructions in programming languages. However, it may be also used for parsing some partially flat, partially structured input. That particularly is trees or some mixes of trees with words. With this, you can probably use most of common algorithms for parsing words, with some minimal modifications. Still, I do not know, what complexity you will get. -- Here is the link. However, it is bad like the hell (I couldn't write properly), so I do not know, will it be helpful. <a href="http://tele-fan.pl/strings_and_cfgs_with_sets.pdf" rel="nofollow">http://tele-fan.pl/strings_and_cfgs_with_sets.pdf</a></p>

CC BY-SA 3.0
2013-05-21T10:00:59.000Z
Thank you for the links, I will read a bit more and comment.
Bruno Le Floch
CC BY-SA 3.0
2013-05-20T21:02:14.627Z
2013-05-20T21:02:14.627Z
Number47
<p>If you are planning on using this kind of syntax for a real
application requiring a parser, you probably do not want to wander
outside the polynomial realm. So you might be interested by 
<code>linear context-fre rewriting systems</code>
which is a hierarchy of grammatical
formalisms parsable in polynomial time. This has been heavily explored
by the community that studies formal syntax for natural languages. You may also look for <code>mildly context-sensitive</code> languages.</p>

<p><code>Context-free</code> (CF) languages are at the bootom of that hierarchy, parsable
in tine n^3. The next family is <code>tree adjoining grammars</code>, parsable in
time n^6. Of course, these are worst case bounds.  If you avoid
pathological cases, things often work a lot better. Anything that is
hard for a software parser is also hard for a human reader.</p>

<p>There is a significant body of litterature on all this. And there have
been more recent extensions: <code>Range concatenation grammars</code> (RCG)</p>

<p>By the way, I suppose one can consider that CF grammars are for nested
words. In the same way, <code>tree adjoining grammars</code> are for nested trees.
All the <code>linear context-fre rewriting systems</code> are for increasingly
complex forms of nesting (<em>nesting</em> is what <em>context-free</em> stands for in
the name).</p>

<p>But I honestly doubt you want that much expressive power.</p>

<p>You should also be aware that you can express a lot of things with
context-free languages when you do not restrict yourself to languages
that are deterministically parsable from left to right with a push-down memory stack. Actually,
depending on the application, ambiguous context-free syntax may be a
perfectly reasonnable choice.</p>

<p>I wonder why you seem so interested in <code>tree automata</code>, though you do not say which variety.</p>

<p><em>Side note : I doubt there is much insight to be gained from the
Chomsky hierarchy. It is more a historical curiosity than a useful
technical concept.</em></p>

CC BY-SA 3.0
2013-05-28T11:48:22.267Z
I looked a bit at your references, not in depth though. I was familiar with FSA on trees, but not in these recent uses. I persist in thinking that `tree adjoining grammars` should interest you as they are much like tree CFG.
babou
CC BY-SA 3.0
2013-05-22T22:39:46.007Z
2013-05-23T09:28:57.900Z
2013-05-23T09:28:57.900Z
babou
<p>I know of the <a href="http://en.wikipedia.org/wiki/Chomsky_hierarchy" rel="nofollow">Chomsky hierarchy</a>, which concerns the expressive power of grammars to recognize languages $L \subseteq \Sigma^*$ made of words on an alphabet $\Sigma$.</p>

<p>Is there a similar hierarchy for grammars/parsers which are specifically taylored for <a href="http://en.wikipedia.org/wiki/Nested_word" rel="nofollow">nested words</a> or trees?  In particular, this hierarchy should include <a href="http://en.wikipedia.org/wiki/Tree_automaton" rel="nofollow">tree automata</a>, perhaps <a href="http://hal.inria.fr/docs/00/31/58/53/PDF/0.pdf" rel="nofollow">streaming tree automata</a>, the algorithms used to apply CSS rules...</p>

<p>As I am planning to implement parsers for one/some of the steps in the hierarchy, I am very interested also in the algorithmic complexity of parsers for those grammars.  I might use this as a basis for a CSS-like functionality in LaTeX.</p>

<fl.formal-languages><automata-theory><tree><grammars><regular-expressions>
Chomsky hierarchy for tree structures
Bruno Le Floch
# Chomsky hierarchy for tree structures

(Asked by: username_0 on 2013-05-20)

I know of the [Chomsky hierarchy](http://en.wikipedia.org/wiki/Chomsky_hierarchy), which concerns the expressive power of grammars to recognize languages $L \subseteq \Sigma^\*$ made of words on an alphabet $\Sigma$.

Is there a similar hierarchy for grammars/parsers which are specifically taylored for [nested words](http://en.wikipedia.org/wiki/Nested_word) or trees? In particular, this hierarchy should include [tree automata](http://en.wikipedia.org/wiki/Tree_automaton), perhaps [streaming tree automata](http://hal.inria.fr/docs/00/31/58/53/PDF/0.pdf), the algorithms used to apply CSS rules...

As I am planning to implement parsers for one/some of the steps in the hierarchy, I am very interested also in the algorithmic complexity of parsers for those grammars. I might use this as a basis for a CSS-like functionality in LaTeX.

**Tags:** fl.formal-languages, automata-theory, tree, grammars, regular-expressions


---

## 3 answers

### Answer by username_1 on 2013-05-20. Score: 3

For tree automata, you have the Mostowski hierarchy, which is about the complexity of acceptance condition: each level is of the form $(i,j)$ with $i\in\{0,1\}$ and $i\leq j$. Being at level $(i,j)$ means that there is a parity automaton using parities from $i$ to $j$ recognizing the language. For more on parity condition, see here: <https://en.wikipedia.org/wiki/%CE%A9-automaton>. This hierarchy exists in 3 versions: deterministic, nondeterministic, or alternating, depending on the model of automaton you are looking at (although the deterministic hierarchy does not cover all regular languages).

There is an other hierarchy called Wadge hierarchy, with a more topological flavour, but it is getting further from complexity of acceptors: <http://en.wikipedia.org/wiki/Wadge_hierarchy>

> **Comments:**
> **username_0**: Thanks for your answer.  Could you please clarify the relation between the Wadge hierarchy (which seems to me as a classification of sets) and trees?  Also, as far as I can tell by reading about ω-automata, they accept/reject infinite words.  Does the Mostowski hierarchy also apply to finite trees?  
> **username_1**: Languages of infinite trees are sets, and you can apply the Wadge hierarchy over them. Mostowski hierarchy is also applied on trees. The nondeterministic one collapses on [1,2]-level on words, but all 3 (det,ND, alt) are strict on trees. The two hierarchy are rather independant, for instance you can arbitrarily high in the Wadge hierarchy, while staying at the [1,2]-level of Mostowski.  
> **username_1**: The Mostowski hierarchy is only defined for infinite trees, because the parity condition does not make sense on finite trees.  

---

### Answer by username_2 on 2013-05-20. Score: 1

The Mostowski hierarchy is about parity automata, thus infinite trees. I believe, it is beyond the question.

Best work I can think of about automata on finite trees is TATA <http://tata.gforge.inria.fr/> . But it is mostly about finite state ones, and rather concerned about using them as a framework for satisfiability problems.

Few years ago, during my studies, I also developed some construction to describe more proper ASTs for order-independent constructions in programming languages. However, it may be also used for parsing some partially flat, partially structured input. That particularly is trees or some mixes of trees with words. With this, you can probably use most of common algorithms for parsing words, with some minimal modifications. Still, I do not know, what complexity you will get. -- Here is the link. However, it is bad like the hell (I couldn't write properly), so I do not know, will it be helpful. <http://tele-fan.pl/strings_and_cfgs_with_sets.pdf>

> **Comments:**
> **username_0**: Thank you for the links, I will read a bit more and comment.  

---

### Answer by username_3 on 2013-05-22. Score: 1

If you are planning on using this kind of syntax for a real
application requiring a parser, you probably do not want to wander
outside the polynomial realm. So you might be interested by
`linear context-fre rewriting systems`
which is a hierarchy of grammatical
formalisms parsable in polynomial time. This has been heavily explored
by the community that studies formal syntax for natural languages. You may also look for `mildly context-sensitive` languages.

`Context-free` (CF) languages are at the bootom of that hierarchy, parsable
in tine n^3. The next family is `tree adjoining grammars`, parsable in
time n^6. Of course, these are worst case bounds. If you avoid
pathological cases, things often work a lot better. Anything that is
hard for a software parser is also hard for a human reader.

There is a significant body of litterature on all this. And there have
been more recent extensions: `Range concatenation grammars` (RCG)

By the way, I suppose one can consider that CF grammars are for nested
words. In the same way, `tree adjoining grammars` are for nested trees.
All the `linear context-fre rewriting systems` are for increasingly
complex forms of nesting (*nesting* is what *context-free* stands for in
the name).

But I honestly doubt you want that much expressive power.

You should also be aware that you can express a lot of things with
context-free languages when you do not restrict yourself to languages
that are deterministically parsable from left to right with a push-down memory stack. Actually,
depending on the application, ambiguous context-free syntax may be a
perfectly reasonnable choice.

I wonder why you seem so interested in `tree automata`, though you do not say which variety.

*Side note : I doubt there is much insight to be gained from the
Chomsky hierarchy. It is more a historical curiosity than a useful
technical concept.*

> **Comments:**
> **username_3**: I looked a bit at your references, not in depth though. I was familiar with FSA on trees, but not in these recent uses. I persist in thinking that `tree adjoining grammars` should interest you as they are much like tree CFG.  

---

