Dessen Lösung approximiert die möglichen Werte der Programmvariablen. Mit dieser Information können wir Programmeigenschaften nachweisen. Diese verwenden wir beispielsweise zum optimierenden Kompilieren.
Es ist entscheidbar, ob ein Set-Constraint-System lösbar ist. Falls ja, dann erlaubt es sogar eine reguläre Lösung (ein Tupel regulärer Baumsprachen). Diese beschreiben wir durch generalized tree set automata.
Das Problem ist NEXPTIME-vollständig. Durch Einschränken der erlaubten Constraints können wir die Komplexität reduzieren.
Literatur:
this page is best viewed with any browser