D-CON 2019

In 2019, the annual D-CON meeting of German scientists working in the area of Concurrency Theory will take place on the 14th and 15th of March at TU Munich. For information on previous editions of D-CON, see the website of the GI working group Concurrency Theory.

The meeting is organized by the Department of Computer Science, Chair for Foundations of Software Reliability and Theoretical Computer Science, Prof. Javier Esparza.

Dates

  • Workshop: March 14-15, 2019.

  • Informal dinner: Pizzeria "Bei Mario", Adalbertstraße 15 in the center of Munich - March 13, 2019, 19:00h.

  • Dinner: Garchinger Augustiner - March 14, 2019, 19:00h.

Schedule

The time schedule for D-CON 2019 is available in PDF format under the following link: dcon2019-schedule.pdf

Call for Contributions

We invite researchers in the area of Concurrency Theory for contributions to D-CON 2019. If you like to present your most-recent work, organize a discussion or breakout session, give a tutorial or whatever else comes to your mind, please send an email, including a title and a short abstract, to . The deadline for proposals is December 15th.

Invited Speakers

Filip Mazowiecki, University of Bordeaux - The Reachability Problem for Petri Nets is Not Elementary

Petri nets, also known as vector addition systems, are a long established and widely used model of concurrent processes. The complexity of their reachability problem is one of the most prominent open questions in the theory of verification. That the reachability problem is decidable was established by Mayr in his seminal STOC 1981 work, and the currently best upper bound is non-primitive recursive cubic-Ackermannian of Leroux and Schmitz from LICS 2015. We show that the reachability problem is not elementary. Until this work, the best lower bound has been exponential space, due to Lipton in 1976.

Joint work with Wojciech Czerwiński, Sławomir Lasota, Ranko Lazić and Jérôme Leroux.

Karoliina Lehtinen, University of Liverpool - Quasi-polynomial automata for playing with parity games.

Parity games are infinite two-player games, which are used in verification, automata theory, and reactive synthesis. Solving parity games -- that is, deciding which player has a winning strategy -- is one of the few problems known to be in both UP and co-UP yet not known to be in P. So far, the quest for a polynomial algorithm has lasted over 25 years.

In 2017, a major breakthrough occurred: parity games were shown to be solvable in quasi-polynomial time.

Since then, several different quasi-polynomial algorithms have been published. I will present an automata-theoretic quasi-polynomial solution, which relates the algorithmic complexity of parity games to the complexity of the logics and automata we use to manipulate them.

Venue

The conference will be held at the department of informatics, on the campus of TU München in Garching:

Institut für Informatik
Technische Universität München
Boltzmannstr. 3
D-85748 Garching near Munich.

The sessions take place in lecture halls HS2 and HS3, directly at the main entrance.

Arrival

Garching is located near Munich in the south-east of Germany. Munich can be reached easily by air, car and rail. You will find all arrival information for Munich on the city's website.

The campus in Garching is reachable via subway from the center of Munich: Take the subway U6 to terminal station Garching Forschungszentrum. The U6 departs every 10 mins. Travel time is 25 mins from station Marienplatz in the center of Munich.

Accomodation

An up-to-date list of hotels near Garching can be found at the webpage of Garching.

Organizers