On the Computational Expressiveness of Model Transformation Languages

Common folklore in the model transformation community dictates that most transformation languages are Turing-complete. It is however seldom that a proof or an explanation is provided on why such property holds; due to the widely different features and execution models in these language, it is not immediately obvious what their computational expressiveness is. In this paper we present an analysis that clarifies the computational expressiveness of a large number of model transformation languages. The analysis confirms the folklore for all model transformation languages, except the bidirectional ones. While this excludes many verification techniques from being applied on the languages as a whole, it might be possible to verify subsets of these languages; this holds especially for those languages which provide optional termination checking or those that require the use of exotic constructs to achieve the stated level of expressiveness.