Decision problems of tree transducers with origin (Q1641005)

The contribution discusses decidability results for tree transducers with origin information. The origin information assigns to each output node the corresponding node in the input tree to which the rule creating the output node was applied. It thus provides additional information about the derivation process used to obtain the given input-output pair. The tree transducer models discussed in this contribution include the classical top-down tree-to-tree transducers, the top-down tree-to-string transducers as well as the MSO tree-to-string transducers. These devices traditionally compute relations between input and output only, but in the origin mode they relate input trees to output trees together with their origin information. For this origin semantics the considered decidability questions include equivalence, injectivity, and subclass definability. With the help of the additional origin information several classical undecidable properties become decidable. For example, equivalence and injectivity become decidable for top-down tree transducers as well as for MSO tree-to-string transducers (with origin information). However, these two problems remain undecidable for top-down tree-to-string transducers. The first subclass definability question is whether a given deterministic top-down tree-to-string transducer permits an equivalent (incl. origin) MSO tree-to-string transducer. It is demonstrated that this question is decidable. Similarly, it is decidable under origin-semantics whether a given total deterministic macro tree transducer (i.e., a top-down tree transducer with additional context-parameters) permits an equivalent top-down tree transducer. The same problem remains open for tree transducers in the classical, origin-less, semantics. The paper is well written and easily accessible. Full proof details are provided for all results and examples illustrate the main notions. Graphical illustrations help the reader with suitable visualization, and ample motivation, context, references, and related work are provided. Overall, a graduate computer science student with some background in tree transducers should be able to fully appreciate the material in this contribution.