A Notion of Glue Expressiveness for Component-Based Systems
Comparison between different formalisms and models is often by flattening structure and reducing them to behaviourally equivalent models e.g. automaton and Turing machine. This leads to a notion of expressiveness which is not adequate for component-based systems where separation between behaviour and coordination mechanisms is essential. The paper proposes a notion of glue expressiveness for component-based frameworks characterizing their ability to coordinate components. Glue is a closed under composition set of operators mapping tuples of behaviour into behaviour. Glue operators preserve behavioural equivalence. They only restrict the behaviour of their arguments by performing memoryless coordination. Behavioural equivalence induces an equivalence on glue operators. We compare expressiveness of two glues G1 and G2 by considering whether glue operators of G1 have equivalent ones in G2 (strong expressiveness). Weak expressiveness is defined by allowing a finite number of additional behaviours in the arguments of operators of G2. We propose an SOS-style definition of glues, where operators are characterized as sets of SOS-rules specifying the transition relation of composite components from the transition relations of their constituents. We provide expressiveness results for the glues of BIP and of process algebras such as CCS, CSP and SCCS. We show that for the considered expressiveness criteria, glues of the considered process calculi are less expressive than general SOS glue. Furthermore, glue of BIP has exactly the same strong expressiveness as glue definable by the SOS characterization.