Structural liveness of Petri nets is ExpSpace-hard and decidable

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Structural liveness of Petri nets is ExpSpace-hard and decidable

Popis výsledku v původním jazyce

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).

Název v anglickém jazyce

Structural liveness of Petri nets is ExpSpace-hard and decidable

Popis výsledku anglicky

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).

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA18-11193S" target="_blank" >GA18-11193S: Algoritmy pro diskrétní systémy a hry s nekonečně mnoha stavy</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2019

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

ACTA INFORMATICA

ISSN

0001-5903

e-ISSN

—

Svazek periodika

56

Číslo periodika v rámci svazku

6

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

16

Strana od-do

537-552

Kód UT WoS článku

000480462800004

EID výsledku v databázi Scopus

2-s2.0-85068843548