Synthesis of deterministic top-down tree transducers from automatic tree relations
Synthesis of deterministic top-down tree transducers from automatic tree relations
复制标题
从自动树关系合成确定性自顶向下树传感器
DOI：
--
复制
发表时间：
2014
影响因子：
1
通讯作者：
Sarah Winter
中科院分区：
文献类型：
--
作者：
Christof Löding;Sarah Winter
摘要我们考虑在有限树上，从自动机可定义的规范，给出二元关系，合成确定树换能器。我们考虑树自动规范的情况，这意味着规范是可识别的自顶向下树自动机，并行同步读取两个给定的树。在这种情况下，我们研究树换能器，允许有任何延迟，保持在一个给定的边界或任意延迟。每当传感器从输入树中读取符号而不产生输出时，就会引起延迟。对于规范，是确定性的自上而下的树自动，我们提供决策程序的有界和任意延迟，产生确定性的自上而下的树换能器，实现规范的输入树的一部分，规范域，并可以任意表现在树域之外。类似于词的关系的情况下，我们使用两个玩家的游戏作为主要技术来获得我们的结果。
Abstract We consider the synthesis of deterministic tree transducers from automaton definable specifications, given as binary relations, over finite trees. We consider the case of tree-automatic specifications, meaning the specification is recognizable by a top-down tree automaton that reads the two given trees synchronously in parallel. In this setting we study tree transducers that are allowed to have either delay that remains in a given bound or arbitrary delay. Delay is caused whenever the transducer reads a symbol from the input tree without producing output. For specifications that are deterministic top-down tree-automatic, we provide decision procedures for both bounded and arbitrary delay that yield deterministic top-down tree transducers which realize the specification for input trees that are part of the specification domain, and can behave arbitrarily on trees outside the domain. Similarly to the case of relations over words, we use two-player games as the main technique to obtain our results.