Closure of Hedge-Automata Languages by Hedge Rewriting

Florent Jacquemard 1 Michael Rusinowitch 2
1 SECSI - Security of information systems
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
2 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies, INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We consider rewriting systems for unranked ordered terms, i.e. trees where the number of successors of a node is not determined by its label, and is not a priori bounded. The rewriting systems are defined such that variables in the rewrite rules can be substituted by hedges (sequences of terms) instead of just terms. Consequently, this notion of rewriting subsumes both standard term rewriting and word rewriting. We investigate some preservation properties for two classes of languages of unranked ordered terms under this generalization of term rewriting. The considered classes include languages of hedge automata (HA) and some extension (called CF-HA) with context-free languages in transitions, instead of regular languages. In particular, we show that the set of unranked terms reachable from a given HA language, using a so called inverse context-free rewrite system, is a HA language. The proof, based on a HA completion procedure, reuses and combines known techniques with non-trivial adaptations. Moreover, we prove, with different techniques, that the closure of CF-HA languages with respect to restricted context-free rewrite systems, the symmetric case of the above rewrite systems, is a CF-HA language. As a consequence, the problems of ground reachability and regular hedge model checking are decidable in both cases. We give several counter examples showing that we cannot relax the restrictions.
Type de document :
Communication dans un congrès
A. Voronkov. 19th International Conference on Rewriting Techniques and Applications - RTA 2008, 2008, Hagenberg, Austria. Springer Berlin / Heidelberg, 5117, pp.157-171, 2008, Lecture Notes in Computer Science. 〈10.1007/978-3-540-70590-1_11〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00329803
Contributeur : Michaël Rusinowitch <>
Soumis le : lundi 13 octobre 2008 - 14:35:31
Dernière modification le : jeudi 11 janvier 2018 - 06:20:00
Document(s) archivé(s) le : mardi 9 octobre 2012 - 12:02:28

Fichier

rta30.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Florent Jacquemard, Michael Rusinowitch. Closure of Hedge-Automata Languages by Hedge Rewriting. A. Voronkov. 19th International Conference on Rewriting Techniques and Applications - RTA 2008, 2008, Hagenberg, Austria. Springer Berlin / Heidelberg, 5117, pp.157-171, 2008, Lecture Notes in Computer Science. 〈10.1007/978-3-540-70590-1_11〉. 〈inria-00329803〉

Partager

Métriques

Consultations de la notice

344

Téléchargements de fichiers

114