2026-07-20T05:25:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6477 2024-03-06T10:38:23Z ddc:004 open_access

Uniformization Problems for Tree-Automatic Relations and Top-Down Tree Transducers Löding, Christof Winter, Sarah tree transducers tree automatic relation uniformization For a given binary relation of finite trees, we consider the synthesis problem of deciding whether there is a deterministic top-down tree transducer that uniformizes the relation, and constructing such a transducer if it exists. A uniformization of a relation is a function that is contained in the relation and has the same domain as the relation. It is known that this problem is decidable if the relation is a deterministic top-down tree-automatic relation. We show that it becomes undecidable for general tree-automatic relations (specified by non-deterministic top-down tree automata). We also exhibit two cases for which the problem remains decidable. If we restrict the transducers to be path-preserving, which is a subclass of linear transducers, then the synthesis problem is decidable for general tree-automatic relations. If we consider relations that are finite unions of deterministic top-down tree-automatic relations, then the problem is decidable for synchronous transducers, which produce exactly one output symbol in each step (but can be non-linear). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christof Löding and Sarah Winter 2016 Is Part Of LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2016.65 urn:nbn:de:0030-drops-64771 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.65 eng https://creativecommons.org/licenses/by/3.0/legalcode