1
$\begingroup$

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

|cite|improve this question|||||
$\endgroup$
  • $\begingroup$ Are your trees finite, as in your example? If infinite, can the arity be unbounded? $\endgroup$ – Klaus Draeger Dec 18 '14 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$ – Andrey Lebedev Dec 18 '14 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$ – Andrey Lebedev Dec 18 '14 at 16:31
2
$\begingroup$

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.

|cite|improve this answer|||||
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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