Composition of Functional Petri Nets

Composition of Functional Petri Nets

Dmitry A. Zaitsev
Copyright: © 2013 |Pages: 61
DOI: 10.4018/978-1-4666-4034-4.ch017
OnDemand:
(Individual Chapters)
Available
$37.50
Current Special Offers
No Current Special Offers
TOTAL SAVINGS: $37.50

Abstract

Functional Petri nets and subnets are introduced and studied for the purpose of speed-up of Petri nets analysis with algebraic methods. The authors show that any functional subnet may be generated by a composition of minimal functional subnets. They propose two ways to decompose a Petri net: via logical equations solution and with an ad-hoc algorithm, whose complexity is polynomial. Then properties of functional subnets are studied. The authors show that linear invariants of a Petri net may be computed from invariants of its functional subnets; similar results also hold for the fundamental equation of Petri nets. A technique for Petri nets analysis using composition of functional subnets is also introduced and studied. The authors show that composition-based calculation of invariants and solutions of fundamental equation provides a significant speed-up of computations. For an additional speed-up, they propose a sequential composition of functional subnets. Sequential composition is formalised in the terms of graph theory and was named the optimal collapse of a weighted graph. At last, the authors apply the introduced technique to the analysis of Petri net models of such well-known networking protocols as ECMA, TCP, BGP.
Chapter Preview
Top

Background

Linear algebra methods (Diaz, 2001; Murata, 1989; Reisig, 1982) based on state equation and invariants are a powerful tool for Petri nets analysis. But to find linear invariants and to solve the fundamental equation of a Petri net we have to solve linear Diophantine systems in nonnegative integer numbers. All known methods of such systems solution (Colom & Silva, 1990; Contejean & Ajili, 1997; Kryviy, 1999; Martinez & Silva, 1982; Schrejver, 1987; Toudic, 1982) possess exponential complexity with respect to space. It makes the analysis of large-scale models practically unfeasible and requires searching of new techniques, which provide essential speed-up of computations.

Two basic approaches were suggested (Berthelot, 1987) to handle large-scale nets: decomposition and reduction. Implementations of these approaches have been designed in the different concrete ways. Moreover, decomposition and reduction are applied not only to nets but to state space also. Reduction provides a set of rules for decreasing the dimension of net preserving its properties. Then usual analysis methods are applied to reduced net.

Complete Chapter List

Search this Book:
Reset