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
UPMC - Université Pierre et Marie Curie - Paris 6, IRCAM, 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 metadatas

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 : Friday, May 24, 2019 - 5:28:29 PM
Long-term archiving on : 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

620

Files downloads

104