Equivalence Problems for Tree Transducers: A Brief Survey

Sebastian Maneth

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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
Title of host publicationProceedings 14th International Conference on Automata and Formal Languages, AFL 2014, Szeged, Hungary, May 27-29, 2014.
PublisherCornell University Press
Pages74-93
Number of pages20
DOIs
Publication statusPublished - 2014

Fingerprint

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

Cite this