Skip to Main content Skip to Navigation

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
2 STMS - Sciences et Technologies de la Musique et du Son
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.
Keywords : XML processing Tree automata Hedge automata Context-free tree languages Rewrite closure Static typechecking Access Control Policies Verification
Document type :
Conference papers
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 : Wednesday, January 8, 2020 - 2:17:26 PM
Document(s) archivé(s) le : Thursday, March 21, 2013 - 3:49:04 AM

Files

Vignette du document
CFHA.pdf
Files produced by the author(s)

Identifiers

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

Collections

CNRS | INRIA | UNIV-FCOMTE | IRCAM | STMS | UPMC | UNIV-LORRAINE | UNIV-BM | FEMTO-ST | UNIV-BM-THESE | LORIA-FM | LORIA | SORBONNE-UNIVERSITE | SU-SCIENCES

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

528

Files downloads

363

 

Contact                    Legal Notice                    Personal Data