Show simple item record

dc.contributor.authorStefansson, Kjartanen_US
dc.date.accessioned2007-04-23T16:32:05Z
dc.date.available2007-04-23T16:32:05Z
dc.date.issued1993-08en_US
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR93-1380en_US
dc.identifier.urihttps://hdl.handle.net/1813/6154
dc.description.abstractA 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.en_US
dc.format.extent711101 bytes
dc.format.extent245065 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.language.isoen_USen_US
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleSystems of Set Constraints with Negative Constraints are NEXPTIME-Completeen_US
dc.typetechnical reporten_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics