We investigate interoperability aspects of Grid workflow systems with respect to models of computation (MoC), workflow languages, and workflow execution environments. We focus on the problems that affect interoperability and illustrate how these problems are tackled by current scientific workflows as well as how similar problems have been addressed in related areas. Emphasis is given to the differences and similarities between local and Grid workflows and how their peculiarities have a positive or negative impact on interoperability. Our long term objective is to achieve (logical) interoperability between workflow systems operating under different MoCs, using distinct language features, and using different execution environments.