Linking theorems for tree transducers

作者：

Highlights：

• Promote links of synchronous grammars to items of study.

• Investigate their properties for various tree transducers.

• Establish new proof method for expressive power of compositions of tree transducers.

• Apply the new technique to new and classic results.

摘要

•Promote links of synchronous grammars to items of study.•Investigate their properties for various tree transducers.•Establish new proof method for expressive power of compositions of tree transducers.•Apply the new technique to new and classic results.

论文关键词：Synchronous grammar,Tree transducer,Linking theorem,Compositions,Expressive power

论文评审过程：Received 17 May 2014, Revised 16 March 2015, Accepted 4 May 2016, Available online 2 June 2016, Version of Record 21 June 2016.

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