YES(?, 404) Initial complexity problem: 1: T: (1, 1) f12(a, b, c, d, e, f) -> f5(400, 0, 0, d, e, f) (?, 1) f5(a, b, c, d, e, f) -> f11(a, b, 0, 0, 0, f) [ b >= a /\ c = 0 ] (?, 1) f5(a, b, c, d, e, f) -> f10(a, b, c, c, c, f) [ c >= 1 ] (?, 1) f5(a, b, c, d, e, f) -> f10(a, b, c, c, c, f) [ 0 >= c + 1 ] (?, 1) f7(a, b, c, d, e, f) -> f5(a, b + 1, g, h, e, g) (?, 1) f8(a, b, c, d, e, f) -> f5(a, b + 1, g, h, e, g) (?, 1) f5(a, b, c, d, e, f) -> f5(a, b + 1, g, h, e, g) [ a >= b + 1 /\ c = 0 ] start location: f12 leaf cost: 0 Slicing away variables that do not contribute to conditions from problem 1 leaves variables [a, b, c]. We thus obtain the following problem: 2: T: (?, 1) f5(a, b, c) -> f5(a, b + 1, g) [ a >= b + 1 /\ c = 0 ] (?, 1) f8(a, b, c) -> f5(a, b + 1, g) (?, 1) f7(a, b, c) -> f5(a, b + 1, g) (?, 1) f5(a, b, c) -> f10(a, b, c) [ 0 >= c + 1 ] (?, 1) f5(a, b, c) -> f10(a, b, c) [ c >= 1 ] (?, 1) f5(a, b, c) -> f11(a, b, 0) [ b >= a /\ c = 0 ] (1, 1) f12(a, b, c) -> f5(400, 0, 0) start location: f12 leaf cost: 0 Repeatedly removing leaves of the complexity graph in problem 2 produces the following problem: 3: T: (?, 1) f5(a, b, c) -> f5(a, b + 1, g) [ a >= b + 1 /\ c = 0 ] (?, 1) f8(a, b, c) -> f5(a, b + 1, g) (?, 1) f7(a, b, c) -> f5(a, b + 1, g) (1, 1) f12(a, b, c) -> f5(400, 0, 0) start location: f12 leaf cost: 3 Testing for reachability in the complexity graph removes the following transitions from problem 3: f8(a, b, c) -> f5(a, b + 1, g) f7(a, b, c) -> f5(a, b + 1, g) We thus obtain the following problem: 4: T: (?, 1) f5(a, b, c) -> f5(a, b + 1, g) [ a >= b + 1 /\ c = 0 ] (1, 1) f12(a, b, c) -> f5(400, 0, 0) start location: f12 leaf cost: 3 A polynomial rank function with Pol(f5) = V_1 - V_2 Pol(f12) = 400 orients all transitions weakly and the transition f5(a, b, c) -> f5(a, b + 1, g) [ a >= b + 1 /\ c = 0 ] strictly and produces the following problem: 5: T: (400, 1) f5(a, b, c) -> f5(a, b + 1, g) [ a >= b + 1 /\ c = 0 ] (1, 1) f12(a, b, c) -> f5(400, 0, 0) start location: f12 leaf cost: 3 Complexity upper bound 404 Time: 0.113 sec (SMT: 0.106 sec)