Automatic Service Composition Based on Behavioral Descriptions

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

Int. J. of Cooperative Information Systems. 14(4):333--376 2005.

This paper addresses the issue of automatic e-Service composition. We first develop a framework in which the exported behavior of an e-Service is described in terms of a so-called execution tree, that is an abstraction for its possible executions. We then study the case in which such exported behavior (i.e., the execution tree of the e-Service) can be represented by a finite state machine. In this specific setting, we devise sound, complete and terminating techniques both to check for the existence of a composition, and to return a composition, if one exists. We also analyze the computational complexity of the proposed algorithms. Finally, we present an open source prototype tool, called ESC (E-Service Composer), that implements our composition technique. To the best of our knowledge, our work is the first attempt to provide a provably correct technique for the automatic synthesis of e-Service composition, in a framework where the behavior of e-Services is explicitly specified.

   title = "Automatic Service Composition Based on Behavioral Descriptions",
   year = "2005",
   author = "Daniela Berardi and Diego Calvanese and De Giacomo, Giuseppe
and Maurizio Lenzerini and Massimo Mecella",
   journal = "Int. J. of Cooperative Information Systems",
   pages = "333--376",
   number = "4",
   volume = "14",
   doi = "10.1142/S0218843005001201",