Item

Abstract

Set-based analysis of logic programs provides an accurate method for descriptive type-checking of logic programs. The key idea of this method is to upper approximate the least model of the program by a regular set of trees. In 1991, Fr\"uhwirth, Shapiro, Vardi and Yardeni raised the question whether it can be more efficient to use the domain of sets of paths instead, {\em i.e.}, to approximate the least model by a regular set of words. We answer the question negatively by showing that type-checking for path-based analysis is as hard as the set-based one, that is DEXPTIME-complete. This result has consequences also in the areas of set constraints, automata theory and model checking.