01322nas a2200205 4500008004100000245006400041210006400105300001200169520071800181653002700899653002500926653002200951653001700973653002000990653001301010653001801023100002201041700002001063856003301083 2010 eng d00aGeneralized Distance Functions in the Theory of Computation0 aGeneralized Distance Functions in the Theory of Computation a443-4643 aWe 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.10adenotational semantics10afixed-point theorems10alogic programming10astable model10asupported model10atopology10aultra-metrics1 aSeda, Anthony, K.1 aHitzler, Pascal uhttp://knoesis.org/node/161900326nam a2200097 4500008004100000245005600041210005600097100002200153700002000175856003300195 2010 eng d00aMathematical Aspects of Logic Programming Semantics0 aMathematical Aspects of Logic Programming Semantics1 aSeda, Anthony, K.1 aHitzler, Pascal uhttp://knoesis.org/node/209701137nas a2200133 4500008004100000245011300041210006900154260002100223300001200244520067200256100002200928700002000950856003300970 2003 eng d00aContinuity of Semantic Operators in Logic Programming and their Approximation by Artificial Neural Networks.0 aContinuity of Semantic Operators in Logic Programming and their aHamburg, Germany a105-1193 aOne 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.1 aSeda, Anthony, K.1 aHitzler, Pascal uhttp://knoesis.org/node/120401332nas a2200145 4500008004100000245006300041210006300104300001200167520086300179653005201042653001701094100002201111700002001133856003301153 2003 eng d00aGeneralized Metrics and Uniquely Determined Logic Programs0 aGeneralized Metrics and Uniquely Determined Logic Programs a187-2193 aThe 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.10aPriess-Crampe and Ribenboim Fixed-Point Theorem10aUltrametrics1 aSeda, Anthony, K.1 aHitzler, Pascal uhttp://knoesis.org/node/163600364nas a2200097 4500008004100000245008100041210006900122100002200191700002000213856003300233 2002 eng d00aThe Fixed-Point Theorems of Priess-Crampe and Ribenboim in Logic Programming0 aFixedPoint Theorems of PriessCrampe and Ribenboim in Logic Progr1 aSeda, Anthony, K.1 aHitzler, Pascal uhttp://knoesis.org/node/204600979nas a2200145 4500008004100000245006000041210005600101300000800157520053100165653002300696653003900719100002000758700002200778856003300800 2001 eng d00aA "Converse" of the Bananch Contraction Mapping Theorem0 aConverse of the Bananch Contraction Mapping Theorem a3-63 aWe 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).10aBanach contraction10aBanach contraction mapping theorem1 aHitzler, Pascal1 aSeda, Anthony, K. uhttp://knoesis.org/node/163101133nas a2200133 4500008004100000245006700041210006600108260002600174300001200200520071200212100002200924700002000946856003300966 2001 eng d00aSemantic Operators and Fixed-Point Theory in Logic Programming0 aSemantic Operators and FixedPoint Theory in Logic Programming aOrlando, Florida, USA a224-2293 aWe 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.1 aSeda, Anthony, K.1 aHitzler, Pascal uhttp://knoesis.org/node/118900973nas a2200157 4500008004100000245005300041210005200094300001200146520050300158653002700661653002200688653003000710100002200740700002000762856003300782 2001 eng d00aUnique Supported-Model Classes of Logic Programs0 aUnique SupportedModel Classes of Logic Programs a295-3023 aWe 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.10adenotational semantics10alogic programming10asupported-model semantics1 aSeda, Anthony, K.1 aHitzler, Pascal uhttp://knoesis.org/node/163701563nas a2200109 4500008004100000245006900041210006800110520120000178100002201378700002001400856003301420 2000 eng d00aClasses of Logic Programs which Possess Unique Supported Models.0 aClasses of Logic Programs which Possess Unique Supported Models3 aLogic 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].1 aSeda, Anthony, K.1 aHitzler, Pascal uhttp://knoesis.org/node/118501259nas a2200109 4500008004100000245006900041210006200110520090200172100002201074700002001096856003301116 2000 eng d00aOn the Coincidence of Semantics for Uniquely Determined Programs0 aCoincidence of Semantics for Uniquely Determined Programs3 aWe 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.1 aSeda, Anthony, K.1 aHitzler, Pascal uhttp://knoesis.org/node/118801055nas a2200133 4500008004100000245002600041210002600067520071500093653002300808653001500831100002000846700002200866856003300888 2000 eng d00aDislocated Topologies0 aDislocated Topologies3 aWe 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.10aBanach contraction10atopologies1 aHitzler, Pascal1 aSeda, Anthony, K. uhttp://knoesis.org/node/163001023nas a2200121 4500008004100000245002600041210002600067520071500093100002000808700001800828700002200846856003300868 2000 eng d00aDislocated Topologies0 aDislocated Topologies3 aWe 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.1 aHitzler, Pascal1 aSeda, Anthony1 aSeda, Anthony, K. uhttp://knoesis.org/node/192801255nas a2200133 4500008004100000245006200041210005900103260002600162300001200188520084600200100002201046700002001068856003301088 2000 eng d00aA New Fixed-point Theorem for Logic Programming Semantics0 aNew Fixedpoint Theorem for Logic Programming Semantics aOrlando, Florida, USA a418-4233 aWe 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.1 aSeda, Anthony, K.1 aHitzler, Pascal uhttp://knoesis.org/node/118600292nas a2200097 4500008004100000245004000041210003800081100002200119700002000141856003300161 2000 eng d00aA Topological View of Acceptability0 aTopological View of Acceptability1 aSeda, Anthony, K.1 aHitzler, Pascal uhttp://knoesis.org/node/192901279nas a2200133 4500008004100000245003400041210003400075260011700109520076200226653008200988100002201070700002001092856003301112 1999 eng d00aAcceptable Programs Revisited0 aAcceptable Programs Revisited bWorkshop on Verification in Logic Programming, 16th International Conference on Logic Programming (ICLP'99),3 aAcceptable 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.10al and o and g and i and c and and p and r and o and g and r and a and m and s1 aSeda, Anthony, K.1 aHitzler, Pascal uhttp://knoesis.org/node/179900292nas a2200097 4500008004100000245004000041210003800081100002200119700002000141856003300161 1999 eng d00aA Characterization of Acceptability0 aCharacterization of Acceptability1 aSeda, Anthony, K.1 aHitzler, Pascal uhttp://knoesis.org/node/118301050nas a2200109 4500008004100000245007100041210006900112520068400181100002200865700002000887856003300907 1999 eng d00aCharacterizations of Classes of Programs by Three-valued Operators0 aCharacterizations of Classes of Programs by Threevalued Operator3 aSeveral 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.1 aSeda, Anthony, K.1 aHitzler, Pascal uhttp://knoesis.org/node/118401805nas a2200121 4500008004100000245007300041210006900114260006400183520136100247100002201608700002001630856003301650 1999 eng d00aMultivalued Mappings, Fixed-Point Theorems and Disjunctive Databases0 aMultivalued Mappings FixedPoint Theorems and Disjunctive Databas bElectronic Workshops in Computing, British Computer Society3 aIn 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.1 aSeda, Anthony, K.1 aHitzler, Pascal uhttp://knoesis.org/node/180201399nas a2200157 4500008004100000245013100041210006900172300001200241520083200253653001701085653003901102653002501141100002201166700002001188856003301208 1999 eng d00aSome Issues Concerning Fixed-Points in Computational Logic: Quasi-Metrics, Multivalued Mappings and the Knaster-Tarski Theorem0 aSome Issues Concerning FixedPoints in Computational Logic QuasiM a223-2503 aMany 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.10afixed points10aKnaster Tarski and Kleene theorems10amultivalued mappings1 aSeda, Anthony, K.1 aHitzler, Pascal uhttp://knoesis.org/node/162901158nas a2200121 4500008004100000245004500041210004400086260004800130520078300178100002200961700002000983856003301003 1998 eng d00aStrictly Level-Decreasing Logic Programs0 aStrictly LevelDecreasing Logic Programs bthe Second Irish Workshop on Formal Methods3 aWe 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.1 aSeda, Anthony, K.1 aHitzler, Pascal uhttp://knoesis.org/node/1801