Blackboard Seminar


In biweekly sessions, a topic of the lecturer's current interest is presented. In particular, still unpublished or unfinished works can be discussed.

In order to be able to focus on details and to not have to leave out difficult proofs, the talks should be given in an informal manner using a blackboard or whiteboard. A main concern is that questions should be treated where they appear.

There is no predefined set of topics, as the talks follow the research areas of the participants. The next topic is fixed in the previous session.

Time and Place

  • The talks take place in the seminar room of the Chair of Computer Science 7 every second Tuesday at 10:30 a.m.
  • There is a public calendar for the seminar with information about the next talk at
  • We have a mailing list for the seminar to inform the participants about the following talks. Please, contact us if you wish your email address to be included in the list.

Next talk

Strategy Composition in Compositional Games
Marcus Gelderie
Tuesday, January 22, 2012, 10:30h

Abstract: When solving games played on finite arenas, the arena is given explicitly as part of the input. This explicit representation hides the underlying structure of the arena and prevents from exploiting this structure when solving the game. We study games where the global arena is a product of several smaller, local arenas. We investigate how these "global games" can be solved by playing "local games" on the local arenas. To this end, we introduce two kinds of products of arenas. Moreover, we define a suitable notion of strategy composition and show how, for the first notion of product, strategies in reachability and Büchi games can be composed from strategies in games on the local arenas. An investigation of the complexity of solving the global game shows that our approach cannot yield a similar result for the second notion of product.

Past talks

  • Upper bounds for Choiceless Polynomial-Time
    Wied Pakusa
    Tuesday, January 15, 2012, 10:30h
  • Solving Parity Games Quickly
    Roman Rabinovich
    Tuesday, December 18, 2012, 10:30h
  • Synthesis of Structured Reactive Programs
    Benedikt Brütsch
    Tuesday, November 26, 2012, 10:30h
  • A lower bound for the existential k-pebble game
    Christoph Berkholz
    Tuesday, November 13, 2012, 10:30h
  • A Max-Flow Generalization of the Shannon Switching Game
    Paul Bonsma
    Tuesday, October 30, 2012, 10:30h
  • Tree width (Part II)
    Roman Rabinovich
    Monday, October 22, 2012, 13:00h
  • Tree width
    Roman Rabinovich
    Monday, October 8, 2012, 13:00h
  • A logical characterization of rational relations
    Nans Lefebvre
    Monday, July 20, 2012, 13:00h
  • The Composition Method Reviewed Part II
    Ingo Felscher
    Monday, July 30, 2012, 13:00h
  • The Composition Method Reviewed
    Ingo Felscher
    Monday, July 23, 2012, 13:00h
  • Strategy Machines and their Complexity, Part II
    Marcus Gelderie
    Monday, July 16, 2012, 13:00h
  • Models for Interaction under Partial Information
    Bernd Puchala
    Monday, July 9, 2012, 13:00h
  • Strategy Machines and their Complexity
    Marcus Gelderie
    Monday, July 2, 2012, 13:00h
  • Regularity Test for Deterministic omega-Pushdown Languages
    Stefan Repke
    Monday, June 25, 2012, 13:00h
  • An Introduction to Linear Logic
    Nans Lefebvre
    Monday, June 18, 2012, 13:00h
  • History Deterministic Automata
    Christof Löding
    Wednesday, June 13, 2012, 15:00h
  • Synthesis of Distributed Reactive Systems from omega-Regular Trace Langauges
    Namit Chaturvedi
    Tuesday, June 5, 2012, 14:00h
  • Monotonicity in Cops and Robber Games
    Roman Rabinovich
    Wednesday, May 30, 2012, 14:00h
  • Omega-Automatic Boolean Algebras
    Faried Abu Zaid
    Wednesday, May 9, 2012, 14:00h
  • Quantitative MSO
    Simon Leßenich
    Wednesday, May 2, 2012, 14:00h
  • Weisfeiler-Lehman for Groups
    Wied Pakusa
    Wednesday, April 25, 2012, 14:00h
  • Tutorial on Complexity Measures for Directed Graphs
    Roman Rabinovich
    Wednesday, April 18, 2012, 14:00h
  • Graph Searching Games with Multiple Robbers and Imperfect Information
    Bernd Puchala
    Wednesday, April 11, 2012, 14:00h
  • The Field of Reals is not omega-Automatic
    Faried Abu Zaid
    Tuesday, April 3, 2012, 14:00h
  • Counter Games and Imperfect Recall
    Simon Leßenich
    Monday, March 26, 2012, 13:00h
  • Directed Graphs of Entanglement Two
    Roman Rabinovich
    Tuesday, March 20, 2012, 13:00h


Simon Lessenich, Roman Rabinovich