Action Machines: a Framework for Encoding and Composing Partial Behaviors

We describe action machines, a framework for encoding and composing partial behavioral descriptions. Action machines encode behavior as a variation of labeled transition systems where the labels are observable activities of the described artifact and the states capture full data models. Labels may also have structure, and both labels and states may be partial with a symbolic representation of the unknown parts. Action machines may stem from software models like state machines, scenario machines, or (model) programs, and can be composed in a variety of ways to synthesize new behaviors. The composition operators include synchronized parallel composition, sequential composition, hierarchical composition, and alternating simulation. We use action machines in analysis processes such as model checking and model-based testing. The current main application is in the area of model-based conformance testing, where our approach addresses practical problems users at Microsoft have in applying model-based testing technology.