|
Guest
|
Dear all,
I use set constraints to model and to reason about type hierarchies.
Here,
I ran into a problem that, although I think it is simple, I did not
solve
yet. Maybe someone knows some literature to point me to.
My tentative name for this problem is the saturation problem.
The problem is as follows. My application creates a type hierarchy
but no
objects are associated with types (yet). This type hierarchy
corresponds to a CSP
with set constraints. The constraints are unary (cardinality) and
binary
(union, intersection, set inclusion, equality, and the negation of the
two previous).
Now I'm interested to find out if there exists an assignment of
objects to
types (a population) such that the CSP has a solution. In other
words, I
want to know if the CSP is consistent.
The consistency can be tested by a set constraint solver.
But such solvers expect fixed domains for the variables.
Therefore, it is necessary to "guess" their domains "large enough",
i.e., in a way it
is guaranteed that if there is a solution to the CSP it can be
established
within the domain bounds.
The domain of the variables are sets of sets of objects.
So the problem asks for the smallest n such that there is a solution
to the CSP for which
the union of its variable assignments results in a set of size n.
Because finding the exact n requires to solve the CSP, I'm looking for
a quick estimate of an upper bound. Currently, my estimate is one
object for every non-equality and every non-setInclusion constraint.
Is that a reasonable estimate, i.e., is it a true upper bound for n?
And can you imagine a better one?
Best regards,
Ulrich |
|
|
