Rewrite Closure and CF Hedge Automata

Florent Jacquemard 1, 2 Michaël Rusinowitch 3
1 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, Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : We introduce an extension of hedge automata called bidimensional context-free hedge automata, proposing a new uniform representation of vertical and horizontal computation steps in unranked ordered trees. The class recognized languages is shown to be preserved by rewrite closure with inverse-monadic rules. We also extend the parameterized rewriting rules used for modeling the W3C XQuery Update Facility in previous works, by the possibility to insert a new parent node above a given node. We show that the rewrite closure of hedge automata languages with these extended rewriting systems are context-free hedge languages.
Type de document :
Pré-publication, Document de travail
2012
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00752496
Contributeur : Florent Jacquemard <>
Soumis le : vendredi 16 novembre 2012 - 15:04:29
Dernière modification le : vendredi 25 mai 2018 - 12:02:06
Document(s) archivé(s) le : vendredi 31 mars 2017 - 16:00:29

Fichier

CFHA.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00752496, version 2

Citation

Florent Jacquemard, Michaël Rusinowitch. Rewrite Closure and CF Hedge Automata. 2012. 〈hal-00752496v2〉

Partager

Métriques

Consultations de la notice

403

Téléchargements de fichiers

298