  Nowadays, Web Services (WS) remain a main actor in the implementation of
distributed applications. They represent a new promising paradigm for the
development, deployment and integration of Internet applications. These
services are in most cases unable to provide the required functionality; they
must be composed to provide appropriate services, richer and more interesting
for other applications as well as for human users. The composition of Web
services is considered as a strong point, which allows answering complex
queries by combining the functionality of multiple services within a same
composition. In this work we showed how the formalism of graphs can be used to
improve the composition of web services and make it automatic. We have proposed
the rewriting logic and its language Maude as a support for a graph-based
approach to automatic composition of web services. The proposed model has made
possible the exploration of different composition schemas as well as the formal
analysis of service compositions. The paper introduces a case study showing how
to apply our formalization.
