%0 Journal Article
%J The Computer Journal
%D 2010
%T Generalized Distance Functions in the Theory of Computation
%A Anthony K. Seda
%A Pascal Hitzler
%K denotational semantics
%K fixed-point theorems
%K logic programming
%K stable model
%K supported model
%K topology
%K ultra-metrics
%X We discuss a number of distance functions encountered in the theory of computation, including metrics, ultra-metrics, quasi-metrics, generalized ultrametrics, partial metrics, d-ultra-metrics, and generalized metrics. We consider their properties, associated fixed-point theorems, and some general applications they have within the theory of computation. We consider in detail the applications of generalized distance functions in giving a uniform treatment of several important semantics for logic programs, including acceptable programs and natural generalizations of them, and also the supported model and the stable model in the context of locally stratified extended disjunctive logic programs and databases.
%B The Computer Journal
%P 443-464
%G eng
%0 Book
%D 2010
%T Mathematical Aspects of Logic Programming Semantics
%A Anthony K. Seda
%A Pascal Hitzler
%G eng
%0 Conference Paper
%B the 26th Annual German Conference on Artificial Intelligence, KI2003
%D 2003
%T Continuity of Semantic Operators in Logic Programming and their Approximation by Artificial Neural Networks.
%A Anthony K. Seda
%A Pascal Hitzler
%X One approach to integrating First-order logic programming and neural network systems employs the approximation of semantic operators by feedforward networks. For this purpose, it is necessary to view these semantic operators as continuous functions on the reals. This can be accomplished by endowing the space of all interpretations of a logic program with topologies obtained from suitable embeddings. We will present such topologies which arise naturally out of the theory of logic programming, discuss continuity issues of several wellknown semantic operators, and derive some results concerning the approximation of these operators by feedforward neural networks.
%B the 26th Annual German Conference on Artificial Intelligence, KI2003
%C Hamburg, Germany
%P 105-119
%G eng
%0 Journal Article
%J Theoretical Computer Science
%D 2003
%T Generalized Metrics and Uniquely Determined Logic Programs
%A Anthony K. Seda
%A Pascal Hitzler
%K Priess-Crampe and Ribenboim Fixed-Point Theorem
%K Ultrametrics
%X The introduction of negation into logic programming brings the benefit of enhanced syntax and expressibility, but creates some semantical problems. Specifically, certain operators which are monotonic in the absence of negation become non-monotonic when it is introduced, with the result that standard approaches to denotational semantics then become inapplicable. In this paper, we show how generalized metric spaces can be used to obtain fixed-point semantics for several classes of programs relative tot eh supported model semantics, and investigate relationships between the underlying spaces we employ. Our methods allow the analysis of classes of programs which include the acyclic, locally hierarchical, and acceptable programs amongst others, and draw on fixed-point theorems which apply to generalized ultrametric spaces and to partial metric spaces.
%B Theoretical Computer Science
%P 187-219
%G eng
%0 Book Section
%D 2002
%T The Fixed-Point Theorems of Priess-Crampe and Ribenboim in Logic Programming
%A Anthony K. Seda
%A Pascal Hitzler
%G eng
%0 Journal Article
%J Journal of Electrical Engineering
%D 2001
%T A "Converse" of the Bananch Contraction Mapping Theorem
%A Pascal Hitzler
%A Anthony K. Seda
%K Banach contraction
%K Banach contraction mapping theorem
%X We prove a type of converse of the Banach contraction mapping theorem for metric spaces: if X is a T_{1} topological space and *f*: X -> X is a function with the unique fixed point *a* such that *f*^{n}(*x*) converges to *a* for each *x* is a member of *X*, then there exists a distance function *d* on *X* such that *f* is a contraction on the complete ultrametric space (X,d) with contractivity factor 1/2. We explore properties of the resulting space (X,d).
%B Journal of Electrical Engineering
%P 3-6
%G eng
%0 Conference Paper
%B 7th International Conference on Information Systems Analysis and Synthesis (ISAS 2001)
%D 2001
%T Semantic Operators and Fixed-Point Theory in Logic Programming
%A Anthony K. Seda
%A Pascal Hitzler
%X We consider rather general operators mapping valuations to (sets of) valuations in the context of the semantics of logic programming languages. This notion generalizes several of the standard operators encountered in this subject and is inspired by earlier work of M.C. Fitting. The fixed points of such operators play a fundamental role in logic programming semantics by providing standard models of logic programs and also in determining the computability properties of these standard models. We discuss some of our recent work employing topological ideas, in conjunction with order theory, to establish methods by which one can nd the fixed points of the operators arising in logic programming semantics.
%B 7th International Conference on Information Systems Analysis and Synthesis (ISAS 2001)
%C Orlando, Florida, USA
%P 224-229
%G eng
%0 Journal Article
%J Information
%D 2001
%T Unique Supported-Model Classes of Logic Programs
%A Anthony K. Seda
%A Pascal Hitzler
%K denotational semantics
%K logic programming
%K supported-model semantics
%X We study classes of programs, herein called *unique supported-model classes,* with the property that each program in the class has a unique supported model. Elsewhere, the authors examined these classes from the point of view of operators defined relative to certain three-valued logics. In this paper, we complement our earlier results by considering how unique supported-model classes fit into the framework given by various classes of programs in several well-known approaches to semantics.
%B Information
%P 295-302
%G eng
%0 Conference Paper
%B Classes of Logic Programs which Possess Unique Supported Models.
%D 2000
%T Classes of Logic Programs which Possess Unique Supported Models.
%A Anthony K. Seda
%A Pascal Hitzler
%X Logic programming is concerned with the use of logic as a programming language. The main manifestation of this computing paradigm is in the various versions of Prolog which are now available, in which computation is viewed as deduction from sets of Horn clauses, although there is also growing interest in the related form known as answer set programming, see [10]. The reference [1] contains a good survey of the growth of logic programming over the last twenty-five years both as a stand-alone programming language and as a software component of large information systems. One advantage a logic program P has over conventional imperative and object oriented programs is that it has a natural machine-independent meaning, namely, its logical meaning. This is often referred to as its declarative semantics, and is usually taken to be some 'standard' model canonically associated with P. Unfortunately, it is often the case that there are many possible choices for the standard model, some even taken in many-valued logic, which do not in general coincide and all of which have a claim to be 'the natural choice' depending on one's view of non-monotonic reasoning [6, 7, 11].
%B Classes of Logic Programs which Possess Unique Supported Models.
%G eng
%0 Conference Paper
%B On the Coincidence of Semantics for Uniquely Determined Programs
%D 2000
%T On the Coincidence of Semantics for Uniquely Determined Programs
%A Anthony K. Seda
%A Pascal Hitzler
%X We study classes of logic programs, called here unique supported model classes or simply usm- classes, with the property that each member in the class is uniquely determined, that is, possesses a unique supported model. Known classes of uniquely determined programs include the acyclic and the acceptable programs, which have been much studied in the context of termination, and the authors gave a unifying treatment of these and other unique supported model classes in an earlier paper. In the present paper, we complement these earlier results by considering how various standard semantics relate to each other within certain unique supported model classes. In particular, we introduce the natural usm-class of all accessible programs, which contains the aforementioned classes, and has the property that, for each member of it, the stable, well-founded and weakly perfect-a models all coincide.
%B On the Coincidence of Semantics for Uniquely Determined Programs
%G eng
%0 Journal Article
%D 2000
%T Dislocated Topologies
%A Pascal Hitzler
%A Anthony K. Seda
%K Banach contraction
%K topologies
%X We study a generalized notion of topology which evolved out of applications in the area of logic programming semantics. The generalization is obtained by relaxing the requirements that a neighbourhood of a point includes the point itself, and by allowing neighbourhoods of points to be empty. The correspoding generalized notion of metric is obtained by allowing points to have non-zero distance to themselves. We further show that it is meaningful to discuss neightbourhoods, convergence, and continuity in these spaces. A generalized version of the Banach contraction mapping theorem can also be established. We show finally how the generalized metrics studied here can be obtained from conventional metrics.
%G eng
%0 Generic
%D 2000
%T Dislocated Topologies
%A Pascal Hitzler
%A Anthony Seda
%A Anthony K. Seda
%X We study a generalized notion of topology which evolved out of applications in the area of logic programming semantics. The generalization is obtained by relaxing the requirements that a neighbourhood of a point includes the point itself, and by allowing neighbourhoods of points to be empty. The correspoding generalized notion of metric is obtained by allowing points to have non-zero distance to themselves. We further show that it is meaningful to discuss neightbourhoods, convergence, and continuity in these spaces. A generalized version of the Banach contraction mapping theorem can also be established. We show finally how the generalized metrics studied here can be obtained from conventional metrics.
%G eng
%0 Conference Paper
%B SCI2000 and ISAS2000
%D 2000
%T A New Fixed-point Theorem for Logic Programming Semantics
%A Anthony K. Seda
%A Pascal Hitzler
%X We present a new fixed-point theorem akin to the Banach contraction mapping theorem, but in the context of a novel notion of generalized metric space, and show how it can be applied to analyse the denotational semantics of certain logic programs. The theorem is obtained by generalizing a theorem of Priess-Crampe and Ribenboim, which grew out of applications within valuation theory, but is also inspired by a theorem of S.G. Matthews which grew out of applications to conventional programming language semantics. The class of programs to which we apply our theorem was defined previously by us in terms of operators using three-valued logics. However, the new treatment we provide here is short and intuitive, and provides further evidence that metriclike structures are an appropriate setting for the study of logic programming semantics.
%B SCI2000 and ISAS2000
%C Orlando, Florida, USA
%P 418-423
%G eng
%0 Generic
%D 2000
%T A Topological View of Acceptability
%A Anthony K. Seda
%A Pascal Hitzler
%G eng
%0 Conference Paper
%D 1999
%T Acceptable Programs Revisited
%A Anthony K. Seda
%A Pascal Hitzler
%K l and o and g and i and c and and p and r and o and g and r and a and m and s
%X Acceptable logic programs have been studied extensively in the context of proving termination of Prolog programs. It is difficult, however, to establish acceptability from the definition since this depends on finding a suitable model, which need not be a Herbrand model in general, together with a suitable level mapping that one can use to check the conditions which characterize acceptability. In this paper, we will see that when working over a fixed but arbitrary preinterpretation, a method can be provided for obtaining both a suitable model and a canonical level mapping which are sufficient for this purpose. Furthermore, the canonical model and level mapping obtained will turn out to be sufficient for discussing termination of non-ground queries.
%I Workshop on Verification in Logic Programming, 16th International Conference on Logic Programming (ICLP'99),
%G eng
%0 Conference Paper
%B A Characterization of Acceptability
%D 1999
%T A Characterization of Acceptability
%A Anthony K. Seda
%A Pascal Hitzler
%B A Characterization of Acceptability
%G eng
%0 Conference Paper
%B Characterizations of Classes of Programs by Three-valued Operators
%D 1999
%T Characterizations of Classes of Programs by Three-valued Operators
%A Anthony K. Seda
%A Pascal Hitzler
%X Several important classes of normal logic programs, including the classes of acyclic, acceptable, and locally hierarchical programs, have the property that every program in the class has a unique twovalued supported model. In this paper, we call such classes unique supported model classes. We analyse and characterize these classes by means of operators on three-valued logics. Our studies will motivate the definition of a larger unique supported model class which we call the class of Phi-accessible programs. Finally, we show that the class of Phi -accessible programs is computationally adequate in that every partial recursive function can be implemented by such a program.
%B Characterizations of Classes of Programs by Three-valued Operators
%G eng
%0 Conference Paper
%D 1999
%T Multivalued Mappings, Fixed-Point Theorems and Disjunctive Databases
%A Anthony K. Seda
%A Pascal Hitzler
%X In this paper, we discuss the semantics of disjunctive programs and databases and show how multivalued mappings and their fixed points arise naturally within this context. A number of fixed-point theorems for multivalued mappings are considered, some of which are already known and some of which are new. The notion of a normal derivative of a disjunctive program is introduced. Normal derivatives are normal logic programs which are determined by the disjunctive program. Thus, the well-known single-step operator associated with a normal derivative is single-valued, and its fixed points can be found by well-established means. It is shown how fixed points of the multivalued mapping determined by a disjunctive program relate to the fixed points of the single-step operators coming from its normal derivatives. This procedure has potential for simplifying the construction of models of disjunctive databases, and this point is discussed. Most of the results for multivalued mappings rest on corresponding, known results concerning fixed points of single-valued mappings. Since the latter results are frequently referred to, they have been collected together for convenience in a survey which should be of independent interest as well as being preparatory for the later results. Finally, a number of problems and issues raised by this work are discussed.
%I Electronic Workshops in Computing, British Computer Society
%G eng
%0 Journal Article
%J Topology Proceedings
%D 1999
%T Some Issues Concerning Fixed-Points in Computational Logic: Quasi-Metrics, Multivalued Mappings and the Knaster-Tarski Theorem
%A Anthony K. Seda
%A Pascal Hitzler
%K fixed points
%K Knaster Tarski and Kleene theorems
%K multivalued mappings
%X Many questions concerning the semantics of disjunctive databases and of logic programming systems depend on the fixed points of various multivalued mappings and operations determined by the database or program. We discuss known versions for multivalued mappings of the Knaster-Tarski theorem and of the Banach contraction mapping theorem and formulate a version of the classical fixed point theorem (sometimes attributed to Kleene) which is new. All these results have applications to the semantics of disjunctive logic programs, and we will describe a class of programs to which the new theorem can be applied. We also show that a unification of the latter two theorems is possible, using quasi-metrics, which parallels the well-known unification of Rutten and Smyth in the case of conventional programming language semantics.
%B Topology Proceedings
%P 223-250
%G eng
%0 Conference Paper
%D 1998
%T Strictly Level-Decreasing Logic Programs
%A Anthony K. Seda
%A Pascal Hitzler
%X We study strictly level-decreasing logic programs (sld-programs) as defined earlier by the present authors. It will be seen that sld-programs, unlike most other classes of logic programs, have both a highly intuitive declarative semantics, given as a unique supported model, and are computationally adequate in the sense that every partial recursive function can be represented by some sld-program *P*. Allowing for a safe use of cuts, an interpreter based on SLDNF-resolution, as implemented for example in standard Prolog systems, is shown to be sound and complete with respect to this class of programs. Furthermore, we study connections between topological dynamics and logic programming which are suggested by our approach to the declarative semantics of sld-programs.
%I the Second Irish Workshop on Formal Methods
%G eng