Skip to main content


eCommons@Cornell

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

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6154
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
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR93-1380
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.
URI: http://hdl.handle.net/1813/6154
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