Structural liveness of Petri nets is ExpSpace-hard and decidable
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989592%3A15310%2F19%3A73595313" target="_blank" >RIV/61989592:15310/19:73595313 - isvavai.cz</a>
Result on the web
<a href="https://link.springer.com/article/10.1007/s00236-019-00338-6" target="_blank" >https://link.springer.com/article/10.1007/s00236-019-00338-6</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00236-019-00338-6" target="_blank" >10.1007/s00236-019-00338-6</a>
Alternative languages
Result language
angličtina
Original language name
Structural liveness of Petri nets is ExpSpace-hard and decidable
Original language description
Place/transition Petri nets are a standard model for a class of distributed systems whose reachability spaces might be infinite. One of well-studied topics is verification of safety and liveness properties in this model; despite an extensive research effort, some basic problems remain open, which is exemplified by the complexity status of the reachability problem that is still not fully clarified. The liveness problems are known to be closely related to the reachability problem, and various structural properties of nets that are related to liveness have been studied. Somewhat surprisingly, the decidability status of the problem of determining whether a net is structurally live, i.e. whether there is an initial marking for which it is live, remained open for some time; e.g. Best and Esparza (Inf Process Lett 116(6):423-427, 2016. 10.1016/j.ipl.2016.01.011) emphasize this open question. Here we show that the structural liveness problem for Petri nets is ExpSpace-hard and decidable. In particular, given a net N and a semilinear set S, it is decidable whether there is an initial marking of N for which the reachability set is included in S; this is based on results by Leroux (28th annual ACM/IEEE symposium on logic in computer science, LICS 2013, New Orleans, LA, USA, June 25-28, 2013, IEEE Computer Society, pp 23-32, 2013. 10.1109/LICS.2013.7).
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA18-11193S" target="_blank" >GA18-11193S: Algorithms for Infinite-State Discrete Systems and Games</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
ACTA INFORMATICA
ISSN
0001-5903
e-ISSN
—
Volume of the periodical
56
Issue of the periodical within the volume
6
Country of publishing house
DE - GERMANY
Number of pages
16
Pages from-to
537-552
UT code for WoS article
000480462800004
EID of the result in the Scopus database
2-s2.0-85068843548