DocumentCode
1628862
Title
A linear time algorithm solving the legal firing sequence problem for a class of edge-weighted cactuses
Author
Taoka, Satoshi ; Watanabe, Toshimasa
Author_Institution
Fac. of Eng., Hiroshima Univ., Japan
Volume
3
fYear
1999
fDate
6/21/1905 12:00:00 AM
Firstpage
893
Abstract
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 σ, starting from M, such that each transition t appears in σ 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
Keywords
Petri nets; automata theory; computational complexity; sequences; edge-weighted cactuses; legal firing sequence problem; linear time algorithm; Circuits and systems; Graph theory; Law; Legal factors; Petri nets; Systems engineering and theory; Terminology; Vectors;
fLanguage
English
Publisher
ieee
Conference_Titel
Systems, Man, and Cybernetics, 1999. IEEE SMC '99 Conference Proceedings. 1999 IEEE International Conference on
Conference_Location
Tokyo
ISSN
1062-922X
Print_ISBN
0-7803-5731-0
Type
conf
DOI
10.1109/ICSMC.1999.823346
Filename
823346
Link To Document