next up previous
Next: Performance Methodology Up: Hoshen-Kopelman Algorithm Previous: Search Path Compression

1.6 The Finite State Machine

A FSM, finite automaton, is a logical construct composed of a set of states, a finite input token alphabet, and a transition function to map states tokens to states. According to Hopcroft and Ullman (1979), a finite automaton is formally denoted by

a 5-tuple (, , , , F), where is a finite set of states, is a finite input alphabet, in is the initial state, is the set of final states, and is the transition function mapping . That is, is a state for each state q and input symbol a.
The transition function, , is defined as a set of 3-tuples (, a, ) where is the current machine state, a is an element of the token alphabet, and is the new machine state. Table 3 formally defines the Hoshen-Kopelman finite state machine (FSM) used in this study.

Table 3: Formal definition of the Hoshen-Kopelman finite state machine.

The FSM begins in and continues until a final state is reached. The states in encapsulate whether or not the west neighbor had been assigned a temporary cluster label thereby eliminating the redundant analysis of the west neighbor. Eliminating redundant conditionals increases the efficiency of the FSM implementation. Table 4 is a working example of the FSM implementation showing the formal state changes for one row of a sample map. A description of the FSM cluster identification (cluster_id) and the cluster relabeling (reLabel) source code is provided in Constantin (1995).

Table 4: Incremental state changes for the FSM working example.

Michael W. Berry (
Sat Mar 30 23:40:13 EST 1996