Extracting minimal siphon-traps of Petri nets and its application to computing nonnegative integer-invariants

作     者：Taoka, S Takano, K Watanabe, T 

作者机构：Hiroshima Univ Grad Sch Engn Higashihiroshima 7398527 Japan Hitachi Software Engn Co Yokohama Kanagawa Japan 

出 版 物：《IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES》 (电子信息通信学会汇刊：电子学、通信及计算机科学基础)

年 卷 期：2002年第E85A卷第11期

页      面：2436-2446页

核心收录：

学科分类：0808[工学-电气工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Petri nets minimal siphon-traps Fourier-Motzkin method invariant computation polynomial-time algorithms 

摘      要：A siphon-trap of a Petri net N is defined as a place set S with S-. = S-., where S-.={u\ N has an edge from u to a vertex of S} and S-. = {v\ N has an edge from a vertex of S to v}. A minimal siphon-trap is a siphon-trap such that any proper subset is not a siphon-trap. The following polynomial-time algorithms are proposed: 1. FDST for finding, if any, a minimal siphon-trap or even a maximal class of mutually disjoint minimal siphon-traps of a given Petri net;2. FDSTi that repeats FDST i times in order to extract more minimal siphon-traps than FDST. 3. STFM-T (STFM-T-i, respectively) which is a combination of the Fourier-Motzkin method and FDST (FDSTi) and which has high possibility of finding, if any, at least one minimal-support nonnegative integer invariant.