Arbeitsgemeinschaft Logik und Automaten

Vorträge im Wintersemester 2009/2010

The covering and boundedness problems for branching vector addition systems

Donnerstag, 28. Januar 2010, 11:45 Uhr, Seminarraum Informatik 7 (Raum 4116)

  Marcin Jurdzinski
University of Warwick, UK


Covering, boundedness and reachability are three fundamental problems for vector addition systems (VAS). In 1976, Lipton established that they are EXPSPACE-hard for VAS (or equivalently, for Petri nets). The lower bound was matched by Rackoff two years later, when he showed that covering and boundedness are in EXPSPACE. Although reachability was proved decidable for VAS by Meyer and Kosaraju several years later, little else is known about its complexity. For branching vector addition systems (BVAS), an intriguing novel model of computation, not even decidability of reachability is known yet. However, covering and boundedness were shown decidable in 2005 by Verma and Goubault-Larrecq. We show that their complexity for BVAS is 2EXPTIME.

Joint work with Stephane Demri, Ranko Lazic, and Oded Lachish.

Nash equilibria for reachability objectives in concurrent and timed games

Dienstag, 2. Februar 2010, 14:00 Uhr, Seminarraum Informatik 7 (Raum 4116)

  Nicolas Markey
ENS Cachan


We consider multi-player concurrent games and propose a generic (but non-effective) procedure to compute qualitative Nash equilibria for reachability objectives. We apply this procedure to finite concurrent games and to timed games, and obtain algorithms whose complexities we prove are optimal.