Topological aspects of logic programming
Kenneth A. Bowen, Aïda Batarekh · Medical Entomology and Zoology · 1989
A topology, called the Query topology, is defined on both the set of interpretations ${\cal I}$ of the language of a sentence and the set of models of that sentence. The basis of the Query topology is generated by existential closures of finite conjunctions of literals, called queries. This topology is shown to possess many properties. The Query space is a $T\sb5$, compact and metrizable space. It is also a Cantor space and is homeomorphic to the Cantor discontinuum. We show that the Query topology is finer than the Scott topology and that both the Lawson and the Order topology coincide in this setting. The operator $T\sb{P}:{\cal I}\to{\cal I}$ is shown to be continuous over the query topology whenever P is a covered general logic program. A new operator $\Upsilon\sb{P}:{\cal I}\to{\cal I}$ is introduced. It is essentially $T\sb{P}$ for every index $i < \omega$. At $\omega,\Upsilon\sb{P}$ is defined as the (o)-limit of the sequence $(\Upsilon\sb{P}@0(I),\Upsilon\sb{P}@1(I), \Upsilon\sb{P}@2(I),\...)$, if such a limit exists. We call sequences of this form trajectories. For a general logic program P, we give constructive proofs for conditions that guarantee respectively the following: (1) that a trajectory will converge, (2) that the limit is a prefixed point (i.e. a model of P), (3) that the limit is a fixed point (i.e. a model of the completion of P), (4) that the limit is a minimal fixed point. The limit of any convergent trajectory over a covered program is a fixed point of $T\sb{P}$. We identify a class of programs (strongly determined) for which $\Upsilon\sb{P} @ \omega(\emptyset)$ always exists and is a minimal fixed point of $T\sb{P}$. We study the relationship between the class A of strongly determined programs and the class B of stratified programs and find that none of the following sets are empty: $A \cap B, A - B, B - A$. We also investigate the connection of $\Upsilon\sb{P}@\omega$ with perfect models.