Fifth Workshop on
Computability and Complexity in Analysis
July 1213, 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 813).
Aim
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 PourEl/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
uptodate information about this exciting and
important but not yet widely known field
of research.
Program Committee
Peter Hertling (Hagen, Germany)
KerI Ko (Stony Brook, USA)
Marian PourEl (Minnesota , USA)
Ludwig Staiger (HalleWittenberg, 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)
Demonstration
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
Program
Friday 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

Saturday 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 Kortewegde Vries Equation is Computable 
13:00 
Closing

Several talks with CCA related topics will be presented at ICALP, see
ICALP Accepted Papers.
Proceedings
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.
