Complexity Aspects of Web Services Composition

摘要

The web service composition problem can be stated as follows: given a finite state machine M, representing a service business protocol, and a set of finite state machines R, representing the business protocols of existing services, the question is to check whether there is a simulation relation between M and the shuffle product closure of R. This paper studies the impact of several parameters on the complexity of this problem. We show that the problem is Exptime-complete if we bound either: (ⅰ) the number of instances of services in R that can be used in a composition, or(ⅱ) the number of instances of services in R that can be used in parallel, or (ⅲ) the number of the so-called hybrid states in the finite state machines of R by 0, 1 or 2. The problem is still open for 3 hybrid states.