May 3 – 7 , 1993, Dagstuhl Seminar 9318

Descriptional Complexity: A Multidisciplinary Perspective


R. Book, E.P.D. Pednault, D. Wotschke

For support, please contact

Dagstuhl Service Team


Dagstuhl-Seminar-Report 63

Goals of this Dagstuhl Seminar

Descriptional complexity is a highly multidisciplinary field, with contributions being made in theoretical computer science, artificial intelligence, statistics, information theory, physics, perceptual psychology, and neurophysiology. However, research efforts in these areas have historically been isolated from each other by disciplinary boundaries. There has been relatively little interdisciplinary interaction and exchange of results despite the fact that the origins of descriptional complexity date back over 30 years.

The purpose of this seminar was to improve interdisciplinary interaction by encouraging such interaction among a small group of leading scientists from several disciplines. The seminar programm included tutorial presentations on the issues each group is addressing, presentations of recent research results, moderated discussions, and many informal discussions as are customary in the conducive Dagstuhl atmoshpere. Through stimulating interactions among the participants we hope to have promoted future interdisciplinary interactions in the field as a whole.

The midterm and longterm goals of this Dagstuhl seminar can thus be summarized as follows:

  1. To promote research in all aspects of descriptional complexity through conferences, publications, and more informal means of scientific interaction;
  2. To promote interaction and the exchange of information across traditional discipline boundaries;
  3. To provide a point of contact for all researchers in all disciplines interested in descriptional complexity and its applications.

In order to achieve the above goals, this Dagstuhl seminar focussed on the following:

  1. Generalized descriptional complexity measures and their properties, inc1ud~ ing resource-bounded complexity, structural complexity, hierarchical complexity, trade-offs in succinctness and the complexity of sets, languages, grammars, automata, etc.;
  2. Algorithmic and other descriptional theories of randomness;
  3. The use of descriptional randomness and associated descriptional complexity measures in computational complexity, economy of description, cryptography, information theory, probability, and statistics;
  4. Descriptional complexity measures for inductive inference and prediction and the use of these measures in machine learning, computational learning theory, computer vision, pattern recognition, statistical inference, and neural networks.


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.