Implicit depth-first state traversal of sequential machines
Abhijit Ghosh, Srinivas Devadas · 1991
A depth-first traversal technique for sequential machines that enables the traversal of counter FSMs (finite state machines) in O(n) steps, where n is the number of bits in the counter, is presented. The depth-first geometric chaining traversal algorithm is conceptually similar to a previously proposed iterative squaring traversal technique, and is based on traversing geometrically increasing (or decreasing) chains of states and edges in the state transition graph (STG) in any given set of steps. An important extension can be made to this algorithm for the traversal of interacting sets of FSMs, some of which can be counters, while others are arbitrary FSMs.>