Rewrite Closure and CF Hedge Automata

Florent Jacquemard 1, 2 Michaël Rusinowitch 3
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
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 metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-00752496
Contributor : Florent Jacquemard <>
Submitted on : Friday, November 16, 2012 - 3:04:29 PM
Last modification on : Thursday, March 21, 2019 - 1:10:14 PM
Long-term archiving on : Friday, March 31, 2017 - 4:00:29 PM

File

CFHA.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00752496, version 2

Citation

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

Share

Metrics

Record views

476

Files downloads

598