  |
Entailment of Set Constraints is not Feasible
Author: Martin Müller and Joachim NiehrenEditor:
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.
|