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 |
|---|---|---|
2011 | 10.1142/S012905411100891X | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE |
Keywords | Field | DocType |
Bottom-up tree transducers, minimization, normal form | Tree transducers,Transducer,Discrete mathematics,Top-down and bottom-up design,Algorithm,Minification,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
22 | 7 | 0129-0541 |
Citations | PageRank | References |
2 | 0.36 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sylvia Friese | 1 | 4 | 0.74 |
| Helmut Seidl | 2 | 1468 | 103.61 |
| Sebastian Maneth | 3 | 975 | 61.51 |