JavaScript is disabled for your browser. Some features of this site may not work without it.
Systems of Set Constraints with Negative Constraints are NEXPTIME-Complete

Author
Stefansson, Kjartan
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.
Date Issued
1993-08Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR93-1380
Type
technical report