Decidability of Systems of Set Constraints with Negative Constraints
DOI:
https://doi.org/10.7146/brics.v1i32.21611Abstract
Set constraints are relations between sets of terms. They have been used extensively in various applications in program analysis and type inference. Recently, several algorithms for solving general systems of positive set constraints have appeared. In this paper we consider systems of mixed positive and negative constraints, which are considerably more expressive than positive constraints alone. We show that it is decidable whether a given such system has a solution. The proof involves a reduction to a number-theoretic decision problem that may be of independent interest.Downloads
Published
1994-10-31
How to Cite
Aiken, A., Kozen, D., & Wimmers, E. (1994). Decidability of Systems of Set Constraints with Negative Constraints. BRICS Report Series, 1(32). https://doi.org/10.7146/brics.v1i32.21611
Issue
Section
Articles
License
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.