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

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

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

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

CC BY-SA 3.0
2014-12-22T10:02:40.907Z
2014-12-22T10:02:40.907Z
Shaull
<p>Could alternating tree automata be used for recognizing set (language) of arbitrary-arity trees? </p>

<p>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\}$.</p>

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

<p><img src="https://i.sstatic.net/s9XHu.png" alt="enter image description here"></p>

CC BY-SA 3.0
2014-12-18T14:59:13.313Z
Are your trees finite, as in your example? If infinite, can the arity be unbounded?
Klaus Draeger
CC BY-SA 3.0
2014-12-18T16:29:12.407Z
@KlausDraeger Let's consider them infinite, but in infinite case arity will be bounded by $|\Sigma|$ (size of the alphabet)
Andrey Lebedev
CC BY-SA 3.0
2014-12-18T16:31:30.070Z
@KlausDraeger In this particular case, arity will be bounded by $2$, because of maximum number of children is $2$: $\{a,b\}$.
Andrey Lebedev
<automata-theory><tree>
Alternating tree automata for arbitrary arity tree
Andrey Lebedev
# Alternating tree automata for arbitrary arity tree

(Asked by: username_0 on 2014-12-18)

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](https://i.sstatic.net/s9XHu.png)

**Tags:** automata-theory, tree

> **Comments:**
> **username_1**: Are your trees finite, as in your example? If infinite, can the arity be unbounded?  
> **username_0**: @KlausDraeger Let's consider them infinite, but in infinite case arity will be bounded by $|\Sigma|$ (size of the alphabet)  
> **username_0**: @KlausDraeger In this particular case, arity will be bounded by $2$, because of maximum number of children is $2$: $\{a,b\}$.  

---

## 1 answers

### Answer by username_2 on 2014-12-22. Score: 2 | Accepted answer

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.


---

