Towards Practical Typechecking for Macro Tree Transducers

Abstract : Macro tree transducers (mtt) are an important model that both covers many useful XML transformations and allows decidable exact typechecking. This paper reports our first step toward an implementation of mtt typechecker that has a practical efficiency. Our approach is to represent an input type obtained from a backward inference as an alternating tree automaton, in a style similar to Tozawa's XSLT0 typechecking. In this approach, typechecking reduces to checking emptiness of an alternating tree automaton. We propose several optimizations (Cartesian factorization, state partitioning) on the backward inference process in order to produce much smaller alternating tree automata than the naive algorithm, and we present our efficient algorithm for checking emptiness of alternating tree automata, where we exploit the explicit representation of alternation for local optimizations. Our preliminary experiments confirm that our algorithm has a practical performance that can typecheck simple transformations with respect to the full XHTML in a reasonable time.
Type de document :
[Research Report] RR-6107, INRIA. 2007, pp.28
Liste complète des métadonnées

Littérature citée [1 références]  Voir  Masquer  Télécharger
Contributeur : Rapport de Recherche Inria <>
Soumis le : lundi 29 janvier 2007 - 16:58:59
Dernière modification le : vendredi 25 mai 2018 - 12:02:07
Document(s) archivé(s) le : mardi 21 septembre 2010 - 11:55:16


Fichiers produits par l'(les) auteur(s)




Alain Frisch, Haruo Hosoya. Towards Practical Typechecking for Macro Tree Transducers. [Research Report] RR-6107, INRIA. 2007, pp.28. 〈inria-00126895v2〉



Consultations de la notice


Téléchargements de fichiers