Service discovery of state-dependent services has to take workflow aspects into account. To increase the usability of a query result, the results should be ordered with regard to their relevance, that is, the similarity of the query and the result list entry. Although there exist service discovery solutions considering workflow aspects, there is no support of ordering the result list. However, there exist several similarity measures in different research areas, which are applied in this paper to workflow similarity based on Finite State Automata.