Paper: Systems of set constraints with negative constraints are NEXPTIME-complete (at LICS 1994)
Authors: Kjartan StefanssonAbstract
A system of set constraints is a system of expressions E⊆F where E and F describe sets of ground terms over a ranked alphabet. Aiken et al. (1993) classified the complexity of such systems. In A. aiken et al. (1993), it was shown that if negative constraints Enot⊆F were allowed, then the problem as decidable. This was done by reduction to a Diophantine problem, the nonlinear reachability problem, which was shown to be decidable. We show that nonlinear reachability is NP-complete. By bounding the reduction of A. aiken et al. (1993), we conclude that systems of set constraints allowing negative constraints are NEXPTIME-complete
BibTeX
@InProceedings{Stefansson-Systemsofsetconstra, author = {Kjartan Stefansson}, title = {Systems of set constraints with negative constraints are NEXPTIME-complete }, booktitle = {Proceedings of the Ninth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1994}, year = 1994, editor = {Samson Abramsky}, month = {July}, pages = {137--141}, location = {Paris, France}, publisher = {IEEE Computer Society Press} }