| Title: |
Complexity of Subtype Satisfiability over Posets |
| Authors: |
Joachim Niehren; Tim Priesnitz; Zhendong Su |
| Contributors: |
The Pennsylvania State University CiteSeerX Archives |
| Source: |
http://www.cs.ucdavis.edu/~su/publications/poset-short.pdf. |
| Publisher Information: |
Springer Verlag |
| Publication Year: |
2005 |
| Collection: |
CiteSeerX |
| Description: |
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. 1 |
| Document Type: |
text |
| File Description: |
application/pdf |
| Language: |
English |
| Relation: |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.93.5121 |
| Availability: |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.93.5121; http://www.cs.ucdavis.edu/~su/publications/poset-short.pdf |
| Rights: |
Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
| Accession Number: |
edsbas.4EAE2C9C |
| Database: |
BASE |