Resource Bisimilarity in Petri Nets is Decidable
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Resource Bisimilarity in Petri Nets is Decidable
Original language description
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.
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
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2022
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
FUNDAMENTA INFORMATICAE
ISSN
0169-2968
e-ISSN
1875-8681
Volume of the periodical
186
Issue of the periodical within the volume
1-4
Country of publishing house
PL - POLAND
Number of pages
20
Pages from-to
175-194
UT code for WoS article
000850446500011
EID of the result in the Scopus database
2-s2.0-85138774633