Rewrite Closure and CF Hedge AutomataReport as inadecuate

Rewrite Closure and CF Hedge Automata - Download this document for free, or read online. Document in PDF available to download.

1 MuTant - Synchronous Realtime Processing and Programming of Music Signals Inria Paris-Rocquencourt, UPMC - Université Pierre et Marie Curie - Paris 6, IRCAM, CNRS - Centre National de la Recherche Scientifique 2 STMS - Sciences et Technologies de la Musique et du Son 3 CASSIS - Combination of approaches to the security of infinite states systems FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies, Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods

Abstract : 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.

Keywords : Tree automata Hedge automata Context-free tree languages Rewrite closure Static typechecking Access Control Policies Verification XML processing

Author: Florent Jacquemard - Michaël Rusinowitch -



Related documents