IEEE Transactions on Automatic Control, Vol.46, No.9, 1500-1505, 2001
Exploiting symmetry in the synthesis of supervisors for discrete event systems
In this note, we investigate a method to exploit the symmetry inherent to many discrete-event systems in order to reduce the computational complexity of the supervisory control problem (SCP). We characterize symmetry using notions of group theory and derive conditions under which there exists a quotient (reduced) automaton representation for a language with, in general, a much smaller state space than the original minimal (in number of states) automaton representation for the language. We then propose an algorithm to synthesize a solution to the SCP which is similar to the classical one, but performed on reduced automata. Special attention is given to the particular case of systems whose models contain similar components. The approach is illustrated by an example of control of a small production line.