Determinacy and Rewriting of Top-Down and MSO Tree Transformations
Determinacy and Rewriting of Top-Down and MSO Tree Transformations
复制标题
自顶向下和 MSO 树变换的确定性和重写
DOI：
10.1007/978-3-642-40313-2_15
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
S. Maneth
中科院分区：
文献类型：
--
作者：
Michael Benedikt;J. Engelfriet;S. Maneth
如果查询的结果可以从视图的结果重建，则查询由视图确定。我们考虑决定两个给定树变换的问题，其中一个变换是否由另一个变换决定。如果视图变换是由可以复制的树转换器引起的，那么确定性是不可判定的，即使对于身份查询也是如此。对于一大类非复制视图，即具有常规前瞻的功能扩展线性自上而下树传感器的组合，我们表明确定性是可判定的，其中查询由具有常规前瞻的确定性自上而下树传感器或 MSO 树传感器给出。我们还表明，如果确定了查询，则可以将其重写为直接在视图上工作的查询，并且与给定查询属于同一类。该证明依赖于所考虑的两个查询类的等价性的可判定性，以及它们在组合下的闭包。
A query is determined by a view, if the result to the query can be reconstructed from the result of the view. We consider the problem of deciding for two given tree transformations, whether one is determined by the other. If the view transformation is induced by a tree transducer that may copy, then determinacy is undecidable, even for identity queries. For a large class of non-copying views, namely compositions of functional extended linear top-down tree transducers with regular look-ahead, we show that determinacy is decidable, where queries are given by deterministic top-down tree transducers with regular look-ahead or by MSO tree transducers. We also show that if a query is determined, then it can be rewritten into a query that works directly over the view and is in the same class as the given query. The proof relies on the decidability of equivalence for the two considered classes of queries, and on their closure under composition.