Generating Hierarchical State Machines from Use Case Charts

There are many examples, in the literature, of algorithms for synthesizing state machines from scenario-based models. The motivation for these is to automate the transition from scenario-based requirements to early analysis and design models. A major challenge for such algorithms, however, is that the relationships between scenarios are usually not explicitly defined. This means that synthesis algorithms have to infer the relationships and this cannot generally be done without also inferring false positives. An alternative is to require users to explicitly give scenario relationships. The challenge here is that the additional burden placed on the user must be less than the effort saved by automatic synthesis. In this paper, we address this problem by defining a synthesis algorithm for use case charts, a language for precisely describing use cases and their relationships. Use case charts are sufficiently precise to allow the automatic generation of hierarchical state machines but retain the benefits of existing scenario-based notations by being based on UML. Use case charts provide an easy way of specifying scenario relationships but also have a formal semantics that can be used both in synthesis and to execute the use case charts. This paper presents the synthesis algorithm for use case charts and illustrates it on a significant example based on students' solutions to an analysis and design problem.