Subtyping constraints in quasi-lattices

Abstract : In this report, we show the decidability and NP-completeness of the satisfiability problem for non-structural subtyping constraints in quasi-lattices. This problem, first introduced by Smolka in 1989, is important for the typing of logic and functional languages. The decidability result is obtained by generalizing Trifonov and Smith's algorithm over lattices, to the case of quasi-lattices. Similarly, we extend Pottier's algorithm for computing explicit solutions to the case of quasi-lattices. Finally we evoke some applications of these results to type inference in constraint logic programming and functional programming languages.
Type de document :
Rapport
[Research Report] RR-4926, INRIA. 2003
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00071653
Contributeur : Rapport de Recherche Inria <>
Soumis le : mardi 23 mai 2006 - 18:24:33
Dernière modification le : samedi 17 septembre 2016 - 01:27:20
Document(s) archivé(s) le : dimanche 4 avril 2010 - 22:31:30

Fichiers

Identifiants

  • HAL Id : inria-00071653, version 1

Collections

Citation

Emmanuel Coquery, Francois Fages. Subtyping constraints in quasi-lattices. [Research Report] RR-4926, INRIA. 2003. 〈inria-00071653〉

Partager

Métriques

Consultations de la notice

184

Téléchargements de fichiers

182