Earliest Normal Form and Minimization for Bottom-up Tree Transducers

Sylvia Friese, Helmut Seidl, Sebastian Maneth

Research output: Contribution to journalArticlepeer-review

Abstract

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
Volume22
Issue number7
DOIs
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