"Set constraints with projections are in NEXPTIME" by Witold Charatonik and
 Leszek Pacholski


<BR>
<BR>

Abstract:

<P>


Systems of set constraints describe relations between sets of ground
terms. They have been successfully used in program analysis and type
inference. In this paper we prove that the problem of existence of a
solution of a system of set constraints with projections is in
NEXPTIME, and thus that it is NEXPTIME-complete.  This extends the
results of A.Aiken, D.Kozen, and E.L.Wimmers and R.Gilleron, S.Tison,
and M.Tommasi on decidability of negated set constraints and solves a
problem that was open for several years.


</P>

  <A Href="focs94.ps">
  postscript file (184K)</A>,
  <A Href="focs94.dvi">
  dvi file (88K)</A>, or 
  <A Href="focs94.ps.Z">
  compressed postscript file (82K)</A>