In: SIGACT News, Vol. 29, No. 4, pages 98-110. December 1998.
Abstract: A new algorithm for the determination of a marking in generalized Petri nets is proposed. The algorithm is based on the matrix-equation approach. Given a Petri net, a so called complemented Petri net is created that consists of the given Petri net and a complementary transition with input and output places depending on the initial and target markings of the given Petri net. Then the reachability task is reduced to the investigation of T-invariants of the complemented Petri net. Using a technique of search for T-invariants, the algorithm determines minimal-support T-invariants, that include the complementary transitions, and then calculates the finite set of their linear combinations. For each T-invariant, the algorithm tries to create sequentially all reachability paths from the given initial marking to the target marking or determines that there are no such paths at all. During the creation of the reachability paths, the algorithm needs memory only for storing the reachability path being created. If it is sufficient to determine only one firing sequence transforming the initial marking into the target one, then the algorithm may be terminated after successful creation of the first reachability path.
Keywords: Petri Nets, reachability of a marking, T-invariants.