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.
Type de document :
Communication dans un congrès
Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science, STACS'93, 1993, Würzburg, Germany. Springer Verlag, 665, pp.505--514, 1993, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00538878
Contributeur : Rémi Gilleron <>
Soumis le : mardi 23 novembre 2010 - 14:48:26
Dernière modification le : mardi 24 avril 2018 - 13:32:52

Identifiants

  • HAL Id : inria-00538878, version 1

Collections

Citation

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. Springer Verlag, 665, pp.505--514, 1993, Lecture Notes in Computer Science. 〈inria-00538878〉

Partager

Métriques

Consultations de la notice

230