The time complexity of typechecking tree-walking tree transducers

摘要

Tree-walking tree transducers can be typechecked in double exponential time. More generally, compositions of k tree-walking tree transducers can be typechecked in (k+1 )-fold exponential time. Consequently k-pebble tree transducers, which form a model of XML transformations and XML queries, can be typechecked in (k + 2)-fold exponential time. The results hold for both ranked and unranked trees.