Abstract
Composition of e-Services is the issue of synthesizing a new composite e-Service, obtained by combining a set of available component e-Services, when a client request cannot be satisfied by available e-Services. In this paper we study the problem of composition synthesis in a general framework. We consider e-Services as arbitrary (possibly infinite) execution trees, i.e., as trees of all potential interactions with clients, and characterize composition in this abstract setting. We then show how this setting can be realized using Reasoning About Actions, in particular reasoning in Situation Calculus, and exploiting a correspondence with Deterministic Propositional Dynamic Logic, we provide automated procedures and complexity results for performing composition.