Skip to Main content Skip to Navigation
New interface
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [35 references]  Display  Hide  Download
Contributor : Joachim Niehren Connect in order to contact the contributor
Submitted on : Tuesday, November 16, 2010 - 1:32:29 PM
Last modification on : Tuesday, November 29, 2022 - 12:12:15 PM
Long-term archiving on: : Thursday, February 17, 2011 - 2:58:02 AM


Files produced by the author(s)


  • HAL Id : inria-00536523, version 1



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⟩



Record views


Files downloads