TY - JOUR
T1 - Generalized Distance Functions in the Theory of Computation
JF - The Computer Journal
Y1 - 2010
A1 - Anthony K. Seda
A1 - Pascal Hitzler
KW - denotational semantics
KW - fixed-point theorems
KW - logic programming
KW - stable model
KW - supported model
KW - topology
KW - ultra-metrics
AB - 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.
ER -
TY - BOOK
T1 - Mathematical Aspects of Logic Programming Semantics
Y1 - 2010
A1 - Anthony K. Seda
A1 - Pascal Hitzler
ER -
TY - CONF
T1 - Continuity of Semantic Operators in Logic Programming and their Approximation by Artificial Neural Networks.
T2 - the 26th Annual German Conference on Artificial Intelligence, KI2003
Y1 - 2003
A1 - Anthony K. Seda
A1 - Pascal Hitzler
AB - 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.
JA - the 26th Annual German Conference on Artificial Intelligence, KI2003
CY - Hamburg, Germany
ER -
TY - JOUR
T1 - Generalized Metrics and Uniquely Determined Logic Programs
JF - Theoretical Computer Science
Y1 - 2003
A1 - Anthony K. Seda
A1 - Pascal Hitzler
KW - Priess-Crampe and Ribenboim Fixed-Point Theorem
KW - Ultrametrics
AB - 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.
ER -
TY - CHAP
T1 - The Fixed-Point Theorems of Priess-Crampe and Ribenboim in Logic Programming
Y1 - 2002
A1 - Anthony K. Seda
A1 - Pascal Hitzler
ER -
TY - JOUR
T1 - A "Converse" of the Bananch Contraction Mapping Theorem
JF - Journal of Electrical Engineering
Y1 - 2001
A1 - Pascal Hitzler
A1 - Anthony K. Seda
KW - Banach contraction
KW - Banach contraction mapping theorem
AB - 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).
ER -
TY - CONF
T1 - Semantic Operators and Fixed-Point Theory in Logic Programming
T2 - 7th International Conference on Information Systems Analysis and Synthesis (ISAS 2001)
Y1 - 2001
A1 - Anthony K. Seda
A1 - Pascal Hitzler
AB - 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.
JA - 7th International Conference on Information Systems Analysis and Synthesis (ISAS 2001)
CY - Orlando, Florida, USA
ER -
TY - JOUR
T1 - Unique Supported-Model Classes of Logic Programs
JF - Information
Y1 - 2001
A1 - Anthony K. Seda
A1 - Pascal Hitzler
KW - denotational semantics
KW - logic programming
KW - supported-model semantics
AB - 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.
ER -
TY - CONF
T1 - Classes of Logic Programs which Possess Unique Supported Models.
T2 - Classes of Logic Programs which Possess Unique Supported Models.
Y1 - 2000
A1 - Anthony K. Seda
A1 - Pascal Hitzler
AB - 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].
JA - Classes of Logic Programs which Possess Unique Supported Models.
ER -
TY - CONF
T1 - On the Coincidence of Semantics for Uniquely Determined Programs
T2 - On the Coincidence of Semantics for Uniquely Determined Programs
Y1 - 2000
A1 - Anthony K. Seda
A1 - Pascal Hitzler
AB - 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.
JA - On the Coincidence of Semantics for Uniquely Determined Programs
ER -
TY - JOUR
T1 - Dislocated Topologies
Y1 - 2000
A1 - Pascal Hitzler
A1 - Anthony K. Seda
KW - Banach contraction
KW - topologies
AB - 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.
ER -
TY - ABST
T1 - Dislocated Topologies
Y1 - 2000
A1 - Pascal Hitzler
A1 - Anthony Seda
A1 - Anthony K. Seda
AB - 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.
ER -
TY - CONF
T1 - A New Fixed-point Theorem for Logic Programming Semantics
T2 - SCI2000 and ISAS2000
Y1 - 2000
A1 - Anthony K. Seda
A1 - Pascal Hitzler
AB - 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.
JA - SCI2000 and ISAS2000
CY - Orlando, Florida, USA
ER -
TY - ABST
T1 - A Topological View of Acceptability
Y1 - 2000
A1 - Anthony K. Seda
A1 - Pascal Hitzler
ER -
TY - CONF
T1 - Acceptable Programs Revisited
Y1 - 1999
A1 - Anthony K. Seda
A1 - Pascal Hitzler
KW - 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
AB - 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.
PB - Workshop on Verification in Logic Programming, 16th International Conference on Logic Programming (ICLP'99),
ER -
TY - CONF
T1 - A Characterization of Acceptability
T2 - A Characterization of Acceptability
Y1 - 1999
A1 - Anthony K. Seda
A1 - Pascal Hitzler
JA - A Characterization of Acceptability
ER -
TY - CONF
T1 - Characterizations of Classes of Programs by Three-valued Operators
T2 - Characterizations of Classes of Programs by Three-valued Operators
Y1 - 1999
A1 - Anthony K. Seda
A1 - Pascal Hitzler
AB - 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.
JA - Characterizations of Classes of Programs by Three-valued Operators
ER -
TY - CONF
T1 - Multivalued Mappings, Fixed-Point Theorems and Disjunctive Databases
Y1 - 1999
A1 - Anthony K. Seda
A1 - Pascal Hitzler
AB - 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.
PB - Electronic Workshops in Computing, British Computer Society
ER -
TY - JOUR
T1 - Some Issues Concerning Fixed-Points in Computational Logic: Quasi-Metrics, Multivalued Mappings and the Knaster-Tarski Theorem
JF - Topology Proceedings
Y1 - 1999
A1 - Anthony K. Seda
A1 - Pascal Hitzler
KW - fixed points
KW - Knaster Tarski and Kleene theorems
KW - multivalued mappings
AB - 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.
ER -
TY - CONF
T1 - Strictly Level-Decreasing Logic Programs
Y1 - 1998
A1 - Anthony K. Seda
A1 - Pascal Hitzler
AB - 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.
PB - the Second Irish Workshop on Formal Methods
ER -