Composition de services: algorithmes et complexité
Fahima Cheikh Alili · HAL (Le Centre pour la Communication Scientifique Directe) · 2009
The problem of combining services, also called the services composition problem, constitutes the centre of intense research activity. To compose services consists of merging their action sequences in order to obtain new sequences that satisfy the client requirements. This problem is in general difficult to solve. In this thesis, we consider services that are able to perform two kinds of actions: communication actions and internal actions. Moreover, services are able to verify conditions before an action execution and to change the value of variables after an action execution. Formally, services are represented by conditional communicating automata. We define for this model the services composition problem and we study its decidability for the following preorder and equivalence relations: traces inclusion, trace equivalence, simulation and bisimulation. Further to the decidability results obtained we propose three variants of the initial model. For each variant we define the composition problem and we study its complexity regarding the relations cited above.