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.
Document type :
Journal articles
Liste complète des métadonnées

Cited literature [35 references]  Display  Hide  Download

https://hal.inria.fr/hal-01426626
Contributor : Florent Jacquemard <>
Submitted on : Wednesday, January 4, 2017 - 5:11:17 PM
Last modification on : Tuesday, December 18, 2018 - 4:38:25 PM
Document(s) archivé(s) le : Wednesday, April 5, 2017 - 2:50:41 PM

File

CFHA-long.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

588

Files downloads

49