Chapter 3
Topology and Logic Programming
In this chapter, we consider the role of topology in logic programming semantics. There is a considerable history of topology being used in computer
science in general, much of it stemming from the role of the Scott topology in
domain theory and in conventional programming language semantics. However, topological methods have been employed in a number of other areas
of importance in computing, including digital topology in image processing,
software engineering, and the use of metric spaces in concurrency, for example. In addition, topological methods and ideas have been used in foundational investigations via the topology of observable properties of M.B. Smyth,
see [Smyth, 1992]. Again, Blair et al. have made considerable use of convergence spaces in unifying discrete and continuous models of computation
and, hence, in providing models for hybrid systems. Indeed, these authors,
see [Blair et al., 1999] and [Blair and Remmel, 2001], for example, view any
model of computation in which there is a notion of evolving state as a dynamical system. Such models of computation include, of course, Turing machines, finite state machines, logic programs, neural networks, etc. On the
other hand, convergence spaces, as already noted earlier, provide a very general framework in which to study convergence and continuity, either by means
of nets or by filters, and include topologies as a special case. It is shown in
[Blair et al., 1999] and [Blair and Remmel, 2001] that the execution traces of
a dynamical system can be realized as those solutions of a certain type of
constraint on a convergence space that yield continuous instances of the constraint. This work provides a foundation for hybrid systems. Furthermore, the
papers [Blair et al., 1997a, Blair et al., 1997b, Blair, 2007, Blair et al., 2007]
give many other interesting applications of ideas of a dynamical systems and
analytical nature to the theory of computation, including logic programming
in particular.
Here, we want to explore the role of topology in finding models for logic
programs and its role as a foundational framework for logic programming
semantics.
1 Thus, our focus is the study of topologies and their properties
on spaces I(X, T ) of interpretations, and we work with general truth sets
T wherever possible, only imposing conditions as appropriate and necessary.
There are two main topologies which we discuss in this chapter and which have
1 The thesis [Ferry, 1994] and the paper [Heinze, 2003] contain results concerning the
characterization in topological terms of the various standard models for logic programs
discussed in Chapter 2.
65
Topology and Logic Programming
In this chapter, we consider the role of topology in logic programming semantics. There is a considerable history of topology being used in computer
science in general, much of it stemming from the role of the Scott topology in
domain theory and in conventional programming language semantics. However, topological methods have been employed in a number of other areas
of importance in computing, including digital topology in image processing,
software engineering, and the use of metric spaces in concurrency, for example. In addition, topological methods and ideas have been used in foundational investigations via the topology of observable properties of M.B. Smyth,
see [Smyth, 1992]. Again, Blair et al. have made considerable use of convergence spaces in unifying discrete and continuous models of computation
and, hence, in providing models for hybrid systems. Indeed, these authors,
see [Blair et al., 1999] and [Blair and Remmel, 2001], for example, view any
model of computation in which there is a notion of evolving state as a dynamical system. Such models of computation include, of course, Turing machines, finite state machines, logic programs, neural networks, etc. On the
other hand, convergence spaces, as already noted earlier, provide a very general framework in which to study convergence and continuity, either by means
of nets or by filters, and include topologies as a special case. It is shown in
[Blair et al., 1999] and [Blair and Remmel, 2001] that the execution traces of
a dynamical system can be realized as those solutions of a certain type of
constraint on a convergence space that yield continuous instances of the constraint. This work provides a foundation for hybrid systems. Furthermore, the
papers [Blair et al., 1997a, Blair et al., 1997b, Blair, 2007, Blair et al., 2007]
give many other interesting applications of ideas of a dynamical systems and
analytical nature to the theory of computation, including logic programming
in particular.
Here, we want to explore the role of topology in finding models for logic
programs and its role as a foundational framework for logic programming
semantics.
1 Thus, our focus is the study of topologies and their properties
on spaces I(X, T ) of interpretations, and we work with general truth sets
T wherever possible, only imposing conditions as appropriate and necessary.
There are two main topologies which we discuss in this chapter and which have
1 The thesis [Ferry, 1994] and the paper [Heinze, 2003] contain results concerning the
characterization in topological terms of the various standard models for logic programs
discussed in Chapter 2.
65