88
Mathematical Aspects of Logic Programming Semantics
Remark We refer the reader to the paper [Seda and Hitzler, 2010] for a
discussion of many recent and fairly recent applications of distance functions to various parts of computer science. The areas in question range from
conventional semantics ([Arnold and Nivat, 1980b, Arnold and Nivat, 1980a,
Bukatin and Scott, 1997, O’Neill, 1996, Smyth, 1992]) and the study of concurrency ([de Bakker and de Vink, 1996, Reed et al., 1991]) to domain theory
([K¨ unzi et al., 2006, Kr¨ otzsch, 2006, Martin, 2000, Waszkiewicz, 2003]) to information theory, cognitive processes and unique fingerprinting of time series
([Albeverio et al., 1999, Khrennikov, 1998, Khrennikov, 2004, Murtagh, 2004,
Murtagh, 2005]) to abstract interpretation ([Crazzolara, 1997]) to complexity and and its connections with semantics ([Castro-Company et al., 2007,
Romaguera and Schellekens, 2003, Rodr´ ıguez-L´ opez et al., 2008]), to neuralsymbolic integration ([Bader et al., 2006, Hitzler et al., 2004, Seda, 2006]),
to measuring the distance between programs in software engineering
([Bukatin, 2002, Seda and Lane, 2003]), through to bioinformatics and the
properties of p-adic numbers of DNA sequences and degeneracy of genetic
codes ([Dragovich and Dragovich, 2006, Khrennikov and Kozyrev, 2007]), and
beyond.
4.1 Distance Functions in General
At a completely general level, a distance function d defined on a set X is
simply a mapping d : X × X → A, where A is some suitable set of values
(a distance set or value set), and the distance between x and y is taken to
be the element d(x, y) of A. Second, and again at a completely general level,
the related notion of closeness can be defined by assigning to each element
x of a set X a family U x of subsets U of X; then y can be thought of as
close to x if y belongs to some element U of U x . These notions are somewhat
dual to each other, even synonymous, as we shall see shortly. However, the
present level of generality is too high to be useful, and therefore we will impose
a variety of restrictions as we proceed.
2 In fact, it is our intention to begin
by briefly considering a uniform, conceptual framework, namely, continuity
spaces,
3 within which all the particular distance functions we encounter can be
described. Indeed, this framework is such that the notions of distance function
and closeness are actually dual to each other when the set U x is taken, for
each x ∈ X, to be the neighbourhood base of x, as defined in the Appendix,
2 [Waszkiewicz, 2002] contains a very general study of spaces based on the notion of
distance function.
3 Our treatment of continuity spaces follows [Kopperman, 1988] closely. We refer also
to [Flagg and Kopperman, 1997] and related papers, where the notion of continuity space
has been developed further in a number of directions, and to [K¨ unzi, 2001] for further
background.
Mathematical Aspects of Logic Programming Semantics
Remark We refer the reader to the paper [Seda and Hitzler, 2010] for a
discussion of many recent and fairly recent applications of distance functions to various parts of computer science. The areas in question range from
conventional semantics ([Arnold and Nivat, 1980b, Arnold and Nivat, 1980a,
Bukatin and Scott, 1997, O’Neill, 1996, Smyth, 1992]) and the study of concurrency ([de Bakker and de Vink, 1996, Reed et al., 1991]) to domain theory
([K¨ unzi et al., 2006, Kr¨ otzsch, 2006, Martin, 2000, Waszkiewicz, 2003]) to information theory, cognitive processes and unique fingerprinting of time series
([Albeverio et al., 1999, Khrennikov, 1998, Khrennikov, 2004, Murtagh, 2004,
Murtagh, 2005]) to abstract interpretation ([Crazzolara, 1997]) to complexity and and its connections with semantics ([Castro-Company et al., 2007,
Romaguera and Schellekens, 2003, Rodr´ ıguez-L´ opez et al., 2008]), to neuralsymbolic integration ([Bader et al., 2006, Hitzler et al., 2004, Seda, 2006]),
to measuring the distance between programs in software engineering
([Bukatin, 2002, Seda and Lane, 2003]), through to bioinformatics and the
properties of p-adic numbers of DNA sequences and degeneracy of genetic
codes ([Dragovich and Dragovich, 2006, Khrennikov and Kozyrev, 2007]), and
beyond.
4.1 Distance Functions in General
At a completely general level, a distance function d defined on a set X is
simply a mapping d : X × X → A, where A is some suitable set of values
(a distance set or value set), and the distance between x and y is taken to
be the element d(x, y) of A. Second, and again at a completely general level,
the related notion of closeness can be defined by assigning to each element
x of a set X a family U x of subsets U of X; then y can be thought of as
close to x if y belongs to some element U of U x . These notions are somewhat
dual to each other, even synonymous, as we shall see shortly. However, the
present level of generality is too high to be useful, and therefore we will impose
a variety of restrictions as we proceed.
2 In fact, it is our intention to begin
by briefly considering a uniform, conceptual framework, namely, continuity
spaces,
3 within which all the particular distance functions we encounter can be
described. Indeed, this framework is such that the notions of distance function
and closeness are actually dual to each other when the set U x is taken, for
each x ∈ X, to be the neighbourhood base of x, as defined in the Appendix,
2 [Waszkiewicz, 2002] contains a very general study of spaces based on the notion of
distance function.
3 Our treatment of continuity spaces follows [Kopperman, 1988] closely. We refer also
to [Flagg and Kopperman, 1997] and related papers, where the notion of continuity space
has been developed further in a number of directions, and to [K¨ unzi, 2001] for further
background.