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.[1] 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):

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

For instance:

$${\displaystyle 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))$$
A tree automaton accepts trees. A tree transducer maps trees into trees. Although string automata generally work natural from left to right, there is no such natural choice for tree automata: they can process the tree from top to bottom, from bottom to top, and there are even models that walk over trees (like two-way string automata walk over the input).

As far as I understand, you example has the following meaning. Your automaton is working top to bottom.

$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''$.