Composition of services: algorithmes and complexity

Composition de services: algorithmes et complexité

Fahima Cheikh Alili (1)

1 IRIT-LILaC - Logique, Interaction, Langue et Calcul

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.

Le problème de la combinaison des services, autrement appelé problème de la composition, constitue le foyer d'une intense activité de recherche. Composer les services entre eux, c'est entrelacer leurs séquences d'actions, de manière à obtenir des séquences qui satisfassent les exigences des clients. Le problème de la composition de services est difficile à résoudre en général. Dans cette thèse nous considérons des services qui peuvent à la fois exécuter des actions de communications ainsi que des actions internes. De plus, des conditions peuvent être exigées et des effets peuvent être appliqués sur les transitions. Formellement, les services sont représentés par des automates communicants conditionnels. Nous définissons, pour ce modèle, le problème de la composition et nous étudions sa décidabilité pour différentes relations d'équivalence et de préordre à savoir : l'inclusion de traces, l'équivalence de traces, la simulation et la bisimulation. Suite aux résultats de décidabilité obtenus, nous proposons trois variantes pour le modèle initial. Pour chacune d'elles, nous définissions le problème de la composition et nous étudions sa complexité pour les relations citées ci-dessus.

Mots clés: Services composition; automata; equivalence relations; preorder relations; decidability and complexity

Mots clés: Composition de services; automates; relations d'équivalence et de préordre; décidabilité et complexité

Domaines: Autre [cs.OH]

Fahima Cheikh Alili. Composition de services: algorithmes et complexité. Autre [cs.OH]. Université Paul Sabatier - Toulouse III, 2009. Français. ⟨NNT : ⟩. ⟨tel-00459114⟩