Path Rewriting in Semistructured Data

Abstract : We consider in this paper rooted labeled directed graphs as models for semistructured data. A path inclusion constraint, in such graphs, is an expression p <= q where p and q are regular expressions over the alphabet of labels. An path inclusion constraint p <= q is satisfied by a rooted labeled directed graph if the set of nodes reached, from the root, by the words of the language described by p is included in the set of nodes reached, from the root, by the words of the language described by q. We answer here to the following problem : given a set C of path inclusion constraints, given a regular expression p describing an infinite regular language, we want to compute, if it exists, a regular expression f describing a finite language, such that p <= f for every graph satisfying C.
Type de document :
Communication dans un congrès
Tero Harju and Juhani Karhumäki. 4th International Conference on Combinatorics on Words, 2003, Turku, Finland. 27, pp.358--369, 2003
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00536731
Contributeur : Denis Debarbieux <>
Soumis le : mardi 16 novembre 2010 - 18:34:48
Dernière modification le : mercredi 20 juin 2018 - 15:18:02
Document(s) archivé(s) le : jeudi 17 février 2011 - 03:08:50

Fichier

Path-Rewriting-in-Semistructur...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00536731, version 1

Collections

Citation

Denis Debarbieux, Yves Roos, Sophie Tison, Yves André, Anne-Cécile Caron. Path Rewriting in Semistructured Data. Tero Harju and Juhani Karhumäki. 4th International Conference on Combinatorics on Words, 2003, Turku, Finland. 27, pp.358--369, 2003. 〈inria-00536731〉

Partager

Métriques

Consultations de la notice

245

Téléchargements de fichiers

155