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.

**Andrej Bauer**(Ljubljana, Slovenia)**Vasco Brattka**, chair (Hagen, Germany)**Abbas Edalat**(London, UK)**Armin Hemmerling**(Greifswald, Germany)**Peter Hertling**(Duisburg-Essen, Germany)**Ker-I Ko**(Stony-Brook, USA)**Ulrich Kohlenbach**(Aarhus, Denmark)**Vladik Kreinovich**(El Paso, USA)**Matthias Schröder**(Edinburgh, UK)**Hideki Tsuiki**(Kyoto, Japan)**John V. Tucker**(Swansea, UK)**Klaus Weihrauch**(Hagen, Germany)**Xizhong Zheng**(Cottbus, Germany)**Ning Zhong**(Cincinnati, USA)

**Ludwig Staiger**, chair (Halle-Wittenberg, Germany),**Sibylle Schwarz**(Halle-Wittenberg, Germany),**Ramona Vahrenhold**(Halle-Wittenberg, Germany),**Renate Winter**(Halle-Wittenberg, Germany),**René Mazala**(Halle-Wittenberg, Germany),

**Vasco Brattka**

On the Borel Complexity of Hahn-Banach Extensions

**Mark Braverman**

Hyperbolic Julia Sets are Poly-Time Computable

**Douglas Bridges and Luminita Vîta**

A General Constructive Proof Technique

**Arthur W. Chou and Ker-I Ko**

On the Complexity of Finding Paths in a Two-Dimensional Domain II: Piecewise Straight-Line Paths

**Abbas Edalat, Dirk Pattinson and André Lieutier**

Domain Theory and Multi-Variable Calculus

**Armin Hemmerling**

Hierarchies of Function Classes Defined by the First-Value Operator

**Hiroyasu Kamo**

Effective Dini's Theorem on Effectively Compact Metric Spaces

**Akitoshi Kawamura**

Type-2 Computability and Moore's Recursive Functions

**Robert Kenny**

Orbit Complexity and Entropy for Group Endomorphisms

**Daren Kunkle and Matthias Schröder**

Some Examples of Non-Metrizable Spaces Allowing a Simple Type-2 Complexity Theory

**Branimir Lambov**

Rates of Convergence of Recursively Defined Sequences

**Alexander Raichev**

Relative Randomness and Real Closed Fields

**Robert Rettinger**

A Fast Algorithm for Julia Sets of Hyperbolic Rational Functions

**Victor L. Selivanov**

Variations on Wadge Reducibility

**Izumi Takeuti**

Transition System over Continuous Time-Space

**Yoshiki Tsujii, Mariko Yasugi and Takakazu Mori**

Sequential Computability of a Function -Diagonal Computability and Limiting Recursion-

**Klaus Weihrauch und Ning Zhong**

An Algorithm for Computing Fundamental Solutions

**Yongcheng Wu and Klaus Weihrauch**

A computable Version of the Daniell-Stone Theorem on Integration and Linear Functionals

**Xizhong Zheng and Robert Rettinger**

On the Turing Degrees of Divergence Bounded Computable Reals

Some participants of CCA 2004

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

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

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.

**Vasco Brattka**: or**Ludwig Staiger**: .