2014/05/22 by Sebastian Maneth
Computer Science · #cs.FL
paper · pdf · doi:10.4204/eptcs.151.5
published as EPTCS 151, 2014, pp. 74-93 · In Proceedings AFL 2014, arXiv:1405.5272
arxiv created 2014/05/22 · arxiv updated 2014/05/23
The decidability of equivalence for three important classes of tree transducers is discussed. Each class can be obtained as a natural restriction of deterministic macro tree transducers (MTTs): (1) no context parameters, i.e., top-down tree transducers, (2) linear size increase, i.e., MSO definable tree transducers, and (3) monadic input and output ranked alphabets. For the full class of MTTs, decidability of equivalence remains a long-standing open problem.