Rewrite Closure and CF Hedge Automata

Florent Jacquemard (1, 2) , Michaël Rusinowitch (3)

1 MuTant - Synchronous Realtime Processing and Programming of Music Signals
2 STMS - Sciences et Technologies de la Musique et du Son
3 CASSIS - Combination of approaches to the security of infinite states systems

We introduce an extension of hedge automata called bidimensional context-free hedge automata, proposing a new uniform representation of vertical and horizontal computation steps in unranked ordered trees. The class recognized languages is shown to be preserved by rewrite closure with inverse-monadic rules. We also extend the parameterized rewriting rules used for modeling the W3C XQuery Update Facility in previous works, by the possibility to insert a new parent node above a given node. We show that the rewrite closure of hedge automata languages with these extended rewriting systems are context-free hedge languages.

Mots clés: Tree automata; Hedge automata; Context-free tree languages; Rewrite closure; Static typechecking; Access Control Policies Verification; XML processing

Domaines: Logique en informatique [cs.LO]

Florent Jacquemard, Michaël Rusinowitch. Rewrite Closure and CF Hedge Automata. 2012. ⟨hal-00752496v2⟩