Set constraint


In mathematics and theoretical computer science, a set constraint is an equation or an inequation between sets of terms.
Similar to systems of equations between numbers, methods are studied for solving systems of set constraints.
Different approaches admit different operators on sets and different equation relations between set expressions.
Systems of set constraints are useful to describe 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 with the rules
is transformed to the set inclusion system :
This system has a minimal solution, viz. :
The maximal solution of the system is trivial; it assigns the set of all terms to every variable.

Literature

*