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
Pages185-196
Number of pages12
Volume6224
ISBN (Electronic)978-3-642-14455-4
ISBN (Print)978-3-642-14454-7
DOIs
Publication statusPublished - 2010

Fingerprint

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

Cite this