YES(?, 35*a + 28*b + 28*c + 13) Initial complexity problem: 1: T: (1, 1) evalaaron2start(a, b, c) -> evalaaron2entryin(a, b, c) (?, 1) evalaaron2entryin(a, b, c) -> evalaaron2bb6in(a, c, b) [ a >= 0 ] (?, 1) evalaaron2entryin(a, b, c) -> evalaaron2returnin(a, b, c) [ 0 >= a + 1 ] (?, 1) evalaaron2bb6in(a, b, c) -> evalaaron2returnin(a, b, c) [ b >= c + 1 ] (?, 1) evalaaron2bb6in(a, b, c) -> evalaaron2returnin(a, b, c) [ 0 >= a + 1 ] (?, 1) evalaaron2bb6in(a, b, c) -> evalaaron2bb3in(a, b, c) [ c >= b /\ a >= 0 ] (?, 1) evalaaron2bb3in(a, b, c) -> evalaaron2bb4in(a, b, c) [ 0 >= d + 1 ] (?, 1) evalaaron2bb3in(a, b, c) -> evalaaron2bb4in(a, b, c) [ d >= 1 ] (?, 1) evalaaron2bb3in(a, b, c) -> evalaaron2bb5in(a, b, c) (?, 1) evalaaron2bb4in(a, b, c) -> evalaaron2bb6in(a, b, c - a - 1) (?, 1) evalaaron2bb5in(a, b, c) -> evalaaron2bb6in(a, b + a + 1, c) (?, 1) evalaaron2returnin(a, b, c) -> evalaaron2stop(a, b, c) start location: evalaaron2start leaf cost: 0 Repeatedly removing leaves of the complexity graph in problem 1 produces the following problem: 2: T: (1, 1) evalaaron2start(a, b, c) -> evalaaron2entryin(a, b, c) (?, 1) evalaaron2entryin(a, b, c) -> evalaaron2bb6in(a, c, b) [ a >= 0 ] (?, 1) evalaaron2bb6in(a, b, c) -> evalaaron2bb3in(a, b, c) [ c >= b /\ a >= 0 ] (?, 1) evalaaron2bb3in(a, b, c) -> evalaaron2bb4in(a, b, c) [ 0 >= d + 1 ] (?, 1) evalaaron2bb3in(a, b, c) -> evalaaron2bb4in(a, b, c) [ d >= 1 ] (?, 1) evalaaron2bb3in(a, b, c) -> evalaaron2bb5in(a, b, c) (?, 1) evalaaron2bb4in(a, b, c) -> evalaaron2bb6in(a, b, c - a - 1) (?, 1) evalaaron2bb5in(a, b, c) -> evalaaron2bb6in(a, b + a + 1, c) start location: evalaaron2start leaf cost: 4 Repeatedly propagating knowledge in problem 2 produces the following problem: 3: T: (1, 1) evalaaron2start(a, b, c) -> evalaaron2entryin(a, b, c) (1, 1) evalaaron2entryin(a, b, c) -> evalaaron2bb6in(a, c, b) [ a >= 0 ] (?, 1) evalaaron2bb6in(a, b, c) -> evalaaron2bb3in(a, b, c) [ c >= b /\ a >= 0 ] (?, 1) evalaaron2bb3in(a, b, c) -> evalaaron2bb4in(a, b, c) [ 0 >= d + 1 ] (?, 1) evalaaron2bb3in(a, b, c) -> evalaaron2bb4in(a, b, c) [ d >= 1 ] (?, 1) evalaaron2bb3in(a, b, c) -> evalaaron2bb5in(a, b, c) (?, 1) evalaaron2bb4in(a, b, c) -> evalaaron2bb6in(a, b, c - a - 1) (?, 1) evalaaron2bb5in(a, b, c) -> evalaaron2bb6in(a, b + a + 1, c) start location: evalaaron2start leaf cost: 4 A polynomial rank function with Pol(evalaaron2start) = 5*V_1 + 4*V_2 - 4*V_3 + 1 Pol(evalaaron2entryin) = 5*V_1 + 4*V_2 - 4*V_3 + 1 Pol(evalaaron2bb6in) = 5*V_1 - 4*V_2 + 4*V_3 + 1 Pol(evalaaron2bb3in) = V_1 - 4*V_2 + 4*V_3 - 1 Pol(evalaaron2bb4in) = V_1 - 4*V_2 + 4*V_3 - 2 Pol(evalaaron2bb5in) = V_1 - 4*V_2 + 4*V_3 - 2 orients all transitions weakly and the transition evalaaron2bb6in(a, b, c) -> evalaaron2bb3in(a, b, c) [ c >= b /\ a >= 0 ] strictly and produces the following problem: 4: T: (1, 1) evalaaron2start(a, b, c) -> evalaaron2entryin(a, b, c) (1, 1) evalaaron2entryin(a, b, c) -> evalaaron2bb6in(a, c, b) [ a >= 0 ] (5*a + 4*b + 4*c + 1, 1) evalaaron2bb6in(a, b, c) -> evalaaron2bb3in(a, b, c) [ c >= b /\ a >= 0 ] (?, 1) evalaaron2bb3in(a, b, c) -> evalaaron2bb4in(a, b, c) [ 0 >= d + 1 ] (?, 1) evalaaron2bb3in(a, b, c) -> evalaaron2bb4in(a, b, c) [ d >= 1 ] (?, 1) evalaaron2bb3in(a, b, c) -> evalaaron2bb5in(a, b, c) (?, 1) evalaaron2bb4in(a, b, c) -> evalaaron2bb6in(a, b, c - a - 1) (?, 1) evalaaron2bb5in(a, b, c) -> evalaaron2bb6in(a, b + a + 1, c) start location: evalaaron2start leaf cost: 4 Repeatedly propagating knowledge in problem 4 produces the following problem: 5: T: (1, 1) evalaaron2start(a, b, c) -> evalaaron2entryin(a, b, c) (1, 1) evalaaron2entryin(a, b, c) -> evalaaron2bb6in(a, c, b) [ a >= 0 ] (5*a + 4*b + 4*c + 1, 1) evalaaron2bb6in(a, b, c) -> evalaaron2bb3in(a, b, c) [ c >= b /\ a >= 0 ] (5*a + 4*b + 4*c + 1, 1) evalaaron2bb3in(a, b, c) -> evalaaron2bb4in(a, b, c) [ 0 >= d + 1 ] (5*a + 4*b + 4*c + 1, 1) evalaaron2bb3in(a, b, c) -> evalaaron2bb4in(a, b, c) [ d >= 1 ] (5*a + 4*b + 4*c + 1, 1) evalaaron2bb3in(a, b, c) -> evalaaron2bb5in(a, b, c) (10*a + 8*b + 8*c + 2, 1) evalaaron2bb4in(a, b, c) -> evalaaron2bb6in(a, b, c - a - 1) (5*a + 4*b + 4*c + 1, 1) evalaaron2bb5in(a, b, c) -> evalaaron2bb6in(a, b + a + 1, c) start location: evalaaron2start leaf cost: 4 Complexity upper bound 35*a + 28*b + 28*c + 13 Time: 0.290 sec (SMT: 0.277 sec)