Minimization of Deterministic Bottom-Up Tree Transducers

Sylvia Friese, Helmut Seidl, Sebastian Maneth

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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.
Original languageEnglish
Title of host publicationDevelopments in Language Theory
Subtitle of host publication14th International Conference, DLT 2010, London, ON, Canada, August 17-20, 2010. Proceedings
PublisherSpringer Berlin Heidelberg
Number of pages12
ISBN (Electronic)978-3-642-14455-4
ISBN (Print)978-3-642-14454-7
Publication statusPublished - 2010


Dive into the research topics of 'Minimization of Deterministic Bottom-Up Tree Transducers'. Together they form a unique fingerprint.

Cite this