The Reachability Problem for Petri Nets Is Not Elementary
- Submitting institution
-
The University of Warwick
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 12780
- Type
- D - Journal article
- DOI
-
10.1145/3422822
- Title of journal
- Journal of the ACM
- Article number
- 7
- First page
- 1
- Volume
- 68
- Issue
- 1
- ISSN
- 0004-5411
- Open access status
- Compliant
- Month of publication
- December
- Year of publication
- 2020
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
4
- Research group(s)
-
T - Theory and Foundations
- Citation count
- -
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- The preliminary version won a Best Paper Award at STOC'19, one of the two top conferences in theoretical computer science. This research introduced novel techniques for accurate multiplication of fractions and simulation of zero tests in Petri nets, and combined them to make the first breakthrough on the lower bound for the central reachability problem since Lipton's 1976 work, disrupting the area by disproving the long-held exponential-space completeness conjecture. It led to invited conference keynotes (LICS'20 and ICALP'20 jointly, FSTTCS'19, Highlights'19, MFCS'19), invited seminar presentations (over 10, including Edinburgh, Manchester, TU Munich, Oxford, Paris-Saclay), and an ERC Starting Grant (950398).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -