Using computer-aided software engineering (CASE) tools to compare different views of similar models offers software developers the ability to evaluate models both qualitatively and quantitatively. Related applications include model-checking, testing, and determining whether two design solutions are similar.

This paper elaborates on the development of techniques and their corresponding algorithms to support the comparison and evaluation of state machine models. Given a reference model and a subject model, both expressed as labeled transition systems (LTSs), how can we measure their similarities, differences, and relative accuracy? The first technique, inspired by model-based testing, compares the languages generated by the two LTSs. Traces are generated from the LTSs by enumerating finite string combinations of the transition labels. Attributes, such as precision, recall, and classification, are expressed formally and their values are computed based on membership and nonmembership of these traces in the languages under consideration. The second technique introduces both local and global ways to compare the structures of the reference machine and the subject machine. The local comparison is limited to a given state and its adjacent neighbors. The global comparison includes a given state of interest and all the remaining states. Again, attributes for measuring global similarities and differences are expressed formally and an algorithm to compute them is presented. The results of an empirical evaluation of the two techniques show that the second technique tends to be highly accurate and more robust than the first.

Such a tool would help software developers compare models generated by different teams, or assess the similarity of an existing model and a reverse-engineered model. CASE tool developers will be inspired by the process of integrating various formalisms to shed light on a different software development issue.

Basing the empirical evaluation of the techniques on real rather than synthetic data would strengthen the claim that the techniques are scalable and the results remain accurate. It would also address the issue of computational costs associated with state explosion inherent in modeling with finite state machines. In this case, a formal complexity analysis of the algorithms is required. The authors, somewhat implicitly, claim that the expressive power of LTSs enables the modeling of any software system. According to automata theory, an LTS is equivalent to a regular grammar or language, whereas software systems may require more powerful machines than finite state machines.