A linear time algorithm solving the legal firing sequence problem for a class of edge-weighted cactuses
説明
The subject of the paper is the legal firing sequence problem of Petri nets (LFS): given a Petri net N, an initial marking M and a firing count vector X, find a firing sequence /spl sigma/, starting from M, such that each transition t appears in /spl sigma/ exactly X(t) times as prescribed by X. The main result of the paper is as follows: LFS is solvable in linear time if N is a cyclic cactus with exactly two kinds of edge-weights and X=1~, meaning that X(t)=1 for every transition t.
収録刊行物
-
- IEEE SMC'99 Conference Proceedings. 1999 IEEE International Conference on Systems, Man, and Cybernetics (Cat. No.99CH37028)
-
IEEE SMC'99 Conference Proceedings. 1999 IEEE International Conference on Systems, Man, and Cybernetics (Cat. No.99CH37028) 3 893-898, 2003-01-20
IEEE
