# Chomsky hierarchy for tree structures

I know of the 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 or trees? In particular, this hierarchy should include tree automata, perhaps streaming tree automata, 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.

## 3 Answers

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

• 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? May 21 '13 at 9:58
• 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. May 22 '13 at 11:51
• The Mostowski hierarchy is only defined for infinite trees, because the parity condition does not make sense on finite trees. May 31 '13 at 12:55

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

• Thank you for the links, I will read a bit more and comment. May 21 '13 at 10:00

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.

• 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. May 28 '13 at 11:48