29. Juni – 04. Juli 2008, Dagstuhl Seminar 08271
Topological and Game-Theoretic Aspects of Infinite Computations
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
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.
- Data Structures / Algorithms / Complexity
- Verification / Logic
- Automata theory
- Computability in analysis
- Dataflow computation
- Infinite computations
- Infinite games with perfect information
- Reactive systems
- Specification and verification
- Topological complexity
- Wadge reducibility.