Dagstuhl Seminar on
Computability and Complexity in Analysis 1999

The Seminar 99461 on Computability and Complexity in Analysis at Schloß Dagstuhl is organized by

Ker-I Ko (New York),
Anil Nerode (Cornell),
Klaus Weihrauch (Hagen).

It takes place at Schloß Dagstuhl, Wadern, Germany, November 14-19, 1999.


Already for a long time physicists, engineers, mathematicians and other scientists are spending large amounts of computing resources on computations over the real numbers. So far computer scientists deal mainly with computations over discrete, countable structures. But increasingly they too are confronted with problems involving real numbers and continuous structures (for example the complexity theoretic analysis of numerical problems, modeling of continuous or partially continuous signals and processes, hybrid systems, computation problems connected with dynamical systems, computational geometry). In order to deal with these problems one has to find effective analogues of results in classical analysis, to classify problems in the framework of computability theory, and to analyze their complexity. It also still requires a careful discussion of suitable models and work on the foundations of computability over the real numbers.

In this seminar the emphasis will be put on computable analysis which was initiated by Turing and Grzegorczyk and which is based on the Turing machine model.


  • Klaus Ambos-Spies, Universität Heidelberg, Germany,
  • Andrej Bauer, Carnegie Mellon University, Pittsburgh, USA,
    Variants of Computable Analysis and Realizability
  • Markus Bläser, Universität Bonn, Germany
  • Jens Blanck, University of Wales, Swansea, UK,
    Applications of Domain Representations
  • Vasco Brattka, FernUniversität Hagen, Germany,
    Recursive Operations over Topological Structures
  • Douglas Cenzer, University of Florida, Gainesville, USA,
    Pi-O-1 Classes in Computable Analysis
  • Abbas Edalat, Imperial College, London, UK,
    A New Foundation for Computational Geometry and Solid Modelling
  • Göran Hamrin, Uppsala University, Sweden,
  • Armin Hemmerling, Universität Greifswald, Germany,
    On Effective Metric Spaces and Representations of the Reals
  • Peter Hertling, FernUniversität Hagen, Germany,
    Nonlinear Integration Problems of High Average Complexity
  • Günter Hotz, Universität Saarbrücken, Germany,
  • Elham Kashefi, Imperial College, London, UK,
  • Ker-I Ko, SUNY at Stony Brook, USA,
  • Michal Konecny, University of Birmingham, UK
    Real Functions Finitely Computable Using Incremental Representations
  • Marco Krznaric, Imperial College, London, UK,
  • David Lester, Manchester University, UK,
    Computable Analysis and ODEs
  • Henri Lombardi, Université de Franche-Comté, France,
    Finite Approximations of Metric Spaces
  • Klaus Meer, Universität Chemnitz, Germany,
    Using Logic to Design Efficient Algorithms
  • Norbert Müller, Universität Trier, Germany,
    How to Compute Multi-Valued Funtions
  • Uwe Mylatz, Universität Lüneburg, Germany,
  • Erich Novak, Universität Erlangen, Germany,
    Lower Bounds on Discrepancy and the Complexity of Integration
  • Gero Presser, Universität Dortmund, Germany,
    Effective Subsets of Metric Spaces
  • Matthias Schröder, FernUniversität Hagen, Germany,
    An Extended Definition of Admissibility
  • Holger Schulz, Universität Siegen, Germany,
  • Dana S. Scott, Carnegie Mellon University, Pittsburgh, USA,
    A Topology for (All) Sets
  • Dieter Spreen, Universität Siegen, Germany,
    Representations Versus Numberings: Some New Results
  • Ludwig Staiger, Universität Halle-Wittenberg, Germany,
    The Kolmogorov Complexity of Real Numbers
  • Viggo Stoltenberg-Hansen, Uppsala University, Sweden,
  • John V. Tucker, University of Wales, Swansea, UK
    Abstract and Concrete Models of Computation for Topological Data Types
  • Masako Washihara, Kyoto-Sangyo University, Japan,
    Computability and Delta Function
  • Klaus Weihrauch, FernUniversität Hagen, Germany,
  • Henryk Wozniakowski, Columbia University, New York, USA,
    Upper Bounds on Discrepancy and the Complexity of Integration
  • Mariko Yasugi, Kyoto-Sangyo University, Japan,
    Function Spaces and Computability of Discontinuous Functions
  • Atsushi Yoshikawa, Kyushu University, Japan,
    Interpolation Functor and Computability
  • Xizhong Zheng, FernUniversität Hagen, Germany,
    Weakly Computable Reals Are Not Closed Under Computable Functions
  • Ning Zhong, University of Cincinnati, USA,
    Computability Theory of Distributions


Please use the following example to create the electronical version of your abstract and send your abstract to the organizers.

Start |  Introduction |  Members |  Events |  Links
© 1999 Vasco Brattka, FernUniversität Hagen