Chennai Mathematical Institute


3.30 p.m
Minimization of Tree Transducers

Helmut Seidl
Technical University of Munich, Germany.


Finite tree transducers can be used to describe simple transformations on structured documents. The talk considers deterministic topdown tree transducers and shows that each of them is equivalent to a corresponding canonical transducer. This result generalizes a corresponding construction for deterministic word transducers by Mohri. It allows for a simpler method for deciding equivalence of topdown transducers and also opens up possiblities for learning transducers from examples.