RUS  ENG
Full version
JOURNALS // Modelirovanie i Analiz Informatsionnykh Sistem // Archive

Model. Anal. Inform. Sist., 2020 Volume 27, Number 2, Pages 234–253 (Mi mais715)

This article is cited in 1 paper

Discrete mathematics in relation to computer science

On the approximation of the resource equivalences in Petri nets with the invisible transitions

V. A. Bashkin

P. G. Demidov Yaroslavl State University, 14 Sovetskaya, Yaroslavl 150003, Russia

Abstract: Two resources (submarkings) are called similar if in any marking any one of them can be replaced by another one without affecting the observable behavior of the net (regarding marking bisimulation). It is known that resource similarity is undecidable for general labelled Petri nets. In this paper we study the properties of the resource similarity and resource bisimulation (a subset of complete similarity relation closed under transition firing) in Petri nets with invisible transitions (where some transitions may be labelled with an invisible label ($\tau$) that makes their firings unobservable for an external observer). It is shown that for a proper subclass ($p$-saturated nets) the resource bisimlation can be effectively checked. For a general class of Petri net with invisible transitions it is possible to construct a sequence of so-called $(n, m)$-equivalences approximating the largest $\tau$-bisimulation of resources.

Keywords: resource, equivalence, Petri nets, invisible transitions, approximation.

UDC: 519.7

MSC: 68Q85

Received: 27.04.2020
Revised: 18.05.2020
Accepted: 20.05.2020

Language: English

DOI: 10.18255/1818-1015-2020-2-234-253



© Steklov Math. Inst. of RAS, 2025