Topological Model Set Deformations in Logic Programming

Article type: Research Article

Authors: Batarekh, Aida | Subrahmanian, V.S.

Affiliations: School of Computer & Information Science, Syracuse University, Syracuse, NY 13244-1240, U.S.A.

Abstract: Given a first order language L, and a notion of a logic L w.r.t. L, we investigate the topological properties of the space of L-structures for L. We show that under a topology called the query topology which arises naturally in logic programming, the space of L-models (where L is a decent logic) of any sentence (set of clauses) in L may be regarded as a (closed, compact) T4-space. We then investigate the properties of maps from structures to structures. Our results allow us to apply various well-known results on the fixed-points of operators on topological spaces to the semantics of logic programming – in particular, we are able to derive necessary and sufficient topological conditions for the completion of covered general logic programs to be consistent. Moreover, we derive sufficient conditions guaranteeing the consistency of program completions, and for logic programs to be determinate. We also apply our results to characterize consistency of the unions of program completions.

DOI: 10.3233/FI-1989-12305

Journal: Fundamenta Informaticae, vol. 12, no. 3, pp. 357-399, 1989