Name
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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-14455-4_18 | Developments in Language Theory |
Keywords | Field | DocType |
non-trivial output,unique equivalent transducer,normalizing transformation,deterministic bottom-up transducer,deterministic bottom-up tree transducer,deterministic bottom-up tree transducers,polynomial time,minimal transducer,bottom up,normal form | Tree transducers,Transducer,Discrete mathematics,Combinatorics,Computer science,Top-down and bottom-up design,Minification,Time complexity | Conference |
Volume | ISSN | ISBN |
6224 | 0302-9743 | 3-642-14454-3 |
Citations | PageRank | References |
2 | 0.39 | 20 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sylvia Friese | 1 | 4 | 0.74 |
| Helmut Seidl | 2 | 1468 | 103.61 |
| Sebastian Maneth | 3 | 975 | 61.51 |