Sixth International Workshop on Computability and Complexity in Analysis
August 16-20, 2004, Lutherstadt Wittenberg, Germany
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
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
.
Submission deadline: May 3, 2004 Notification: June 7, 2004 Camera-ready versions: July 5, 2004
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.
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.
