http://www.dagstuhl.de/08271

29. Juni – 04. Juli 2008, Dagstuhl Seminar 08271

Topological and Game-Theoretic Aspects of Infinite Computations

Organisatoren

Peter Hertling (Universität der Bundeswehr – München, DE)
Victor Selivanov (A. P. Ershov Institute – Novosibirsk, RU)
Wolfgang Thomas (RWTH Aachen, DE)
Bill Wadge (University of Victoria, CA)
Klaus W. Wagner (Universität Würzburg, DE)

Auskunft zu diesem Dagstuhl Seminar erteilt

Dagstuhl Service Team

Dokumente

Dagstuhl Seminar Proceedings DROPS
Teilnehmerliste
Dagstuhl's Impact: Dokumente verfügbar

Summary

The theory of the infinite behaviour of continuously operating computing devices is of primary importance for several branches of theoretical and practical computer science. In particular, it is fundamental for the verification and synthesis of reactive systems like microprocessors or operating systems, for the understanding of data ow computation, and for the development of adequate mathematical foundations for exact real computation. The seminar brought together researchers from many different disciplines who are working on theoretical or practical aspects of infinite computations. In this summary we describe the topics, the goals, and the contributions of the seminar.

The theory of infinite computations develops different classifications of the corresponding mathematical objects, for example, languages of infinite words or trees as in automata theory, filters which transform infinite streams in dataflow computation, or functions on infinite words as in computability in analysis.

The study of computability with infinite objects, unlike that with finite objects, is intimately related to topology. It makes essential use of such classification tools as hierarchies as in descriptive set theory, reducibilities as in computability theory, and infinite games with perfect information. In the development of this area, ideas and techniques from different fields were employed, e.g. from topology, logic, game theory, Wadge reducibility, and domain theory. This work has produced, in particular, an impressive theory of the specification and verification of reactive systems, which is developing rapidly and is already of practical importance for the computer industry.

Despite the tight connections with several branches of mathematics, researchers from the cited fields often work independently and from time to time rediscover notions and techniques that have been used already in another field. The idea of this seminar is to bring together researchers from different fields, ranging from pure mathematics (descriptive set theory, domain theory, logic, symbolic dynamics) to theoretical and applied computer science (automata theory, computability in analysis, model checking), who work on topological and game-theoretic aspects of infinite computations, using similar notions and tools. The goal of the proposed seminar is to stimulate their work and establish ways for future cooperation and synergy. For example, while the theory of automata over infinite words already has direct applications in the theory of specification and synthesis of reactive systems, it would be very interesting to establish such direct applications also for the theory of infinite games.

The seminar was attended by 35 people from various scientific areas related to the topics of the seminar: by people working in computability, topology, descriptive set theory, automata theory, game theory, and by people working on applications in verification and synthesis of reactive systems and stream computations. In fact, many participants are working in several of these areas and presented results connecting two or more of these areas. There were 5 overview talks of fifty minutes each and 26 contributed talks of thirty minutes each. Besides that, there were many discussions among smaller groups of people.

Classification

  • Data Structures / Algorithms / Complexity
  • Verification / Logic

Keywords

  • Automata theory
  • Computability in analysis
  • Dataflow computation
  • Hierarchies
  • Infinite computations
  • Infinite games with perfect information
  • Reactive systems
  • Specification and verification
  • Topological complexity
  • Wadge reducibility.

Buchausstellung

Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.