Document Type
Report
Date
1990
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. 90.
https://surface.syr.edu/eecs_techreports/90
Source
local
Additional Information
School of Computer and Information Science, Syracuse University, SU-CIS-90-26