Complexity of Subtype Satisfiability over Posets

Abstract : Subtype satisfiability is an important problem for designing advanced subtype systems and subtype-based program analysis algorithms. The problem is well understood if the atomic types form a lattice. However, little is known about subtype satisfiability over posets. In this paper, we investigate algorithms for and the complexity of subtype satisfiability over general posets. We present a uniform treatment of different flavors of subtyping: simple versus recursive types and structural versus non-structural subtype orders. Our results are established through a new connection of subtype constraints and modal logic. As a consequence, we settle a problem left open by Tiuryn and Wand in 1993.
Type de document :
Communication dans un congrès
Shmuel Sagiv. 14th European Symposium on Programming, 2005, Edinburgh, United Kingdom. Springer, 3444, pp.357-373, 2005, Lecture Notes in Computer Science
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00536523
Contributeur : Joachim Niehren <>
Soumis le : mardi 16 novembre 2010 - 13:32:29
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : jeudi 17 février 2011 - 02:58:02

Fichier

pdl05.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00536523, version 1

Collections

Citation

Joachim Niehren, Tim Priesnitz, Zhendong Su. Complexity of Subtype Satisfiability over Posets. Shmuel Sagiv. 14th European Symposium on Programming, 2005, Edinburgh, United Kingdom. Springer, 3444, pp.357-373, 2005, Lecture Notes in Computer Science. 〈inria-00536523〉

Partager

Métriques

Consultations de la notice

183

Téléchargements de fichiers

134