On the tree-transformation power of XSLT
Identifieur interne : 003B09 ( Istex/Curation ); précédent : 003B08; suivant : 003B10On the tree-transformation power of XSLT
Auteurs : Wim Janssen [Belgique] ; Alexandr Korlyukov [Biélorussie] ; Jan Van Den Bussche [Belgique]Source :
- Acta Informatica [ 0001-5903 ] ; 2007-01-01.
Abstract
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.
Url:
DOI: 10.1007/s00236-006-0026-8
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :003B53
Links to Exploration step
ISTEX:F885A4530E9755182AA734C506BFA6D2A2881CABLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">On the tree-transformation power of XSLT</title><author><name sortKey="Janssen, Wim" sort="Janssen, Wim" uniqKey="Janssen W" first="Wim" last="Janssen">Wim Janssen</name><affiliation wicri:level="1"><mods:affiliation>Hasselt University & transnational University of Limburg, 3590, Diepenbeek, Belgium</mods:affiliation><country xml:lang="fr">Belgique</country><wicri:regionArea>Hasselt University & transnational University of Limburg, 3590, Diepenbeek</wicri:regionArea></affiliation></author><author><name sortKey="Korlyukov, Alexandr" sort="Korlyukov, Alexandr" uniqKey="Korlyukov A" first="Alexandr" last="Korlyukov">Alexandr Korlyukov</name><affiliation wicri:level="1"><mods:affiliation>Grodno State University, Grodno, Belarus</mods:affiliation><country xml:lang="fr">Biélorussie</country><wicri:regionArea>Grodno State University, Grodno</wicri:regionArea></affiliation></author><author><name sortKey="Van Den Bussche, Jan" sort="Van Den Bussche, Jan" uniqKey="Van Den Bussche J" first="Jan" last="Van Den Bussche">Jan Van Den Bussche</name><affiliation wicri:level="1"><mods:affiliation>Hasselt University & transnational University of Limburg, 3590, Diepenbeek, Belgium</mods:affiliation><country xml:lang="fr">Belgique</country><wicri:regionArea>Hasselt University & transnational University of Limburg, 3590, Diepenbeek</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: jan.vandenbussche@uhasselt.be</mods:affiliation><country wicri:rule="url">Belgique</country></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:F885A4530E9755182AA734C506BFA6D2A2881CAB</idno><date when="2006" year="2006">2006</date><idno type="doi">10.1007/s00236-006-0026-8</idno><idno type="url">https://api.istex.fr/ark:/67375/VQC-8NJK6NS8-X/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">003B53</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">003B53</idno><idno type="wicri:Area/Istex/Curation">003B09</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">On the tree-transformation power of XSLT</title><author><name sortKey="Janssen, Wim" sort="Janssen, Wim" uniqKey="Janssen W" first="Wim" last="Janssen">Wim Janssen</name><affiliation wicri:level="1"><mods:affiliation>Hasselt University & transnational University of Limburg, 3590, Diepenbeek, Belgium</mods:affiliation><country xml:lang="fr">Belgique</country><wicri:regionArea>Hasselt University & transnational University of Limburg, 3590, Diepenbeek</wicri:regionArea></affiliation></author><author><name sortKey="Korlyukov, Alexandr" sort="Korlyukov, Alexandr" uniqKey="Korlyukov A" first="Alexandr" last="Korlyukov">Alexandr Korlyukov</name><affiliation wicri:level="1"><mods:affiliation>Grodno State University, Grodno, Belarus</mods:affiliation><country xml:lang="fr">Biélorussie</country><wicri:regionArea>Grodno State University, Grodno</wicri:regionArea></affiliation></author><author><name sortKey="Van Den Bussche, Jan" sort="Van Den Bussche, Jan" uniqKey="Van Den Bussche J" first="Jan" last="Van Den Bussche">Jan Van Den Bussche</name><affiliation wicri:level="1"><mods:affiliation>Hasselt University & transnational University of Limburg, 3590, Diepenbeek, Belgium</mods:affiliation><country xml:lang="fr">Belgique</country><wicri:regionArea>Hasselt University & transnational University of Limburg, 3590, Diepenbeek</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: jan.vandenbussche@uhasselt.be</mods:affiliation><country wicri:rule="url">Belgique</country></affiliation></author></analytic><monogr></monogr><series><title level="j">Acta Informatica</title><title level="j" type="abbrev">Acta Informatica</title><idno type="ISSN">0001-5903</idno><idno type="eISSN">1432-0525</idno><imprint><publisher>Springer-Verlag</publisher><pubPlace>Berlin/Heidelberg</pubPlace><date type="published" when="2007-01-01">2007-01-01</date><biblScope unit="volume">43</biblScope><biblScope unit="issue">6</biblScope><biblScope unit="page" from="371">371</biblScope><biblScope unit="page" to="393">393</biblScope></imprint><idno type="ISSN">0001-5903</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0001-5903</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">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.</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Istex/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003B09 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 003B09 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Istex
|étape= Curation
|type= RBID
|clé= ISTEX:F885A4530E9755182AA734C506BFA6D2A2881CAB
|texte= On the tree-transformation power of XSLT
}}
| This area was generated with Dilib version V0.6.33. |  |