Bounded self-stabilizing Petri nets |
| |
| Authors: | Ludmila Cherkasova Rodney R Howell Louis E Rosier |
| |
| Affiliation: | (1) Hewlett-Packard Laboratories, 1501 Page Mill Road, Bldg. 1U-14, P.O. Box 10490, 94303 Palo Alto, CA, USA;(2) Department of Computing and Information Sciences, Kansas State University, 66506 Manhattan, KS, USA;(3) Department of Computer Sciences, The University of Texas at Austin, 78712 Austin, TX, USA |
| |
| Abstract: | We investigate the property of self-stabilization in bounded Petri nets. We give characterizations for both self-stabilizing bounded ordinary Petri nets (i.e., Petri nets without multiple arcs) and self-stabilizing bounded general Petri nets (i.e., Petri nets with multiple arcs). These characterizations allow us to determine the complexity of deciding self-stabilization for each of these classes. In particular, we show the self-stabilization problem to be PTIME-complete for bounded ordinary Petri nets and PSPACE-complete for bounded general Petri nets.Louis Rosier passed away on May 6, 1991, while this paper was under review |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
