Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 9318

Descriptional Complexity: A Multidisciplinary Perspective

( May 03 – May 07, 1993 )

Please use the following short url to reference this page:

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

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.

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