Composing web services through automatic reformulation of service specifications

Typical approaches to service composition seek to realize a goal service specification, described using a labeled transition system (LTS) provided by a service developer, by constructing a structurally equivalent LTS using a set of available component services (also described using LTSs) that match the input and output requirements of the transitions. As such, existing composition approaches fail to realize the goal LTS whenever available component service LTSs cannot be used to "mimic" the structure of the goal LTS. This failure requires that the service developer formulates an alternate goal LTS and re-iterates the composition step. However, the process of manual reformulation of the goal LTS is both laborious and error prone. In this setting, we describe an efficient data structure and algorithms for analyzing data and control flow dependencies implicit in a user-supplied goal LTS specification to automatically generate alternate LTS specifications that capture the same overall functionality with respect to the data and control dependencies, and determine whether any of the alternatives can lead to a feasible composition. The result is a significant reduction in the need for the tedious manual intervention in reformulating LTS specifications of the goal service.