04. – 09. Juni 2000, Dagstuhl Seminar 00231
Topology in Computer Science: Constructivity; Asymmetry and Partiality; Digitization
R. Kopperman (New York), M. Smyth (London), D. Spreen (Siegen)
Auskunft zu diesem Dagstuhl Seminar erteilt
Topological notions and methods have successfully been applied in various areas of computer science. The seminar we propose will concentrate on the following aspects: constructivity, asymmetry and partiality, and digitization. These key words not only describe the main line of present-day research in computer science oriented topology, but also reflect the various features in which topological spaces used in computer science applications differ from those classically studied in mathematics.
In great part, topological research in computer science originates from work on the formal description of programming language semantics and on automated program verification. Because of this connection constructive (effective) approaches to the theory of semantic domains and the relation of such domains to logic have been considered from the very beginning.
Nowadays this work is continued in research on Effective Topologies, Locale Theory and Formal Topologies. In studies on Formal Topology the theories of Scott domains and of metric spaces (especially the real numbers) are developed in the framework of higher-order formal intuitionistic logic.
- Asymmetry and Partiality
Both notions are characteristic for topological spaces used in computer science, as opposed to those considered in classical mathematics. Typically, a space considered in theory of computation is a space of partially defined objects which represent stages of some computation process. As a result of this, given two points, in general only one of them is separable from the other by an observable (or positive) property: whenever a (partial) object satisfies such a property, then also every more fully defined object must satisfy it. Thus a topology based on such properties can satisfy only very weak separation axioms. In the usual spaces coming from applications in analysis or physics, however, two points can symmetrically be separated by a pair of disjoint properties. In other words, the spaces are at least Hausdorff.
In recent years, early ideas of Scott and Weihrauch/Schreiber to embed the real numbers or, more generally, metric spaces in suitable Scott domains formed by intervals or spheres, respectively, have been taken up again. The program is to develop an important part of analysis starting with domains which contain not only the real numbers, but also their "unsharp" approximations. In this way one will come up with data structures and algorithms for numerical computations that are superior to those based on floating point representation and arithmetic.
Another line of research which is characterized by the above notions is the work on generalized metrics and quasi uniform spaces. By relaxing the classical requirements for a metric space categories of spaces are defined that contain Scott domains as well as metric spaces. Both types of spaces are used in giving meaning to certain programming language constructs. As has been shown this approach not only leads to a unified theory to be used in programming language semantics, but also allows the study of quantitative aspects of computations, which is impossible when dealing merely with Scott domains.
This draws attention to the digital nature of most computer applications. Starting from classical applications in physics, most topological notions have been developed by having the continuum in mind. In computer science applications they very often turn out to be no longer applicable in their classical form, or even to be meaningless, which means that they have to be redefined. Work done here is also basic to the other subfields of topology in computer science.
Obviously, all aspects mentioned above are strongly intertwined. The research trends characterized hereby originate from the same applications and basic studies. Moreover, most researchers in the field work on several of the subfields reported above.
There has been much work on the above mentioned aspects of topology in computer science in recent years, and substantial results have been obtained. But this work is, for the most part, scattered around in various conferences (e.g. the Workshop on Mathematical Foundations of Program Semantics, Workshop on Domains, logic meetings, Northeastern Conference on Topological Methods in Computer Science, and conferences on General Topology and its Applications). It is the goal of the workshop to create a common forum for the exchange of ideas and results.
Moreover, it is our aim to encourage communication and, hopefully, collaboration between computer scientists and those mathematicians who work on similar problems but from a different perspective and who, often, are not aware of the computer science motivations.