Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.3/158410

Title

Action prefixes: reified synchronization paths in minimal component interaction automata

Author(s)

Lumpe, Markus

Abstract

Component Interaction Automata provide a fitting model to capture and analyze the temporal facets of hierarchical-structured component-oriented software systems. However, the rules governing composition, as is typical for all automata-based approaches, suffer from combinatorial state explosion, an effect that can have significant ramifications on the successful application of the Component Interaction Automata formalism to real-world scenarios. We must, therefore, find some appropriate means to counteract state explosion - one of which is partition refinement through weak bisimulation. But, while this technique can yield the desired state space reduction, it does not consider synchronization cliques, i.e., groups of states that are interconnected solely by internal synchronization transitions. Synchronization cliques give rise to action prefixes that capture pre-conditions for a component's ability to interact with the environment. Current practice does not pay attention to these cliques, but ignoring them can result in a loss of valuable information. For this reason we show, in this paper, how synchronization cliques emerge and how we can capture their behavior in order to make state space reduction aware of the presence of synchronization cliques.

Publication type

Journal article

Research centre

Swinburne University of Technology. Faculty of Information and Communication Technologies

Source

Electronic Notes in Theoretical Computer Science: proceedings of the 6th International Workshop on Formal Aspects of Component Software (FACS 2009), Eindhoven, the Netherlands, 02-03 November 2009, Vol. 263 (Jun 2010), pp. 179-195

Publication year

2010

FOR Code(s)

080201 Analysis of Algorithms and Complexity;  080308 Programming Languages;  080309 Software Engineering

Keyword(s)

Component Interaction Automata;  Emerging properties;  Partition refinement

Publisher

Elsevier

ISSN

1571-0661

Publisher URL

http://dx.doi.org/10.1016/j.entcs.2010.05.011

Copyright

Copyright © 2010 Elsevier B.V. All rights reserved.

Peer reviewed