A Survey on Decidable Equivalence Problems for Tree Transducers

Sebastian Maneth

Research output: Contribution to journalArticlepeer-review


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.
Original languageEnglish
Pages (from-to)1069-1100
Number of pages32
JournalInternational Journal of Foundations of Computer Science
Issue number08
Publication statusPublished - Dec 2015

Fingerprint Dive into the research topics of 'A Survey on Decidable Equivalence Problems for Tree Transducers'. Together they form a unique fingerprint.

Cite this