A Learning-Based Synthesis Approach to the Supremal Nonblocking Supervisor of Discrete-Event Systems

This paper presents a novel approach to synthesize supremal nonblocking supervisors of discrete-event systems (DES), when the automaton models of specifications are not available. Extending the L* learning algorithm, an S* algorithm is developed to infer a tentatively correct supervisor. If the tentatively correct supervisor is nonblocking, it is indeed the supremal nonblocking supervisor with respect to the plant and specifications. Otherwise, the blocking automaton is regarded as a new plant, and the specification is the nonblocking property. Then, the supremal nonblocking supervisor with respect to the new problem is computed using supervisory control theory of DES. Two simplification rules are introduced to the S* algorithm to decrease the computational cost. Finally, the S* algorithm is implemented based on the LearnLib framework, and experiments are performed to verify the proposed approach.