Search

The paper considers an efficient simulation algorithm for discrete event systems with a great number of elements. With the use of Petri-object simulation and parallel computing, the algorithm is developed that simultaneously reproduces operation of Petri objects in separate streams. The linear dependence of the runtime of the algorithm on model’s complexity is confirmed by experimental results.

A reduced Petri net model of a parallel distributed system is considered as a component Petri net (a CN) with a view to determining the adequacy between two models, namely, a detailed Petri model N and a component Petri model (CN model) of this distributed system. The concepts of a component relation ? and a component relation domain are introduced. A surjective homomorphism between the N and CN models and an isomorphism between the N / ? net, i.e., the factor model of N with respect to the relation ?, and CN are established.

The use of timed Petri nets for simulation modeling is analyzed. An equation for transforming states of timed Petri nets and fundamental matrix equations of a stochastic timed Petri net with conflicting and multichannel transitions and informational relations are obtained.

A universal inhibitor Petri net executing an arbitrary given inhibitor Petri net is constructed. An inhibitor Petri net graph, its marking, and transition firing sequence are encoded as 10 scalar nonnegative integer variables and are represented by the corresponding places of the universal net. An algorithm using only these scalar variables and executing an arbitrary inhibitor net is developed based on the state equation and is encoded by the universal inhibitor Petri net. Subnets that implement arithmetic, comparison, and copy operations are employed.

A model of a hypercube communication structure of arbitrary size with an arbitrary number of dimensions is constructed in the form of a parametric Petri net. A technique for calculating linear invariants of parametric Petri nets is developed that allows one to analyze information transmission processes in such a hypercube. The structure of complicated deadlocks caused by a path (loop) of blockings and the isolation of devices is investigated. In real-life networks, the described deadlocks lead to a considerable decrease in performance and can be induced by some ill-intentioned traffic.

Foundations of compositional analysis of Petri nets are presented. This analysis consist of the determination of properties of a given Petri net from the properties of its functional subnets. Compositional analysis covers the investigation of behavioral and structural properties of Petri nets with the help of matrix methods that use fundamental equations and invariants. The exponential acceleration of computations as a function of the dimensionality of a net is obtained.

The problem of splitting any given Petri net into functional subnets is considered. The properties of functional subnets and sets that induce them are investigated. An algorithm of polynomial complexity is constructed for decomposition of nets.

A linear fundamental equation for a timed Petri net is constructed. Full and partial invariants of state and behavior of a timed Petri net are introduced. Properties of invariant nets are analyzed. Interrelations of full and partial invariants are shown. Examples of analysis of net models of production systems and processes are described.

The problem of inverse mapping of Petri nets into CES remains an interesting open question. Raczunas [5] claims that it is not for every PN that a strictly equivalent CES exists. He accordingly proposes weak equivalence of this mapping. Kotov [6] defines a topologically structured subclass of PN—regular PN. The subclass of regular PN has the same cardinality as the class of all PN in the sense of behavioral equivalence. It is therefore relevant to compare the class of regular PN with CES.

Dynamic net models of a special kind — discrete process generators — are considered. Their relation to automata, Petri nets, partially commutative monoids, and the theory of traces is examined.