On the Computational Expressiveness of Model Transformation Languages

TR-2015-184, Author: Ahmad Salim Al-Sibahi

On the Computational Expressiveness of Model Transformation Languages

Ahmad Salim Al-Sibahi

Abstract

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.

Technical report TR-2015-184 in IT University Technical Report Series, January 2015. 

Available as PDF