Introduction
The paper "Representing Extended Finite State Machines for SDL by A Novel Control Model of Discrete Event Systems" establishes a formal bridge between software modeling and control theory. In modern software engineering, Extended Finite State Machines (EFSMs) are widely used to model complex systems, particularly those defined in the Specification and Description Language (SDL). However, these models often lack a connection to the rigorous mathematical frameworks of control theory, such as the Ramadge-Wonham (RW) framework for Discrete Event Systems (DES).
The authors address this gap by proposing a novel transformation that reframes software logic as a supervisory control problem. This allows for the application of formal verification and analysis tools from control theory to software behavior.
Methodology: Bridging EFSMs and DES
The core of the proposed approach is a new control model for DES that treats software predicates as "conflicting event pairs." Unlike traditional control theory, which partitions events into controllable and uncontrollable sets, this model uses boolean conditions to drive event selection.
The transformation involves two primary algorithms:
- Extracting the Controlled DES: This algorithm simplifies an EFSM by removing variable logic to create a "plant" model, represented as a Mealy Automaton. This captures the raw state transitions of the system.
- Extracting the Supervisor: This algorithm captures the "intelligence" or logic of the software. It maps variable update functions to the supervisor's internal state and boolean predicates (if-then-else statements) to a state feedback map.
By combining the plant and the supervisor, the software's execution is fully modeled as a controlled discrete event system.
Key Insights and Results
A central insight of this work is the treatment of software as a cybernetic system. By viewing predicates ($P(V)$) as control signals that enable or disable specific events, the "control" in software is elevated from an analogy to a formal mathematical structure.
Key results of this research include:
- Behavioral Equivalence: The authors prove that the resulting DES model is behaviorally equivalent to the original EFSM, producing identical input and output sequences.
- Formal Language Representation: The system's behavior can be described using regular expressions, providing a robust language for formal verification.
- Feasibility: The transformation was successfully demonstrated on sample SDL flow graphs, proving its applicability to standard software modeling languages.
Limitations and Future Outlook
While the current model provides a solid foundation for deterministic EFSMs, real-world software often involves non-determinism and concurrency. The authors identify Communicating EFSMs (CEFSMs) as a primary area for future work, as modeling interactions between multiple state machines introduces significant complexity. Additionally, the computational overhead of transforming large-scale systems—potentially leading to state explosion—remains a challenge to be addressed in practical implementations.
Summary updated