{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,25]],"date-time":"2026-06-25T15:53:44Z","timestamp":1782402824856,"version":"3.54.5"},"reference-count":28,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Coop. Info. Syst."],"published-print":{"date-parts":[[2005,12]]},"abstract":"<jats:p> This paper addresses the issue of automatic service composition. We first develop a framework in which the exported behavior of a 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 service) can be represented by a finite state machine (i.e. finite state transition system). 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 [Formula: see text] (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 service composition, in a framework where the behavior of services is explicitly specified. <\/jats:p>","DOI":"10.1142\/s0218843005001201","type":"journal-article","created":{"date-parts":[[2005,7,26]],"date-time":"2005-07-26T12:20:29Z","timestamp":1122380429000},"page":"333-376","source":"Crossref","is-referenced-by-count":131,"title":["AUTOMATIC SERVICE COMPOSITION BASED ON BEHAVIORAL DESCRIPTIONS"],"prefix":"10.1142","volume":"14","author":[{"given":"DANIELA","family":"BERARDI","sequence":"first","affiliation":[{"name":"Dipartimento di Informatica e Sistemistica \"A. Ruberti\", Universit\u00e0 di Roma \"La Sapienza\", Via Salaria 113, 00198 Roma, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"DIEGO","family":"CALVANESE","sequence":"additional","affiliation":[{"name":"Libera Universit\u00e0 di Bolzano\/Bozen, Facolt\u00e0 di Scienze e Tecnologie Informatiche, Piazza Domenicani, 3, 39100 Bolzano\/Bozen, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"GIUSEPPE","family":"DE GIACOMO","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica e Sistemistica \"A. Ruberti\", Universit\u00e0 di Roma \"La Sapienza\", Via Salaria 113, 00198 Roma, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"MAURIZIO","family":"LENZERINI","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica e Sistemistica \"A. Ruberti\", Universit\u00e0 di Roma \"La Sapienza\", Via Salaria 113, 00198 Roma, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"MASSIMO","family":"MECELLA","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica e Sistemistica \"A. Ruberti\", Universit\u00e0 di Roma \"La Sapienza\", Via Salaria 113, 00198 Roma, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2012,1,25]]},"reference":[{"key":"rf2","volume-title":"Web Services. Concepts, Architectures and Applications","author":"Alonso G.","year":"2004"},{"key":"rf7","volume-title":"The Description Logic Handbook: Theory, Implementation and Applications","author":"Baader F.","year":"2003"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-25975-6_22"},{"key":"rf9","volume":"34","author":"Batini C.","journal-title":"IEEE Computer"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90018-6"},{"key":"rf11","volume":"7","author":"Benatallah B.","journal-title":"IEEE Internet Computing"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45017-3_31"},{"key":"rf18","author":"Berardi D.","journal-title":"J. Integrated Design and Process Science"},{"key":"rf20","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1613\/jair.21","volume":"1","author":"Buchheit M.","journal-title":"J. Artificial Intelligence Research"},{"key":"rf22","volume":"6","author":"Casati F.","journal-title":"Information Systems"},{"key":"rf26","volume":"25","author":"Colombo E.","journal-title":"IEEE Data Engineering Bulletin"},{"key":"rf27","first-page":"117","volume":"160","author":"De Giacomo G.","journal-title":"Information and Computation"},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90046-1"},{"key":"rf31","volume-title":"Automated Task Planning: Theory & Practice","author":"Ghallab M.","year":"2004"},{"key":"rf34","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45744-5_59"},{"key":"rf35","doi-asserted-by":"publisher","DOI":"10.1007\/s007780100054"},{"key":"rf36","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/2516.001.0001","volume-title":"Dynamic Logic","author":"Harel D.","year":"2000"},{"key":"rf37","doi-asserted-by":"crossref","unstructured":"I.\u00a0Horrocks, Proc. TABLEAUX'98\u00a01397, ed. Harrie\u00a0de Swart (Springer-Verlag, 1998)\u00a0pp. 307\u2013312.","DOI":"10.1007\/3-540-69778-0_30"},{"key":"rf40","volume-title":"Handbook of Theoretical Computer Science \u2014 Formal Models and Semantics","author":"Kozen D.","year":"1990"},{"key":"rf42","volume":"15","author":"Lazcano A.","journal-title":"Int. J. Computer Systems Science & Engineering"},{"key":"rf43","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24593-3_23"},{"key":"rf47","volume":"16","author":"McIlraith S.","journal-title":"IEEE Intelligent Systems"},{"key":"rf49","volume":"46","author":"Papazoglou M. P.","journal-title":"Communications of the ACM"},{"key":"rf51","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/4074.001.0001","volume-title":"Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems","author":"Reiter R.","year":"2001"},{"key":"rf52","volume-title":"Contemporany Logic Design","author":"Katz R. H.","year":"1993"},{"key":"rf53","volume":"7","author":"Schmidt C.","journal-title":"World Wide Web Journal"},{"key":"rf54","volume":"10","author":"Shegalov G.","journal-title":"Very Large Database J."},{"key":"rf60","volume":"29","author":"Yang J.","journal-title":"Information Systems"}],"container-title":["International Journal of Cooperative Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218843005001201","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T14:06:59Z","timestamp":1565186819000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218843005001201"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,12]]},"references-count":28,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2012,1,25]]},"published-print":{"date-parts":[[2005,12]]}},"alternative-id":["10.1142\/S0218843005001201"],"URL":"https:\/\/doi.org\/10.1142\/s0218843005001201","relation":{},"ISSN":["0218-8430","1793-6365"],"issn-type":[{"value":"0218-8430","type":"print"},{"value":"1793-6365","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,12]]}}}