Sylvia Friese, Helmut Seidl and Sebastian Maneth. Minimization of Deterministic Bottom-Up Tree Transducers. In Yuan Gao, Hanlin Lu, Shinnosuke Seki and Sheng Yu, editors, Developments in Language Theory, volume 6224 of Lecture Notes in Computer Science, pages 185-196, 2010. Springer.

We show that for every deterministic bottom-up tree transducer, a unique equivalent transducer can be constructed which is minimal. The construction is based on a sequence of normalizing transformations which, among others, guarantee that non-trivial output is produced as early as possible. For a deterministic bottom-up transducer where every state produces either none or infinitely many outputs, the minimal transducer can be constructed in polynomial time.

Download: PDF Reference: Bibtex The original publication is available at www.springerlink.com