| Title: |
Complexity of Subtype Satisfiability over Posets. |
| Authors: |
Sagiv, Mooly; Niehren, Joachim; Priesnitz, Tim; Su, Zhendong |
| Source: |
Programming Languages & Systems (9783540254355); 2005, p357-373, 17p |
| 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. [ABSTRACT FROM AUTHOR] |
| : |
Copyright of Programming Languages & Systems (9783540254355) is the property of Springer eBooks and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Complementary Index |