Earliest Normal Form and Minimization for Bottom-up Tree Transducers

Sylvia Friese, Helmut Seidl, Sebastian Maneth

Research output: Contribution to journalArticlepeer-review


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
Pages (from-to)1607-1623
Number of pages17
JournalInternational Journal of Foundations of Computer Science
Issue number7
Publication statusPublished - 2011

Fingerprint Dive into the research topics of 'Earliest Normal Form and Minimization for Bottom-up Tree Transducers'. Together they form a unique fingerprint.

Cite this