TOP
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
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 08271

Topological and Game-Theoretic Aspects of Infinite Computations

( Jun 29 – Jul 04, 2008 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/08271

Organizers




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.


Participants
  • Veronica Becher (University of Buenos Aires, AR) [dblp]
  • Dietmar Berwanger (ENS - Cachan, FR) [dblp]
  • Julian Bradfield (University of Edinburgh, GB) [dblp]
  • Vasco Brattka (University of Cape Town, ZA) [dblp]
  • Jeremie Cabessa (Univesity of Lausanne, CH)
  • Olivier Carton (University Paris-Diderot, FR) [dblp]
  • Jacques Duparc (University of Lausanne, CH) [dblp]
  • Olivier Finkel (ENS - Lyon, FR) [dblp]
  • Chrysida Galanaki (University of Athens, GR)
  • Serge Grigorieff (University of Paris VII, FR) [dblp]
  • Peter Hertling (Universität der Bundeswehr - München, DE) [dblp]
  • Lukasz Kaiser (RWTH Aachen, DE) [dblp]
  • Vassilis Kountouriotis (University of Athens, GR)
  • Oleg V. Kudinov (Sobolev Institute of Mathematics - Novosibirsk, RU) [dblp]
  • Dietrich Kuske (TU Ilmenau, DE) [dblp]
  • Blanca Mancilla (UNSW - Sydney, AU)
  • Steve G. Matthews (University of Warwick - Coventry, GB)
  • Filip Murlak (University of Warsaw, PL) [dblp]
  • Damian Niwinski (University of Warsaw, PL) [dblp]
  • Jean-Eric Pin (University of Paris VII, FR) [dblp]
  • Nir Piterman (University of Leicester, GB) [dblp]
  • John Plaice (UNSW - Sydney, AU) [dblp]
  • Alexander Rabinovich (Tel Aviv University, IL) [dblp]
  • Panos Rondogiannis (University of Athens, GR)
  • Matthias Schröder (Universität der Bundeswehr - München, DE) [dblp]
  • Victor Selivanov (A. P. Ershov Institute - Novosibirsk, RU) [dblp]
  • Pierre Simonnet (Université de Corse, FR)
  • Ludwig Staiger (Martin-Luther-Universität Halle-Wittenberg, DE)
  • Wolfgang Thomas (RWTH Aachen, DE) [dblp]
  • Michael Ummels (RWTH Aachen, DE) [dblp]
  • Bill Wadge (University of Victoria, CA) [dblp]
  • Klaus W. Wagner (Universität Würzburg, DE)
  • Klaus Weihrauch (FernUniversität in Hagen, DE) [dblp]
  • Anton Zhukov (Pedagogical University - Novosibirsk, RU)
  • Martin Ziegler (TU Darmstadt, DE) [dblp]

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.