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.
| Original language | English |
|---|---|
| Pages (from-to) | 253-287 |
| Number of pages | 35 |
| Journal | International Journal of Foundations of Computer Science |
| Volume | 34 |
| Issue number | 2-3 |
| DOIs | |
| State | Published - 1 Feb 2023 |
Keywords
- Transducer
- homomorphism
- linearity