Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: Systems of Set Constraints with Negative Constraints are NEXPTIME-Complete
Authors: Stefansson, Kjartan
Keywords: computer science
technical report
Issue Date: Aug-1993
Publisher: Cornell University
Abstract: A system of set constraints is a system of expressions $E\subseteq F$ where $E$ and $F$ describe sets of ground terms over a ranked alphabet. Aiken et al. [AKVW93] classified the complexity of such systems. In [AKW93] it was shown that if negative constraints $E\not\subseteq F$ were allowed, then the problem is 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 [AKW93] we conclude that systems of set constraints, allowing negative constraints, is NEXPTIME-complete.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
93-1380.pdf694.43 kBAdobe PDFView/Open
93-1380.ps239.32 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us