BOUNDED SELF-STABILIZING PETRI NETS

We investigate the property of self-stabilization in bounded Petri net s. We give characterizations for both self-stabilizing bounded ordinar y Petri nets (i.e., Petri nets without multiple arcs) and self-stabili zing bounded general Petri nets (i.e., Petri nets with multiple arcs). These characterizations allow us to determine the complexity of decid ing self-stabilization for each of these classes. In particular, we sh ow the self-stabilization problem to be PTIME-complete for bounded ord inary Petri nets and PSPACE-complete for bounded general Petri nets.