hide
Free keywords:
-
Abstract:
We investigate a class of set constraints defined as atomic set
constraints augmented with projection. This class subsumes some
already studied classes such as atomic set constraints with
left-hand side projection and INES constraints. All these classes
enjoy a nice property that satisfiability can be performed in cubic time. This
has be contrasted with several other classes of set constraints, such as
definite set constraints and positive set constraints, for which
satisfiability ranges from DEXPTIME-complete to NEXPTIME-complete. However,
these latter classes allow set operators such as intersection or union which
is not the case for the class studied here. In the case of atomic set
constraints with projection one might expect that satisfiability remains
polynomial. Unfortunately, we show that that the satisfiability problem for
this class is no longer polynomial, but CoNP-hard. Furthermore, we devise a
PSPACE algorithm to solve this satisfiability problem.
