On the tree-transformation power of XSLT

DOI10.1007/S00236-006-0026-8MaRDI QIDQ855270zbMATH OpenOpenAlexWikidataFDO

Authors Wim Janssen, Alexandr Korlyukov, Jan Van den Bussche

Publication date 5 January 2007

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0603028

zbMATH Keywords

XML datarule-based programming language

Mathematics Subject Classification ID

Theory of programming languages (68N15) Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.) (68N19)

Abstract: XSLT is a standard rule-based programming language for expressing transformations of XML data. The language is currently in transition from version 1.0 to 2.0. In order to understand the computational consequences of this transition, we restrict XSLT to its pure tree-transformation capabilities. Under this focus, we observe that XSLT~1.0 was not yet a computationally complete tree-transformation language: every 1.0 program can be implemented in exponential time. A crucial new feature of version~2.0, however, which allows nodesets over temporary trees, yields completeness. We provide a formal operational semantics for XSLT programs, and establish confluence for this semantics.

Recommendations

• XSLT Version 2.0 Is Turing-Complete: A Purely Transformation Based Proof
• A formal model for an expressive fragment of XSLT
• scientific article; zbMATH DE number 2080402
• Equivalences and optimizations in an expressive XSLT subset
• scientific article; zbMATH DE number 1696859

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1942450 (Why is no real title available?)
• scientific article; zbMATH DE number 1954390 (Why is no real title available?)
• A formal model for an expressive fragment of XSLT
• Equivalences and optimizations in an expressive XSLT subset
• Linear unification
• Macro forest transducers
• Macro tree transducers
• Tree-Manipulating Systems and Church-Rosser Theorems
• Typechecking for XML transformers

Cited in

(11)

• Translating XQuery into XSLT
• The TXL source transformation language
• Highly expressive query languages for unordered data trees
• scientific article; zbMATH DE number 2080402 (Why is no real title available?)
• A formal model for an expressive fragment of XSLT
• Transformation of XML data using updates without side effects
• scientific article; zbMATH DE number 1954115 (Why is no real title available?)
• Equivalences and optimizations in an expressive XSLT subset
• scientific article; zbMATH DE number 1982648 (Why is no real title available?)
• XSLT Version 2.0 Is Turing-Complete: A Purely Transformation Based Proof
• XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles

Describes a project that uses

Uses Software

• SAXON
• XPath
• XDuce
• XQuery

This page was built for publication: On the tree-transformation power of XSLT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q855270)