YES(?, a + b + 1) Initial complexity problem: 1: T: (?, 1) f(a, b) -> f(a + 1, b + 2) [ a >= b + 1 ] (1, 1) start(a, b) -> f(a, b) start location: start leaf cost: 0 A polynomial rank function with Pol(f) = V_1 - V_2 Pol(start) = V_1 - V_2 orients all transitions weakly and the transition f(a, b) -> f(a + 1, b + 2) [ a >= b + 1 ] strictly and produces the following problem: 2: T: (a + b, 1) f(a, b) -> f(a + 1, b + 2) [ a >= b + 1 ] (1, 1) start(a, b) -> f(a, b) start location: start leaf cost: 0 Complexity upper bound a + b + 1 Time: 0.058 sec (SMT: 0.055 sec)