Unranked Tree Rewriting and Effective Closures of Languages

Florent Jacquemard 1, 2 Michaël Rusinowitch 3
1 Repmus - Représentations musicales
STMS - Sciences et Technologies de la Musique et du Son
2 MuTant - Synchronous Realtime Processing and Programming of Music Signals
Inria Paris-Rocquencourt, UPMC - Université Pierre et Marie Curie - Paris 6, IRCAM, CNRS - Centre National de la Recherche Scientifique
3 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174), Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : We consider rewriting systems for unranked ordered trees, where the number of chil- dren of a node is not determined by its label, and is not a priori bounded. The rewriting systems are defined such that variables in the rewrite rules can be substituted by hedges (sequences of trees) instead of just trees. Consequently, this notion of rewriting subsumes both standard term rewriting and word rewriting. We present some properties of preservation for classes of unranked tree languages, including hedge automata languages and various context-free extensions. Finally, ap- plications to static type checking for XML transformations and to the verification of read/write access control policies for XML updates are mentioned.
Type de document :
Communication dans un congrès
Meeting of the IFIP WG 1.6 on Term Rewriting, Jun 2013, Eindhoven, Netherlands. 2013
Liste complète des métadonnées

Contributeur : Florent Jacquemard <>
Soumis le : mardi 20 août 2013 - 18:14:52
Dernière modification le : vendredi 31 août 2018 - 09:18:08
Document(s) archivé(s) le : mercredi 5 avril 2017 - 22:47:10



  • HAL Id : hal-00852379, version 1


Florent Jacquemard, Michaël Rusinowitch. Unranked Tree Rewriting and Effective Closures of Languages. Meeting of the IFIP WG 1.6 on Term Rewriting, Jun 2013, Eindhoven, Netherlands. 2013. 〈hal-00852379〉



Consultations de la notice


Téléchargements de fichiers