Set difference operation for regular Petri net languages for the producer/consumer problem with the bounded buffer

Authors

  • Vitalii Statkevych Educational and Scientific Complex "Institute for Applied System Analysis" of the National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute", Kyiv, Ukraine https://orcid.org/0000-0001-5210-9890

DOI:

https://doi.org/10.20535/SRIT.2308-8893.2021.2.08

Keywords:

Petri net, producer/consumer problem, Petri net language, formal language, regular language, finite automaton, regular expression

Abstract

We consider a Petri net for the producer/consumer problem (one of the classical synchronization problems) with the bounded buffer of size n and the regular formal languages Ln, generated by the net. The objective of this paper is to obtain a regular expression for the set difference of languages Ln \ Lm, n > m. For this purpose, we give the finite automaton which accepts the set difference of mentioned languages, and then we use the state elimination method to obtain the regular expression in the recursive form. The main result is illustrated by the examples. In an appendix, we consider the problem with two producers and two consumers with the bounded buffer of size 1. We give a reachability graph and propose the method for obtaining the regular expression. The explicit formulas are given for the problem with two producers and one consumer and also for the problem with one producer and two consumers.

Author Biography

Vitalii Statkevych, Educational and Scientific Complex "Institute for Applied System Analysis" of the National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute", Kyiv

Vitalii M. Statkevych,

Ph.D. in Mathematics, a researcher at the Department of Applied Nonlinear Analysis of Educational and Scientific Complex "Institute for Applied System Analysis" of the National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute", Kyiv, Ukraine.

References

J. Peterson, Petri net theory and modeling of systems. Moscow: Mir, 1984.

V.E. Kotov, Petri nets. Moscow: Nauka, 1984.

T. Murata, “Petri nets: Properties, analysis and applications”, Trudy Instituta inzhenerov po elektrotekhnike i radioelektronike, vol. 77, no. 4, pp. 41–85, 1989.

A.E. Pentus and M.R. Pentus, Formal language theory. Moscow: Mekhaniko-matematicheskii fakul’tet Moskovskogo Gosudarstvenogo Universiteta, 2004.

A.E. Pentus and M.R. Pentus, The mathematical theory of formal languages. Moscow: Binom, 2006.

J.E. Hopcroft, R. Motwani and J.D. Ullman, Introduction to automata theory, languages, and computation. Moscow: Williams Publishing House, 2002.

V.M. Statkevych, “Regular expressions for some Petri net languages for the producer/consumer problem”, System Research & Information Technologies, no. 3, pp. 105–123, 2020. doi: 10.20535/SRIT.2308-8893.2020.3.08

A. Salomaa, Jewels of formal language theory. Moscow: Mir, 1986.

F.A. Novikov, Discrete mathematics for programmers. St. Petersburg: Piter, 2000.

Downloads

Published

2021-09-14

Issue

No. 2 (2021)

Section

Problem- and function-oriented computer systems and networks

License

This is an open access journal which means that all content is freely available without charge to the user or his/her institution. Users are allowed to read, download, copy, distribute, print, search, or link to the full texts of the articles in this journal without asking prior permission from the publisher or the author. This is in accordance with the BOAI definition of open access.