Automated Discovery of Finite State Automata for the Control of Discrete Event Systems

Abstract

In many industrial systems, control-related information is often opaque, undermining the ability to formally ensure safety, correctness, and performance. Representing such systems as Discrete Event Systems (DES) models enables rigorous analysis, synthesis, and correct-by-construction control, but modeling is typically manual, which limits the adoption of DES-based approaches. This paper proposes a data-driven engineering approach to automate the discovery of DES models from raw event logs. Based on premises that typically apply to many real systems, our method identifies structural patterns that capture alternative ways in which tasks are executed. Building on these structures, we show how DES models can be constructed while balancing generalization and precision, a long-standing challenge in model discovery. The approach applies to the discovery of both isolated components and closed-loop DES, either to streamline early design steps or to enable computational analysis and verification. Comparisons with related discovery methods and illustrative case studies highlight our contributions. Note to Practitioners—DESs typically require formal models to be designed so that the system can be analyzed and controlled. As execution traces can usually be obtained from event records stored by information systems, we propose in this paper a way to take such records as input for a discovery method that delivers the system plant model. We start by extracting traces and, when the log contains multiple components, projecting the global trace onto a component-level view. Then, events are classified, and logs are decomposed into restartable parts. Within each part, different types of repetition patterns are identified to guide the unfolding of the state space. This enables us to control the balance between precision and generalization. The proposed method targets applications where plant models are unavailable, but event logs are available for analysis. Under the structural assumptions stated in the paper, models of plant components are recovered from recorded event logs, enabling practitioners to use them in subsequent analysis and control engineering practices.