Introduction
In the design of automated manufacturing and transportation systems, Petri nets (PNs) serve as a robust mathematical framework for modeling discrete event systems. A central challenge in this domain is supervisor synthesis: the creation of a controller that ensures the system adheres to specific linear constraints (avoiding "illegal" states) while maintaining maximal permissiveness. This task is significantly complicated by the presence of uncontrollable transitions—events that the supervisor cannot prevent.
In 2012, Luo et al. proposed a method to transform complex linear constraints into "weakly admissible" ones to handle these uncontrollable events. Their "Theorem 3" claimed that this transformation was always equivalent to the original constraint. However, recent analysis reveals a fundamental flaw in this theorem.
The Counterexample
The critique rests on a purely logical and mathematical foundation, utilizing a specific Petri net model to serve as a counterexample.
The authors demonstrate that the transformation algorithm proposed by Luo et al. is sensitive to the sequence in which uncontrollable transitions are processed. By applying the transformation to the Petri net shown in Figure 1 using two different sequences of uncontrollable transitions, they arrive at non-equivalent sets of admissible markings.
Key Insights: Why Order Matters
The primary insight is that the transformation process lacks invariance. In the original work, it was assumed that transforming a constraint at an uncontrollable transition would yield a stable, equivalent disjunction regardless of the global context.
By examining transitions $t_1$ and $t_2$ in Figure 1, the authors show:
- Sequence A ($t_1$ then $t_2$): This path leads to an empty set of admissible markings ($\mathcal{A} = \emptyset$), effectively blocking the system entirely.
- Sequence B ($t_2$ then $t_1$): This path results in a non-empty set of admissible markings ($\mathcal{A} \neq \emptyset$), allowing for valid system operation.
This discrepancy proves that the transformation is not "equivalent" as claimed. The result depends on an arbitrary choice of processing order, which is not accounted for in the original theory. Furthermore, the authors utilize "zero constraints"—constraints that can never be satisfied by the initial marking—to show how one sequence can lead to a set of entirely empty constraints while another allows for valid markings.
Conclusion
The debunking of Theorem 3 indicates that the supervisor synthesis method proposed by Luo et al. is unreliable for general applications in ordinary Petri nets. The problem of linear constraint transformation in the presence of uncontrollable transitions remains a difficult and open topic. Future research must develop transformation methods that are either invariant to transition sequences or incorporate the reachability logic necessary to ensure true equivalence.
Summary updated