Linear inclusion for XML regular expression types
| Autor: | Giorgio Ghelli, Luca Pardini, Carlo Sartiani, Dario Colazzo |
|---|---|
| Přispěvatelé: | Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Dipartimento di Informatica [Pisa], University of Pisa - Università di Pisa, Dipartimento di Matematica e Informatica (DMI), Università degli Studi della Basilicata, ANR-08-EMER-0004,CODEX,Performance, évolution et composition pour XML: modèles, algorithmes et systèmes(2008), Colazzo, Dario, domaines émergent - Performance, évolution et composition pour XML: modèles, algorithmes et systèmes - - CODEX2008 - ANR-08-EMER-0004 - DEFIS - VALID |
| Jazyk: | angličtina |
| Rok vydání: | 2009 |
| Předmět: |
Polynomial
Theoretical computer science Computer science computer.internet_protocol XML validation Type inclusion 02 engineering and technology XML computer.software_genre [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL] [INFO.INFO-CL] Computer Science [cs]/Computation and Language [cs.CL] 020204 information systems 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Regular expression XML schema Compiler Time complexity computer ComputingMilieux_MISCELLANEOUS computer.programming_language |
| Zdroj: | ACM Conference on Information and Knowledge Management (CIKM) ACM Conference on Information and Knowledge Management (CIKM), Nov 2009, Hong Kong, China. pp.137-146 CIKM CIKM 2009, pp. 137–146, Hong Kong, 2009 info:cnr-pdr/source/autori:Colazzo D.; Ghelli G.; Pardini L.; Sartiani C./congresso_nome:CIKM 2009/congresso_luogo:Hong Kong/congresso_data:2009/anno:2009/pagina_da:137/pagina_a:146/intervallo_pagine:137–146 |
| Popis: | 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. Copyright 2009 ACM. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|