Synthesis of underspecified composite e-services based on automated reasoning

ABSTRACT

In this paper we study automatic composition synthesis of <i>e</i>-Services, based on automated reasoning. We represent the behavior of an <i>e</i>-Service in terms of a deterministic transition syst (or a finite state machine), in which for each action the role of the <i>e</i>-Service, either as initiator or as servant, is highlighted. In this setting we present an algorithm based on satisfiability in a variant of Propositional Dynamic Logic that solves the automatic composition probl. Specifically, given (<i>i</i>) a possibly incomplete specification of the sequences of actions that a client would like to realize, and (<i>ii</i>) a set of available <i>e</i>-Services, our technique synthesizes a composite <i>e</i>-Service that (<i>i</i>) uses only the available <i>e</i>-Services and (<i>ii</i>) interacts with the client "in accordance" to the given specification. We also study the computational complexity of the proposed algorithm.

REFERENCES

• 1: Marco Aiello , Mike P. Papazoglou , Jian Yang , M. Carman , Marco Pistore , Luciano Serafini , Paolo Traverso, A Request Language for Web-Services Based on Planning and Constraint Satisfaction, Proceedings of the Third International Workshop on Technologies for E-Services, p.76-85, August 23-24, 2002
• 2: T. Andrews, F. Curbera, H. Dholakia, Y. Goland, J. Klein, F. Leymann, K. Liu, D. Roller, D. Smith, S. Thatte, I. Trickovic, and S. Weerawarana. Business Process Execution Language for Web Services (Version 1.1). http://www-106.ibm.com/developerworks/library/ws-bpel/.
• 3: Mark H. Burstein , Jerry R. Hobbs , Ora Lassila , David Martin , Drew V. McDermott , Sheila A. McIlraith , Srini Narayanan , Massimo Paolucci , Terry R. Payne , Katia P. Sycara, DAML-S: Web Service Description for the Semantic Web, Proceedings of the First International Semantic Web Conference on The Semantic Web, p.348-363, June 09-12, 2002
• 4: Franz Baader , Diego Calvanese , Deborah L. McGuinness , Daniele Nardi , Peter F. Patel-Schneider, The description logic handbook: theory, implementation, and applications, Cambridge University Press, New York, NY, 2003
• 5: F. Baader and U. Sattler. An overview of tableau algorithms for description logics. Studia Logica, 69(1):5--40, 2001.
• 6: D. Berardi, D. Calvanese, G. De Giacomo, M. Lenzerini, and M. Mecella. Automatic Composition of phe-Services that Export their Behavior. In Proc. of ICSOC 2003.
• 7: D. Berardi, D. Calvanese, G. De Giacomo, M. Lenzerini, and M. Mecella. A Foundational Vision of phe-Services. In Proc. of WES~2003.
• 8: M. Buchheit, F. M. Donini, and A. Schaerf. Decidable Reasoning in Tterminological Knowledge Representation systems. J. of Artificial Intelligence Research, 1:109--138, 1993.
• 9: Tevfik Bultan , Xiang Fu , Richard Hull , Jianwen Su, Conversation specification: a new approach to design and analysis of e-service composition, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775210]
• 10: Diego Calvanese , Giuseppe De Giacomo, Expressive description logics, The description logic handbook: theory, implementation, and applications, Cambridge University Press, New York, NY, 2003
• 11: Dynamic and adaptive composition of e-services, Information Systems, v.26 n.3, p.143-163, May 2001 [doi>10.1016/S0306-4379(01)00014-X]
• 12: Giuseppe de Giacomo , Fabio Massacci, Combining deduction and model checking into Tableaux and algorithms for converse-PDL, Information and Computation, v.162 n.1/2, p.117-137, Oct 2000
• 13: Ahmed K. Elmagarmid , William J. McIver, Guest Editors' Introduction: The Ongoing March Toward Digital Government, Computer, v.34 n.2, p.32-38, February 2001
• 14: M. Fattorosi-Barnaba and F. De Caro. Graded modalities I. Studia Logica, 44:197--221, 1985.
• 15: Marie-Christine Fauvet , Marlon Dumas , Boualem Benatallah , Hye-Young Paik, Peer-to-Peer Traced Execution of Composite Services, Proceedings of the Second International Workshop on Technologies for E-Services, p.103-117, September 14-15, 2001
• 16: K. Fine. In so many possible worlds. Notre Dame Journal of Formal Logic, 13(4):516--520, 1972.
• 17: G. Alonso, F. Casati, H. Kuno, and V. Machiraju. Web Services. Concepts, Architectures and Applications. Springer-Verlag, 2004.
• 18: D. Georgakopoulos, editor. Proc. of RIDE-VE'99
• 19: Dana Nau , Malik Ghallab , Paolo Traverso, Automated Planning: Theory & Practice, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 20: S. Ghandeharizadeh, C. A. Knoblock, C. Papadopoulos, C. Shahabi, E. Alwagait, J. L. Ambite, M. Cai, C. Chen, P. Pol, R. R. Schmidt, S. Song, S. Thakkar, and R. Zhou. Proteus: A Syst for Dynamically Composing and Intelligently Executing Web Services. In Proc. of ICWS 2003.
• 21: Volker Haarslev , Ralf Möller, RACER System Description, Proceedings of the First International Joint Conference on Automated Reasoning, p.701-706, June 18-23, 2001
• 22: Alon Y. Halevy, Answering queries using views: A survey, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.270-294, December 2001 [doi>10.1007/s007780100054]
• 23: David Harel , Jerzy Tiuryn , Dexter Kozen, Dynamic Logic, MIT Press, Cambridge, MA, 2000
• 24: Ian Horrocks, The FaCT System, Proceedings of the International Conference on Automated Reasoning with Analytic Tableaux and Related Methods, p.307-312, May 05-08, 1998
• 25: Richard Hull , Michael Benedikt , Vassilis Christophides , Jianwen Su, E-services: a look behind the curtain, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.1-14, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773154]
• 26: U. Kuter, E. Sirin, D. Nau, B. Parsia, and J. Hendler. Information Gathering during Planning for Web Service Composition. In Proc. of ICAPS-P4WGS 2004.
• 27: Maurizio Lenzerini, Data integration: a theoretical perspective, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543644]
• 28: E. Martinez and Y. Lesperance. Web Service Composition as a Planning Task: Experiments using Knowledge-Based Planning. In Proc. of ICAPS-P4WGS 2004.
• 29: Sheila A. McIlraith , Tran Cao Son , Honglei Zeng, Semantic Web Services, IEEE Intelligent Systems, v.16 n.2, p.46-53, March 2001 [doi>10.1109/5254.920599]
• 30: M. Mecella and B. Pernici. Building Flexible and Cooperative Applications Based on e-Services. Technical Report 21-2002, Dipartimento di Informatica e Sististica, Università di Roma "La Sapienza", Roma, Italy, 2002. (available on line at: http://www.dis.uniroma1.it/~mecella/publications/mp_techreport_212002.pdf).
• 31: Massimo Mecella , Barbara Pernici , Paolo Craca, Compatibility of e -Services in a Cooperative Multi-platform Environment, Proceedings of the Second International Workshop on Technologies for E-Services, p.44-57, September 14-15, 2001
• 32: Ralf Möller , Volker Haarslev, Description logic systems, The description logic handbook: theory, implementation, and applications, Cambridge University Press, New York, NY, 2003
• 33: M. P. Papazoglou , D. Georgakopoulos, Introduction, Communications of the ACM, v.46 n.10, October 2003 [doi>10.1145/944217.944233]
• 34: Thomi Pilioura , Aphrodite Tsalgatidou, E-Services: Current Technology and Open Issues, Proceedings of the Second International Workshop on Technologies for E-Services, p.1-15, September 14-15, 2001
• 35: F. Pistore, M. and Barbon, P. Bertoli, and P. Shaparau, D. and Traverso. Planning and Monitoring Web Service Composition. In Proc. of ICAPS-P4WGS 2004.
• 36: Hans Schuster , Dimitrios Georgakopoulos , Andrzej Cichocki , Donald Baker, Modeling and Composing Service-Based nd Reference Process-Based Multi-enterprise Processes, Proceedings of the 12th International Conference on Advanced Information Systems Engineering, p.247-263, June 05-09, 2000
• 37: German Shegalov , Michael Gillmann , Gerhard Weikum, XML-enabled workflow management for e-services across heterogeneous platforms, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.1, p.91-103, August 2001
• 38: W. Van der Hoek. On the santics of graded modalities. Journal of Applied Non-Classical Logics, 2(1):81--123, 1992.
• 39: Jian Yang , Mike P. Papazoglou, Web Component: A Substrate for Web Service Reuse and Composition, Proceedings of the 14th International Conference on Advanced Information Systems Engineering, p.21-36, May 27-31, 2002

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program synthesis

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: State diagrams
      D.2.4 Software/Program Verification
          Subjects: Formal methods

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.1 Specifying and Verifying and Reasoning about Programs
          Subjects: Logics of programs

General Terms:
Design, Theory, Verification

Keywords:
intelligent services, service composition models and language, theoretical framework for service representation and compositions