YES(?, 5*a + 2*b + 3*c + 4) Initial complexity problem: 1: T: (?, 1) eval(a, b, c) -> eval(a, b + 1, c) [ a >= b + 1 /\ c >= b + 1 ] (?, 1) eval(a, b, c) -> eval(a, b, c + 1) [ a >= b + 1 /\ b >= c ] (1, 1) start(a, b, c) -> eval(a, b, c) start location: start leaf cost: 0 A polynomial rank function with Pol(eval) = 4*V_1 - V_2 - 3*V_3 - 3 Pol(start) = 4*V_1 - V_2 - 3*V_3 - 3 orients all transitions weakly and the transition eval(a, b, c) -> eval(a, b, c + 1) [ a >= b + 1 /\ b >= c ] strictly and produces the following problem: 2: T: (?, 1) eval(a, b, c) -> eval(a, b + 1, c) [ a >= b + 1 /\ c >= b + 1 ] (4*a + b + 3*c + 3, 1) eval(a, b, c) -> eval(a, b, c + 1) [ a >= b + 1 /\ b >= c ] (1, 1) start(a, b, c) -> eval(a, b, c) start location: start leaf cost: 0 A polynomial rank function with Pol(eval) = V_1 - V_2 Pol(start) = V_1 - V_2 orients all transitions weakly and the transition eval(a, b, c) -> eval(a, b + 1, c) [ a >= b + 1 /\ c >= b + 1 ] strictly and produces the following problem: 3: T: (a + b, 1) eval(a, b, c) -> eval(a, b + 1, c) [ a >= b + 1 /\ c >= b + 1 ] (4*a + b + 3*c + 3, 1) eval(a, b, c) -> eval(a, b, c + 1) [ a >= b + 1 /\ b >= c ] (1, 1) start(a, b, c) -> eval(a, b, c) start location: start leaf cost: 0 Complexity upper bound 5*a + 2*b + 3*c + 4 Time: 0.110 sec (SMT: 0.102 sec)