Skip to Main content Skip to Navigation
Conference papers

Solving Systems of Set Constraints using Tree Automata

Abstract : A set constraint is of the form exp 1 $$\subseteq$$ exp 2 where exp 1 and exp 2 are set expressions constructed using variables, function symbols, and the set union, intersection and complement symbols. An algorithm for solving such systems of set constraints was proposed by Aiken and Wimmers [1]. We present a new algorithm for solving this problem. Indeed, we define a new class of tree automata called Tree Set Automata. We prove that, given a system of set constraints, we can associate a tree set automaton such that the set of tuples of tree languages recognized by this automaton is the set of tuples of solutions of the system. We also prove the converse property. Furthermore, if the system has a solution, we prove, in a constructive way, that there is a regular solution (i.e. a tuple of regular tree languages) and a minimal solution and a maximal solution which are actually regular.
Document type :
Conference papers
Complete list of metadatas
Contributor : Rémi Gilleron <>
Submitted on : Tuesday, November 23, 2010 - 2:48:26 PM
Last modification on : Tuesday, April 28, 2020 - 11:52:08 AM


  • HAL Id : inria-00538878, version 1



Rémi Gilleron, Sophie Tison, Marc Tommasi. Solving Systems of Set Constraints using Tree Automata. Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science, STACS'93, 1993, Würzburg, Germany. pp.505--514. ⟨inria-00538878⟩



Record views