Art

J-GLOBAL ID：200902219774930977   Reference number：09A1152405

Computational Complexity of Liveness Problem of Normal Petri Net

正規Petriネットの活性問題の計算量

Author (2)： OHTA Atsushi (Aichi Prefectural Univ., Aichi-ken, JPN) ,  TSUJI Kohkichi (Aichi Prefectural Univ., Aichi-ken, JPN)
Material： IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Institute of Electronics, Information and Communication Engineers)  (IEICE Trans Fundam Electron Commun Comput Sci (Inst Electron Inf Commun Eng))
Volume： E92-A  Issue： 11  Page： 2717-2722  Publication year： Nov. 01, 2009 
JST Material Number： F0699C  ISSN： 0916-8508  Document type： Article
Article type： 原著論文  Country of issue： Japan (JPN)  Language： ENGLISH (EN)

Thesaurus term： *Petri net ,  regular expression ,  activity (property) ,  *computational complexity ,  reachability ,  concurrent processing ,  modeling ,  deadlock ,  existence ,  condition ,  subset ,  system characteristic ,  NP complete problem ,  computer algorithm ,  equivalency ,  computational complexity theory ,  deterministic algorithm
Semi thesaurus term： necessary and sufficient condition ,  polynomial time algorithm ,  complexity class

JST classification (2)： System and control theory in general  (IA02010H) ,  Theory of computation  (JB02000A)

Reference (13)：

• MURATA, T. Petri nets : Properties, analysis and applications. Proc. IEEE. 1989, 77, 4, 541-580
• JONES, N. D. Complexity of some problems in Petri nets. Theor. Comput. Sci. 1977, 4, 277-299
• ESPARZA, J. A polynomial-time algorithm to decide liveness of bounded free choice nets. Theor. Comput. Sci. 1992, 102, 185-205
• BARKAOUI, K. On the equivalence between liveness and deadlock-freeness in Petri nets. Applications and Theory of Petri Nets 2005. 2005, 90-107
• MATSUMOTO, T. Necessary and sufficient condition of structural liveness for general Petri nets-Virtual deadlock-trap properties. IEICE Trans. Fundamentals, A. 1995, E78, 12, 1862-1874

Terms in the title (4)： Petriネット ,  活性 ,  問題 ,  計算量