Sixth International Workshop on Computability and Complexity in Analysis

August 16-20, 2004, Lutherstadt Wittenberg, Germany



The workshop is concerned with the theory of computability and complexity over real-valued data.

Computability theory and complexity theory are two central areas of research in mathematical logic and theoretical computer science. Computability theory is the study of the limitations and abilities of computers in principle. Computational complexity theory provides a framework for understanding the cost of solving computational problems, as measured by the requirement for resources such as time and space. The classical approach in these areas is to consider algorithms as operating on finite strings of symbols from a finite alphabet. Such strings may represent various discrete objects such as integers or algebraic expressions, but cannot represent a general real or complex number, unless it is rounded.

The classical theory of computation does not deal adequately with computations that operate on real-valued data. Most computational problems in the physical sciences and engineering are of this type, such as the complexity of network flow problems and of dynamical and hybrid systems. To study these types of problem, alternative models over real-valued data and other continuous structures have been developed in recent years. Unlike the well established classical theory of computation over discrete structures, the theory of computation over continuous data is still in its infancy.

Scientists working in the area of computation on real-valued data come from different fields, such as theoretical computer science, domain theory, logic, constructive mathematics, computer arithmetic, numerical mathematics, analysis, etc. The workshop provides a unique opportunity for people from such diverse areas to meet and exchange ideas and knowledge.

The topics of interest include foundational work on various models and approaches for describing computability and complexity over the real numbers; complexity-theoretic investigations, both foundational and with respect to concrete problems; and new implementations of exact real arithmetic, as well as further developments of already existing software packages. We hope to gain new insights into computability-theoretic aspects of various computational questions from physics and from other fields involving computations over the real numbers. This will require the extension of existing computability notions to more general classes of objects.

Scientific Program Committee

Organizing Committee

Accepted Papers

  1. Vasco Brattka
    On the Borel Complexity of Hahn-Banach Extensions
  2. Mark Braverman
    Hyperbolic Julia Sets are Poly-Time Computable
  3. Douglas Bridges and Luminita Vîta
    A General Constructive Proof Technique
  4. Arthur W. Chou and Ker-I Ko
    On the Complexity of Finding Paths in a Two-Dimensional Domain II: Piecewise Straight-Line Paths
  5. Abbas Edalat, Dirk Pattinson and André Lieutier
    Domain Theory and Multi-Variable Calculus
  6. Armin Hemmerling
    Hierarchies of Function Classes Defined by the First-Value Operator
  7. Hiroyasu Kamo
    Effective Dini's Theorem on Effectively Compact Metric Spaces
  8. Akitoshi Kawamura
    Type-2 Computability and Moore's Recursive Functions
  9. Robert Kenny
    Orbit Complexity and Entropy for Group Endomorphisms
  10. Daren Kunkle and Matthias Schröder
    Some Examples of Non-Metrizable Spaces Allowing a Simple Type-2 Complexity Theory
  11. Branimir Lambov
    Rates of Convergence of Recursively Defined Sequences
  12. Alexander Raichev
    Relative Randomness and Real Closed Fields
  13. Robert Rettinger
    A Fast Algorithm for Julia Sets of Hyperbolic Rational Functions
  14. Victor L. Selivanov
    Variations on Wadge Reducibility
  15. Izumi Takeuti
    Transition System over Continuous Time-Space
  16. Yoshiki Tsujii, Mariko Yasugi and Takakazu Mori
    Sequential Computability of a Function -Diagonal Computability and Limiting Recursion-
  17. Klaus Weihrauch und Ning Zhong
    An Algorithm for Computing Fundamental Solutions
  18. Yongcheng Wu and Klaus Weihrauch
    A computable Version of the Daniell-Stone Theorem on Integration and Linear Functionals
  19. Xizhong Zheng and Robert Rettinger
    On the Turing Degrees of Divergence Bounded Computable Reals
Group Picture
Some participants of CCA 2004

Further pictures of the workshop are available (thanks to René Mazala).


Here is the current PDF version of the Program.


The workshop proceedings will be published in the Elsevier series

Electronic Notes in Theoretical Computer Science (ENTCS).

Hardcopies will be made available during the workshop. Authors are invited to submit LaTeX and PostScript versions of papers with a length of 10 to 12 pages to .

Papers have to be prepared according to the guidelines of ENTCS using the corresponding style file prentcsmacro.sty.

Submission deadline: May 3, 2004
Notification: June 7, 2004
Camera-ready versions: July 5, 2004


Participants are requested to register for the workshop until June 30, 2004 by sending an email to

Renate Winter: .

Please send name, address, expected date of arrival and departure with your email. The workshop fee of 120 Euro (including breakfast, lunch and cultural program) will be collected in cash at the conference site (no card payment possible).

A number of participants can stay in single or double rooms offered by the Academy Leucorea (the workshop venue). The room charge will be approx. 30 Euro per night (details will be given later). Please indicate in your email that you intend to make use of this offer and inform us whether you only accept a single room or wether you would agree to stay in a double room (rooms will be assigned in order of registration).

Other accomodation is available here. Any arrangements with these hotels have to be made directly.

The scientific program of the workshop will take place from Tuesday to Thursday (August 17 until August 19) with an excursion on Wednesday afternoon; Monday and Friday are considered as days of arrival and departure.

Funding Opportunities

The workshop is sponsored by the Association for Symbolic Logic (ASL). Student Travel Awards are available for student members of the ASL.


The workshop will take place in Lutherstadt Wittenberg, located at the river Elbe roughly halfway between Berlin (100 km) and Leipzig (70km). Lutherstadt Wittenberg (not to be confused with a place called "Wittenberge", also located at the river Elbe) is famous as an old German university town: in 1502 one of the first universities has been founded at this place (which now is part of the University Halle-Wittenberg). Nowadays, the historical building of the University of Wittenberg hosts the Academy Leucorea which will be the venue of our workshop. Wittenberg is called Lutherstadt ("city of Luther") since in 1517 Martin Luther declared his famous 95 theses in Wittenberg which started the process of reformation and, finally, led to the protestantic religion. Since 1508 Luther had been a professor of theology in Wittenberg. Wittenberg is part of the UNESCO world heritage. Here you can find: travelling information and a map.


For further information, please contact