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

siiky

2023/12/05

2023/12/05

2023/12/05

whitepaper,petri_nets

https://doi.org/10.1134/S0005117914080025

§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 proces- sor (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.

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

[13]

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

Inform. Tekhnol., 2012, no. 2, pp. 26–41.

Anal. Inform. Sist., 2011, vol. 18, no. 4, pp. 80–93.