Minimization of Deterministic Bottom-Up Tree Transducers

Sylvia Friese; Helmut Seidl; Sebastian Maneth

doi:10.1007/978-3-642-14455-4_18

Minimization of Deterministic Bottom-Up Tree Transducers

Sylvia Friese, Helmut Seidl, Sebastian Maneth

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 language	English
Title of host publication	Developments in Language Theory
Subtitle of host publication	14th International Conference, DLT 2010, London, ON, Canada, August 17-20, 2010. Proceedings
Publisher	Springer
Pages	185-196
Number of pages	12
Volume	6224
ISBN (Electronic)	978-3-642-14455-4
ISBN (Print)	978-3-642-14454-7
DOIs	https://doi.org/10.1007/978-3-642-14455-4_18
Publication status	Published - 2010

Access to Document

10.1007/978-3-642-14455-4_18

http://dx.doi.org/10.1007/978-3-642-14455-4_18

Cite this

@inproceedings{445b790a39224e87b7d09c5f6ec9d769,

title = "Minimization of Deterministic Bottom-Up Tree Transducers",

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.",

author = "Sylvia Friese and Helmut Seidl and Sebastian Maneth",

year = "2010",

doi = "10.1007/978-3-642-14455-4_18",

language = "English",

isbn = "978-3-642-14454-7",

volume = "6224",

pages = "185--196",

booktitle = "Developments in Language Theory",

publisher = "Springer",

address = "United Kingdom",

}

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.

U2 - 10.1007/978-3-642-14455-4_18

DO - 10.1007/978-3-642-14455-4_18

M3 - Conference contribution

SN - 978-3-642-14454-7

VL - 6224

SP - 185

EP - 196

BT - Developments in Language Theory

PB - Springer

ER -

Minimization of Deterministic Bottom-Up Tree Transducers

Abstract

Access to Document

Fingerprint

Cite this