Determinacy and rewriting of functional top–down and MSO tree transformations

作者：

Highlights：

• Decidability of view–query determinacy is proven for large classes of views and queries given by tree transducers.

• If the query is determined by the view, then we can construct a function that realizes the query on the output of the view.

• View–query determinacy is a strong static property.

摘要

•Decidability of view–query determinacy is proven for large classes of views and queries given by tree transducers.•If the query is determined by the view, then we can construct a function that realizes the query on the output of the view.•View–query determinacy is a strong static property.

论文关键词：View–query determinacy,Top–down tree transducers,MSO definable tree transducers

论文评审过程：Received 18 July 2014, Revised 21 September 2016, Accepted 4 November 2016, Available online 22 November 2016, Version of Record 19 December 2016.

论文官网地址：https://doi.org/10.1016/j.jcss.2016.11.001