Français Anglais
Accueil Annuaire Plan du site
Home > Research results > Research highlights
Research results
Research highlight : ALMOST-LINEAR INCLUSION FOR XML REGULAR EXPRESSION TYPES
ALMOST-LINEAR INCLUSION FOR XML REGULAR EXPRESSION TYPES
26 March 2013

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.



Keyword
  ° Type Theory
  ° XML
  ° Static Analysis

Group
  ° Databases

Contact
  [none]
Research highlights
COMPUTER‐AIDED BIOCHEMICAL PROGRAMMING OF SYNTHETIC MICROREACTORS AS DIAGNOSTIC DEVICES
27 April 2018
Alexis Courbet, Patrick Amar, Francois Fages, Eric Renard, Franck Molina Mol Syst Biol. (2018) 14:

SELF-STABILIZING DISTRIBUTED STABLE MARRIAGE
5 November 2017


A MODEL OF PULSATION FOR EVOLUTIVE FORMALIZING INCOMPLETE INTELLIGENT SYSTEMS
27 July 2017


INFORMATION-GEOMETRIC OPTIMIZATION ALGORITHMS: A UNIFYING PICTURE VIA INVARIANCE PRINCIPLES
2 May 2017
Yann Ollivier, Ludovic Arnold, Anne Auger, Nikolaus Hansen - JMLR 18(18):1−65, 2017.

FORMAL MUTATION TESTING FOR CIRCUS
21 April 2016
Alex Donizeti Betez Alberto, Ana Cavalcanti, Marie-Claude Gaudel, Adenilso Simao Journal of Infor