
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Time Complexity Analysis of the Legal Firing Sequence Problem of Petri Nets with Inhibitor Arcs
Satoshi TAOKA Toshimasa WATANABE
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E89A
No.11
pp.32163226 Publication Date: 2006/11/01
Online ISSN: 17451337
DOI: 10.1093/ietfec/e89a.11.3216
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Concurrent/Hybrid Systems: Theory and Applications) Category: Concurrent Systems Keyword: Petri nets, inhibitorarcs, legal firing sequences, pseudopolynomial time algorithms, NPhardness,
Full Text: PDF(446.4KB)>>
Summary:
Petri nets with inhibitor arcs are referred to as inhibitorarc Petri nets. It is shown that modeling capability of inhibitorarc Petri nets is equivalent to that of Turing machines. The subject of this paper is the legal firing sequence problem (INLFS) for inhibitorarc Petri nets: given an inhibitorarc Petri net IN, an initial marking M_{0} and a firing count vector X, find a firing sequence δ such that its firing starts from M_{0} and each transition t appears in δ exactly X(t) times as prescribed by X. The paper is the first step of research for time complexity analysis and designing algorithms of INLFS, one of the most fundamental problems for inhibitorarc Petri nets having more modeling capability than ordinary Peri nets. The recognition version of INLFS, denoted as RINLFS, means a decision problem, asking a "yes" or "no" answer on the existence of a solution δ to INLFS. The main results are the following (1) and (2). (1) Proving (11) and (12) when the underlying Petri net of IN is an unweighted state machine: (11) INLFS can be solved in pseudopolynomial (O(X)) time for IN of nonadjacent type having only one special place called a rivet; (12) RINLFS is NPhard for IN with at least three rivets; (2) Proving that RINLFS for IN whose underlying Petri net is unweighted and forward conflictfree is NPhard. Heuristic algorithms for solving INLFS are going to be proposed in separate papers.

