XML Type Checking for Macro Tree Transducers with Holes

Sebastian Maneth, Keisuke Nakano

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Macro forest transducers (mfts) extend macro tree transducers (mtts) from ranked to unranked trees. Mfts are more powerful than mtts (operating on binary tree encodings) because they support sequence concatenation of output trees as build-in operation. Surprisingly, inverse type inference for mfts, for a fixed output type, can be done within the same complexity as for mtts. Inverse type inference is used in algorithms for exact type checking of XML transformations. The macro tree transducer with holes (hmtt) is a new concept that is introduced in this paper. It generalizes sequence concatenation of mfts to arbitrary tree concatenation. Hmtts are strictly more powerful than mfts, in a similar way as mfts are more powerful than mtts. Again, it comes as a surprise that inverse type inference remains within the same complexity bound as for mfts. Hmtts are a natural and robust extension of mtts: any hmtt can be simulated by an mtt, followed by a so called “YIELD-mapping”, and, conversely, any composition of an mtt with a YIELD-mapping can be simulated by an hmtt. This characterization implies that inverse type inference for two-fold compositions of total deterministic mtts can be done in 2-exponential time (a tower of exponents of height 2), while the previously best known algorithm takes 3-exponential time.
Original languageEnglish
Title of host publicationPLAN-X 2008, Programming Language Technologies for XML, An ACM SIGPLAN Workshop colocated with POPL 2008, San Francisco, California, USA, January 9, 2008
Publication statusPublished - 2008


Dive into the research topics of 'XML Type Checking for Macro Tree Transducers with Holes'. Together they form a unique fingerprint.

Cite this