Document Type
Report
Date
1990
Embargo Period
5-1-2012
Keywords
Perfect models
Language
English
Disciplines
Computer Sciences
Description/Abstract
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.
Recommended Citation
Apt, Krzysztof R. and Blair, Howard A., "Arithmetic Classification of Perfect Models of Stratified Programs (Addendum)" (1990). Electrical Engineering and Computer Science Technical Reports. Paper 90.
http://surface.syr.edu/eecs_techreports/90
Source
local
Additional Information
School of Computer and Information Science, Syracuse University, SU-CIS-90-26