文章基本信息

标题：Computing the Cost of Typechecking of Composition of Macro Tree Transducers
本地全文：下载
作者：Keisuke Nakano ; Sebastian Maneth
期刊名称：Information and Media Technologies
电子版ISSN：1881-0896
出版年度：2009
卷号：4
期号：4
页码：846-856
DOI：10.11185/imt.4.846
出版社：Information and Media Technologies Editorial Board
摘要：Macro tree transducers are a classical formal model for structural-recursive tree transformation with accumulative parameters. They have recently been applied to model XML transformations and queries. Typechecking a tree transformation means checking whether all valid input trees are transformed into valid output trees, for the given regular tree languages of input and output trees. Typechecking macro tree transducers is generally based on inverse type inference, because of the advantageous property that inverse transformations effectively preserve regular tree languages. It is known that the time complexity of typechecking an n -fold composition of macro tree transducers is non-elementary. The cost of typechecking can be reduced if transducers in the composition have special properties, such as being deterministic or total, or having no accumulative parameters. In this paper, the impact of such properties on the cost of typechecking is investigated. Reductions in cost are achieved by applying composition and decomposition constructions to tree transducers. Even though these constructions are well-known, they have not yet been analyzed with respect to the precise sizes of the transducers involved. The results can directly be applied to typechecking XML transformations, because type formalisms for XML are captured by regular tree languages.