Almost-linear inclusion for XML regular expression types
Open Access
- 1 August 2013
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 38 (3) , 1-45
Abstract
Type inclusion is a fundamental operation in every type-checking compiler, but it is quite expensive for XML manipulation languages. A polynomial inclusion checking algorithm for an expressive family of XML type languages is known, but it 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 is much faster than the quadratic one, and that it typically runs in linear time, hence it can be used as a building block for a practical type-checking compiler.Keywords
Funding Information
- Agence Nationale de la Recherche (ANR-08-DEFIS-004)
This publication has 14 references indexed in Scilit:
- Efficient asymmetric inclusion of regular expressions with interleaving and counting for XML type-checkingTheoretical Computer Science, 2013
- The Inclusion Problem for Regular ExpressionsLecture Notes in Computer Science, 2010
- Efficient inclusion for a class of XML types with interleaving and countingInformation Systems, 2009
- Efficient inclusion checking for deterministic tree automata and XML SchemasInformation and Computation, 2009
- Regular Expressions with Counting: Weak versus Strong Determinism2009
- One-unambiguity of regular expressions with numeric occurrence indicatorsInformation and Computation, 2007
- Efficient Inclusion for a Class of XML Types with Interleaving and Counting2006
- Optimizing Schema Languages for XML: Numerical Constraints and InterleavingLecture Notes in Computer Science, 2006
- DTDs versus XML schema2004
- The Complexity of Word Problems - This Time with InterleavingInformation and Computation, 1994