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):

enter image description here

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

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.