  We show that equivalence of deterministic linear tree transducers can be
decided in polynomial time when their outputs are interpreted over the free
group. Due to the cancellation properties offered by the free group, the
required constructions are not only more general, but also simpler than the
corresponding constructions for proving equivalence of deterministic linear
tree-to-word transducers.
