# Extraction and Implication of Path Constraints

2 MOSTRARE - Modeling Tree Structures, Machine Learning, and Information Extraction
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : We consider semistructured data as rooted edge-labeled directed graphs, and path inclusion constraints on these graphs. In this paper, we give a new decision algorithm for the implication problem of a constraint $p \preceq q$ by a set of constraints $p_i \preceq u_i$ where $p$, $q$, and the $p_i$'s are regular path expressions and the $u_i$'s are non-empty paths, improving in this particular case, the more general algorithms of S. Abiteboul and V. Vianu, and Alechina et al. Moreover, in the case of a set of word equalities $u_i \equiv v_i$, we give a more efficient decision algorithm for the implication of a word equality $u \equiv v$, improving the more general algorithm of P. Buneman et al., and we prove that, in this case, the implication problem for non-deterministic models or for (complete) deterministic models are equivalent.
Type de document :
Communication dans un congrès
29th Symposium on Mathematical Foundations of Computer Science, 2004, Prague, Costa Rica. Springer, 3153, pp.863-875, 2004, Lecture Notes in Computer Science

Littérature citée [17 références]

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

### Fichier

Extraction-And-Implication-Of-...
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : inria-00536715, version 1

### Citation

Yves André, Anne-Cécile Caron, Denis Debarbieux, Yves Roos, Sophie Tison. Extraction and Implication of Path Constraints. 29th Symposium on Mathematical Foundations of Computer Science, 2004, Prague, Costa Rica. Springer, 3153, pp.863-875, 2004, Lecture Notes in Computer Science. 〈inria-00536715〉

### Métriques

Consultations de la notice

## 215

Téléchargements de fichiers