Skip to Main content Skip to Navigation
New interface
Journal articles

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
IRCAM - Institut de Recherche et Coordination Acoustique/Musique, UPMC - Université Pierre et Marie Curie - Paris 6, CNRS - Centre National de la Recherche Scientifique, Inria de Paris
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
Complete list of metadata

Cited literature [35 references]  Display  Hide  Download
Contributor : Florent Jacquemard Connect in order to contact the contributor
Submitted on : Wednesday, January 4, 2017 - 5:11:17 PM
Last modification on : Friday, July 8, 2022 - 10:07:35 AM
Long-term archiving on: : Wednesday, April 5, 2017 - 2:50:41 PM


Files produced by the author(s)



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



Record views


Files downloads