Orchestration languages are of paramount importance when implementing business processes based on services. Several languages for specifying Web Services-based orchestrations are available today. Examples are the Web Services Business Process Execution Language or Windows Workflow. Patterns for process-aware information systems have frequently been used to assess such languages. Various studies discuss the degree of support such languages provide for certain sets of patterns. However, the traditional trivalent support measure is limited in terms of granularity and selectivity. This paper proposes an edit distance complexity measure that allows to overcome these issues. The applicability of this measure is demonstrated by an analysis of several orchestration languages using four different pattern catalogs.