YES(?, 15*a + 12*b + 27*c + 18) Initial complexity problem: 1: T: (1, 1) evalEx6start(a, b, c) -> evalEx6entryin(a, b, c) (?, 1) evalEx6entryin(a, b, c) -> evalEx6bb3in(b, a, c) (?, 1) evalEx6bb3in(a, b, c) -> evalEx6bbin(a, b, c) [ c >= b + 1 ] (?, 1) evalEx6bb3in(a, b, c) -> evalEx6returnin(a, b, c) [ b >= c ] (?, 1) evalEx6bbin(a, b, c) -> evalEx6bb1in(a, b, c) [ a >= b + 1 ] (?, 1) evalEx6bbin(a, b, c) -> evalEx6bb2in(a, b, c) [ b >= a ] (?, 1) evalEx6bb1in(a, b, c) -> evalEx6bb3in(a, b + 1, c) (?, 1) evalEx6bb2in(a, b, c) -> evalEx6bb3in(a + 1, b, c) (?, 1) evalEx6returnin(a, b, c) -> evalEx6stop(a, b, c) start location: evalEx6start leaf cost: 0 Repeatedly removing leaves of the complexity graph in problem 1 produces the following problem: 2: T: (1, 1) evalEx6start(a, b, c) -> evalEx6entryin(a, b, c) (?, 1) evalEx6entryin(a, b, c) -> evalEx6bb3in(b, a, c) (?, 1) evalEx6bb3in(a, b, c) -> evalEx6bbin(a, b, c) [ c >= b + 1 ] (?, 1) evalEx6bbin(a, b, c) -> evalEx6bb1in(a, b, c) [ a >= b + 1 ] (?, 1) evalEx6bbin(a, b, c) -> evalEx6bb2in(a, b, c) [ b >= a ] (?, 1) evalEx6bb1in(a, b, c) -> evalEx6bb3in(a, b + 1, c) (?, 1) evalEx6bb2in(a, b, c) -> evalEx6bb3in(a + 1, b, c) start location: evalEx6start leaf cost: 2 Repeatedly propagating knowledge in problem 2 produces the following problem: 3: T: (1, 1) evalEx6start(a, b, c) -> evalEx6entryin(a, b, c) (1, 1) evalEx6entryin(a, b, c) -> evalEx6bb3in(b, a, c) (?, 1) evalEx6bb3in(a, b, c) -> evalEx6bbin(a, b, c) [ c >= b + 1 ] (?, 1) evalEx6bbin(a, b, c) -> evalEx6bb1in(a, b, c) [ a >= b + 1 ] (?, 1) evalEx6bbin(a, b, c) -> evalEx6bb2in(a, b, c) [ b >= a ] (?, 1) evalEx6bb1in(a, b, c) -> evalEx6bb3in(a, b + 1, c) (?, 1) evalEx6bb2in(a, b, c) -> evalEx6bb3in(a + 1, b, c) start location: evalEx6start leaf cost: 2 Applied AI with 'oct' on problem 3 to obtain the following invariants: For symbol evalEx6bb1in: -X_2 + X_3 - 1 >= 0 /\ X_1 - X_2 - 1 >= 0 For symbol evalEx6bb2in: -X_2 + X_3 - 1 >= 0 /\ -X_1 + X_3 - 1 >= 0 /\ -X_1 + X_2 >= 0 For symbol evalEx6bbin: -X_2 + X_3 - 1 >= 0 This yielded the following problem: 4: T: (?, 1) evalEx6bb2in(a, b, c) -> evalEx6bb3in(a + 1, b, c) [ -b + c - 1 >= 0 /\ -a + c - 1 >= 0 /\ -a + b >= 0 ] (?, 1) evalEx6bb1in(a, b, c) -> evalEx6bb3in(a, b + 1, c) [ -b + c - 1 >= 0 /\ a - b - 1 >= 0 ] (?, 1) evalEx6bbin(a, b, c) -> evalEx6bb2in(a, b, c) [ -b + c - 1 >= 0 /\ b >= a ] (?, 1) evalEx6bbin(a, b, c) -> evalEx6bb1in(a, b, c) [ -b + c - 1 >= 0 /\ a >= b + 1 ] (?, 1) evalEx6bb3in(a, b, c) -> evalEx6bbin(a, b, c) [ c >= b + 1 ] (1, 1) evalEx6entryin(a, b, c) -> evalEx6bb3in(b, a, c) (1, 1) evalEx6start(a, b, c) -> evalEx6entryin(a, b, c) start location: evalEx6start leaf cost: 2 A polynomial rank function with Pol(evalEx6bb2in) = -4*V_1 - 3*V_2 + 7*V_3 - 6 Pol(evalEx6bb3in) = -4*V_1 - 3*V_2 + 7*V_3 - 4 Pol(evalEx6bb1in) = -4*V_1 - 3*V_2 + 7*V_3 - 6 Pol(evalEx6bbin) = -4*V_1 - 3*V_2 + 7*V_3 - 5 Pol(evalEx6entryin) = -3*V_1 - 4*V_2 + 7*V_3 - 4 Pol(evalEx6start) = -3*V_1 - 4*V_2 + 7*V_3 - 4 orients all transitions weakly and the transition evalEx6bb2in(a, b, c) -> evalEx6bb3in(a + 1, b, c) [ -b + c - 1 >= 0 /\ -a + c - 1 >= 0 /\ -a + b >= 0 ] strictly and produces the following problem: 5: T: (3*a + 4*b + 7*c + 4, 1) evalEx6bb2in(a, b, c) -> evalEx6bb3in(a + 1, b, c) [ -b + c - 1 >= 0 /\ -a + c - 1 >= 0 /\ -a + b >= 0 ] (?, 1) evalEx6bb1in(a, b, c) -> evalEx6bb3in(a, b + 1, c) [ -b + c - 1 >= 0 /\ a - b - 1 >= 0 ] (?, 1) evalEx6bbin(a, b, c) -> evalEx6bb2in(a, b, c) [ -b + c - 1 >= 0 /\ b >= a ] (?, 1) evalEx6bbin(a, b, c) -> evalEx6bb1in(a, b, c) [ -b + c - 1 >= 0 /\ a >= b + 1 ] (?, 1) evalEx6bb3in(a, b, c) -> evalEx6bbin(a, b, c) [ c >= b + 1 ] (1, 1) evalEx6entryin(a, b, c) -> evalEx6bb3in(b, a, c) (1, 1) evalEx6start(a, b, c) -> evalEx6entryin(a, b, c) start location: evalEx6start leaf cost: 2 A polynomial rank function with Pol(evalEx6bbin) = 1 Pol(evalEx6bb2in) = 0 Pol(evalEx6bb1in) = 1 Pol(evalEx6bb3in) = 1 and size complexities S("evalEx6start(a, b, c) -> evalEx6entryin(a, b, c)", 0-0) = a S("evalEx6start(a, b, c) -> evalEx6entryin(a, b, c)", 0-1) = b S("evalEx6start(a, b, c) -> evalEx6entryin(a, b, c)", 0-2) = c S("evalEx6entryin(a, b, c) -> evalEx6bb3in(b, a, c)", 0-0) = b S("evalEx6entryin(a, b, c) -> evalEx6bb3in(b, a, c)", 0-1) = a S("evalEx6entryin(a, b, c) -> evalEx6bb3in(b, a, c)", 0-2) = c S("evalEx6bb3in(a, b, c) -> evalEx6bbin(a, b, c) [ c >= b + 1 ]", 0-0) = 8*a + 8*b + 8*c + 256 S("evalEx6bb3in(a, b, c) -> evalEx6bbin(a, b, c) [ c >= b + 1 ]", 0-1) = ? S("evalEx6bb3in(a, b, c) -> evalEx6bbin(a, b, c) [ c >= b + 1 ]", 0-2) = c S("evalEx6bbin(a, b, c) -> evalEx6bb1in(a, b, c) [ -b + c - 1 >= 0 /\\ a >= b + 1 ]", 0-0) = 8*a + 8*b + 8*c + 256 S("evalEx6bbin(a, b, c) -> evalEx6bb1in(a, b, c) [ -b + c - 1 >= 0 /\\ a >= b + 1 ]", 0-1) = ? S("evalEx6bbin(a, b, c) -> evalEx6bb1in(a, b, c) [ -b + c - 1 >= 0 /\\ a >= b + 1 ]", 0-2) = c S("evalEx6bbin(a, b, c) -> evalEx6bb2in(a, b, c) [ -b + c - 1 >= 0 /\\ b >= a ]", 0-0) = 8*a + 8*b + 8*c + 256 S("evalEx6bbin(a, b, c) -> evalEx6bb2in(a, b, c) [ -b + c - 1 >= 0 /\\ b >= a ]", 0-1) = ? S("evalEx6bbin(a, b, c) -> evalEx6bb2in(a, b, c) [ -b + c - 1 >= 0 /\\ b >= a ]", 0-2) = c S("evalEx6bb1in(a, b, c) -> evalEx6bb3in(a, b + 1, c) [ -b + c - 1 >= 0 /\\ a - b - 1 >= 0 ]", 0-0) = 8*a + 8*b + 8*c + 256 S("evalEx6bb1in(a, b, c) -> evalEx6bb3in(a, b + 1, c) [ -b + c - 1 >= 0 /\\ a - b - 1 >= 0 ]", 0-1) = ? S("evalEx6bb1in(a, b, c) -> evalEx6bb3in(a, b + 1, c) [ -b + c - 1 >= 0 /\\ a - b - 1 >= 0 ]", 0-2) = c S("evalEx6bb2in(a, b, c) -> evalEx6bb3in(a + 1, b, c) [ -b + c - 1 >= 0 /\\ -a + c - 1 >= 0 /\\ -a + b >= 0 ]", 0-0) = 8*a + 8*b + 8*c + 256 S("evalEx6bb2in(a, b, c) -> evalEx6bb3in(a + 1, b, c) [ -b + c - 1 >= 0 /\\ -a + c - 1 >= 0 /\\ -a + b >= 0 ]", 0-1) = ? S("evalEx6bb2in(a, b, c) -> evalEx6bb3in(a + 1, b, c) [ -b + c - 1 >= 0 /\\ -a + c - 1 >= 0 /\\ -a + b >= 0 ]", 0-2) = c orients the transitions evalEx6bbin(a, b, c) -> evalEx6bb2in(a, b, c) [ -b + c - 1 >= 0 /\ b >= a ] evalEx6bbin(a, b, c) -> evalEx6bb1in(a, b, c) [ -b + c - 1 >= 0 /\ a >= b + 1 ] evalEx6bb3in(a, b, c) -> evalEx6bbin(a, b, c) [ c >= b + 1 ] evalEx6bb1in(a, b, c) -> evalEx6bb3in(a, b + 1, c) [ -b + c - 1 >= 0 /\ a - b - 1 >= 0 ] weakly and the transition evalEx6bbin(a, b, c) -> evalEx6bb2in(a, b, c) [ -b + c - 1 >= 0 /\ b >= a ] strictly and produces the following problem: 6: T: (3*a + 4*b + 7*c + 4, 1) evalEx6bb2in(a, b, c) -> evalEx6bb3in(a + 1, b, c) [ -b + c - 1 >= 0 /\ -a + c - 1 >= 0 /\ -a + b >= 0 ] (?, 1) evalEx6bb1in(a, b, c) -> evalEx6bb3in(a, b + 1, c) [ -b + c - 1 >= 0 /\ a - b - 1 >= 0 ] (3*a + 4*b + 7*c + 5, 1) evalEx6bbin(a, b, c) -> evalEx6bb2in(a, b, c) [ -b + c - 1 >= 0 /\ b >= a ] (?, 1) evalEx6bbin(a, b, c) -> evalEx6bb1in(a, b, c) [ -b + c - 1 >= 0 /\ a >= b + 1 ] (?, 1) evalEx6bb3in(a, b, c) -> evalEx6bbin(a, b, c) [ c >= b + 1 ] (1, 1) evalEx6entryin(a, b, c) -> evalEx6bb3in(b, a, c) (1, 1) evalEx6start(a, b, c) -> evalEx6entryin(a, b, c) start location: evalEx6start leaf cost: 2 A polynomial rank function with Pol(evalEx6bb2in) = -2*V_2 + 2*V_3 Pol(evalEx6bb3in) = -2*V_2 + 2*V_3 Pol(evalEx6bb1in) = -2*V_2 + 2*V_3 - 1 Pol(evalEx6bbin) = -2*V_2 + 2*V_3 Pol(evalEx6entryin) = -2*V_1 + 2*V_3 Pol(evalEx6start) = -2*V_1 + 2*V_3 orients all transitions weakly and the transitions evalEx6bbin(a, b, c) -> evalEx6bb1in(a, b, c) [ -b + c - 1 >= 0 /\ a >= b + 1 ] evalEx6bb1in(a, b, c) -> evalEx6bb3in(a, b + 1, c) [ -b + c - 1 >= 0 /\ a - b - 1 >= 0 ] strictly and produces the following problem: 7: T: (3*a + 4*b + 7*c + 4, 1) evalEx6bb2in(a, b, c) -> evalEx6bb3in(a + 1, b, c) [ -b + c - 1 >= 0 /\ -a + c - 1 >= 0 /\ -a + b >= 0 ] (2*a + 2*c, 1) evalEx6bb1in(a, b, c) -> evalEx6bb3in(a, b + 1, c) [ -b + c - 1 >= 0 /\ a - b - 1 >= 0 ] (3*a + 4*b + 7*c + 5, 1) evalEx6bbin(a, b, c) -> evalEx6bb2in(a, b, c) [ -b + c - 1 >= 0 /\ b >= a ] (2*a + 2*c, 1) evalEx6bbin(a, b, c) -> evalEx6bb1in(a, b, c) [ -b + c - 1 >= 0 /\ a >= b + 1 ] (?, 1) evalEx6bb3in(a, b, c) -> evalEx6bbin(a, b, c) [ c >= b + 1 ] (1, 1) evalEx6entryin(a, b, c) -> evalEx6bb3in(b, a, c) (1, 1) evalEx6start(a, b, c) -> evalEx6entryin(a, b, c) start location: evalEx6start leaf cost: 2 Repeatedly propagating knowledge in problem 7 produces the following problem: 8: T: (3*a + 4*b + 7*c + 4, 1) evalEx6bb2in(a, b, c) -> evalEx6bb3in(a + 1, b, c) [ -b + c - 1 >= 0 /\ -a + c - 1 >= 0 /\ -a + b >= 0 ] (2*a + 2*c, 1) evalEx6bb1in(a, b, c) -> evalEx6bb3in(a, b + 1, c) [ -b + c - 1 >= 0 /\ a - b - 1 >= 0 ] (3*a + 4*b + 7*c + 5, 1) evalEx6bbin(a, b, c) -> evalEx6bb2in(a, b, c) [ -b + c - 1 >= 0 /\ b >= a ] (2*a + 2*c, 1) evalEx6bbin(a, b, c) -> evalEx6bb1in(a, b, c) [ -b + c - 1 >= 0 /\ a >= b + 1 ] (5*a + 9*c + 4*b + 5, 1) evalEx6bb3in(a, b, c) -> evalEx6bbin(a, b, c) [ c >= b + 1 ] (1, 1) evalEx6entryin(a, b, c) -> evalEx6bb3in(b, a, c) (1, 1) evalEx6start(a, b, c) -> evalEx6entryin(a, b, c) start location: evalEx6start leaf cost: 2 Complexity upper bound 15*a + 12*b + 27*c + 18 Time: 0.348 sec (SMT: 0.327 sec)