This work was supported by the National Natural Science Foundation of China (Grant Nos. 69973029 and 69933020) ; the National Key Basic Science Foundation of P. R. China (973 Project, Grant No. G1998030604) ; the Key Project of National Science & Techn
As far as we know, the testing problem of legal firing sequence is NP-complete for gener-al Petri net, the related results of this problem on the polynomial-time solvability are limited only to some special net classe...