In: Vestsi Akademii Navuk BSSR; Seryya Fizika-Matematychnykh Navuk, No. 2, pages 106-110, 128. 1989. In Russian.
Abstract: The author considers the problem of reducing the computational complexity of finding the parallelism relation for a subclass of Petri nets. The author presents an algorithm for finding this relation, whose estimated time complexity is a polynomial of small degree in the dimensions of the net. The correctness of the algorithm on the basis of a property of the given subclass of Petri nets is proved and estimates for the computational complexity of the algorithm are derived.
Keywords: parallelism relation (on a set of places); reducing (of) computational complexity.