Syntactic Rule Based Approach toWeb Service Composition

This paper studies a problem of web service composition from a syntactic approach. In contrast with other approaches on enriched semantic description such as statetransition description of web services, our focus is in the case when only the input-output type information from the WSDL specifications is available. The web service composition problem is formally formulated as deriving a given desired type from a collection of available types and web services using a prescribed set of rules with costs. We show that solving the minimal cost composition is NP-complete in general, and present a practical solution based on dynamic programming. Experiements using a mixture of synthetic and real data sets show that our approach is viable and produces good results.