One-variable context-free hedge automata

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.

Recommended citation: Florent Jacquemard, Michael Rusinowitch, "One-variable context-free hedge automata" Journal of Computer and System Sciences vol. 104, 2016.