Campus Event Calendar
Event Entry
What and Who
The Reachability Problem for Vector Addition Systems is Not Elementary
Wojciech Czerwiński
University of Warsaw
SWS Colloquium
Wojciech Czerwiński is an assistant professor (pol. adiunkt) at the Institute of Informatics, Faculty of Mathematics, Informatics and Mechanics of the University of Warsaw. His interests include automata and logic, more concretely infinite state systems and separability problems.
AG 1, AG 2, AG 3, INET, AG 4, AG 5, SWS, RG1, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 22 November 2018
16:00
60 Minutes
G26
111
Kaiserslautern
Abstract
I will present a recent non-elementary lower bound for the complexity of reachability problem for Vector Addition Systems. I plan to show the main insights of the proof. In particular I will present a surprising equation on fractions, which is the core of the new source of hardness found in VASes.
Contact
Susanne Girard
--email hidden
Video Broadcast
Yes
Saarbrücken
E1 5
029
passcode not visible
logged in users only
Susanne Girard, 10/12/2018 15:30 -- Created document.