One-variable context-free hedge automata

Florent Jacquemard 1, 2 Michael 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 de Paris, UPMC - Université Pierre et Marie Curie - Paris 6, IRCAM, CNRS - Centre National de la Recherche Scientifique
3 PESTO - Proof techniques for security protocols
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : We introduce an extension of hedge automata called One-Variable Context-Free Hedge Automata. The class of unranked ordered tree languages they recognize has polynomial membership problem and is preserved by rewrite closure with inverse-monadic rules. We also propose a modeling of primitives of the W3C XQuery Update Facility by mean of parameterized rewriting rules, and show that the rewrite closure of a context-free hedge language with these extended rewriting systems is a context-free hedge language. This result is applied to static analysis of XML access control policies expressed with update primitives.
Type de document :
Article dans une revue
Journal of Computer and System Sciences, Elsevier, 2016, 〈10.1016/j.jcss.2016.10.006〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01426626
Contributeur : Florent Jacquemard <>
Soumis le : mercredi 4 janvier 2017 - 17:11:17
Dernière modification le : mercredi 21 mars 2018 - 18:58:22
Document(s) archivé(s) le : mercredi 5 avril 2017 - 14:50:41

Fichier

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

Identifiants

Collections

Citation

Florent Jacquemard, Michael Rusinowitch. One-variable context-free hedge automata. Journal of Computer and System Sciences, Elsevier, 2016, 〈10.1016/j.jcss.2016.10.006〉. 〈hal-01426626〉

Partager

Métriques

Consultations de la notice

514

Téléchargements de fichiers

26