Skip to Main content Skip to Navigation
New interface
Conference papers

Rewrite Closure and CF Hedge Automata

Florent Jacquemard 1, 2 Michael 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. The class of unranked ordered tree languages they recognize 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.
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Florent Jacquemard Connect in order to contact the contributor
Submitted on : Thursday, December 20, 2012 - 4:25:21 PM
Last modification on : Tuesday, March 15, 2022 - 3:21:21 AM
Long-term archiving on: : Thursday, March 21, 2013 - 3:49:04 AM


Files produced by the author(s)


  • HAL Id : hal-00767719, version 1
  • ARXIV : 1212.5108


Florent Jacquemard, Michael Rusinowitch. Rewrite Closure and CF Hedge Automata. 7th International Conference on Language and Automata Theory and Application, Apr 2013, Bilbao, Spain. ⟨hal-00767719⟩



Record views


Files downloads