On the tree-transformation power of XSLT | Acta Informatica Skip to main content
Springer Nature Link
Log in

On the tree-transformation power of XSLT

  • Original article
  • Published:
Acta Informatica Aims and scope Submit manuscript

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, using a DAG representation of trees. A crucial new feature of version 2.0, however, which allows node sets over temporary trees, yields completeness. We provide a formal operational semantics for XSLT programs, and establish confluence for this semantics.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. XML path language (XPath) version 1.0. W3C Recommendation, November (1999)

  2. XSL transformations (XSLT) version 1.0. W3C Recommendation, November (1999)

  3. XSLT requirements version 2.0. W3C Working Draft, February (2001)

  4. XML schema. W3C Recommendation, October (2004)

  5. XML path language (XPath) version 2.0. W3C Working Draft, April (2005)

  6. XQuery 1.0 and XPath 2.0 data model. W3C Working Draft, April (2005)

  7. XQuery 1.0 and XPath 2.0 formal semantics. W3C Working Draft, June (2005)

  8. XSL transformations (XSLT) version 2.0. W3C Working Draft, April (2005)

  9. Bex, G.J., Maneth, S., Neven, F.: A formal model for an expressive fragment of XSLT. Informat. Syst. 27(1), 21–39 (2002)

    Google Scholar 

  10. Buneman, P., Grohe, M., Koch, C.: Path queries on compressed XML. In: Freytag, J.C., Lockemann, P.C., et al. (eds.) Proceedings 29th International Conference on Very Large Data Bases, pp. 141–152, Morgan Kaufmann (2003)

  11. Dong, C., Bailey, J.: Static analysis of XSLT programs. In: Schewe, K.D., Williams, H.E., (eds.) Database Technologies—Proceedings ADC 2004, pp. 151–160 Australian Computer Society (2004)

  12. Engelfriet J., Vogler H. (1985): Macro tree transducers. J. Comput. Syst. Sci. 31(1): 71–146

    Article  MATH  MathSciNet  Google Scholar 

  13. Gottlob G., Koch C., Pichler R. (2003): XPath processing in a nutshell. SIGMOD Rec. 32(2): 21–27

    Article  Google Scholar 

  14. Hidders, J., Paredaens, J., Vercammen, R., et al.: A light but formal introduction to XQuery. In: Bellahsène, Z., Milo, T., Rys, M., et al. (eds.) Database and XML Technologies—Proceedings XSym. Lecture Notes in Computer Science, vol. 3186, pp. 5–20. Springer, Berlin Heidelberg New York (2004)

  15. Hopcroft J.E., Ullman J.E. (1979): Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA

    MATH  Google Scholar 

  16. Hosoya H., Pierce B.C. (2003): XDuce: A statically typed XML processing language. ACM Trans. Internet Technol. 3(2): 117–148

    Article  Google Scholar 

  17. Kay, M.: SAXON: The XSLT and XQuery processor. http://saxon.sourceforge.net

  18. Kay, M.: XSLT 2.0 Programmer’s Reference. Wrox, 3rd ed (2004)

  19. Kepser, S.: A simple proof for the turing-completeness of XSLT and XQuery. Presented at Extreme Markup Languages 2004. http://www.mulberrytech.com/Extreme/Proceedings/

  20. Kirchner, C., Qian, Z., Singh, P.K., Stuber, J.: Xemantics: a rewriting calculus-based semantics of XSLT@. LORIA Technical Report A01-R-386, Laboratoire Lorrain de Recherche en Informatique et ses Applications, Nancy (2001)

  21. Korlyukov, A.: Turing machine for XSLT. http://www.refal.net/~korlukov/tm/index.htm

  22. Lyons, B.: Universal turing machines in XSLT. http://www.unidex.com/turing/utm.htm

  23. Maneth, S.: The complexity of compositions of deterministic tree transducers. In: Agrawal, M., Seth, A., (eds.) FST TCS 2002 Proceedings, Lecture Notes in Computer Science, vol. 2556, pp. 265–276. Springer, Berlin Heidelberg New York (2002)

  24. Maneth, S., Berlea, A., Perst, T., Seidl, H.: XML type checking with macro tree transducers. In: Proceedings 24th ACM Symposium on Principles of Database Systems, pp. 283–294. ACM Press (2005)

  25. Milo T., Suciu D., Vianu V. (2003): Typechecking for XML transformers. J. Comput. Syst. Sci. 66(1): 66–97

    Article  MATH  MathSciNet  Google Scholar 

  26. Novatchev, D.: FXSL: The functional programming library for XSLT. http://fxsl.sourceforge.net

  27. Papadimitriou C.H. (1994): Computational Complexity. Addison-Wesley, Reading MA

    MATH  Google Scholar 

  28. Paterson M.S., Wegman M.N. (1978): Linear unification. J. Comput. Syst. Sci. 16(2): 158–167

    Article  MATH  MathSciNet  Google Scholar 

  29. Perst T., Seidl H. (2004): Macro forest transducers. Informat. Process. Lett. 89(3): 141–149

    Article  MathSciNet  Google Scholar 

  30. Rosen B.K. (1973): Tree-manipulating systems and Church-Rosser theorems. J. ACM 20(1): 160–187

    Article  MATH  Google Scholar 

  31. Siméon, J., Wadler, P.: The essence of XML. In: Proceedings 30th ACM Symposium on Principles of Programming Languages, p. 1–13. ACM Press (2003)

  32. Terese. (2003): Term Rewriting Systems. Cambridge University Press, Cambridge

  33. Trombetta A., Montesi D. (2006): Equivalences and optimizations in an expressive XSLT subset. Acta Informat. 42(6): 515–539

    Article  MATH  MathSciNet  Google Scholar 

  34. Wadler P. (2000): A formal semantics of patterns in XSLT and XPath. Markup Langu. Theor. Pract. 2(2): 183–202

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Hasselt University & transnational University of Limburg, 3590, Diepenbeek, Belgium

    Wim Janssen & Jan Van den Bussche

  2. Grodno State University, Grodno, Belarus

    Alexandr Korlyukov

Authors
  1. Wim Janssen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alexandr Korlyukov
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jan Van den Bussche
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jan Van den Bussche.

Additional information

Wim Janssen is a research assistant of the Fund for Scientific Research, Flanders. Alexandr Korlyukov sadly passed away shortly after we agreed to write a joint paper.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Janssen, W., Korlyukov, A. & Van den Bussche, J. On the tree-transformation power of XSLT. Acta Informatica 43, 371–393 (2007). https://doi.org/10.1007/s00236-006-0026-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00236-006-0026-8

Keywords

Search

Navigation