A new algorithm to derive generators for both invariants and particular solutions of state equations for P/T Petri Nets - a method via Z-Basis for augmented incidence matrix

摘要

Recently; it has been shown that an arbitrary nonnegative integer inhomogeneous solution x = x{sub}(H6) + x{sub}(P6) ∈(Z{sub}(NN)){sup}(n×l) for state (or matrix) equation Ax=b(A∈Z{sup}(m×n),b∈Z{sup}(m×l)) of P/T Petri nets is represented at level 6 as the simplest form such that the homogeneous solution x{sub}(H6) ∈(Z{sub}(NN)){sup}(n×l) is a linear combination of the l{sub}6 nonnegative integer generators U{sub}6 = {u{sub}I ∈(Z{sub}(NN)){sup}(n×l)|Au{sub}i = 0{sup}(m×l), i∈I(l{sub}6)}, with nonnegative integer weights, and the particular solution x{sub}(P6) ∈(Z{sub}(NN)){sup}(n×l) is a single term v{sub}j ∈(Z{sub}(NN)){sup}(n×l), i.e., just one term out of the k{sub}6 nonnegative integer particular solutions V{sub}6 ={v{sub}j∈(Z{sub}(NN)){sup}(n×l)|Av{sub}i =b, j ∈I(k{sub}6)}, with also a nonnegative integer and unity weight. Therefore it is strongly hoped to give an algorithm for finding effectively the level-6 generators (U{sub}6, V{sub}6) from the given matrices A∈Z{sup}(m×n) and b∈Z{sup}(m×l) for a P/T Petri net. In this paper a new and useful algorithm for (U{sub}6, V{sub}6) via Z-basis (i.e., the level-2 generator for (A(top)～)(x{top}～)= 0{sup}(m×l)) (U{top}～){sub}2 ={(x{top}～){sub}i∈Z{sup}((n250L羖)×l)|(A{top}～)(x{top}～){sub}i = 0{sup}(m×l), i∈I(n+l-r)} is proposed, where (A{top}～)=[A, b] ∈Z{sup}(m×(n×l)) and r = rank(A) = rank(A{top}～). First, U{sub}2 is obtained from (A{top}～)=[A, -b] by the extended Kannan and Bachen algorithm which is with polynomial time and space complexity. Secondly, from (U{top}～){sub}2, find the maximal set of minimal T-invariants (U{top}～){sub}6 = {(u{top}～){sub}i ∈(Z{sub}(NN)){sup}((n×l)×l)|(A{top}～)(u{top}～){sub}i =0{sup}(m×l), i∈I((l{top}～){sub}6)} for (A{top}～)(x{top}～) = 0{sup}(m×l). Thirdly from (U{top}～){sub}6, obtain simultaneously both U{sub}6 and V{sub}6 i.e., the level-6 generators for Ax = b. Fourthly reduce (U{sub}6, V{sub}6) to the level-5 and level-4 generators, U{sub}4 and V{sub}4 = V{sub}5, by using support(x) properties for x ∈(Z{sub}(NN)){sup}(n×l), because of U{sub}6 =U{sub}5 {contains} U{sub}4 and V{sub}6 {contains} V{sub}5 = V{sub}4, where U{sub}L = {u{sub}i ∈(Z{sub}(NN)){sup}(n×l)|Au{sub}i = 0{sup}(m×l), i ∈ I(l{sub}L)} and V{sub}L ={v{sub}j ∈(Z{sub}(NN)){sup}(n×l)|Av{sub}j =b, j ∈ I(k{sub}L)} for L=4, 5. Note that l{sub}6 = l{sub}5 and l{sub}4 means the total number of all minimal T- invariants and the that of all minimal support (or all elementary) T-invariants for Ax =0{sup}(m×l), respectively. Note also that k{sub}6 and k{sub}5 = k{sub}4 means the total number of all nonnegative integer particular solutions and that of all nonnegative integer basic particular solutions for Ax =b, respectively, where a basic particular solution is a particular solution, but the converse is not always true.