April 21 – 25 , 1997, Dagstuhl Seminar 9717

Computability and Complexity in Analysis


Ker-I Ko (Stony Brook), A. Nerode (Cornell), K. Weihrauch (Hagen)

For support, please contact

Dagstuhl Service Team


External Homepage
Dagstuhl's Impact: Documents available
Dagstuhl-Seminar-Report 176


The seminar “Computability and Complexity in Analysis” was held in Dagstuhl from April 21 to 25, 1997. It was attended by 43 computer scientists, mathematicians and logicians who are interested in the diverse areas of computational analysis. The 33 talks presented here represented many different theories and approaches in this topic.

In the foundational study, they included constructive analysis (of E. Bishop), recursive analysis, type-2 theory of effectivity and the domaintheoretic approach. Classical theories on real-valued functions have been extended to more general functional spaces. Specific problems in computable analysis, such as the Riemann mapping theorem and problems in calculus of variations, have also been presented. In the complexity study, a number of talks were about the modifications and comparisons of three different models: Turing machine-based complexity theory, information-based complexity theory (IBC) and real RAM-based complexity theory (BSS). More practical issues, including interval analysis, automatic result verification, bounded-value problem, on-line computation and geometric and stochastic modelling, were also presented.

Dagstuhl Seminar Series


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.