Resource Bisimilarity in Petri Nets is Decidable
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989592%3A15310%2F22%3A73615425" target="_blank" >RIV/61989592:15310/22:73615425 - isvavai.cz</a>
Výsledek na webu
<a href="https://obd.upol.cz/id_publ/333195312" target="_blank" >https://obd.upol.cz/id_publ/333195312</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.3233/FI-222125" target="_blank" >10.3233/FI-222125</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Resource Bisimilarity in Petri Nets is Decidable
Popis výsledku v původním jazyce
Petri nets are a popular formalism for modeling and analyzing distributed systems. Tokens in Petri net models can represent the control flow state or resources produced/consumed by transition firings. We define a resource as a part (a submultiset) of Petri net markings and call two resources equivalent when replacing one of them with another in any marking does not change the observable Petri net behavior. We consider resource similarity and resource bisimilarity, two congruent restrictions of bisimulation equivalence on Petri net markings. Previously it was proved that resource similarity (the largest congruence included in bisimulation equivalence) is undecidable. Here we present an algorithm for checking resource bisimilarity, thereby proving that this relation (the largest congruence included in bisimulation equivalence that is a bisimulation) is decidable. We also give an example of two resources in a Petri net that are similar but not bisimilar.
Název v anglickém jazyce
Resource Bisimilarity in Petri Nets is Decidable
Popis výsledku anglicky
Petri nets are a popular formalism for modeling and analyzing distributed systems. Tokens in Petri net models can represent the control flow state or resources produced/consumed by transition firings. We define a resource as a part (a submultiset) of Petri net markings and call two resources equivalent when replacing one of them with another in any marking does not change the observable Petri net behavior. We consider resource similarity and resource bisimilarity, two congruent restrictions of bisimulation equivalence on Petri net markings. Previously it was proved that resource similarity (the largest congruence included in bisimulation equivalence) is undecidable. Here we present an algorithm for checking resource bisimilarity, thereby proving that this relation (the largest congruence included in bisimulation equivalence that is a bisimulation) is decidable. We also give an example of two resources in a Petri net that are similar but not bisimilar.
Klasifikace
Druh
J<sub>imp</sub> - Č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)
Návaznosti výsledku
Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2022
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ů
Údaje specifické pro druh výsledku
Název periodika
FUNDAMENTA INFORMATICAE
ISSN
0169-2968
e-ISSN
1875-8681
Svazek periodika
186
Číslo periodika v rámci svazku
1-4
Stát vydavatele periodika
PL - Polská republika
Počet stran výsledku
20
Strana od-do
175-194
Kód UT WoS článku
000850446500011
EID výsledku v databázi Scopus
2-s2.0-85138774633