Affordable Access

Publisher Website

An analysis of loop checking mechanisms for logic programs

Authors
Journal
Theoretical Computer Science
0304-3975
Publisher
Elsevier
Publication Date
Volume
86
Issue
1
Identifiers
DOI: 10.1016/0304-3975(91)90004-l
Disciplines
  • Computer Science

Abstract

Abstract We systematically study loop checking mechanisms for logic programs by considering their soundness, completeness, relative strength and related concepts. We introduce a natural concept of a simple loop check and prove that no sound and complete simple loop check exists, even for programs without function symbols. Then we introduce a number of sound simple loop checks and identify natural classes of Prolog programs without function symbols for which they are complete. In these classes a limited form of recursion is allowed. As a by-product we obtain an implementation of the closed world assumption of Reiter (1978) and a query evaluation algorithm for these classes of logic programs.

There are no comments yet on this publication. Be the first to share your thoughts.