Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Automated comparison of state-based software models in terms of their language and structure
Walkinshaw N., Bogdanov K. ACM Transactions on Software Engineering and Methodology22 (2):1-37,2013.Type:Article
Date Reviewed: Jun 24 2013

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.

Reviewer:  B. Belkhouche Review #: CR141305 (1309-0811)
Bookmark and Share
  Reviewer Selected
Featured Reviewer
 
 
Languages (D.2.1 ... )
 
 
State Diagrams (D.2.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Languages": Date
An examination of requirements specification languages
Tse T., Pong L. The Computer Journal 34(2): 143-152, 1991. Type: Article
Apr 1 1992
Towards a formal basis for the formal development method and the Ina Jo specification language
Berry D. IEEE Transactions on Software Engineering SE-13(2): 184-201, 1987. Type: Article
Oct 1 1987
On the design of ANNA, a specification language for ADA
Luckham D.  Software validation: inspection-testing-verification-alternatives (, Darmstadt, West Germany,2271984. Type: Proceedings
May 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy