Generalized Metrics and Topology in Logic Programming Semantics

Many fixed-point theorems are essentially topological in nature. Among them are the Banach contraction mapping theorem on metric spaces and the fixed-point theorem for Scott-continuous mappings on complete partial orders. The latter theorem is fundamental in denotational semantics since semantic operators in most programming language paradigms satisfy its requirements. The use of negation in logic programming and non-monotonic reasoning, however, renders some semantic operators to be non-monotonic, hence discontinuous with respect to the Scott topology, and therefore invalidates the standard approach, so that alternative methods have to be sought. In this thesis, we investigate topological methods, including generalized metric fixed-point theorems, and their applicability to the analysis of semantic operators in logic programming and non-monotonic reasoning. In the first part of the thesis, we present weak versions of the Banach contraction mapping theorem for single-valued and multivalued mappings, and investigate relationships between the underlying spaces. In the second part, we apply the obtained results to several semantic paradigms in logic programming and non-monotonic reasoning. These investigations will also lead to a clearer understanding of some of the relationships between these semantic paradigms and of the general topological structures which underly the behaviour of the corresponding semantic operators. We will also obtain some results related to termination properties of normal logic programs, clarify some of the relationships between different semantic approaches in non-monotonic reasoning, and will establish some results concerning the conversion of logic programs into artificial neural networks