Algebraic Foundations of Logic Programming, I: The Distributive Lattice of Logic Programs

Article type: Research Article

Authors: Hirani, Anil^{a; b} | Subrahmanian, V.S.^{a; b; *}

Affiliations: [a] MS 1-40, SUN Microsystems, 2550 Garcia Avenue, Mountain View, CA 94043, USA | [b] Department of Computer Science, University of Maryland, College Park, MD 20742, USA

Correspondence: [*] Address Correspondence to V.S. Subrahmanian.

Abstract: Given a logic program P, the operator TP associated with P is closely related to the intended meaning of P. Given a first order language L that is generated by finitely many non-logical symbols, our aim is to study the algebraic properties of the set {TP|P is a general logic program in language L} with certain operators on it. For the operators defined in this paper the resulting algebraic structure is a bounded distributive lattice. Our study extends (to the case of general logic programs), the work of Mancarella and Pedreschi who initiated a study of the algebraic properties of the space of pure logic programs. We study the algebraic properties of this set and identify the ideals and zero divisors. In addition, we prove that our algebra satisfies various non-extensibility conditions.

DOI: 10.3233/FI-1990-13306

Journal: Fundamenta Informaticae, vol. 13, no. 3, pp. 317-332, 1990