Skip to Main content Skip to Navigation
New interface
Preprints, Working Papers, ...

Rewrite Closure and CF Hedge Automata

Florent Jacquemard 1, 2 Michaël Rusinowitch 3 
1 MuTant - Synchronous Realtime Processing and Programming of Music Signals
IRCAM - Institut de Recherche et Coordination Acoustique/Musique, Inria Paris-Rocquencourt, UPMC - Université Pierre et Marie Curie - Paris 6, CNRS - Centre National de la Recherche Scientifique
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 (UMR 6174), 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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Florent Jacquemard Connect in order to contact the contributor
Submitted on : Friday, November 16, 2012 - 3:04:29 PM
Last modification on : Tuesday, March 15, 2022 - 3:21:21 AM
Long-term archiving on: : Friday, March 31, 2017 - 4:00:29 PM


Files produced by the author(s)


  • HAL Id : hal-00752496, version 2


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



Record views


Files downloads