Compactness Properties for Stable Semantics of Logic Programs

Issue title: Topics in Logic, Philosophy and Foundations of Mathematics and Computer Science. In Recognition of Professor Andrzej Grzegorczyk

Article type: Research Article

Authors: Marek, Victor W. | Remmel, Jeffrey B.

Affiliations: Department of Computer Science, University of Kentucky Lexington, KY 40506–0046, USA. E-mail: marek@cs.uky.edu | Departments of Mathematics and Computer Science, University of California at San Diego La Jolla, CA 92093, USA. E-mail: jremmel@ucsd.edu

Abstract: Logic programming with stable logic semantics (SLP) is a logical formalism that assigns to programs, i.e. sets of clauses where we allow both atoms and their negations in the body of clause, a special class of models of the program, called stable models. We show that stable logic semantics does not satisfy the natural analogue of the compactness theorem. However, we show that there are a variety of conditions which will ensure that a program satisfies the analogue of the compactness theorem.

Journal: Fundamenta Informaticae, vol. 81, no. 1-3, pp. 211-239, 2007