Deciding Equivalence of Linear Tree-to-Word Transducers in Polynomial Time

Adrien Boiret, Raphaela Palenta

We show that the equivalence of deterministic linear top-down tree-to-word transducers is decidable in polynomial time. Linear tree-to-word transducers are non-copying but not nece…