Set constraint

Set constraints obtained from abstract interpretation of the Collatz algorithm

In mathematics and theoretical computer science, a set constraint is an equation or an inequation between sets of terms. Similar to systems of (in)equations between numbers, methods are studied for solving systems of set constraints. Different approaches admit different operators (like "∪", "∩", "\", and function application) on sets and different (in)equation relations (like "=", "⊆", and "⊈") between set expressions.

Systems of set constraints are useful to describe (in particular infinite) sets of ground terms. They arise in program analysis, abstract interpretation, and type inference.

Relation to regular tree grammars

Each regular tree grammar can be systematically transformed into a system of set inclusions such that its minimal solution corresponds to the tree language of the grammar.

For example, the grammar (terminal and nonterminal symbols indicated by lower and upper case initials, respectively) with the rules

BoolG→ false
BoolG→ true
BListG→ nil
BListG→ cons(BoolG,BListG)
BList1G→ cons(true,BListG)
BList1G→ cons(false,BList1G)

is transformed to the set inclusion system (constants and variables indicated by lower and upper case initials, respectively):

BoolS⊇ false
BoolS⊇ true
BListS⊇ nil
BListS⊇ cons(BoolS,BListS)
BList1S⊇ cons(true,BListS)
BList1S⊇ cons(false,BList1S)

This system has a minimal solution, viz. ("L(N)" denoting the tree language corresponding to the nonterminal N in the above tree grammar):

BoolS= L(BoolG)= { false, true }
BListS= L(BListG)= { nil, cons(false,nil), cons(true,nil), cons(false,cons(false,nil)), ... }
BList1S= L(BList1G)= { nil, cons(true,nil), cons(true,cons(false,nil)),... }

The maximal solution of the system is trivial; it assigns the set of all terms to every variable.

Literature

Literature on negative constraints

  • Aiken, A., Kozen, D., Wimmers, E.L. (Jun 1993). Decidability of Systems of Set Constraints with Negative Constraints (Technical report). Computer Science Department, Cornell University. 93–1362.{{cite tech report}}: CS1 maint: multiple names: authors list (link)
  • Charatonik, W., Pacholski, L. (Jul 1994). "Negative Set Constraints with Equality". Ninth Annual IEEE Symposium on Logic in Computer Science. pp. 128–136.{{cite book}}: CS1 maint: multiple names: authors list (link)
  • R. Gilleron; S. Tison; M. Tommasi (1993). "Solving Systems of Set Constraints with Negated Subset Relationships". Proceedings of the 34th Symp. on Foundations of Computer Science. pp. 372–380.
  • Gilleron, R., Tison, S., Tommasi, M. (1993). Solving Systems of Set Constraints with Negated Subset Relationships (Technical report). Laboratoire d'Informatique Fondamentale de Lille. IT 247.{{cite tech report}}: CS1 maint: multiple names: authors list (link)
  • Stefansson, K. (Aug 1993). Systems of Set Constraints with Negative Constraints are NEXPTIME-Complete (Technical report). Computer Science Department, Cornell University. 93–1380.
  • Stefansson, K. (1994). "Systems of Set Constraints with Negative Constraints are NEXPTIME-Complete". Ninth Annual IEEE Symposium on Logic in Computer Science. pp. 137–141.

Notes

  1. ↑ If f is an n-ary function symbol admitted in a term, then "f(E1,...,En)" is a set expression denoting the set { f(t1,...,tn) : t1∈E1 and ... and tn∈En }, where E1,...,En are set expressions in turn.
  2. ↑ This is similar to describing e.g. a rational number as a solution to an equation a⋅x + b = 0, with integer coefficients a, b.