Automatic detection of the finite state machines (FSMs) in a register transfer level (RTL) design is a widely utilised technique in logical synthesis for optimised FSM implementation and in hardware verification for the fast coverage of the control circuit. It is believed that FSM detection can also be used to explore the potential system partitions. Chosen an optimal partition, a large scale synchronous RTL system can be automatically converted into energy efficient globally asynchronous and locally synchronous (GALS) systems. A new FSM detection algorithm is presented providing a full coverage of all FSM-like controllers. It uses several criteria to detect FSMs on a register level abstracted graph generated from the RTL design. It is the first FSM detection algorithm that provides full FSM detection in the granularity level of signals without any restrictions on coding styles. © 2013 IEEE.