Fifth Workshop on
Computability and Complexity in Analysis

July 12-13, 2002, Málaga, Spain

The fifth workshop on Computability and Complexity in Analysis will take place in Málaga as a satellite workshop of ICALP 2002, the 29th International Colloquium on Automata, Languages, and Programming (which will be held on July 8-13).


The workshop 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 after a long period of slow development has seen rapid growth in recent years. Newcomers can find introductions in the books by Pour-El/Richards, Ko, and Weihrauch.

Until recently, most work in computability and complexity concentrated on problems over discrete structures, and many computer scientists do not know much about computable real functions. Maybe, for this reason problems including real number computation have been neglected, avoided or even ignored by the majority of computer scientists.

Although still many even basic questions are unsettled, meanwhile a rich toolkit has been developed for numerous applications of computer science requiring real number computation like image processing, computational geometry, dynamical systems, hybrid systems and, last but not least, numerical mathematics and scientific computation. ICALP participants will have an excellent opportunity to get up-to-date information about this exciting and important but not yet widely known field of research.

Program Committee

Peter Hertling (Hagen, Germany)
Ker-I Ko (Stony Brook, USA)
Marian Pour-El (Minnesota , USA)
Ludwig Staiger (Halle-Wittenberg, Germany)
John V. Tucker (Swansea, Wales)
Klaus Weihrauch, chair (Hagen, Germany)
Mariko Yasugi (Kyoto Sangyo, Japan)
Xizhong Zheng (Cottbus, Germany)
Ning Zhong (Cincinnati, USA)

Organizing Committee

Vasco Brattka (Hagen, Germany)
Matthias Schröder (Hagen, Germany)


As part of the workshop a demonstration of systems for exact real computation will be organized by

Norbert Müller (Trier, Germany)

Some participants of CCA 2002


July 12
9:00 Opening
9:05 Iraj Kalantari and Larry Welch
Recursive Quantum Functions, Avoidable Points, & Shadow Points in Recursive Analysis
9:30 Joseph S. Miller
Effectiveness for Embedded Spheres and Balls
9:55 Xizhong Zheng, Robert Rettinger, and Burchard von Braunmühl
Effectively Absolute Continuity and Effective Jordan Decomposability
10:20 Mariko Yasugi and Yoshiki Tsujii
Two Notions of Sequential Computability of a Function with Jumps
10:45 Coffee break
11:15 Hideki Tsuiki
Representations of Complete Uniform Spaces via Uniform Domains
11:40 Robert Rettinger and Klaus Weihrauch
The Computational Complexity of Some Julia Sets
12:05 Break
12:10 Peter Hertling
A Comparison of Certain Representations of Regularly Closed Sets
12:35 Matthias Schröder
A Natural Weak Limit Space with Admissible Representation which is not a Limit Space
13:00 Lunch
15:00 Simon Langley and Daniel Richardson
What can we do with a Solution?
15:25 Zilin Du, Maria Eleftheriou, José Moreira, and Chee Yap
Hypergeometric Functions in Exact Geometric Computation
15:50 Break
16:00 Ali Asghar Khanban, Abbas Edalat, and André Lieutier
Computability of Partial Delaunay Triangulation and Voronoi Diagram
16:25 Norbert Th. Müller
Real Numbers and BDDs
16:50 Coffee break
17:10 Demonstration of Systems for Exact Real Computation
July 13
10:00 Rod G. Downey, Denis R. Hirschfeldt, André Nies, and Frank Stephan
Trivial Reals
10:25 Rod G. Downey and Evan J. Griffiths
Schnorr Randomness
10:50 Coffee Break
11:20 George Barmpalias
On 0'-computable Reals
11:45 Margarita V. Korovina
Fixed Points on the Real Numbers without Equality Test
12:10 Vasco Brattka
Computing Uniform Bounds
12:35 Klaus Weihrauch and Ning Zhong
The Solution Operator of the Korteweg-de Vries Equation is Computable
13:00 Closing

Several talks with CCA related topics will be presented at ICALP, see ICALP Accepted Papers.


The workshop proceedings have been published in the Elsevier series ENTCS:

Electronic Notes in Theoretical Computer Science, Volume 66, Issue 1, 2002.

Hardcopies have been made available during the workshop.

Call for Papers

Here is a PostScript version (removed) and a PDF version (removed) of the third Call for Papers.
And here is the workshop postcard.

Start |  Introduction |  Members |  Events |  Links
© 2001-2002 Vasco Brattka, FernUniversität Hagen