Tree transducer

In theoretical computer science and formal language theory, a tree transducer (TT) is an abstract machine taking as input a tree structure, and generating output – generally other trees, but models producing words or other structures exist. Roughly speaking, tree transducers extend tree automata in the same way that word transducers extend word automata.

Manipulating tree structures instead of words enable TT to model syntax-directed transformations of formal or natural languages. However, TT are not as well-behaved as their word counterparts in terms of algorithmic complexity, closure properties, etcetera. In particular, most of the main classes are not closed under composition.

The main classes of tree transducers are:

Top-Down Tree Transducers (TOP)

A TOP T is a tuple (Q, Σ, Γ, I, δ) such that:

• Q is a finite set, the set of states;
• Σ is a finite ranked alphabet, called the input alphabet;
• Γ is a finite ranked alphabet, called the output alphabet;
• I is a subset of Q, the set of initial states; and
• $\delta$ is a set of rules of the form $q(f(x_{1},\dots ,x_{n}))\to u$, where

f is a symbol of Σ, n is the arity of f, q is a state, and u is a tree on Γ and $Q\times 1..n$, such pairs being nullary.

For instance,

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

is a rule – one customarily writes $q(x_{i})$ instead of the pair $(q,x_{i})$ – and its intuitive semantics is that, under the action of q, a tree with f at the root and three children is transformed into

$g(a,q'(x_{1}),h(q''(x_{3})))$

where, recursively, $q'(x_{1})$ and $q''(x_{3})$ are replaced, respectively, with the application of $q'$ on the first child and with the application of $q''$ on the third.

The semantics of the transducer T is a binary relation between input trees (on Σ) and output trees (on Γ), defined as the union of the semantics of its initial states, each of which is of the same type.

As with tree automata, a TOP is said to be deterministic (abbreviated DTOP) if no two rules of δ share the same left-hand side, and there is at most one initial state. In that case, the semantics of the DTOP is a partial function from input trees (on Σ) to output trees (on Γ), as are the semantics of each of the DTOP's states.

The domain of a transducer is the domain of its semantics.

Properties of DTOP

• DTOP are not closed under union: this is already the case for deterministic word transducers.

• The domain of a DTOP is a regular tree language.

• DTOP are not closed under composition. However this problem can be solved by the addition of a lookahead: a tree automaton coupled to the transducer, which can perform tests on the domain which the transducer is incapable of.

• The typechecking problem -- testing whether the image of a regular tree language is included in another regular tree language -- is decidable.

• The equivalence problem -- testing whether two DTOP define the same functions -- is decidable.

Bottom-Up Tree Transducers (BOT)

As in the simpler case of tree automata, bottom-up tree transducers are defined similarly to their top-down counterparts, but proceed from the leaves of the tree to the root, instead of from the root to the leaves. Thus the main difference is in the form of the rules, which are of the form $f(q_{1}(x_{1}),\dots ,q_{n}(x_{n})))\to q(u)$.

See also

• Rewriting#Term_rewriting_systems: the rules of tree automata and transducers are specific term rewriting rules.

References

• Comon, Hubert; Dauchet, Max; Gilleron, Rémi; Jacquemard, Florent; Lugiez, Denis; Löding, Christof; Tison, Sophie; Tommasi, Marc (November 2008). "Chapter 6: Tree Transducers". Tree Automata Techniques and Applications (PDF). Retrieved 11 February 2014.
• Hosoya, Haruo (4 November 2010). Foundations of XML Processing: The Tree-Automata Approach. Cambridge University Press. ISBN 978-1-139-49236-2. {{cite book}}: Invalid |ref=harv (help)