Name
Title | ||
|---|---|---|
Efficient asymmetric inclusion of regular expressions with interleaving and counting for XML type-checking. |
Abstract | ||
|---|---|---|
The inclusion of Regular Expressions (REs) is the kernel of any type-checking algorithm for XML manipulation languages. XML applications would benefit from the extension of REs with interleaving and counting, but this is not feasible in general, since inclusion is EXPSPACE-complete for such extended REs. In Colazzo et al. (2009) [1] we introduced a notion of “conflict-free REs”, which are extended REs with excellent complexity behaviour, including a polynomial inclusion algorithm [1] and linear membership (Ghelli et al., 2008 [2]). Conflict-free REs have interleaving and counting, but the complexity is tamed by the “conflict-free” limitations, which have been found to be satisfied by the vast majority of the content models published on the Web. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.tcs.2013.04.023 | Theoretical Computer Science |
Keywords | DocType | Volume |
XML,Regular expressions,Subtyping,XML schema | Journal | 492 |
ISSN | Citations | PageRank |
0304-3975 | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dario Colazzo | 1 | 283 | 34.21 |
| Giorgio Ghelli | 2 | 1300 | 255.19 |
| Luca Pardini | 3 | 12 | 1.25 |
| Carlo Sartiani | 4 | 240 | 28.54 |