Rewrite Closure and CF Hedge Automata

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

https://hal.inria.fr/hal-00752496
Contributor : Florent Jacquemard <>
Submitted on : Thursday, November 15, 2012 - 11:14:35 PM
Last modification on : Wednesday, January 8, 2020 - 2:16:59 PM
Long-term archiving on: Saturday, December 17, 2016 - 11:02:27 AM

File

CFHA.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00752496, version 1

Citation

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

Share

Metrics

Record views

21

Files downloads

11