Paper: Solving systems of set constraints (at LICS 1992)

Authors: Alexander Aiken Edward L. Wimmers

Abstract

It is shown that systems of set constraints that use all the standard set operations, especially unrestricted union and complement, can be solved. The centerpiece of the development is an algorithm that incrementally transforms a system of constraints while preserving the set of solutions. Eventually, either the system is shown to be inconsistent or all solutions can be exhibited. Most of the work is in proving that if this algorithm does not discover an inconsistency, then the system has a solution. This is done by showing that the system of constraints generated by the algorithm can be transformed into an equivalent set of equations that are guaranteed to have a solution. These equations are essentially tree automata

BibTeX

  @InProceedings{AikenWimmers-Solvingsystemsofset,
    author = 	 {Alexander Aiken and Edward L. Wimmers},
    title = 	 {Solving systems of set constraints},
    booktitle =  {Proceedings of the Seventh Annual IEEE Symposium on Logic in Computer Science (LICS 1992)},
    year =	 {1992},
    month =	 {June}, 
    pages =      {329--340},
    location =   {Santa Cruz, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }