## 1 Introduction  
Finite-State Machines (FSMs) are fundamental components in digital systems, extensively used in control applications, communication protocols, and various other areas requiring predictable and structured behavior. The efficiency of an FSM significantly impacts the overall performance and resource utilization of digital systems, particularly when implemented in hardware platforms such as Field-Programmable Gate Arrays (FPGAs), Complex Programmable Logic Devices (CPLDs), and Application-Specific Integrated Circuits (ASICs). Given the ubiquity of control devices in digital systems, FSMs are pivotal in digital hardware design. Many digital systems and devices are distinctly defined by their control logic, making the synthesis of FSMs a critical concern in every new project. State encoding is a crucial step in FSM design, influencing the resulting implementation's area and performance. Traditional methods for state encoding often do not fully exploit the potential optimizations available through modern hardware platforms, leaving room for improvement. The need for more advanced encoding techniques that consider the architectural nuances of contemporary electronic components is evident. The state encoding task involves addressing a complex logical combinatorial problem classified as NP-hard. The complexity and significance of FSM state encoding have been a focal point for scientists and engineers since the inception of FSM theory. This subject garnered particular attention in the late 1980s, leading to the proposal of several methods such as two-level [1]and multi-level synthesis [2] of FSMs, directly addressing FSM state encoding. Two-level synthesis methods target the implementation of FSMs in devices equipped with two programmable matrix structures, notably CPLDs. Conversely, multi-level synthesis methods are tailored for implementing FSMs in FPGAs utilizing look-up tables (LUTs). Given that the FSM state encoding problem is NP-hard, exact solutions are only feasible for small or specific FSMs, such as counters. As a result, numerous algorithms have been developed to address this challenge, typically categorized as heuristic (deterministic) or genetic (evolutionary) algorithms. Heuristic algorithms aim to identify local minima or maxima within a specific FSM parameter in a reasonably practical timeframe. While heuristic algorithms often produce solutions that closely approach the optimal, there are instances where their outcomes significantly diverge from the optimal result. The main drawback of heuristic algorithms stems from their tendency to become trapped in local minima or maxima. The conventional method for addressing NP-hard tasks involves employing genetic (evolutionary) algorithms. Genetic algorithms offer the advantage of escaping local minima, thereby broadening the search space for solutions. Nonetheless, genetic algorithms are computationally intensive, require lengthy execution times, and do not consistently yield optimal solutions. Consequently, in practical applications, genetic algorithms are primarily employed to encode the states for critical FSM parameters, as the success of extensive and intricate projects hinges on the optimization of these parameters. The challenge lies in the fact that achieving an optimal solution for the state encoding task does not ensure an optimal solution for the FSM synthesis task. This is because FSM synthesis methods employed in design tools encompass various other tasks besides state encoding. These tasks include mapping the design logic to the physical structure of electronic devices (such as FPGA, CPLD, or ASIC), meeting the time constraints of the design, and more. While state encoding primarily impacts the realization of the transition functions of FSMs, synthesis methods may integrate the implementation of both transition functions and output functions. Such integration often necessitates the use of an entirely different state encoding method. A review of algorithms and methods for FSM state encoding is provided in [3].