Optimal supervisor synthesis for petri nets with uncontrollable transitions: A bottom-up algorithm

Petri nets are a widely used tool to model, analyze and control discrete event systems that arise from automated production, intelligent transportation, and workflow management. For a class of Petri nets with uncontrollable transitions, this paper proposes a bottom-up algorithm to transform a given generalized mutual exclusion constraint into an optimal admissible one. Based on the transformation, a design method is proposed to synthesize an optimal supervisor. Compared with the existing methods that require the computation of exponential complexity, the proposed one can obtain an optimal supervisor with polynomial complexity.