Automatic composition of web services has drawn a great deal of attention recently. By composition, we mean taking advantage of currently existing web services to provide a new service that does not exist on its own. Therefore, in order to have a more complex service, we can use some semantically related simpler web services and execute them in such a way that the whole set provides the desired service. There are web service specification languages that specify semantic properties of web services. These languages are helpful in searching for those web services that can participate in a composition. This work is aimed at searching among web services in order to find those whose composition provides a specific behavior. Those web services found after this search are incrementally composed together to build a new service that realizes that behavior. Our technique takes advantage of graph structures and also a particular formalism called interface automata.