Complexity of Subtype Satisfiability over Posets - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2005

Complexity of Subtype Satisfiability over Posets

Résumé

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.
Fichier principal
Vignette du fichier
pdl05.pdf (166.31 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00536523 , version 1 (16-11-2010)

Identifiants

  • HAL Id : inria-00536523 , version 1

Citer

Joachim Niehren, Tim Priesnitz, Zhendong Su. Complexity of Subtype Satisfiability over Posets. 14th European Symposium on Programming, 2005, Edinburgh, United Kingdom. pp.357-373. ⟨inria-00536523⟩
92 Consultations
106 Téléchargements

Partager

Gmail Facebook X LinkedIn More