Automatic Composition of e-Services

Daniela Berardi, Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Massimo Mecella

Technical Report, Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza". Technical Report 22-2003 2003.

The main focus of this paper is on automatic e-Service composition. We start by developing a framework in which the exported behavior of an e-Service is described in terms of its possible executions (execution trees). Then we specialize the framework to the case in which such exported behavior (i.e., the execution tree of the e-Service) is represented by a finite state machine. In this specific setting, we analyze the complexity of synthesizing a composition, and develop sound and complete algorithms to check the existence of a composition and to return one such a composition if one exists. To the best of our knowledge, our work is the first attempt to provide an algorithm for the automatic synthesis of e-Service composition, that is both proved to be correct, and has an associated computational complexity characterization.

   title = "Automatic Composition of e-Services",
   year = "2003",
   author = "Daniela Berardi and Diego Calvanese and De Giacomo, Giuseppe
and Maurizio Lenzerini and Massimo Mecella",
   institution = "Dipartimento di Informatica e Sistemistica, Università
di Roma "La Sapienza"",
   number = "22-2003",
ps.gz pdf