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 01461

Computability and Complexity in Analysis

( Nov 11 – Nov 16, 2001 )

Please use the following short url to reference this page:



This Dagstuhl seminar is concerned with the theory of computability and complexity over the real numbers which is built on the Turing machine model. This theory was initiated by Turing, Grzegorczyk, Lacombe, Banach and Mazur, and has seen a rapid growth in recent years. Recent monographs are by Pour-El/Richards, Ko, and Weihrauch.

Computability theory and complexity theory are two central areas of research in theoretical computer science. Until recently, most work in these areas concentrated on problems over discrete structures. In the last years, though, there has been an enormous growth of computability theory and complexity theory over the real numbers and other continuous structures. One of the reasons for this phenomenon is that more and more practical computation problems over the real numbers are being dealt with by computer scientists, for example, in computational geometry, in the modelling of dynamical and hybrid systems, but also in classical problems from numerical mathematics. The scientists working on these questions come from different fields, such as theoretical computer science, domain theory, logic, constructive mathematics, computer arithmetic, numerical mathematics, analysis etc.

The Dagstuhl seminar provides a unique opportunity for people from such diverse areas to meet and exchange ideas and knowledge. One of the topics of interest is foundational work concerning the various models and approaches for defining or describing computability and complexity over the real numbers. We also hope to gain new insights into the computability--theoretic side of various computational questions from physics as well as from other fields involving computations over the real numbers. This, of course, also requires the extension of existing computability notions to more general classes of objects. Other topics of interest are complexity--theoretic investigations, both foundational and with respect to concrete problems. Last but not least, new implementations of exact real arithmetic and further developments of already existing software packages will be of interest.

  • Götz Alefeld (KIT - Karlsruher Institut für Technologie, DE)
  • Klaus Ambos-Spies (Universität Heidelberg, DE) [dblp]
  • George Barmpalias (University of Leeds, GB) [dblp]
  • Andrej Bauer (University of Ljubljana, SI) [dblp]
  • Jens Blanck (Swansea University, GB) [dblp]
  • Markus Bläser (Universität des Saarlandes, DE) [dblp]
  • Vasco Brattka (University of Cape Town, ZA) [dblp]
  • Douglas Bridges (University of Canterbury - Christchurch, NZ)
  • Douglas Cenzer (University of Florida - Gainesville, US)
  • Rodney Downey (Victoria University of Wellington, NZ) [dblp]
  • Martín H. Escardó (University of Birmingham, GB) [dblp]
  • Tobias Gärtner (Universität des Saarlandes, DE)
  • Magne Haveraaen (University of Bergen, NO)
  • Armin Hemmerling (Universität Greifswald, DE) [dblp]
  • Peter Hertling (Universität der Bundeswehr - München, DE) [dblp]
  • Denis R. Hirschfeldt (University of Chicago, US) [dblp]
  • Elham Kashefi (Imperial College London, GB) [dblp]
  • Ulrich Kohlenbach (TU Darmstadt, DE) [dblp]
  • Michal Konecny (University of Edinburgh, GB) [dblp]
  • Margarita Korovina (A. P. Ershov Institute - Novosibirsk, RU) [dblp]
  • Marko Krznaric (Imperial College London, GB)
  • Oleg V. Kudinov (Sobolev Institute of Mathematics - Novosibirsk, RU) [dblp]
  • David Lester (University of Manchester, GB)
  • Peter Lietz (TU Darmstadt, DE)
  • Klaus Meer (University of Southern Denmark - Odense, DK) [dblp]
  • Joseph S. Miller (University of Connecticut - Storrs, US) [dblp]
  • Takakazu Mori (Kyoto-Sangyo University, JP)
  • Norbert T. Müller (Universität Trier, DE) [dblp]
  • Dag Normann (University of Oslo, NO)
  • Paulo Oliva (Queen Mary University of London, GB) [dblp]
  • Robert Rettinger (FernUniversität in Hagen, DE) [dblp]
  • Matthias Schröder (University of Edinburgh, GB) [dblp]
  • Peter M. Schuster (LMU München, DE) [dblp]
  • Victor Selivanov (Pedagogical University - Novosibirsk, RU) [dblp]
  • Olha Shkaravska (Materialise Ukraine - Kiew, UA)
  • Alex Simpson (University of Edinburgh, GB) [dblp]
  • Dimiter Skordev (University of Sofia, BG)
  • Bas Spitters (Radboud University Nijmegen, NL) [dblp]
  • Ludwig Staiger (Universität Halle-Wittenberg, DE)
  • Izumi Takeuti (Kyoto University, JP)
  • Hideki Tsuiki (Kyoto University, JP)
  • Klaus Weihrauch (FernUniversität in Hagen, DE) [dblp]
  • Mariko Yasugi (Kyoto-Sangyo University, JP)
  • Atsushi Yoshikawa (Kyushu University, JP)
  • Xizhong Zheng (BTU Cottbus, DE)
  • Ning Zhong (Maebashi Institute of Technology, JP)
  • Martin Ziegler (Universität Paderborn, DE) [dblp]

Related Seminars
  • Dagstuhl Seminar 9717: Computability and Complexity in Analysis (1997-04-21 - 1997-04-25) (Details)
  • Dagstuhl Seminar 99461: Computability and Complexity in Analysis (1999-11-14 - 1999-11-19) (Details)