BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260914T105725Z
UID:Seminar-dept-481@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20191126T130000
DTEND:20191126T140000
SUMMARY:School Seminar Series
DESCRIPTION:Dr. Filip Mazowiecki: The Reachability Problem for Petri Nets is Not Elementary\n\nPetri 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 published upper bound is the non-primitive recursive Ackermannian bound of Leroux and Schmitz from LICS 2019. 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.\n\n\n\nJoint work with Wojciech Czerwiński, Sławomir Lasota, Ranko Lazić and Jérôme Leroux.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=481
LOCATION:Ashton Lecture Theater
END:VEVENT
END:VCALENDAR