YES(?, 202*b + 2*a + 2*a*b + 103) Initial complexity problem: 1: T: (?, 1) f300(a, b, c) -> f300(a - 99, 0, c) [ 0 >= a + 1 /\ b + 1 = 0 ] (?, 1) f300(a, b, c) -> f300(a + 1, b + 1, c) [ 0 >= a + 1 /\ b >= 0 ] (?, 1) f300(a, b, c) -> f300(a + 1, b + 1, c) [ 0 >= a + 1 /\ 0 >= b + 2 ] (?, 1) f300(a, b, c) -> f1(a, b, d) [ a >= 0 ] (1, 1) f2(a, b, c) -> f300(a, b, c) start location: f2 leaf cost: 0 Repeatedly removing leaves of the complexity graph in problem 1 produces the following problem: 2: T: (?, 1) f300(a, b, c) -> f300(a - 99, 0, c) [ 0 >= a + 1 /\ b + 1 = 0 ] (?, 1) f300(a, b, c) -> f300(a + 1, b + 1, c) [ 0 >= a + 1 /\ b >= 0 ] (?, 1) f300(a, b, c) -> f300(a + 1, b + 1, c) [ 0 >= a + 1 /\ 0 >= b + 2 ] (1, 1) f2(a, b, c) -> f300(a, b, c) start location: f2 leaf cost: 1 A polynomial rank function with Pol(f300) = -2*V_2 - 1 Pol(f2) = -2*V_2 - 1 orients all transitions weakly and the transitions f300(a, b, c) -> f300(a + 1, b + 1, c) [ 0 >= a + 1 /\ 0 >= b + 2 ] f300(a, b, c) -> f300(a - 99, 0, c) [ 0 >= a + 1 /\ b + 1 = 0 ] strictly and produces the following problem: 3: T: (2*b + 1, 1) f300(a, b, c) -> f300(a - 99, 0, c) [ 0 >= a + 1 /\ b + 1 = 0 ] (?, 1) f300(a, b, c) -> f300(a + 1, b + 1, c) [ 0 >= a + 1 /\ b >= 0 ] (2*b + 1, 1) f300(a, b, c) -> f300(a + 1, b + 1, c) [ 0 >= a + 1 /\ 0 >= b + 2 ] (1, 1) f2(a, b, c) -> f300(a, b, c) start location: f2 leaf cost: 1 A polynomial rank function with Pol(f300) = -V_1 and size complexities S("f2(a, b, c) -> f300(a, b, c)", 0-0) = a S("f2(a, b, c) -> f300(a, b, c)", 0-1) = b S("f2(a, b, c) -> f300(a, b, c)", 0-2) = c S("f300(a, b, c) -> f300(a + 1, b + 1, c) [ 0 >= a + 1 /\\ 0 >= b + 2 ]", 0-0) = a S("f300(a, b, c) -> f300(a + 1, b + 1, c) [ 0 >= a + 1 /\\ 0 >= b + 2 ]", 0-1) = b S("f300(a, b, c) -> f300(a + 1, b + 1, c) [ 0 >= a + 1 /\\ 0 >= b + 2 ]", 0-2) = c S("f300(a, b, c) -> f300(a + 1, b + 1, c) [ 0 >= a + 1 /\\ b >= 0 ]", 0-0) = a + 99 S("f300(a, b, c) -> f300(a + 1, b + 1, c) [ 0 >= a + 1 /\\ b >= 0 ]", 0-1) = ? S("f300(a, b, c) -> f300(a + 1, b + 1, c) [ 0 >= a + 1 /\\ b >= 0 ]", 0-2) = c S("f300(a, b, c) -> f300(a - 99, 0, c) [ 0 >= a + 1 /\\ b + 1 = 0 ]", 0-0) = a + 99 S("f300(a, b, c) -> f300(a - 99, 0, c) [ 0 >= a + 1 /\\ b + 1 = 0 ]", 0-1) = 0 S("f300(a, b, c) -> f300(a - 99, 0, c) [ 0 >= a + 1 /\\ b + 1 = 0 ]", 0-2) = c orients the transition f300(a, b, c) -> f300(a + 1, b + 1, c) [ 0 >= a + 1 /\ b >= 0 ] weakly and the transition f300(a, b, c) -> f300(a + 1, b + 1, c) [ 0 >= a + 1 /\ b >= 0 ] strictly and produces the following problem: 4: T: (2*b + 1, 1) f300(a, b, c) -> f300(a - 99, 0, c) [ 0 >= a + 1 /\ b + 1 = 0 ] (2*a + 2*a*b + 198*b + 99, 1) f300(a, b, c) -> f300(a + 1, b + 1, c) [ 0 >= a + 1 /\ b >= 0 ] (2*b + 1, 1) f300(a, b, c) -> f300(a + 1, b + 1, c) [ 0 >= a + 1 /\ 0 >= b + 2 ] (1, 1) f2(a, b, c) -> f300(a, b, c) start location: f2 leaf cost: 1 Complexity upper bound 202*b + 2*a + 2*a*b + 103 Time: 0.301 sec (SMT: 0.287 sec)