Interface Automata with Complex Actions: Limiting Interleaving in Interface Automata

Issue title: Behavior of Composed Concurrent Systems: Logic and Reasoning

Article type: Research Article

Authors: Esmaeilsabzali, Shahram | Day, Nancy A. | Mavaddat, Farhad

Affiliations: David R. Cheriton School of Computer Science, University of Waterloo Waterloo, Ontario, N2L 3G1 Canada. E-mail: [email protected]; [email protected]; [email protected]

Abstract: Many formalisms use interleaving to model concurrency. To describe some system behaviours appropriately, we need to limit interleaving. For example, in a component-based system, we might wish to limit interleaving to force the inputs to a method to arrive together in order. InWeb services, the arrival of XML messages consisting of multiple simple parts should not be interleaved with the behaviour of another component. We introduce interface automata with complex actions (IACA), which adds complex actions to de Alfaro and Henzinger's interface automata (IA). A complex action is a sequence of actions that may not be interleaved with actions from other components. The composition operation and refinement relation are more involved in IACA compared to IA, and we must sacrifice associativity of composition. However, we argue that the advantages of having complex actions make it a useful formalism. We provide proofs of various properties of IACA and discuss the use of IACA for modellingWeb services.

Journal: Fundamenta Informaticae, vol. 82, no. 4, pp. 465-512, 2008