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 behavioral design models. To date, however, these synthesis algorithms have tended to generate flat state machines which can be difficult to understand or adapt for practical systems. One of the reasons for this is that relationships between scenarios are often not taken into account during synthesis—either because the relationships are not explicitly defined or because the synthesis algorithms are not sophisticated enough to cope with them. If relationships are not considered, it is impossible for a synthesis algorithm to know, for example, where one scenario stops and another continues. Furthermore, the lack of relationships makes it difficult to introduce structure into the generated state machines. With the introduction of interaction overview diagrams (IODs) in UML2.0, relationships such as continuation and concurrency can now be specified between scenarios in a way that conforms to the UML standard. But synthesis algorithms do not currently exist that take into account all of these relationships. This article presents a novel synthesis algorithm for an extended version of interaction overview diagram. This algorithm takes into account not only continuation and concurrency, but also preemption, suspension and the notion of a negative scenario. Furthermore, the synthesis algorithm generates well-structured state machines. These state machines are executable and can therefore be used to validate the scenarios. The hierarchy generated aids readability and so the state machines are more amenable to subsequent design steps. Our IOD extensions have a formal semantics and are supported by a synthesis and execution tool, UCSIM, which is currently provided as a plug-in to IBM Rational Software Modeler.

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