Solving systems of set constraints using tree automata. (English) Zbl 0797.68115

Enjalbert, Patrice (ed.) et al., STACS 93. 10th annual symposium on theoretical aspects of computer science, Würzburg, Germany, February 25-27, 1993. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 665, 505-514 (1993).
Summary: 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 A. Aiken and E. L. Wimmers. 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.
For the entire collection see [Zbl 0866.00060].


68Q45 Formal languages and automata