Structured Document Transformations Based on XSL

Abstract

Based on the recursion mechanism of the XML transformation language XSL, the document transformation language is defined. First the instantiation is considered that uses regular expressions as pattern language. This instantiation closely resembles the navigation mechanism of XSL. For the complexity of relevant decision problems such as termination of programs, usefulness of rules and equivalence of selection patterns, is addressed. Next, a much more powerful ion of XSL is considered that uses monadic second-order logic formulas as pattern language ( ). If is restricted to top-down transformations ( ), then a computational model can be defined which is a natural generalization to unranked trees of top-down tree transducers with look-ahead. The look-ahead can be realized by a straightforward bottom-up pre-processing pass through the document. The size of the output of an XSL program is at most exponential in the size of the input. By restricting copying in XSL a decidable fragment of programs is obtained which induces transformations of linear size increase (safe ). It is shown that the emptiness and finiteness problems are decidable for ranges of programs and that the ranges are closed under intersection with generalized Document Type Definitions (DTDs).