# Alternating tree automata for arbitrary arity tree

Could alternating tree automata be used for recognizing set (language) of arbitrary-arity trees?

More specifically, as an example: let $\Sigma = \{a,b,c\}$ - labels for tree nodes. Trees from $T$ are of the form: from each node only one of the following children could appear: $\{a,b\},\{b\},\{c\}$.

I.e. tree will be of the form, smth like this ($e$ on picture is just root of the tree, indexes on labels are just features of drawing tool, they aren't related to the question):

• Are your trees finite, as in your example? If infinite, can the arity be unbounded? – Klaus Draeger Dec 18 '14 at 14:59
• @KlausDraeger Let's consider them infinite, but in infinite case arity will be bounded by $|\Sigma|$ (size of the alphabet) – Andrey Lebedev Dec 18 '14 at 16:29
• @KlausDraeger In this particular case, arity will be bounded by $2$, because of maximum number of children is $2$: $\{a,b\}$. – Andrey Lebedev Dec 18 '14 at 16:31

An alternating tree automaton for arbitrary degree trees has a transition function of the following type: $$\delta:Q\times \Sigma\times D\to {\cal B}(\mathbb{N}\times Q)$$ where ${\cal B}$ is the set of Boolean functions over the given set.

This has a limitation that $\delta(q,\sigma,d)$ only outputs values between $1,...,d$ (so it fits the degree of the tree).

Thus, the transition function is defined separately for each degree, so it's effectively a family of automata. In particular, this means that if you want to handle arbitrary degrees, you need an infinite description (or a finite description of an infinite object). While this is mathematically possible, it can of course make things undecidable, if (for example) your transition function is given by a TM.

In your example, you can clearly construct such an automaton, since you can construct one for every degree.