@TechReport{Müller_Niehren:1997,
AUTHOR = {Müller, Martin and Niehren, Joachim},
TITLE = {Entailment of Set Constraints is not Feasible},
YEAR = {1997},
ADDRESS = {Saarbrücken},
TYPE = {Technical Report},
INSTITUTION = {Universität des Saarlandes, Programming Systems Lab},
URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/inesInfeas.ps.gz},
ABSTRACT = {Set constraints are inclusions between expressions denoting sets of trees. They have been used extensively for type inference and program analysis. At the lower end of the expressiveness scale there are atomic set constraints and Ines constraints (inclusions over non-empty sets) for both of which a cubic time satisfiability test is known. Recently, there has been increasing interest in entailment tests for set constraints. We prove that the entailment problem of atomic set constraints is coNP-hard. We also show that the entailment problem of Ines constraints is coNP-hard. This corrects a claim of polynomial complexity presented at CP'96. Our results suggest that a complete entailment test is not feasible even for simple classes of set constraints.},
ANNOTE = {COLIURL : Muller:1997:ESC.pdf Muller:1997:ESC.ps}
}
|
