Synthesis of supervisors using learning algorithm of regular languages (Q5943166)

The paper addresses the problem of applying the theory of supervisory control of Ramdage and Wonham (1988) when only partial initial specification is available. The task of producing a complete specification as required by the theory is often problematic, especially for large systems. The paper assumes the designer has some description of the system specification expressed in some suitable form, such as logical formulas, algebraic formulas, or generators representing partial behavior of the system. The designer may also have some idea on the specification though not expressed in an explicit form. The algorithm completes the plant description and the behavior specification using a learning algorithm of regular languages proposed by Angluin (1978). The algorithm works by posing several queries to the designer and by proposing conjectures for the supervisor. The process is repeated until the designer considers a conjecture to be satisfactory. The proposed algorithm exploits the independence between events and uses partial order reduction techniques to improve efficiency when applied to concurrent systems.