01428432

j

01428432 Talbot, Jean-Marc Devienne, Philippe Tison, Sophie Generalized definite set constraints. Constraints 5, No.1-2, 161-202 (2000). 2000 Springer, Norwell, MA EN computational complexity of set constraints algorithm satisfiability problem tree automata

doi:10.1023/A:1009826603139

Building neatly on results of N. Heintze and J. Jaffar on a decision procedure for a class of Herbrand set constraints, the authors prove several interesting results on the computational complexity of set constraints. E.g., they present an algorithm which provides a DEXPTIME test for the satisfiability problem of shallow systems of generalized definite set constraints. The algorithm for the satisfiability problem is based on use of deterministic bottom-up tree automata. Albert A.Mullin (Madison)