Logic in Computer Science (LICS 1994)

Paper: Systems of set constraints with negative constraints are NEXPTIME-complete (at LICS 1994)

Authors: Kjartan Stefansson

Abstract

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}
  }