1
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – SimonJ
    Commented Jun 6, 2018 at 13:58

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$

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.