State machine models provide an effective way to compare different versions of a software system, or different systems to solve the same problem. They facilitate software development, testing, and maintenance.

Two complementary techniques for comparing state machines are presented in this paper. The first identifies similarities and differences between state machines in terms of the possible sequences of events they describe, that is, the languages generated by the state machines. The second compares the states and transition structures of two state machines. Both start by reducing the state machines to a set of states and labeled transitions, called labeled transition systems (LTSs). The techniques are illustrated using different state machine models of a simple text editor. The authors conducted experiments to assess the scalability of the techniques. These indicate that language-based comparison grows more rapidly with increasing state machine complexity than does structural comparison.

These approaches to comparing state machines represent a promising basis for new software engineering tools. It would also be interesting to see a theoretical analysis of the computational complexity of these techniques.