Name
Abstract | ||
|---|---|---|
Top-down tree transducers are a convenient formalism for describing tree transformations. They can be equipped with regular look-ahead, which allows them to inspect a subtree before processing it. In certain cases, such a look-ahead can be avoided and the transformation can be realized by a transducer without look-ahead. Removing the look-ahead from a transducer, if possible, is technically highly challenging. For a restricted class of transducers with look-ahead, namely those that are total, deterministic, ultralinear, and bounded erasing, we present an algorithm that, for a given transducer from that class, (1) decides whether it is equivalent to a total deterministic transducer without look-ahead, and (2) constructs such a transducer if the answer is positive. For the whole class of total deterministic transducers with look-ahead we present a similar algorithm, which assumes that a so-called difference bound is known for the given transducer. The designer of a transducer can usually also determine a difference bound for it. |
Year | Venue | Field |
|---|---|---|
2013 | CoRR | Tree transducers,Transducer,Discrete mathematics,Tree (data structure),Top-down and bottom-up design,Algorithm,Look-ahead,Formalism (philosophy),Mathematics,Bounded function |
DocType | Volume | Citations |
Journal | abs/1311.2400 | 3 |
PageRank | References | Authors |
0.38 | 13 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Joost Engelfriet | 1 | 2783 | 212.93 |
| Sebastian Maneth | 2 | 975 | 61.51 |
| Helmut Seidl | 3 | 1468 | 103.61 |