# Sixth International Workshop on Computability and Complexity in Analysis

## Scope

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

• 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)

## Organizing Committee

• 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),

## 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
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

Some participants of CCA 2004

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

## Submissions

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.

## Registration

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.

## Venue

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.