Simulation, verification and automated composition of web services

ABSTRACT

Web services -- Web-accessible programs and devices - are a key application area for the Semantic Web. With the proliferation of Web services and the evolution towards the Semantic Web comes the opportunity to automate various Web services tasks. Our objective is to enable markup and automated reasoning technology to describe, simulate, compose, test, and verify compositions of Web services. We take as our starting point the DAML-S DAML+OIL ontology for describing the capabilities of Web services. We define the semantics for a relevant subset of DAML-S in terms of a first-order logical language. With the semantics in hand, we encode our service descriptions in a Petri Net formalism and provide decision procedures for Web service simulation, verification and composition. We also provide an analysis of the complexity of these tasks under different restrictions to the DAML-S composite services we can describe. Finally, we present an implementation of our analysis techniques. This implementation takes as input a DAML-S description of a Web service, automatically generates a Petri Net and performs the desired analysis. Such a tool has broad applicability both as a back end to existing manual Web service composition tools, and as a stand-alone tool for Web service developers.

REFERENCES

• 1: W. M. P. van der Aalst, Woflan: a Petri-net-based workflow analyzer, Systems Analysis Modelling Simulation, v.35 n.3, p.345-357, Nov. 1999
• 2: Chitta Baral , Vladik Kreinovich , Raúl Trejo, Computational complexity of planning and approximate planning in the presence of incompleteness, Artificial Intelligence, v.122 n.1-2, p.241-267, Sept., 2000 [doi>10.1016/S0004-3702(00)00043-6]
• 3: V. Richard Benjamins, Enric Plaza,Enrico Motta, Dieter Fensel, Rudi Studer, Bob Wielinga, Guus Schreiber and Zdenek Zdrahal:Benjamins, V.R., Plaza, E., Motta, E., Fensel, D., Studer, R., Wielinga, B., Schreiber, G., and Zdrahal, Z. IBROW3 - An intelligent brokering service for
• 4: Berners-Lee, T., Hendler, J., Lassila, O. The Semantic Web, Scientific American, May, 2001.
• 5: Best, E. and Desel, J. Partial order behaviour and structure of Petri Nets. Formal Aspects of Computing, 2:123--138, 1990.
• 6: Avrim L. Blum , Merrick L. Furst, Fast planning through planning graph analysis, Artificial Intelligence, v.90 n.1-2, p.281-300, Feb. 1997 [doi>10.1016/S0004-3702(96)00047-1]
• 7: Allan Cheng , Javier Esparza , Jens Palsberg, Complexity Results for 1-safe Nets, Proceedings of the 13th Conference on Foundations of Software Technology and Theoretical Computer Science, p.326-337, December 15-17, 1993
• 8: DAML-S versions 0.5 and 0.6. http://www.daml.org/services/.
• 9: DAML Services Coalition: Ankolekar, A., Burstein, M., Hobbs, J., Lassila, O., Martin, D., McIlraith, S., Narayanan, S., Paolucci, M., Payne, T., Sycara, K., Zeng, H. DAML-S: Semantic Markup for Web Services, Proc. International Semantic Web Working Symposium (SWWS), 2001.
• 10: Denker, G., Hobbs, J., Martin D., Narayanan, S. and Waldinger, R., Querying and accessing information on the semantic web, Proc. Semantic Web Workshop, in conjunction with 10th International Worldwide Web Conference, 2001.
• 11: Jörg Desel , Javier Esparza, Shortest Paths in Reachability Graphs, Proceedings of the 14th International Conference on Application and Theory of Petri Nets, p.224-241, June 21-25, 1993
• 12: Clarence A. Ellis , Gary J. Nutt, Modeling and Enactment of Workflow Systems, Proceedings of the 14th International Conference on Application and Theory of Petri Nets, p.1-16, June 21-25, 1993
• 13: Fikes, R. and McGuinness, D. An Axiomatic Semantics for RDF, RDF-S, and DAML+OIL, Manuscript. March, 2001.
• 14: Giuseppe de Giacomo , Yves Lespérance , Hector J. Levesque, ConGolog, a concurrent programming language based on the situation calculus, Artificial Intelligence, v.121 n.1-2, p.109-169, Aug. 2000 [doi>10.1016/S0004-3702(00)00031-X]
• 15: Gruninger, M. Personal communications, August, 2001.
• 16: James Hendler, Agents and the Semantic Web, IEEE Intelligent Systems, v.16 n.2, p.30-37, March 2001 [doi>10.1109/5254.920597]
• 17: Hendler, J. and McGuinness, D. The DARPA Agent Markup Language. IEEE Intelligent Systems, Trends and Controversies, pp. 6--7, November/December 2000.
• 18: Rodney R. Howell , Louis E. Rosier, Problems concerning fairness and temporal logic for conflict-free Petri nets, Theoretical Computer Science, v.64 n.3, p.305-329, 29 May 1989 [doi>10.1016/0304-3975(89)90053-4]
• 19: Henry A. Kautz , Bart Selman, Unifying SAT-based and Graph-based Planning, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.318-325, July 31-August 06, 1999
• 20: David Lowe , Mann , Steve Wright , Xin Chen , Todd Mondor, BizTalk Server: The Complete Reference with Cdrom, McGraw-Hill Professional, 2001
• 21: Mayr, E.W. An algorithm for the general Petri net reachability problem. SIAM Journal on Computing, 13:441--460, 1984.
• 22: McIlraith, S. and Fadel, R. Planning with Complex Actions. Proc. International Workshop on Non-Monotonic Reasoning (NMR2002). To appear, 2002.
• 23: 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]
• 24: McIlraith, S. and Son, T. Adapting Golog for composition of semantic Web services, Proc 8th International Conference on Principles of Knowledge Representation and Reasoning. To appear, 2002.
• 25: José Meseguer , Ugo Montanari, Petri nets are moniods, Information and Computation, v.88 n.2, p.105-155, Oct. 1990 [doi>10.1016/0890-5401(90)90013-8]
• 26: Murata, T. Petri Nets: Properties, analysis and applications. Proc. of the IEEE, 77(4):541--580, 1989.
• 27: Srinivas Narayanan, Reasoning About Actions in Narrative Understanding, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.350-357, July 31-August 06, 1999
• 28: Knowlege in action: logical foundations for specifying and implementing dynamical systems, MIT Press, Cambridge, MA, 2001
• 29: Schlenoff, M. Gruninger, F. Tissot, J. Valois, J. Lubell, J. Lee, The Process Specification Language (PSL): Overview and Version 1.0 Specification, NISTIR 6459, National Institute of Standards and Technology, Gaithersburg, MD, 2001.
• 30: van Harmelen, F. and Horrocks, I. FAQs on OIL: the Ontology Inference Layer. IEEE Intelligent Systems, Trends and Controversies, pp. 3--6, November/December 2000.
• 31: Waldinger, R. Deductive composition of Web software agents. Proc. NASA Goddard Workshop on Formal Approaches to Agent-Based Systems, LNCS 1871, Springer-Verlag. 2000.
• 32: Glynn Winskel, Petr nets, algebras, morphisms, and compositionality, Information and Computation, v.72 n.3, p.197-238, March 1987 [doi>10.1016/0890-5401(87)90032-0]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Representation languages

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Predicate logic; Frames and scripts; Representations (procedural and rule-based)

General Terms:
Algorithms, Design, Languages, Standardization, Theory, Verification

Keywords:
DAML, automated reasoning, distributed systems, ontologies, semantic web, web service composition, web services