Arithmetic Classification of Perfect Models of Stratified Programs (Addendum)
Krzysztof Rafal Apt, Howard A. Blair · Syracuse University Libraries (Syracuse University) · 1990
RECURSION-FREE PROGRAMS The following section completes the analysis of arithmetic complexity of perfect models and has been inadvertently omitted in the previous version of the paper. We say that a general program P is recursion-free if in its dependency graph Dp there is no cycle. Clearly recursion-free programs form a subclass of stratified programs. Recursion-free programs form a very simple generalization of the class of hierarchical programs introduced in [C78]. Hierarchical programs satisfy an additional condition on variable occurrences in clauses that prevents floundering, i.e. a forced selection of a non-ground negative literal in an SLDNF- derivation. In this section we study the complexity of perfect models of recursion-free programs.