Efficient Determination of Dead Markings of Petri Nets in Systems Biology

In this paper, we present an efficient algorithm to detect dead markings of a Petri net which is used as a modeling of a biological system. In doing so, we apply computer algebraic techniques to convert the problem of finding dead markings of a Petri net to a problem in the theory of polynomials and then, we use Gröbner basis to solve it. It is worth noting that Gröbner basis is one of the novel computer algebraic tools which is used to solve systems of polynomial equations. Although Gröbner basis is previously used to analyse a Petri net, however our modeling is simpler and more efficient than the previous work. As a comparison, there is needed to compute ((w+1)(w+2))/2+m+1 polynomials where w is the maximum weight and m is the number of transitions in the Petri net. This is while in our method it is enough to construct m polynomials. Moreover, we state a criterion which can also decrease the number of polynomials. More precisely, in the new modeling, we find a relation between transitions so that some of them are dependent to the others. This may halp then to omit some transitions and this may reduce the amount of computations.

کلیدواژه ها:

Systems Biology ، Petri Net ، Polynomial Algebra ، Gröbner Basis