Deciding service composition and substitutability using extended operating guidelines

We study the correct interaction between services using the following notion for correctness: there is no deadlock in the interaction of the services, and a given set of activities is not dead, that is, each activity in this set is executed in at least one run. The second condition has not been studied before.An operating guideline of a service P is an operational characterization of all deadlock-free interacting partners of P. In this paper, we present an extension of the concept of an operating guideline to characterize all correctly interacting partners of a service P. This extension can be used for answering at least the following two questions. First, given a service R, does R interact correctly with P  ? Second, given a service P′P′, can P   be substituted by P′P′, that is, is every correctly interacting partner of P   a correctly interacting partner of P′P′, too?