ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique
Autres revues >>

L'Objet

1262-1137
logiciel, bases de données, réseaux
Publication abandonné
 

 ARTICLE VOL 9/RSTI1 - 2003  - pp.253-266
TITRE
Contraintes de sous-typage dans les quasi-treillis

RÉSUMÉ
Dans cet article nous montrons la décidabilité et la NP-complétude du problème de la satisfaction des contraintes de sous-typage non-structurel dans les quasi-treillis. Ce problème posé par Smolka en 1988 est important pour le typage des langages logiques et fonctionnels. Nous généralisons l'algorithme de Trifonov et Smith dans les treillis, au cas des quasi-treillis avec une complexité en temps en Ç?ÑÚ £ ÅÚ £ Ò¿ µ, où Ñ (resp. Å) est le nombre d'éléments minimaux (resp. maximaux) du quasi-treillis, Ú est le nombre de variables non bornées, et Ò est le nombre de contraintes. Nous étendons de la même manière l'algorithme de Pottier de calcul explicite de solutions au cas des quasi-treillis. Nous évoquons ensuite les applications de ces résultats, notamment au système TCLP de typage des programmes logiques avec contraintes.


ABSTRACT
In this paper, we show the decidability and NP-completeness of the satisfiability problem for non-structural subtyping constraints in quasi-lattices. This problem, introduced by Smolka in 1988, is important for typing logic and functionnal languages. We generalize Trifonov and Smith's algorithm in lattices, to the case of quasi-lattices with a time complexity in Ç?ÑÚ £ ÅÚ £ Ò¿ µ, where Ñ (resp. Å) is the number of minimal (resp. maximal) elements in the quasi-lattice, Ú is the number of unbounded variables and Ò the number of constraints. Similarly, we extend Pottier's algorithm for computing explicit solutions to the case of quasilattices. Finally, we evoke applications of these results, especially to the TCLP system for typing constraint logic programs.


AUTEUR(S)


MOTS-CLÉS
sous-typage, contraintes, quasi-treillis.

KEYWORDS
subtyping, constraints, quasi-lattices.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 34.95 €
• Non abonné : 34.95 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (239 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier