20. – 25. August 2006, Dagstuhl-Seminar 06341

Computational Structures for Modelling Space, Time and Causality


Ralph Kopperman (City University of New York, US)
Prakash Panangaden (McGill University – Montreal, CA)
Michael B. Smyth (Imperial College London, GB)
Dieter Spreen (Universität Siegen, DE)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Dagstuhl Seminar Proceedings DROPS
Dagstuhl's Impact: Dokumente verfügbar


Topological notions and methods have been successfully applied in various areas of computer science. Image processing, programming language semantics and exact computing with real numbers and vectors in Banach spaces are important examples. Computerized geometric constructions have many applications in engineering and physics. The seminar concentrated on computational structures for modelling space, time and causality, which are basic in these applications. Special emphasis was given to connections with physics.

Due to the digital nature of computation, such structures differ from the mathematical structures they model, based on the continuum, that are classically used in these fields. Their typical features include a graph-based digital framework useful in computing algorithms, and also feature asymmetry and partiality. The classical spaces contain only the ideal elements that are the result of a completed computation (approximation) process which involves algorithms based on moving between points (for which a graph structure is used). But spaces that also allow reasoning about such processes in a formal way must contain the partial (and finite) objects appearing during a computation as well, and must consider a limiting process. Only the partial and finite objects can be observed in finite time. The leading example of such a structure is the domain (in Scott's sense). Here, the finitely observable properties of a process are the primary objects of study. The ideal entities which are the only elements considered in classical mathematical structures are obtained as derived objects via the limiting relationship. By a continuous model of a classical space we usually mean a domain, perhaps with additional structure such as a measurement or partial metric to represent the original space, as the subspace of maximal points. This gives a handle on the computational aspects of the classical space.

This, from a computational perspective, is some of the motivation for developing alternative models, in which a partial ordering (of the approximation of ideal elements by partial or finite ones) is fundamental.

What is remarkable is that very similar order-theoretic models are being developed for (apparently) entirely different reasons in theoretical physics.

The singlarity theorems e.g. show that in classical general relativity the basic geometric assumptions break down (singularities develop) so one seeks alternatives: Ashtekar's quantum geometry, string theory or Sorkin's causets.

Rafael Sorkin and his collaborator in combinatorics, Graham Brightwell, working in a program towards quantum gravity where the causal structure is taken as fundamental, use causal sets as basic structure, which are nothing more than locally finite partial orders. Keye Martin and Prakash Panangaden showed that globally hyperbolic spacetimes (studied in Kronheimer and Penrose's 1967 classic, "On the structure of causal spaces'', Proc. Camb. Phil. Soc. 63, 481--501) are special continuous domains.

There are several consequences of the work of Martin and Panangaden. The topology of the spacetime manifold can be reconstructed from the causal structure; indeed from a countable dense subset of the spacetime. The result relates the areas of domain theory in computing and causality in physics, and provides new tools for deriving results relevant to quantum gravity, but it is only a beginning and much needs to be done.

In most work in physics of the kind just mentioned, one views space (or space-time) as a continuous manifold. But by using domains, we gain a clearer view of ideas derived from computer science being applied in the direction of physics.

There are reasons for wanting to consider also discrete models of space and time. Philosophically quantum mechanics suggests that one should look to discrete structures rather than continuum structures. There are no experiments that can probe arbitrarily deeply into the structure of spacetime (as that would require unboundedly high energies) so there can never be any experimental support for a true continuum.

We can now compare causal sets and other event structures with process models in computer science, so that posets and graphs will figure extensively in``discrete'' models.

\smallskip After very successful predecessor seminars in 2000, 2002 and 2004, the seminar in 2006 was the fourth in this series of Dagstuhl seminars which aim to bring together people working in fields like domain theory, topology, geometry, formal topology, and now causal spaces in physics, and to foster interaction between them. A further goal has always been to encourage communication and, hopefully, collaboration between computer scientists and those mathematicians and now physicists who work on similar problems but from a different perspective and who, often, are not aware of what their work has in common.

IWe are actively looking for people in more fields that involve related ideas of digital approximation of continuous structures.

This time the seminar attracted 49 participants representing 16 countries and 5 continents, among them 8 young researchers working for their master or PhD. The atmosphere was very friendly, but discussions were most lively. During the breaks and until late at night, participants also gathered in smaller groups for continuing discussions, communicating new results and exchanging ideas. Again the seminar led to several new research contacts, collaborations, and at least one successful application for a new Dagstuhl seminar.

As with the seminars in 2000 and 2004, the participants are again invited to submit a full paper for a special issue of Theoretical Computer Science.

The great success of the seminar is not only due to the participants, but also to all the staff members, both in Saarbrücken and Dagstuhl, who always do a great job in making everything run in such an efficient and smooth way. Our thanks go to both groups!


  • Geometry
  • Topology
  • Domains
  • Approximation By Finite T0-spaces
  • Closure Spaces
  • Logic
  • Causal Sets
  • Order-theoretic And Generalized Metric Models
  • Quantum Gravity
  • General Relativity


  • Mathematical structures in computer science
  • Interdisciplinary: computer science and physics
  • Verification / logic
  • Semantics / formal methods


In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.