Dmitry A. Zaitsev, "Paradigm of computations on the Petri nets"

siiky

2023/12/05

2024/01/25

whitepaper,petri_nets

§6 discusses theoretical algorithmic complexity of an implementation of an Universal Petri Net (UPN).

A certain gap between the theory of asynchronous parallel programming based on the Petri nets and the programming for the existing computers remains open over many years. The programmable logic controllers (PLC) [8] seem to be a single area where the programming languages based on the Petri nets are used practically. The experimental realizations of the Petri net-based programming languages [9–13] either involve compilation into classical languages or interpretation of programs by the programmed Petri net processors. Therefore, the hardware architectures used do not allow one to fully realize the advantages of the asynchronous approach because the asynchronous parallel processor is emulated by a sequential synchronous hardware.

Recently, constructed were the universal Petri net (UPN) [15, 16] and the Petri nets executing the given Turing machine (PNTM) [17] and the normal Markov algorithm (PNNMA) [18], thus supporting succession of concepts. The UPN is considered as the prototype of the Petri net processor (PNP) realized on the Petri nets , and PNTM and PNNMA are considered as the prototypes of the coprocessors executing the algorithms in terms of the sequences of instructions or products (substitutions). Therefore, the program in the language of Petri nets is executed by UPN, the other fragments of the code being executed by PNTM, PNNMA and other dedicated nets.

In different formal systems, the synchronous and asynchronous concepts only prevail one over the other, but as a rule do not manifest themselves in a pure form. Behavior of the classical Petri net implies synchronization at the step where all transitions are verified and only one is selected and triggered. The class of synchronous Petri nets where the maximum of the excited transitions is triggered at a step is Turing complete. Yet a new class of step-free Petri nets is required where all transitions are independent, but the results of their triggering coincide at certain given time instants of observation.

Anatolii Il’ich Sleptsov suggested use of multiple triggering of transition at a step in the presence of multiple conditions for its excitation [19]. Later on the concept of multiple triggering was developed in the study of time nets with multichannel transitions [20]. As was shown in [21], the universal net constructed in the class of nets with multiple triggering of transitions has polynomial complexity. This gives rise to the objective premises for calling this class as the Sleptsov nets. These nets are calculated promptly, whereas the traditional Petri nets are calculated slowly.

[19] Sleptsov, A.I., State Equations and Equivalent Transformations of Loaded Petri Nets (Algebraic Approach), in Formal Models of Parallel Computation, Proc. All-Union Conf., Novosibirsk, 1988, pp. 151–158.
[20] Zaitsev, D.A. and Sleptsov, A.I., State Equation and Equivalent Transformations of the Time Petri Nets, Kibern. Sist. Anal., 1997, no. 5, pp. 59–76.
[21] Zaitsev, D.A., Small Polynomial Time Universal Petri Nets, arXiv:1309.7288.

References 8-14 are supposedly "programming-related".

[8] Peng, S.S. and Zhou, M.Ch., Petri Net Based PLC Stage Programming for Discrete-event Control Design, in Systems, Man, and Cybernetics, 2001 IEEE Int. Conf., 2001, vol. 4, pp. 2706–2710.
[9] Rossmann, J. and Eilers, K., Translating Robot Programming Language Flow Control into Petri Nets, in Emerging Technologies and Factory Automation (ETFA), 2011 IEEE 16th Conf. Digital Object Identifier, 2011, pp. 1–7.
[10] Palomeras, N., Ridao, P., Carreras, M., et al., Using Petri Nets to Specify and Execute Missions for Autonomous Underwater Vehicles, in Intelligent Robots and Systems, IROS 2009, IEEE/RSJ Int. Conf., Oct. 10–15, 2009, pp. 4439–4444.
[11] Dodd, R.B., Coloured Petri Net Modelling of a Generic Avionics Mission Computer, Air Operations Division: Defence Science and Technology Organisation, Australia, DSTO-TN-0692, 2006.
[12] Usher, M. and Jackson, D., A Petri Net Based Visual Programming Language, in Systems, Man, and Cybernetics, 1998. IEEE Int. Conf., 1998, vol. 1, pp. 107–112.

[13]

[14] Voevodin, V.V. and Voevodin, Vl.V., Parallel’nye vychisleniya (Parallel Computations) St. Petersburg: BKnV-Peterburg, 2002.

References 15-16 are supposedly "universal"/"closed" Petri nets theories.

[15] Zaitsev, D.A., Universal Petri Net, Kibern. Sist. Anal., 2012, no. 4, pp. 24–39.
[16] Zaitsev, D.A., Toward the Minimal Universal Petri Net, IEEE Trans. Syst., Man, Cybernet., 2014, vol. 44, no. 1, pp. 47–58.
[17] Zaitsev, D.A., Inhibitory Petri Net Executing an Arbitrary Defined Turing Machine, Sist. Doslidzh. Inform. Tekhnol., 2012, no. 2, pp. 26–41.
[18] Zaitsev, D.A., Inhibitory Petri Net Executing an Arbitrary Defined Normal Markov Algorithm, Modelir. Anal. Inform. Sist., 2011, vol. 18, no. 4, pp. 80–93.