非表示:
キーワード:
-
要旨:
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.
