Name
Abstract | ||
|---|---|---|
Type inclusion is a fundamental operation in every type-checking compiler, but it is quite expensive for XML manipulation languages. We recently presented an inclusion checking algorithm for an expressive family of XML type languages which is polynomial, but runs in quadratic time both in the best and in the worst cases. We present here an algorithm that has a linear-time backbone, and resorts to the quadratic approach for some specific parts of the compared types. Our experiments show that the new algorithm typically runs in linear time, hence can be used as a building block for a practical type-checking compiler. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1145/1645953.1645973 | CIKM |
Keywords | Field | DocType |
inclusion checking algorithm,quadratic time,linear inclusion,type inclusion,practical type-checking compiler,xml type language,linear time,new algorithm,xml regular expression type,type-checking compiler,quadratic approach,xml manipulation language,regular expression,xml | Regular expression,Polynomial,XML,XML validation,Computer science,Quadratic equation,Compiler,Theoretical computer science,XML schema,Time complexity | Conference |
Citations | PageRank | References |
8 | 0.51 | 7 |
Authors | ||
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 |