# Difference Between Tree Automata and Tree Transducers

Wondering what the differences are between Tree Automata and Tree Transducers.

Wikipedia says:

Tree transducers extend tree automata in the same way that word transducers extend word automata.

And about word transducers it says:

A finite-state transducer (FST) is a finite-state machine with two memory tapes, following the terminology for Turing machines: an input tape and an output tape. This contrasts with an ordinary finite-state automaton, which has a single tape. An FST is a type of finite-state automaton that maps between two sets of symbols. An FST is more general than a finite-state automaton (FSA). An FSA defines a formal language by defining a set of accepted strings while an FST defines relations between sets of strings.

But I don't understand what the implications are and what the differences really are, even though there is the extra tape. Not sure about the tapes in the Tree Transducers.

All I see so far is tree transducers have the extra "output alphabet" for constructing a new tree (which you plug the state into):

$$q(f(x_{1},\dots ,x_{n}))\to u$$

For instance:

$$q(f(x_{1},\dots ,x_{3}))\to g(a,q'(x_{1}),h(q''(x_{3})))$$

but the automata have pretty much the same signature, just using the input alphabet only:

$$q(f(x_1,...,x_n)) → f(q_1(x_1),...,q_n(x_n))$$

• I'm not familiar with the details concerning tree automata/transducers. In the domain of words an automaton defines a language, i.e. a set of words, as it accepts certain words and rejects others. A transducer on the other hand takes a word as input and produces another word. Thus it defines a function from words to words. I think the tree setting is a generalization. Not sure if this helps you though, as this is pretty much what wikipedia says. Jun 6, 2018 at 13:58

$q(f(x1,\dots ,x3))\to g(a,q′(x1),h(q′′(x3)))$
To the right of the rule we read $q(f(x1,\dots ,x3))$. This means the input is a tree that has a root labelled with symbol $f$. This root has three children represented by the variables $x1,\dots ,x3$. The transducer is at state $q$ when it visits the root labelled $f$.
To the right we see the tree that is constructed when the rule is applied. The tree has a root labelled $g$ and three children. The first child is a leaf labelled by $a$. The next two subtrees are computed by two copies of the original transducer. The second child (of the output) $q′(x1)$ means a copy of the transducer starts at the first child "$x_1$" of the input tree in state $q'$, and the third child $h(q′′(x3))$ indicates a tree with node labelled $h$ which has a single child computed by another copy of the transducer started at the third child "$x_3$" of the input in state $q''$.