Solving systems of set constraints with negated subset relationships
- 30 December 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 372-380
- https://doi.org/10.1109/sfcs.1993.366850
Abstract
We present a decision procedure, based on tree automata techniques, for satisfiability of systems of set constraints including negated subset relationships. This result extends all previous works on set constraints solving and solves a problem which was left open by L. Bachmair et al. (1993). We prove in a constructive way that a non empty set of solutions always contains a regular solution, that is a tuple of regular tree languages. Moreover, we think that the new class of tree automata described here could be interesting in its own.Keywords
This publication has 8 references indexed in Scilit:
- Solving systems of set constraintsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Solving systems of set constraints with negated subset relationshipsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Set constraints are the monadic classPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- 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
- A finite presentation theorem for approximating logic programsPublished by Association for Computing Machinery (ACM) ,1990
- 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