Abstract
Top-down tree transducers are well established formalism for describing tree translations. Such transducers can be further enhanced with look-ahead allowing them to inspect input subtrees before processing them. Oftentimes it is advantageous to know when the look-ahead can be eliminated and the translation be implemented by a simpler transducer. We show that for a given top-down transducer with look-ahead it is decidable whether or not its translation is definable (1) by a linear deterministic top-down tree transducer or (2) by a tree homomorphism. We present algorithms that construct equivalent such transducers if they exist. Our results also apply to bottom-up transducers as well as compositions of transducers.
Originalsprache | Englisch |
---|---|
Seiten (von - bis) | 253-287 |
Seitenumfang | 35 |
Fachzeitschrift | International Journal of Foundations of Computer Science |
Jahrgang | 34 |
Ausgabenummer | 2-3 |
DOIs | |
Publikationsstatus | Veröffentlicht - 1 Feb. 2023 |