Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 06341

Computational Structures for Modelling Space, Time and Causality

( Aug 20 – Aug 25, 2006 )

(Click in the middle of the image to enlarge)

Please use the following short url to reference this page:



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!

  • Samy Abbes (University of Maryland - College Park, US)
  • Samson Abramsky (University of Oxford, GB) [dblp]
  • Ingo David Battenfeld (University of Edinburgh, GB)
  • Ulrich Berger (Swansea University, GB) [dblp]
  • Howard Blair (Syracuse University, US)
  • Jens Blanck (Swansea University, GB) [dblp]
  • Richard Blute (University of Ottawa, CA)
  • Vasco Brattka (University of Cape Town, ZA) [dblp]
  • Douglas Bridges (University of Canterbury - Christchurch, NZ)
  • Fredrik Dahlgren (Uppsala University, SE)
  • Manfred Droste (Universität Leipzig, DE) [dblp]
  • Martín H. Escardó (University of Birmingham, GB) [dblp]
  • Lisbeth Fajstrup (Aalborg University, DK) [dblp]
  • Reinhold Heckmann (AbsInt - Saarbrücken, DE) [dblp]
  • Peter Hines (University of York, GB)
  • Weng Kin Ho (University of Birmingham, GB)
  • Fangping Huang (Sichuan University - Chengdu, CN)
  • Michael Huth (Imperial College London, GB) [dblp]
  • Achim Jung (University of Birmingham, GB) [dblp]
  • Klaus Keimel (TU Darmstadt, DE) [dblp]
  • Ralph Kopperman (City University of New York, US)
  • Martin Kovar (Brno University of Technology, CZ)
  • Vladik Kreinovich (University of Texas - El Paso, US) [dblp]
  • Hans-Peter Albert Künzi (University of Cape Town, ZA) [dblp]
  • Jimmie D. Lawson (Louisiana State University - Baton Rouge, US) [dblp]
  • Steve G. Matthews (University of Warwick - Coventry, GB)
  • Dag Normann (University of Oslo, NO)
  • Prakash Panangaden (McGill University - Montreal, CA) [dblp]
  • John L. Pfaltz (University of Virginia - Charlottesville, US)
  • Timothy Porter (Bangor University, GB)
  • Ian Pratt-Hartmann (University of Manchester, GB) [dblp]
  • Martin Raussen (Aalborg University, DK) [dblp]
  • Joel Ravelomanantsoa-Ratsimihah (University of Cape Town, ZA)
  • Giovanni Sambin (University of Padova, IT)
  • Matthias Schröder (Universität Siegen, DE) [dblp]
  • Victor Selivanov (Pedagogical University - Novosibirsk, RU) [dblp]
  • Alex Simpson (University of Edinburgh, GB) [dblp]
  • Josef Slapal (Brno University of Technology, CZ)
  • Michael B. Smyth (Imperial College London, GB)
  • Dieter Spreen (Universität Siegen, DE) [dblp]
  • John Stell (University of Leeds, GB)
  • Sumati Surya (Raman Research Institute - Bangalore, IN)
  • Paul Taylor (University of Manchester, GB) [dblp]
  • Hideki Tsuiki (Kyoto University, JP)
  • Peter Ullrich (TU München, DE)
  • Steven J. Vickers (University of Birmingham, GB) [dblp]
  • Bill Wadge (University of Victoria, CA) [dblp]
  • Klaus Weihrauch (FernUniversität in Hagen, DE) [dblp]
  • Guo-Qiang Zhang (Case Western Reserve University - Cleveland, US)

  • 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