TY - GEN
T1 - Minimization of deterministic bottom-up tree transducers
AU - Friese, Sylvia
AU - Seidl, Helmut
AU - Maneth, Sebastian
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
KW - Bottom-up Tree Transducers
KW - Minimization
KW - Normal form
UR - http://www.scopus.com/inward/record.url?scp=78049291826&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-14455-4_18
DO - 10.1007/978-3-642-14455-4_18
M3 - Conference contribution
AN - SCOPUS:78049291826
SN - 3642144543
SN - 9783642144547
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 185
EP - 196
BT - Developments in Language Theory - 14th International Conference, DLT 2010, Proceedings
T2 - 14th International Conference on Developments in Language Theory, DLT 2010
Y2 - 17 August 2010 through 20 August 2010
ER -