Entailment of Non-Structural Subtype Constraints

Abstract : Entailment of subtype constraints was introduced for constraint simplification in subtype inference systems. Designing an efficient algorithm for subtype entailment turned out to be surprisingly difficult. The situation was clarified by Rehof and Henglein who proved entailment of structural subtype constraints to be coNP-complete for simple types and PSPACE-complete for recursive types. For entailment of non-structural subtype constraints of both simple and recursive types they proved PSPACE-hardness and conjectured PSPACE-completeness but failed in finding a complete algorithm. In this paper, we investigate the source of complications and isolate a natural subproblem of non-structural subtype entailment that we prove PSPACE-complete. We conjecture (but this is left open) that the presented approach can be extended to the general case.
Type de document :
Communication dans un congrès
P. S. Thiagarajan and Roland H. C. Yap. Asian Computing Science Conference, 1999, Phuket, Thailand. Springer, 1742, pp.251--265, 1999, Lecture Notes on Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00536825
Contributeur : Joachim Niehren <>
Soumis le : mardi 16 novembre 2010 - 23:12:16
Dernière modification le : mardi 31 octobre 2017 - 14:22:18
Document(s) archivé(s) le : jeudi 17 février 2011 - 03:17:35

Fichiers

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

Identifiants

  • HAL Id : inria-00536825, version 1

Citation

Joachim Niehren, Tim Priesnitz. Entailment of Non-Structural Subtype Constraints. P. S. Thiagarajan and Roland H. C. Yap. Asian Computing Science Conference, 1999, Phuket, Thailand. Springer, 1742, pp.251--265, 1999, Lecture Notes on Computer Science. 〈inria-00536825〉

Partager

Métriques

Consultations de la notice

74

Téléchargements de fichiers

128