Generalized metrics and topology in logic programming semantics

No Thumbnail Available
2001
Hitzler, Pascal
Publisher
University College Cork
Abstract
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 applicabil­ity 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 contrac­tion mapping theorem for single-valued and multivalued mappings, and investi­gate 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 under­standing 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.
Keywords
Metrics , Topology , Logic programming semantics
Citation
Hitzler, P. 2001. Generalized metrics and topology in logic programming semantics. PhD Thesis, University College Cork.