maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2020-2-234-253mais-1327Research ArticleDiscrete Mathematics in Relation to Computer ScienceАппроксимация ресурсных эквивалентностей в сетях Петри с невидимыми переходамиOn the Approximation of the Resource Equivalences in Petri Nets with the Invisible Transitionshttps://orcid.org/0000-0002-2534-1026БашкинВладимир АнатольевичBashkinVladimir A.

доцент, д.ф.-м.н.

ул. Советская, 14, г. Ярославль, 150003

associate professor, doctor of science

14 Sovetskaya, Yaroslavl 150003

v_bashkin@mail.ruЯрославский государственный университет им. П. Г. ДемидоваРоссияP. G. Demidov Yaroslavl State UniversityRussian Federation202024062020272234253Copyright © Башкин В.А., 20202020Башкин В.А.Bashkin V.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/1327

Два ресурса (подразметки) называются подобными, если в любой разметке любой из них может быть заменен другим, и при этом наблюдаемое поведение сети не изменится (относительно бисимуляции разметок). Известно, что подобие ресурсов неразрешимо для обыкновенных сетей Петри. В этой статье мы изучаем свойства подобия ресурсов и бисимуляции ресурсов (подмножество отношения подобия, замкнутое по срабатыванию переходов) в сетях Петри с невидимыми переходами (где некоторые переходы могут быть помечены специальной меткой (τ), что делает их срабатывания невидимыми для внешнего наблюдателя). Показано, что для собственного подкласса (p-насыщенных сетей) бисимуляция ресурсов может быть эффективно проверена. Для общего класса сетей Петри с невидимыми переходами можно построить последовательность так называемых (n, m)-эквивалентностей, аппроксимирующую наибольшую τ-бисимиляцию ресурсов.

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 (τ) 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 τ-bisimulation of resources.

ресурсэквивалентностьсети Петриневидимые переходыаппроксимацияresourceequivalencePetri netsinvisible transitionsapproximationРФФИ, проект № 17-07-00823.RFBR, project No 17-07-00823.ReferencesR. Milner, “A Calculus of Communicating Systems”, in, ser. Lecture Notes in Computer Science, vol. 92, Springer Berlin Heidelberg, 1980.R. Milner, “A Calculus of Communicating Systems”, in, ser. Lecture Notes in Computer Science, vol. 92, Springer Berlin Heidelberg, 1980.D. Park, “Concurrency and automata on infinite sequences”, in Theoretical Computer Science, ser. Lecture Notes in Computer Science, P. Deussen, Ed., vol. 104, Springer Berlin Heidelberg, 1981, pp. 167–183, isbn: 978-3-540-10576-3. [Online]. Available: http://dx.doi.org/10.1007/BFb0017309.D. Park, “Concurrency and automata on infinite sequences”, in Theoretical Computer Science, ser. Lecture Notes in Computer Science, P. Deussen, Ed., vol. 104, Springer Berlin Heidelberg, 1981, pp. 167–183, isbn: 978-3-540-10576-3. [Online]. Available: http://dx.doi.org/10.1007/BFb0017309.P. Janˇcar, “Decidability questions for bisimilarity of Petri nets and some related problems”, in STACS 94, ser. Lecture Notes in Computer Science, P. Enjalbert, E. W. Mayr, and K. W. Wagner, Eds., vol. 775, Springer Berlin Heidelberg, 1994, pp. 581–592.P. Janˇcar, “Decidability questions for bisimilarity of Petri nets and some related problems”, in STACS 94, ser. Lecture Notes in Computer Science, P. Enjalbert, E. W. Mayr, and K. W. Wagner, Eds., vol. 775, Springer Berlin Heidelberg, 1994, pp. 581–592.C. Autant and P. Schnoebelen,“Place bisimulations in Petri nets”, in Application and Theory of Petri Nets 1992, ser. Lecture Notes in Computer Science, K. Jensen, Ed., vol. 616, Springer Berlin Heidelberg, 1992, pp. 45–61, isbn: 978-3-540-55676-3. [Online]. Available: http://dx.doi.org/10.1007/3-540-55676-1_3.C. Autant and P. Schnoebelen,“Place bisimulations in Petri nets”, in Application and Theory of Petri Nets 1992, ser. Lecture Notes in Computer Science, K. Jensen, Ed., vol. 616, Springer Berlin Heidelberg, 1992, pp. 45–61, isbn: 978-3-540-55676-3. [Online]. Available: http://dx.doi.org/10.1007/3-540-55676-1_3.C. Autant, W. Pfster, and P. Schnoebelen, “Place bisimulations for the reduction of labeled Petri nets with silent moves”, in Proc. 6th Int. Conf. on Computing and Information, Peterborough, Canada, 1994.C. Autant, W. Pfster, and P. Schnoebelen, “Place bisimulations for the reduction of labeled Petri nets with silent moves”, in Proc. 6th Int. Conf. on Computing and Information, Peterborough, Canada, 1994.P. Schnoebelen and N. Sidorova, “Bisimulation and the reduction of Petri nets”, in Application and Theory of Petri Nets, ser. Lecture Notes in Computer Science, vol. 1825, Springer Berlin Heidelberg, 2000, pp. 409–423.P. Schnoebelen and N. Sidorova, “Bisimulation and the reduction of Petri nets”, in Application and Theory of Petri Nets, ser. Lecture Notes in Computer Science, vol. 1825, Springer Berlin Heidelberg, 2000, pp. 409–423.V. A. Bashkin and I. A. Lomazova, “Reduction of Coloured Petri nets based on resource bisimulation”, Joint Bulletin of NCC & IIS, Comp. Science, vol. 13, pp. 12–17, 2000.V. A. Bashkin and I. A. Lomazova, “Reduction of Coloured Petri nets based on resource bisimulation”, Joint Bulletin of NCC & IIS, Comp. Science, vol. 13, pp. 12–17, 2000.V. A. Bashkin and I. A. Lomazova, “Petri nets and resource bisimulation”, Fundamenta Informaticae, vol. 55, no. 2, pp. 101–114, 2003. [Online]. Available: http://iospress.metapress.com/content/NGX4LWFX81475D07.V. A. Bashkin and I. A. Lomazova, “Petri nets and resource bisimulation”, Fundamenta Informaticae, vol. 55, no. 2, pp. 101–114, 2003. [Online]. Available: http://iospress.metapress.com/content/NGX4LWFX81475D07.V. A. Bashkin and I. A. Lomazova, “Resource Similarities in Petri Net Models of Distributed Systems”, in Parallel Computing Technologies, ser. Lecture Notes in Computer Science, V. E. Malyshkin, Ed., vol. 2763, Springer Berlin Heidelberg, 2003, pp. 35–48, isbn: 978-3-540-40673-0. [Online]. Available: http://dx.doi.org/10.1007/978-3-540-45145-7_4.V. A. Bashkin and I. A. Lomazova, “Resource Similarities in Petri Net Models of Distributed Systems”, in Parallel Computing Technologies, ser. Lecture Notes in Computer Science, V. E. Malyshkin, Ed., vol. 2763, Springer Berlin Heidelberg, 2003, pp. 35–48, isbn: 978-3-540-40673-0. [Online]. Available: http://dx.doi.org/10.1007/978-3-540-45145-7_4.I. A. Lomazova, “Resource Equivalences in Petri Nets”, in Application and Theory of Petri Nets and Concurrency, ser. Lecture Notes in Computer Science, B. E. van der Aalst W., Ed., vol. 10258, Springer Berlin Heidelberg, 2017, pp. 19–34.I. A. Lomazova, “Resource Equivalences in Petri Nets”, in Application and Theory of Petri Nets and Concurrency, ser. Lecture Notes in Computer Science, B. E. van der Aalst W., Ed., vol. 10258, Springer Berlin Heidelberg, 2017, pp. 19–34.V. A. Bashkin, “On the Resource Equivalences in Petri Nets with Invisible Transitions”, in PNSE and Petri Nets 2017, ser. CEUR-WS, vol. 1846, 2017, pp. 51–68.V. A. Bashkin, “On the Resource Equivalences in Petri Nets with Invisible Transitions”, in PNSE and Petri Nets 2017, ser. CEUR-WS, vol. 1846, 2017, pp. 51–68.L. Redei, The theory of finitely generated commutative semigroups. Oxford University Press, 1965.L. Redei, The theory of finitely generated commutative semigroups. Oxford University Press, 1965.Y. Hirshfeld, “Congruences in commutative semigroups”, Edinburgh, University of Edinburgh, Department of Computer Science, Research Report ECS-LFCS-94-291, 1994.Y. Hirshfeld, “Congruences in commutative semigroups”, Edinburgh, University of Edinburgh, Department of Computer Science, Research Report ECS-LFCS-94-291, 1994.

The authors declare that there are no conflicts of interest present.