Abstract: As for the technology of semantic Web services automatic composition, the key which solves this problem is to construct a model of the formal description of Web services and realize the Web service composition request by using this dependency relationship of available data. However, current approaches for service composition may return back lots of global state with exponential growth. To address this issue, backward reasoning algorithm of fuzzy petri nets for semantic Web services automatic composition with correctness guarantees was proposed. The algorithm fully takes advantage of mathematics foundation of petri nets, a complex system can be transformed into a simpler system closely related to the current problems. Thus, the space complexity of the algorithm can be reduced. Finally, an example was used to illustrate the applicability of this approach.

Key words: Web services composition, Fuzzy petri nets, Backward reasoning, Relational matrix