Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:The complexity of reachability in vector addition systems
Speaker:Sylvain Schmitz
coming from:École Normale Supérieure Paris-Saclay
Speakers Bio:Sylvain Schmitz is an assistant professor (maître de conférences) at École Normale Supérieure Paris-Saclay since 2008 and a junior member of Institut Universitaire de France since 2018. He received his Ph.D. degree in Computer Science from Université Nice-Sophia Antipolis in 2007 and his habilitation from École Normale Supérieure Paris-Saclay in 2017. His research interests are in logic, verification, and complexity.
Event Type:SWS Colloquium
Visibility:D1, D2, D3, INET, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Friday, 5 April 2019
Time:14:00
Duration:60 Minutes
Location:Saarbrücken
Building:G26
Room:111
Abstract
The last few years have seen a surge of decision problems with an astronomical, non primitive-recursive complexity, in logic, verification, and games. While the existence of such uncontrived problems is known since the early 1980s, the field has matured with techniques for proving complexity lower and upper bounds and the definition of suitable complexity classes. This framework has been especially successful for analysing so-called `well-structured systems'---i.e., transition systems endowed with a well-quasi-order, which underly most of these astronomical problems---, but it turns out to be applicable to other decision problems that resisted analysis,
including two famous problems: reachability in vector addition systems and bisimilarity of pushdown automata. In this talk, I will explain how some of these techniques apply to reachability in vector addition
systems, yielding tight Ackermannian upper bounds for the decomposition algorithm initially invented by Mayr, Kosaraju, and Lambert; this will be based on joint work with Jérôme Leroux.
Contact
Name(s):Mouna Litz
Video Broadcast
Video Broadcast:YesTo Location:Kaiserslautern
To Building:E1 5To Room:029
Meeting ID:SWS Space 2 (6312)
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
Created:
Mouna Litz/MPI-SWS, 03/28/2019 09:28 AM
Last modified:
Uwe Brahm/MPII/DE, 04/05/2019 07:01 AM
  • Mouna Litz, 03/28/2019 10:31 AM
  • Mouna Litz, 03/28/2019 09:34 AM -- Created document.