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 metadatas

Cited literature [35 references]  Display  Hide  Download

https://hal.inria.fr/inria-00536523
Contributor : Joachim Niehren <>
Submitted on : Tuesday, November 16, 2010 - 1:32:29 PM
Last modification on : Wednesday, August 7, 2019 - 12:19:22 PM
Long-term archiving on : Thursday, February 17, 2011 - 2:58:02 AM

File

pdl05.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00536523, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

284

Files downloads

263