Solving Systems of Set Constraints (Extended Abstract)
Alex Aiken, Edward L. Wimmers · 1992
) Alexander Aiken Edward L. Wimmers IBM Almaden Research Center 650 Harry Rd. San Jose, CA 95120 phone: 408/927-1876 or 927-1882 email: [email protected] fax: 408/927-2100 Abstract Systems of set constraints are a natural formalism for many problems in program analysis. Set constraints are also a generalization of tree automata. We present an algorithm for solving systems of set constraints built from free variables, constructors, and the set operations of intersection, union, and complement. Furthermore, we show that all solutions of such systems can be finitely represented. 1 1 Introduction Set constraints are a natural formalism for describing relationships between sets of terms of a free algebra. A set constraint has the form X ` Y , where X and Y are set expressions. Examples of set expressions are 0 (the empty set), 1 (the set of all terms), ff (a set-valued variable), c(X; Y ) (a constructor application) , and the union, intersection, or complement of set expressi...