Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/inria-00536731
Contributor : Denis Debarbieux <>
Submitted on : Tuesday, November 16, 2010 - 6:34:48 PM
Last modification on : Thursday, July 25, 2019 - 8:50:03 AM
Document(s) archivé(s) le : Thursday, February 17, 2011 - 3:08:50 AM

File

Path-Rewriting-in-Semistructur...
Files produced by the author(s)

Identifiers

  • 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. 4th International Conference on Combinatorics on Words, 2003, Turku, Finland. pp.358--369. ⟨inria-00536731⟩

Share

Metrics

Record views

304

Files downloads

241