The paper “Runtime Complexity Analysis via Tuple Interpretations” has been accepted for an extended version on MSCS journal.