FOM: workshop on computability and complexity in analysis

Stephen G Simpson simpson at
Fri Jun 14 09:45:02 EDT 2002

 From: Vasco Brattka <Vasco.Brattka at>
 Subject:      CCA 2002 Program
 Date:         Fri, 14 Jun 2002 15:32:34 +0200


    C  C  A
    2 0 0 2

    Fifth Workshop on
    Computability and Complexity in Analysis

    July 12-13, 2002, Malaga, Spain

    Call for Participation


    The fifth workshop on Computability and Complexity in Analysis
    will take place in Malaga 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

    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.


    Preliminary Program

    Friday, July 12

     9:00 Opening

     9:05 Iraj Kalantari
	  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, Burchard von Braunmühl
	  Effectively Absolute Continuity Does Not Imply Effective Jordan

    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 ufb-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, Jose 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 Delaunay Triangulation and Voronoi Diagram

    16:25 Norbert 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 Korteweg-de Vries Equation is Computable

    13:00 Closing

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


    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.

    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) vasco.brattka at
    Matthias Schroeder     (Hagen, Germany) matthias.schroeder at


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

    Norbert Mueller       (Trier, Germany)  mueller at


    cca at



    Participants should register via the ICALP registration webpage, see
    Registration for CCA 2002 does not require a registration for ICALP 2002.
    Hotels can be booked via the webpage as well.

More information about the FOM mailing list