Solving systems of set constraints
- 2 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 68, 329-340
- https://doi.org/10.1109/lics.1992.185545
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.Keywords
This publication has 11 references indexed in Scilit:
- Logic programs as types for logic programsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A decision procedure for a class of set constraintsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Static type inference in a dynamically typed languagePublished by Association for Computing Machinery (ACM) ,1991
- Deciding Equivalence of Finite Tree AutomataSIAM Journal on Computing, 1990
- A finite presentation theorem for approximating logic programsPublished by Association for Computing Machinery (ACM) ,1990
- Alternating tree automataTheoretical Computer Science, 1985
- Declaration-free type checkingPublished by Association for Computing Machinery (ACM) ,1985
- On equations for regular languages, finite automata, and sequential networksTheoretical Computer Science, 1980
- Flow analysis and optimization of LISP-like structuresPublished by Association for Computing Machinery (ACM) ,1979
- Decidability of Second-Order Theories and Automata on Infinite TreesTransactions of the American Mathematical Society, 1969