Skip to Main content Skip to Navigation
New interface
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 metadata

Cited literature [8 references]  Display  Hide  Download
Contributor : Denis Debarbieux Connect in order to contact the contributor
Submitted on : Tuesday, November 16, 2010 - 6:34:48 PM
Last modification on : Thursday, July 25, 2019 - 8:50:03 AM
Long-term archiving on: : Thursday, February 17, 2011 - 3:08:50 AM


Files produced by the author(s)


  • HAL Id : inria-00536731, version 1



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⟩



Record views


Files downloads