Publication details

Saarland University Computer Science

The Complexity of Subtype Satisfiability over Posets

Joachim Niehren, Tim Priesnitz, Zhendong Su

14th European Symposium on Programming, Vol. 3444 of LNCS, pp. 357-373, Springer Verlag, April 2005

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.

Download PDF        Show BibTeX               


Login to edit


Webmaster, Wed Sep 16 10:47:00 2009