Rewrite Closure and CF Hedge Automata

Florent Jacquemard 1, 2 Michael 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 (UMR 6174), Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : We introduce an extension of hedge automata called bidimensional context-free hedge automata. The class of unranked ordered tree languages they recognize 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 :
Communication dans un congrès
7th International Conference on Language and Automata Theory and Application, Apr 2013, Bilbao, Spain. Springer, 2013, Lecture Notes in Computer Science
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00767719
Contributeur : Florent Jacquemard <>
Soumis le : jeudi 20 décembre 2012 - 16:25:21
Dernière modification le : vendredi 31 août 2018 - 09:14:29
Document(s) archivé(s) le : jeudi 21 mars 2013 - 03:49:04

Fichiers

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

Identifiants

  • HAL Id : hal-00767719, version 1
  • ARXIV : 1212.5108

Citation

Florent Jacquemard, Michael Rusinowitch. Rewrite Closure and CF Hedge Automata. 7th International Conference on Language and Automata Theory and Application, Apr 2013, Bilbao, Spain. Springer, 2013, Lecture Notes in Computer Science. 〈hal-00767719〉

Partager

Métriques

Consultations de la notice

422

Téléchargements de fichiers

199