Rewrite Closure and CF Hedge Automata

Florent Jacquemard 1, 2 Michael 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. 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 metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-00767719
Contributor : Florent Jacquemard <>
Submitted on : Thursday, December 20, 2012 - 4:25:21 PM
Last modification on : Saturday, March 30, 2019 - 1:26:31 AM
Long-term archiving on : Thursday, March 21, 2013 - 3:49:04 AM

Files

CFHA.pdf
Files produced by the author(s)

Identifiers

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

Citation

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⟩

Share

Metrics

Record views

486

Files downloads

262