| Presentation | 1995/4/21 The Legal Firing Sequence Problem of Petri Nets with State Machine Structure Keisuke Morita, Hirofumi Nakawaki, Toshimasa Watanabe, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The Legal Firing Sequence Problem of Petri nets (LFS for short) is defined by : "Given a Petri net, an initial marking M and a firing count vector X (with each component X(t) denoting the prescribed total firing number of a transition t), find a firing sequence δ which is legal on M with respect to X", where δ is a sequence of transitions and is called legal on M with respect to X if and only if the first transition of δ is firable on M, the rest can be fired one by one subsequently and each transition t appears exactly X(t) times in δ. It is known that LFS is NP-complete and that LFS restricted to a state machine can be solved in O(|X|^2) time. First, we propose an O(|X|) time algorithm that solves LFS for state machines. Secondly, linear time algorithms for solving LFS for some classes of weighted state machines with two kinds of edge weights are given, where the term "weighted" means that some edge weights may be greater than 1. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Petri nets / State machines / Legal Firing Sequence Problems / Polynomial-Time Algorithms / NP-completeness |
| Paper # | |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1995/4/21(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | The Legal Firing Sequence Problem of Petri Nets with State Machine Structure |
| Sub Title (in English) | |
| Keyword(1) | Petri nets |
| Keyword(2) | State machines |
| Keyword(3) | Legal Firing Sequence Problems |
| Keyword(4) | Polynomial-Time Algorithms |
| Keyword(5) | NP-completeness |
| 1st Author's Name | Keisuke Morita |
| 1st Author's Affiliation | Department of Circuits and Systems, Faculty of Engineering, Hiroshima University,() |
| 2nd Author's Name | Hirofumi Nakawaki |
| 2nd Author's Affiliation | Department of Circuits and Systems, Faculty of Engineering, Hiroshima University, |
| 3rd Author's Name | Toshimasa Watanabe |
| 3rd Author's Affiliation | Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
| Date | 1995/4/21 |
| Paper # | |
| Volume (vol) | vol.95 |
| Number (no) | 13 |
| Page | pp.pp.- |
| #Pages | 10 |
| Date of Issue | |