/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.koat /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^2)) proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, max(2, 2 * Arg_0) + max(2, 2 * Arg_0) * nat(max(4 * Arg_1, -4 + 4 * Arg_1, 8) + max(-8, min(8 + -8 * Arg_0, -8))) + 2 * max(2, 2 * Arg_0) * max(2 * Arg_1, 4, -2 + 2 * Arg_1) + max(2, 2 * Arg_0) * nat(max(min(2 + -2 * Arg_0, -2), -2) + max(2 * Arg_1, 4, -2 + 2 * Arg_1)) + max(2, 2 * Arg_0) * max(-1 + Arg_1, Arg_1, 0) + max(2, 2 * Arg_0) * max(1 + 2 * Arg_1, 5, -1 + 2 * Arg_1) + max(2, 2 * Arg_0) * nat(max(-1 + Arg_1, Arg_1) + max(min(2 + -2 * Arg_0, -2), -2)) + 2 * max(2, -2 + 2 * Arg_0) * max(2 * Arg_1, 4, -2 + 2 * Arg_1) + max(2, -2 + 2 * Arg_0) * nat(max(min(2 + -2 * Arg_0, -2), -2) + max(2 * Arg_1, 4, -2 + 2 * Arg_1)) + max(2, -2 + 2 * Arg_0) * max(-1 + Arg_1, Arg_1, 0) + max(2, -2 + 2 * Arg_0) * max(1 + 2 * Arg_1, 5, -1 + 2 * Arg_1) + max(2, -2 + 2 * Arg_0) * nat(max(-1 + Arg_1, Arg_1) + max(min(2 + -2 * Arg_0, -2), -2)) + max(2, -2 + 2 * Arg_0) + max(2, -2 + 2 * Arg_0) * nat(max(-8, min(8 + -8 * Arg_0, -8)) + max(4 * Arg_1, -4 + 4 * Arg_1, 8)) + nat(1 + 2 * Arg_1) + nat(2 * Arg_1 + max(2 + -2 * Arg_0, -2)) + nat(4 * Arg_1) + nat(-1 + 2 * Arg_1) + nat(-1 + Arg_1 + max(-2 * Arg_0, -2)) + nat(-4 + 4 * Arg_1 + max(-8 * Arg_0, -8)) + nat(-2 + 2 * Arg_1 + max(-2 * Arg_0, -2)) + nat(-4 + 4 * Arg_1) + nat(Arg_1 + max(2 + -2 * Arg_0, -2)) + max(2, 2 * Arg_1) + nat(-1 + Arg_1) * max(-3 + Arg_1, -2 + Arg_1, 0) + nat(-1 + Arg_1) * max(-4 + 2 * Arg_1, -2 + 2 * Arg_1, 0) + nat(-1 + Arg_1) * max(-8 + 4 * Arg_1, 0, -12 + 4 * Arg_1) + nat(Arg_1) * max(-3 + Arg_1, -2 + Arg_1, 0) + nat(Arg_1) * max(-4 + 2 * Arg_1, -2 + 2 * Arg_1, 0) + nat(Arg_1) * max(-8 + 4 * Arg_1, 0, -12 + 4 * Arg_1) + nat(2 * Arg_1) + nat(4 * Arg_1 + max(8 + -8 * Arg_0, -8))). (0) CpxIntTrs (1) Koat2 Proof [FINISHED, 2714 ms] (2) BOUNDS(1, max(2, 2 * Arg_0) + max(2, 2 * Arg_0) * nat(max(4 * Arg_1, -4 + 4 * Arg_1, 8) + max(-8, min(8 + -8 * Arg_0, -8))) + 2 * max(2, 2 * Arg_0) * max(2 * Arg_1, 4, -2 + 2 * Arg_1) + max(2, 2 * Arg_0) * nat(max(min(2 + -2 * Arg_0, -2), -2) + max(2 * Arg_1, 4, -2 + 2 * Arg_1)) + max(2, 2 * Arg_0) * max(-1 + Arg_1, Arg_1, 0) + max(2, 2 * Arg_0) * max(1 + 2 * Arg_1, 5, -1 + 2 * Arg_1) + max(2, 2 * Arg_0) * nat(max(-1 + Arg_1, Arg_1) + max(min(2 + -2 * Arg_0, -2), -2)) + 2 * max(2, -2 + 2 * Arg_0) * max(2 * Arg_1, 4, -2 + 2 * Arg_1) + max(2, -2 + 2 * Arg_0) * nat(max(min(2 + -2 * Arg_0, -2), -2) + max(2 * Arg_1, 4, -2 + 2 * Arg_1)) + max(2, -2 + 2 * Arg_0) * max(-1 + Arg_1, Arg_1, 0) + max(2, -2 + 2 * Arg_0) * max(1 + 2 * Arg_1, 5, -1 + 2 * Arg_1) + max(2, -2 + 2 * Arg_0) * nat(max(-1 + Arg_1, Arg_1) + max(min(2 + -2 * Arg_0, -2), -2)) + max(2, -2 + 2 * Arg_0) + max(2, -2 + 2 * Arg_0) * nat(max(-8, min(8 + -8 * Arg_0, -8)) + max(4 * Arg_1, -4 + 4 * Arg_1, 8)) + nat(1 + 2 * Arg_1) + nat(2 * Arg_1 + max(2 + -2 * Arg_0, -2)) + nat(4 * Arg_1) + nat(-1 + 2 * Arg_1) + nat(-1 + Arg_1 + max(-2 * Arg_0, -2)) + nat(-4 + 4 * Arg_1 + max(-8 * Arg_0, -8)) + nat(-2 + 2 * Arg_1 + max(-2 * Arg_0, -2)) + nat(-4 + 4 * Arg_1) + nat(Arg_1 + max(2 + -2 * Arg_0, -2)) + max(2, 2 * Arg_1) + nat(-1 + Arg_1) * max(-3 + Arg_1, -2 + Arg_1, 0) + nat(-1 + Arg_1) * max(-4 + 2 * Arg_1, -2 + 2 * Arg_1, 0) + nat(-1 + Arg_1) * max(-8 + 4 * Arg_1, 0, -12 + 4 * Arg_1) + nat(Arg_1) * max(-3 + Arg_1, -2 + Arg_1, 0) + nat(Arg_1) * max(-4 + 2 * Arg_1, -2 + 2 * Arg_1, 0) + nat(Arg_1) * max(-8 + 4 * Arg_1, 0, -12 + 4 * Arg_1) + nat(2 * Arg_1) + nat(4 * Arg_1 + max(8 + -8 * Arg_0, -8))) (3) Loat Proof [FINISHED, 93.0 s] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: eval1(A, B, C, D) -> Com_1(eval2(A - 1, B, C, D)) :|: A >= 2 eval1(A, B, C, D) -> Com_1(eval2(A, B - 1, C, D)) :|: 1 >= A eval2(A, B, C, D) -> Com_1(eval3(A, B, A, 2 * A)) :|: B >= 2 eval3(A, B, C, D) -> Com_1(eval4(A, B, C, D)) :|: B >= D && B >= 1 + D eval3(A, B, C, D) -> Com_1(eval4(A, B, C, D + 1)) :|: B >= D && B >= 1 + D eval3(A, B, C, D) -> Com_1(eval3(A, B, D, 2 * D)) :|: B >= D && B >= 1 + D && D >= 1 eval3(A, B, C, D) -> Com_1(eval3(A, B, D + 1, 2 * D + 2)) :|: B >= D && B >= 1 + D && D >= 1 eval3(A, B, C, D) -> Com_1(eval4(A, B, C, D)) :|: B >= D && B <= D eval3(A, B, C, D) -> Com_1(eval3(A, B, D, 2 * D)) :|: D >= 1 && B >= D && B <= D eval4(A, B, C, D) -> Com_1(eval2(A - 1, B, C, D)) :|: A >= 2 && A >= 1 && B >= 2 eval4(A, B, C, D) -> Com_1(eval2(A, B - 1, C, D)) :|: B >= 2 && A >= 1 && A <= 1 The start-symbols are:[eval1_4] ---------------------------------------- (1) Koat2 Proof (FINISHED) YES( ?, 2+(max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+max([0, 1+2*Arg_1])+(max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])])+(max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+2*max([Arg_1, -1+Arg_1])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([4, 2*max([Arg_1, -1+Arg_1])])+max([0, 2*Arg_1+max([-2, -2*(-1+Arg_0)])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])])+max([0, 2*Arg_1])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([4, 2*max([Arg_1, -1+Arg_1])])+max([0, Arg_1])+max([2, 2*Arg_0])+max([0, 2*Arg_1])+max([0, -1+Arg_1])+max([2, 2*(-1+Arg_0)])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([5, 1+2*max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-2, -2*max([1, -1+Arg_0])])+max([4, 2*max([Arg_1, -1+Arg_1])])])+max([0, 1+2*(-1+Arg_1)])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 2*(-1+Arg_1)+max([-2, -2*Arg_0])])+max([0, 2*(-1+Arg_1)])+max([0, -1+Arg_1])+max([0, 2*(-1+Arg_1)])+max([0, Arg_1]) {O(n^2)}) Initial Complexity Problem: Start: eval1 Program_Vars: Arg_0, Arg_1, Arg_2, Arg_3 Temp_Vars: Locations: eval1, eval2, eval3, eval4 Transitions: eval1(Arg_0,Arg_1,Arg_2,Arg_3) -> eval2(Arg_0-1,Arg_1,Arg_2,Arg_3):|:2 <= Arg_0 eval1(Arg_0,Arg_1,Arg_2,Arg_3) -> eval2(Arg_0,Arg_1-1,Arg_2,Arg_3):|:Arg_0 <= 1 eval2(Arg_0,Arg_1,Arg_2,Arg_3) -> eval3(Arg_0,Arg_1,Arg_0,(2)*Arg_0):|:2 <= Arg_1 eval3(Arg_0,Arg_1,Arg_2,Arg_3) -> eval3(Arg_0,Arg_1,Arg_3,(2)*Arg_3):|:2 <= Arg_1 && Arg_3 <= Arg_1 && 1+Arg_3 <= Arg_1 && 1 <= Arg_3 eval3(Arg_0,Arg_1,Arg_2,Arg_3) -> eval3(Arg_0,Arg_1,Arg_3+1,(2)*Arg_3+2):|:2 <= Arg_1 && Arg_3 <= Arg_1 && 1+Arg_3 <= Arg_1 && 1 <= Arg_3 eval3(Arg_0,Arg_1,Arg_2,Arg_3) -> eval3(Arg_0,Arg_1,Arg_3,(2)*Arg_3):|:2 <= Arg_1 && 1 <= Arg_3 && Arg_1 <= Arg_3 && Arg_3 <= Arg_1 eval3(Arg_0,Arg_1,Arg_2,Arg_3) -> eval4(Arg_0,Arg_1,Arg_2,Arg_3):|:2 <= Arg_1 && Arg_3 <= Arg_1 && 1+Arg_3 <= Arg_1 eval3(Arg_0,Arg_1,Arg_2,Arg_3) -> eval4(Arg_0,Arg_1,Arg_2,Arg_3+1):|:2 <= Arg_1 && Arg_3 <= Arg_1 && 1+Arg_3 <= Arg_1 eval3(Arg_0,Arg_1,Arg_2,Arg_3) -> eval4(Arg_0,Arg_1,Arg_2,Arg_3):|:2 <= Arg_1 && Arg_1 <= Arg_3 && Arg_3 <= Arg_1 eval4(Arg_0,Arg_1,Arg_2,Arg_3) -> eval2(Arg_0-1,Arg_1,Arg_2,Arg_3):|:2 <= Arg_1 && 2 <= Arg_0 && 1 <= Arg_0 && 2 <= Arg_1 eval4(Arg_0,Arg_1,Arg_2,Arg_3) -> eval2(Arg_0,Arg_1-1,Arg_2,Arg_3):|:2 <= Arg_1 && 2 <= Arg_1 && Arg_0 <= 1 && 1 <= Arg_0 Timebounds: Overall timebound: 2+(max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+max([0, 1+2*Arg_1])+(max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])])+(max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+2*max([Arg_1, -1+Arg_1])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([4, 2*max([Arg_1, -1+Arg_1])])+max([0, 2*Arg_1+max([-2, -2*(-1+Arg_0)])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])])+max([0, 2*Arg_1])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([4, 2*max([Arg_1, -1+Arg_1])])+max([0, Arg_1])+max([2, 2*Arg_0])+max([0, 2*Arg_1])+max([0, -1+Arg_1])+max([2, 2*(-1+Arg_0)])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([5, 1+2*max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-2, -2*max([1, -1+Arg_0])])+max([4, 2*max([Arg_1, -1+Arg_1])])])+max([0, 1+2*(-1+Arg_1)])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 2*(-1+Arg_1)+max([-2, -2*Arg_0])])+max([0, 2*(-1+Arg_1)])+max([0, -1+Arg_1])+max([0, 2*(-1+Arg_1)])+max([0, Arg_1]) {O(n^2)} 0: eval1->eval2: 1 {O(1)} 1: eval1->eval2: 1 {O(1)} 2: eval2->eval3: (max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([5, 1+2*max([Arg_1, -1+Arg_1])])+max([0, 1+2*(-1+Arg_1)])+max([0, 1+2*Arg_1]) {O(n^2)} 3: eval3->eval4: (max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([4, 2*max([Arg_1, -1+Arg_1])])+max([0, 2*(-1+Arg_1)])+max([0, 2*Arg_1]) {O(n^2)} 4: eval3->eval4: (max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])])+max([0, -1+Arg_1])+max([0, Arg_1]) {O(n^2)} 5: eval3->eval3: (max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]) {O(n^2)} 6: eval3->eval3: (max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]) {O(n^2)} 7: eval3->eval4: (max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([4, 2*max([Arg_1, -1+Arg_1])])+max([0, 2*(-1+Arg_1)])+max([0, 2*Arg_1]) {O(n^2)} 8: eval3->eval3: (max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+2*max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-2, -2*max([1, -1+Arg_0])])+max([4, 2*max([Arg_1, -1+Arg_1])])])+max([0, 2*(-1+Arg_1)+max([-2, -2*Arg_0])])+max([0, 2*Arg_1+max([-2, -2*(-1+Arg_0)])]) {O(n^2)} 9: eval4->eval2: max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]) {O(n)} 10: eval4->eval2: max([0, -1+Arg_1])+max([0, Arg_1]) {O(n)} Costbounds: Overall costbound: 2+(max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+max([0, 1+2*Arg_1])+(max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])])+(max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+2*max([Arg_1, -1+Arg_1])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([4, 2*max([Arg_1, -1+Arg_1])])+max([0, 2*Arg_1+max([-2, -2*(-1+Arg_0)])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])])+max([0, 2*Arg_1])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([4, 2*max([Arg_1, -1+Arg_1])])+max([0, Arg_1])+max([2, 2*Arg_0])+max([0, 2*Arg_1])+max([0, -1+Arg_1])+max([2, 2*(-1+Arg_0)])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([5, 1+2*max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-2, -2*max([1, -1+Arg_0])])+max([4, 2*max([Arg_1, -1+Arg_1])])])+max([0, 1+2*(-1+Arg_1)])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 2*(-1+Arg_1)+max([-2, -2*Arg_0])])+max([0, 2*(-1+Arg_1)])+max([0, -1+Arg_1])+max([0, 2*(-1+Arg_1)])+max([0, Arg_1]) {O(n^2)} 0: eval1->eval2: 1 {O(1)} 1: eval1->eval2: 1 {O(1)} 2: eval2->eval3: (max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([5, 1+2*max([Arg_1, -1+Arg_1])])+max([0, 1+2*(-1+Arg_1)])+max([0, 1+2*Arg_1]) {O(n^2)} 3: eval3->eval4: (max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([4, 2*max([Arg_1, -1+Arg_1])])+max([0, 2*(-1+Arg_1)])+max([0, 2*Arg_1]) {O(n^2)} 4: eval3->eval4: (max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])])+max([0, -1+Arg_1])+max([0, Arg_1]) {O(n^2)} 5: eval3->eval3: (max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]) {O(n^2)} 6: eval3->eval3: (max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]) {O(n^2)} 7: eval3->eval4: (max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([4, 2*max([Arg_1, -1+Arg_1])])+max([0, 2*(-1+Arg_1)])+max([0, 2*Arg_1]) {O(n^2)} 8: eval3->eval3: (max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+2*max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-2, -2*max([1, -1+Arg_0])])+max([4, 2*max([Arg_1, -1+Arg_1])])])+max([0, 2*(-1+Arg_1)+max([-2, -2*Arg_0])])+max([0, 2*Arg_1+max([-2, -2*(-1+Arg_0)])]) {O(n^2)} 9: eval4->eval2: max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]) {O(n)} 10: eval4->eval2: max([0, -1+Arg_1])+max([0, Arg_1]) {O(n)} Sizebounds: `Lower: 0: eval1->eval2, Arg_0: 1 {O(1)} 0: eval1->eval2, Arg_1: Arg_1 {O(n)} 0: eval1->eval2, Arg_2: Arg_2 {O(n)} 0: eval1->eval2, Arg_3: Arg_3 {O(n)} 1: eval1->eval2, Arg_0: Arg_0 {O(n)} 1: eval1->eval2, Arg_1: -1+Arg_1 {O(n)} 1: eval1->eval2, Arg_2: Arg_2 {O(n)} 1: eval1->eval2, Arg_3: Arg_3 {O(n)} 2: eval2->eval3, Arg_0: min([1, Arg_0]) {O(n)} 2: eval2->eval3, Arg_1: 2 {O(1)} 2: eval2->eval3, Arg_2: min([1, Arg_0]) {O(n)} 2: eval2->eval3, Arg_3: min([2, -(-2*Arg_0)]) {O(n)} 3: eval3->eval4, Arg_0: min([1, Arg_0]) {O(n)} 3: eval3->eval4, Arg_1: 2 {O(1)} 3: eval3->eval4, Arg_2: min([1, min([1, Arg_0])]) {O(n)} 3: eval3->eval4, Arg_3: min([2, min([2, -(-2*Arg_0)])]) {O(n)} 4: eval3->eval4, Arg_0: min([1, Arg_0]) {O(n)} 4: eval3->eval4, Arg_1: 2 {O(1)} 4: eval3->eval4, Arg_2: min([1, min([1, Arg_0])]) {O(n)} 4: eval3->eval4, Arg_3: min([3, min([3, -(-1+-2*Arg_0)])]) {O(n)} 5: eval3->eval3, Arg_0: min([1, Arg_0]) {O(n)} 5: eval3->eval3, Arg_1: 2 {O(1)} 5: eval3->eval3, Arg_2: 1 {O(1)} 5: eval3->eval3, Arg_3: 2 {O(1)} 6: eval3->eval3, Arg_0: min([1, Arg_0]) {O(n)} 6: eval3->eval3, Arg_1: 2 {O(1)} 6: eval3->eval3, Arg_2: 2 {O(1)} 6: eval3->eval3, Arg_3: 4 {O(1)} 7: eval3->eval4, Arg_0: min([1, Arg_0]) {O(n)} 7: eval3->eval4, Arg_1: 2 {O(1)} 7: eval3->eval4, Arg_2: min([1, min([1, Arg_0])]) {O(n)} 7: eval3->eval4, Arg_3: 2 {O(1)} 8: eval3->eval3, Arg_0: min([1, Arg_0]) {O(n)} 8: eval3->eval3, Arg_1: 2 {O(1)} 8: eval3->eval3, Arg_2: 2 {O(1)} 8: eval3->eval3, Arg_3: 4 {O(1)} 9: eval4->eval2, Arg_0: 1 {O(1)} 9: eval4->eval2, Arg_1: 2 {O(1)} 9: eval4->eval2, Arg_2: min([1, min([1, Arg_0])]) {O(n)} 9: eval4->eval2, Arg_3: min([2, min([2, min([3, min([3, min([2, min([-(-1+-2*Arg_0), -(-2*Arg_0)])])])])])]) {O(n)} 10: eval4->eval2, Arg_0: 1 {O(1)} 10: eval4->eval2, Arg_1: 1 {O(1)} 10: eval4->eval2, Arg_2: min([1, min([1, Arg_0])]) {O(n)} 10: eval4->eval2, Arg_3: min([2, min([2, min([3, min([3, min([2, min([-(-1+-2*Arg_0), -(-2*Arg_0)])])])])])]) {O(n)} `Upper: 0: eval1->eval2, Arg_0: -1+Arg_0 {O(n)} 0: eval1->eval2, Arg_1: Arg_1 {O(n)} 0: eval1->eval2, Arg_2: Arg_2 {O(n)} 0: eval1->eval2, Arg_3: Arg_3 {O(n)} 1: eval1->eval2, Arg_0: 1 {O(1)} 1: eval1->eval2, Arg_1: -1+Arg_1 {O(n)} 1: eval1->eval2, Arg_2: Arg_2 {O(n)} 1: eval1->eval2, Arg_3: Arg_3 {O(n)} 2: eval2->eval3, Arg_0: max([1, -1+Arg_0]) {O(n)} 2: eval2->eval3, Arg_1: max([Arg_1, -1+Arg_1]) {O(n)} 2: eval2->eval3, Arg_2: max([1, -1+Arg_0]) {O(n)} 2: eval2->eval3, Arg_3: max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])]) {O(n)} 3: eval3->eval4, Arg_0: max([1, -1+Arg_0]) {O(n)} 3: eval3->eval4, Arg_1: max([Arg_1, -1+Arg_1]) {O(n)} 3: eval3->eval4, Arg_2: max([1, max([3, max([2, max([1+2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]))*2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]))*((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])), max([1+max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])]), max([-1+Arg_0, max([2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]))*2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]))*((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])), max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])])])])])])]) {O(EXP)} 3: eval3->eval4, Arg_3: max([2, max([2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]))*2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]))*((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])), max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])]) {O(EXP)} 4: eval3->eval4, Arg_0: max([1, -1+Arg_0]) {O(n)} 4: eval3->eval4, Arg_1: max([Arg_1, -1+Arg_1]) {O(n)} 4: eval3->eval4, Arg_2: max([1, max([3, max([2, max([1+2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]))*2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]))*((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])), max([1+max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])]), max([-1+Arg_0, max([2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]))*2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]))*((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])), max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])])])])])])]) {O(EXP)} 4: eval3->eval4, Arg_3: max([3, max([1+2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]))*2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]))*((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])), 1+max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])]) {O(EXP)} 5: eval3->eval3, Arg_0: max([1, -1+Arg_0]) {O(n)} 5: eval3->eval3, Arg_1: max([Arg_1, -1+Arg_1]) {O(n)} 5: eval3->eval3, Arg_2: max([2, max([2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]))*2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]))*((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])), max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])]) {O(EXP)} 5: eval3->eval3, Arg_3: 2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]))*2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]))*((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])) {O(EXP)} 6: eval3->eval3, Arg_0: max([1, -1+Arg_0]) {O(n)} 6: eval3->eval3, Arg_1: max([Arg_1, -1+Arg_1]) {O(n)} 6: eval3->eval3, Arg_2: max([3, max([1+2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]))*2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]))*((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])), 1+max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])]) {O(EXP)} 6: eval3->eval3, Arg_3: 2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]))*2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]))*((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])) {O(EXP)} 7: eval3->eval4, Arg_0: max([1, -1+Arg_0]) {O(n)} 7: eval3->eval4, Arg_1: max([Arg_1, -1+Arg_1]) {O(n)} 7: eval3->eval4, Arg_2: max([1, max([3, max([2, max([1+2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]))*2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]))*((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])), max([1+max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])]), max([-1+Arg_0, max([2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]))*2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]))*((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])), max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])])])])])])]) {O(EXP)} 7: eval3->eval4, Arg_3: max([2, max([2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]))*2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]))*((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])), max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])]) {O(EXP)} 8: eval3->eval3, Arg_0: max([1, -1+Arg_0]) {O(n)} 8: eval3->eval3, Arg_1: max([Arg_1, -1+Arg_1]) {O(n)} 8: eval3->eval3, Arg_2: max([2, max([2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]))*2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]))*((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])), max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])]) {O(EXP)} 8: eval3->eval3, Arg_3: max([2*2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]))*2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]))*((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])), 2*max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])]) {O(EXP)} 9: eval4->eval2, Arg_0: max([1, -1+Arg_0]) {O(n)} 9: eval4->eval2, Arg_1: max([Arg_1, -1+Arg_1]) {O(n)} 9: eval4->eval2, Arg_2: max([1, max([3, max([2, max([1+2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]))*2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]))*((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])), max([1+max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])]), max([-1+Arg_0, max([2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]))*2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]))*((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])), max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])])])])])])]) {O(EXP)} 9: eval4->eval2, Arg_3: max([2, max([2, max([3, max([1+2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]))*2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]))*((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])), max([1+max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])]), max([2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]))*2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]))*((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])), max([2*(-1+Arg_0), max([2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]))*2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]))*((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])), max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])])])])])])])]) {O(EXP)} 10: eval4->eval2, Arg_0: 1 {O(1)} 10: eval4->eval2, Arg_1: max([Arg_1, -1+Arg_1]) {O(n)} 10: eval4->eval2, Arg_2: max([1, max([3, max([2, max([1+2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]))*2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]))*((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])), max([1+max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])]), max([-1+Arg_0, max([2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]))*2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]))*((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])), max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])])])])])])]) {O(EXP)} 10: eval4->eval2, Arg_3: max([2, max([2, max([3, max([1+2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]))*2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]))*((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])), max([1+max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])]), max([2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]))*2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]))*((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])), max([2*(-1+Arg_0), max([2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])]))*2^((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, -2+max([Arg_1, -1+Arg_1])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([Arg_1, -1+Arg_1])+max([-2, -2*max([1, -1+Arg_0])])])+max([0, -1+Arg_1+max([-2, -2*Arg_0])])+max([0, Arg_1+max([-2, -2*(-1+Arg_0)])]))*((max([0, -1+Arg_1])+max([0, Arg_1]))*max([0, max([-4, -8+4*max([Arg_1, -1+Arg_1])])])+(max([2, 2*Arg_0])+max([2, 2*(-1+Arg_0)]))*max([0, max([-8, -8*max([1, -1+Arg_0])])+max([8, 4*max([Arg_1, -1+Arg_1])])])+max([2, max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])+max([0, 4*Arg_1+max([-8, -8*(-1+Arg_0)])])+max([0, 4*(-1+Arg_1)+max([-8, -8*Arg_0])])), max([2*(-1+Arg_0), 2*max([1, -1+Arg_0])])])])])])])])])]) {O(EXP)} ---------------------------------------- (2) BOUNDS(1, max(2, 2 * Arg_0) + max(2, 2 * Arg_0) * nat(max(4 * Arg_1, -4 + 4 * Arg_1, 8) + max(-8, min(8 + -8 * Arg_0, -8))) + 2 * max(2, 2 * Arg_0) * max(2 * Arg_1, 4, -2 + 2 * Arg_1) + max(2, 2 * Arg_0) * nat(max(min(2 + -2 * Arg_0, -2), -2) + max(2 * Arg_1, 4, -2 + 2 * Arg_1)) + max(2, 2 * Arg_0) * max(-1 + Arg_1, Arg_1, 0) + max(2, 2 * Arg_0) * max(1 + 2 * Arg_1, 5, -1 + 2 * Arg_1) + max(2, 2 * Arg_0) * nat(max(-1 + Arg_1, Arg_1) + max(min(2 + -2 * Arg_0, -2), -2)) + 2 * max(2, -2 + 2 * Arg_0) * max(2 * Arg_1, 4, -2 + 2 * Arg_1) + max(2, -2 + 2 * Arg_0) * nat(max(min(2 + -2 * Arg_0, -2), -2) + max(2 * Arg_1, 4, -2 + 2 * Arg_1)) + max(2, -2 + 2 * Arg_0) * max(-1 + Arg_1, Arg_1, 0) + max(2, -2 + 2 * Arg_0) * max(1 + 2 * Arg_1, 5, -1 + 2 * Arg_1) + max(2, -2 + 2 * Arg_0) * nat(max(-1 + Arg_1, Arg_1) + max(min(2 + -2 * Arg_0, -2), -2)) + max(2, -2 + 2 * Arg_0) + max(2, -2 + 2 * Arg_0) * nat(max(-8, min(8 + -8 * Arg_0, -8)) + max(4 * Arg_1, -4 + 4 * Arg_1, 8)) + nat(1 + 2 * Arg_1) + nat(2 * Arg_1 + max(2 + -2 * Arg_0, -2)) + nat(4 * Arg_1) + nat(-1 + 2 * Arg_1) + nat(-1 + Arg_1 + max(-2 * Arg_0, -2)) + nat(-4 + 4 * Arg_1 + max(-8 * Arg_0, -8)) + nat(-2 + 2 * Arg_1 + max(-2 * Arg_0, -2)) + nat(-4 + 4 * Arg_1) + nat(Arg_1 + max(2 + -2 * Arg_0, -2)) + max(2, 2 * Arg_1) + nat(-1 + Arg_1) * max(-3 + Arg_1, -2 + Arg_1, 0) + nat(-1 + Arg_1) * max(-4 + 2 * Arg_1, -2 + 2 * Arg_1, 0) + nat(-1 + Arg_1) * max(-8 + 4 * Arg_1, 0, -12 + 4 * Arg_1) + nat(Arg_1) * max(-3 + Arg_1, -2 + Arg_1, 0) + nat(Arg_1) * max(-4 + 2 * Arg_1, -2 + 2 * Arg_1, 0) + nat(Arg_1) * max(-8 + 4 * Arg_1, 0, -12 + 4 * Arg_1) + nat(2 * Arg_1) + nat(4 * Arg_1 + max(8 + -8 * Arg_0, -8))) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: eval1 0: eval1 -> eval2 : A'=-1+A, [ A>=2 ], cost: 1 1: eval1 -> eval2 : B'=-1+B, [ 1>=A ], cost: 1 2: eval2 -> eval3 : C'=A, D'=2*A, [ B>=2 ], cost: 1 3: eval3 -> eval4 : [ B>=D && B>=1+D ], cost: 1 4: eval3 -> eval4 : D'=1+D, [ B>=D && B>=1+D ], cost: 1 5: eval3 -> eval3 : C'=D, D'=2*D, [ B>=D && B>=1+D && D>=1 ], cost: 1 6: eval3 -> eval3 : C'=1+D, D'=2+2*D, [ B>=D && B>=1+D && D>=1 ], cost: 1 7: eval3 -> eval4 : [ B==D ], cost: 1 8: eval3 -> eval3 : C'=D, D'=2*D, [ D>=1 && B==D ], cost: 1 9: eval4 -> eval2 : A'=-1+A, [ A>=2 && A>=1 && B>=2 ], cost: 1 10: eval4 -> eval2 : B'=-1+B, [ B>=2 && A==1 ], cost: 1 Simplified all rules, resulting in: Start location: eval1 0: eval1 -> eval2 : A'=-1+A, [ A>=2 ], cost: 1 1: eval1 -> eval2 : B'=-1+B, [ 1>=A ], cost: 1 2: eval2 -> eval3 : C'=A, D'=2*A, [ B>=2 ], cost: 1 3: eval3 -> eval4 : [ B>=1+D ], cost: 1 4: eval3 -> eval4 : D'=1+D, [ B>=1+D ], cost: 1 5: eval3 -> eval3 : C'=D, D'=2*D, [ B>=1+D && D>=1 ], cost: 1 6: eval3 -> eval3 : C'=1+D, D'=2+2*D, [ B>=1+D && D>=1 ], cost: 1 7: eval3 -> eval4 : [ B==D ], cost: 1 8: eval3 -> eval3 : C'=D, D'=2*D, [ D>=1 && B==D ], cost: 1 9: eval4 -> eval2 : A'=-1+A, [ A>=2 && B>=2 ], cost: 1 10: eval4 -> eval2 : B'=-1+B, [ B>=2 && A==1 ], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 2. Accelerating the following rules: 5: eval3 -> eval3 : C'=D, D'=2*D, [ B>=1+D && D>=1 ], cost: 1 6: eval3 -> eval3 : C'=1+D, D'=2+2*D, [ B>=1+D && D>=1 ], cost: 1 8: eval3 -> eval3 : C'=D, D'=2*D, [ D>=1 && B==D ], cost: 1 Accelerated rule 5 with backward acceleration, yielding the new rule 11. Accelerated rule 6 with backward acceleration, yielding the new rule 12. Found no metering function for rule 8. Removing the simple loops: 5 6. Accelerated all simple loops using metering functions (where possible): Start location: eval1 0: eval1 -> eval2 : A'=-1+A, [ A>=2 ], cost: 1 1: eval1 -> eval2 : B'=-1+B, [ 1>=A ], cost: 1 2: eval2 -> eval3 : C'=A, D'=2*A, [ B>=2 ], cost: 1 3: eval3 -> eval4 : [ B>=1+D ], cost: 1 4: eval3 -> eval4 : D'=1+D, [ B>=1+D ], cost: 1 7: eval3 -> eval4 : [ B==D ], cost: 1 8: eval3 -> eval3 : C'=D, D'=2*D, [ D>=1 && B==D ], cost: 1 11: eval3 -> eval3 : C'=1/2*2^k*D, D'=2^k*D, [ B>=1+D && D>=1 && k>0 && B>=1+2^(-1+k)*D && 2^(-1+k)*D>=1 ], cost: k 12: eval3 -> eval3 : C'=-1+2^k_1+1/2*2^k_1*D, D'=-2+2^k_1*D+2^(1+k_1), [ B>=1+D && D>=1 && k_1>0 && B>=-1+2^(-1+k_1)*D+2^k_1 && -2+2^(-1+k_1)*D+2^k_1>=1 ], cost: k_1 9: eval4 -> eval2 : A'=-1+A, [ A>=2 && B>=2 ], cost: 1 10: eval4 -> eval2 : B'=-1+B, [ B>=2 && A==1 ], cost: 1 Chained accelerated rules (with incoming rules): Start location: eval1 0: eval1 -> eval2 : A'=-1+A, [ A>=2 ], cost: 1 1: eval1 -> eval2 : B'=-1+B, [ 1>=A ], cost: 1 2: eval2 -> eval3 : C'=A, D'=2*A, [ B>=2 ], cost: 1 13: eval2 -> eval3 : C'=2*A, D'=4*A, [ B>=2 && 2*A>=1 && B==2*A ], cost: 2 14: eval2 -> eval3 : C'=2^k*A, D'=2*2^k*A, [ B>=2 && B>=1+2*A && 2*A>=1 && k>0 && B>=1+2*2^(-1+k)*A && 2*2^(-1+k)*A>=1 ], cost: 1+k 15: eval2 -> eval3 : C'=-1+2^k_1+2^k_1*A, D'=-2+2*2^k_1*A+2^(1+k_1), [ B>=2 && B>=1+2*A && 2*A>=1 && k_1>0 && B>=-1+2*2^(-1+k_1)*A+2^k_1 && -2+2*2^(-1+k_1)*A+2^k_1>=1 ], cost: 1+k_1 3: eval3 -> eval4 : [ B>=1+D ], cost: 1 4: eval3 -> eval4 : D'=1+D, [ B>=1+D ], cost: 1 7: eval3 -> eval4 : [ B==D ], cost: 1 9: eval4 -> eval2 : A'=-1+A, [ A>=2 && B>=2 ], cost: 1 10: eval4 -> eval2 : B'=-1+B, [ B>=2 && A==1 ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: eval1 0: eval1 -> eval2 : A'=-1+A, [ A>=2 ], cost: 1 1: eval1 -> eval2 : B'=-1+B, [ 1>=A ], cost: 1 16: eval2 -> eval4 : C'=A, D'=2*A, [ B>=2 && B>=1+2*A ], cost: 2 17: eval2 -> eval4 : C'=A, D'=1+2*A, [ B>=2 && B>=1+2*A ], cost: 2 18: eval2 -> eval4 : C'=A, D'=2*A, [ B>=2 && B==2*A ], cost: 2 19: eval2 -> eval4 : C'=2^k*A, D'=2*2^k*A, [ B>=2 && B>=1+2*A && 2*A>=1 && k>0 && B>=1+2*2^(-1+k)*A && 2*2^(-1+k)*A>=1 && B>=1+2*2^k*A ], cost: 2+k 20: eval2 -> eval4 : C'=2^k*A, D'=1+2*2^k*A, [ B>=2 && B>=1+2*A && 2*A>=1 && k>0 && B>=1+2*2^(-1+k)*A && 2*2^(-1+k)*A>=1 && B>=1+2*2^k*A ], cost: 2+k 21: eval2 -> eval4 : C'=2^k*A, D'=2*2^k*A, [ B>=2 && B>=1+2*A && 2*A>=1 && k>0 && B>=1+2*2^(-1+k)*A && 2*2^(-1+k)*A>=1 && B==2*2^k*A ], cost: 2+k 22: eval2 -> eval4 : C'=-1+2^k_1+2^k_1*A, D'=-2+2*2^k_1*A+2^(1+k_1), [ B>=2 && B>=1+2*A && 2*A>=1 && k_1>0 && B>=-1+2*2^(-1+k_1)*A+2^k_1 && -2+2*2^(-1+k_1)*A+2^k_1>=1 && B>=-1+2*2^k_1*A+2^(1+k_1) ], cost: 2+k_1 23: eval2 -> eval4 : C'=-1+2^k_1+2^k_1*A, D'=-1+2*2^k_1*A+2^(1+k_1), [ B>=2 && B>=1+2*A && 2*A>=1 && k_1>0 && B>=-1+2*2^(-1+k_1)*A+2^k_1 && -2+2*2^(-1+k_1)*A+2^k_1>=1 && B>=-1+2*2^k_1*A+2^(1+k_1) ], cost: 2+k_1 24: eval2 -> eval4 : C'=-1+2^k_1+2^k_1*A, D'=-2+2*2^k_1*A+2^(1+k_1), [ B>=2 && B>=1+2*A && 2*A>=1 && k_1>0 && B>=-1+2*2^(-1+k_1)*A+2^k_1 && -2+2*2^(-1+k_1)*A+2^k_1>=1 && B==-2+2*2^k_1*A+2^(1+k_1) ], cost: 2+k_1 9: eval4 -> eval2 : A'=-1+A, [ A>=2 && B>=2 ], cost: 1 10: eval4 -> eval2 : B'=-1+B, [ B>=2 && A==1 ], cost: 1 Applied pruning (of leafs and parallel rules): Start location: eval1 0: eval1 -> eval2 : A'=-1+A, [ A>=2 ], cost: 1 1: eval1 -> eval2 : B'=-1+B, [ 1>=A ], cost: 1 16: eval2 -> eval4 : C'=A, D'=2*A, [ B>=2 && B>=1+2*A ], cost: 2 17: eval2 -> eval4 : C'=A, D'=1+2*A, [ B>=2 && B>=1+2*A ], cost: 2 19: eval2 -> eval4 : C'=2^k*A, D'=2*2^k*A, [ B>=2 && B>=1+2*A && 2*A>=1 && k>0 && B>=1+2*2^(-1+k)*A && 2*2^(-1+k)*A>=1 && B>=1+2*2^k*A ], cost: 2+k 20: eval2 -> eval4 : C'=2^k*A, D'=1+2*2^k*A, [ B>=2 && B>=1+2*A && 2*A>=1 && k>0 && B>=1+2*2^(-1+k)*A && 2*2^(-1+k)*A>=1 && B>=1+2*2^k*A ], cost: 2+k 22: eval2 -> eval4 : C'=-1+2^k_1+2^k_1*A, D'=-2+2*2^k_1*A+2^(1+k_1), [ B>=2 && B>=1+2*A && 2*A>=1 && k_1>0 && B>=-1+2*2^(-1+k_1)*A+2^k_1 && -2+2*2^(-1+k_1)*A+2^k_1>=1 && B>=-1+2*2^k_1*A+2^(1+k_1) ], cost: 2+k_1 9: eval4 -> eval2 : A'=-1+A, [ A>=2 && B>=2 ], cost: 1 10: eval4 -> eval2 : B'=-1+B, [ B>=2 && A==1 ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: eval1 0: eval1 -> eval2 : A'=-1+A, [ A>=2 ], cost: 1 1: eval1 -> eval2 : B'=-1+B, [ 1>=A ], cost: 1 25: eval2 -> eval2 : A'=-1+A, C'=A, D'=2*A, [ B>=2 && B>=1+2*A && A>=2 ], cost: 3 26: eval2 -> eval2 : B'=-1+B, C'=A, D'=2*A, [ B>=2 && B>=1+2*A && A==1 ], cost: 3 27: eval2 -> eval2 : A'=-1+A, C'=A, D'=1+2*A, [ B>=2 && B>=1+2*A && A>=2 ], cost: 3 28: eval2 -> eval2 : B'=-1+B, C'=A, D'=1+2*A, [ B>=2 && B>=1+2*A && A==1 ], cost: 3 29: eval2 -> eval2 : A'=-1+A, C'=2^k*A, D'=2*2^k*A, [ B>=2 && B>=1+2*A && 2*A>=1 && k>0 && B>=1+2*2^(-1+k)*A && 2*2^(-1+k)*A>=1 && B>=1+2*2^k*A && A>=2 ], cost: 3+k 30: eval2 -> eval2 : B'=-1+B, C'=2^k*A, D'=2*2^k*A, [ B>=2 && B>=1+2*A && 2*A>=1 && k>0 && B>=1+2*2^(-1+k)*A && 2*2^(-1+k)*A>=1 && B>=1+2*2^k*A && A==1 ], cost: 3+k 31: eval2 -> eval2 : A'=-1+A, C'=2^k*A, D'=1+2*2^k*A, [ B>=2 && B>=1+2*A && 2*A>=1 && k>0 && B>=1+2*2^(-1+k)*A && 2*2^(-1+k)*A>=1 && B>=1+2*2^k*A && A>=2 ], cost: 3+k 32: eval2 -> eval2 : B'=-1+B, C'=2^k*A, D'=1+2*2^k*A, [ B>=2 && B>=1+2*A && 2*A>=1 && k>0 && B>=1+2*2^(-1+k)*A && 2*2^(-1+k)*A>=1 && B>=1+2*2^k*A && A==1 ], cost: 3+k 33: eval2 -> eval2 : A'=-1+A, C'=-1+2^k_1+2^k_1*A, D'=-2+2*2^k_1*A+2^(1+k_1), [ B>=2 && B>=1+2*A && 2*A>=1 && k_1>0 && B>=-1+2*2^(-1+k_1)*A+2^k_1 && -2+2*2^(-1+k_1)*A+2^k_1>=1 && B>=-1+2*2^k_1*A+2^(1+k_1) && A>=2 ], cost: 3+k_1 34: eval2 -> eval2 : B'=-1+B, C'=-1+2^k_1+2^k_1*A, D'=-2+2*2^k_1*A+2^(1+k_1), [ B>=2 && B>=1+2*A && 2*A>=1 && k_1>0 && B>=-1+2*2^(-1+k_1)*A+2^k_1 && -2+2*2^(-1+k_1)*A+2^k_1>=1 && B>=-1+2*2^k_1*A+2^(1+k_1) && A==1 ], cost: 3+k_1 Applied pruning (of leafs and parallel rules): Start location: eval1 0: eval1 -> eval2 : A'=-1+A, [ A>=2 ], cost: 1 1: eval1 -> eval2 : B'=-1+B, [ 1>=A ], cost: 1 25: eval2 -> eval2 : A'=-1+A, C'=A, D'=2*A, [ B>=2 && B>=1+2*A && A>=2 ], cost: 3 26: eval2 -> eval2 : B'=-1+B, C'=A, D'=2*A, [ B>=2 && B>=1+2*A && A==1 ], cost: 3 28: eval2 -> eval2 : B'=-1+B, C'=A, D'=1+2*A, [ B>=2 && B>=1+2*A && A==1 ], cost: 3 29: eval2 -> eval2 : A'=-1+A, C'=2^k*A, D'=2*2^k*A, [ B>=2 && B>=1+2*A && 2*A>=1 && k>0 && B>=1+2*2^(-1+k)*A && 2*2^(-1+k)*A>=1 && B>=1+2*2^k*A && A>=2 ], cost: 3+k 30: eval2 -> eval2 : B'=-1+B, C'=2^k*A, D'=2*2^k*A, [ B>=2 && B>=1+2*A && 2*A>=1 && k>0 && B>=1+2*2^(-1+k)*A && 2*2^(-1+k)*A>=1 && B>=1+2*2^k*A && A==1 ], cost: 3+k Accelerating simple loops of location 1. Accelerating the following rules: 25: eval2 -> eval2 : A'=-1+A, C'=A, D'=2*A, [ B>=2 && B>=1+2*A && A>=2 ], cost: 3 26: eval2 -> eval2 : B'=-1+B, C'=A, D'=2*A, [ B>=2 && B>=1+2*A && A==1 ], cost: 3 28: eval2 -> eval2 : B'=-1+B, C'=A, D'=1+2*A, [ B>=2 && B>=1+2*A && A==1 ], cost: 3 29: eval2 -> eval2 : A'=-1+A, C'=2^k*A, D'=2*2^k*A, [ B>=2 && B>=1+2*A && 2*A>=1 && k>0 && B>=1+2*2^(-1+k)*A && 2*2^(-1+k)*A>=1 && B>=1+2*2^k*A && A>=2 ], cost: 3+k 30: eval2 -> eval2 : B'=-1+B, C'=2^k*A, D'=2*2^k*A, [ B>=2 && B>=1+2*A && 2*A>=1 && k>0 && B>=1+2*2^(-1+k)*A && 2*2^(-1+k)*A>=1 && B>=1+2*2^k*A && A==1 ], cost: 3+k Accelerated rule 25 with metering function -1+A, yielding the new rule 35. Accelerated rule 26 with metering function -2*A+B, yielding the new rule 36. Accelerated rule 28 with metering function -2*A+B, yielding the new rule 37. Accelerated rule 29 with backward acceleration, yielding the new rule 38. Accelerated rule 30 with backward acceleration, yielding the new rule 39. Removing the simple loops: 25 26 28 29 30. Accelerated all simple loops using metering functions (where possible): Start location: eval1 0: eval1 -> eval2 : A'=-1+A, [ A>=2 ], cost: 1 1: eval1 -> eval2 : B'=-1+B, [ 1>=A ], cost: 1 35: eval2 -> eval2 : A'=1, C'=2, D'=4, [ B>=2 && B>=1+2*A && A>=2 ], cost: -3+3*A 36: eval2 -> eval2 : B'=2*A, C'=A, D'=2*A, [ B>=2 && B>=1+2*A && A==1 ], cost: -6*A+3*B 37: eval2 -> eval2 : B'=2*A, C'=A, D'=1+2*A, [ B>=2 && B>=1+2*A && A==1 ], cost: -6*A+3*B 38: eval2 -> eval2 : A'=-k_2+A, C'=2^k+2^k*A-2^k*k_2, D'=2*2^k+2*2^k*A-2*2^k*k_2, [ B>=2 && B>=1+2*A && 2*A>=1 && k>0 && B>=1+2*2^(-1+k)*A && 2*2^(-1+k)*A>=1 && B>=1+2*2^k*A && A>=2 && k_2>0 && B>=3-2*k_2+2*A && 2-2*k_2+2*A>=1 && B>=1-2*2^(-1+k)*(-1+k_2-A) && -2*2^(-1+k)*(-1+k_2-A)>=1 && B>=1-2*2^k*(-1+k_2-A) && 1-k_2+A>=2 ], cost: 3*k_2+k_2*k 39: eval2 -> eval2 : B'=-k_3+B, C'=2^k*A, D'=2*2^k*A, [ B>=2 && B>=1+2*A && 2*A>=1 && k>0 && B>=1+2*2^(-1+k)*A && 2*2^(-1+k)*A>=1 && B>=1+2*2^k*A && A==1 && k_3>0 && 1-k_3+B>=2 && 1-k_3+B>=1+2*A && 1-k_3+B>=1+2*2^(-1+k)*A && 1-k_3+B>=1+2*2^k*A ], cost: 3*k_3+k_3*k Chained accelerated rules (with incoming rules): Start location: eval1 0: eval1 -> eval2 : A'=-1+A, [ A>=2 ], cost: 1 1: eval1 -> eval2 : B'=-1+B, [ 1>=A ], cost: 1 40: eval1 -> eval2 : A'=1, C'=2, D'=4, [ B>=2 && B>=-1+2*A && -1+A>=2 ], cost: -5+3*A 41: eval1 -> eval2 : A'=-1+A, B'=-2+2*A, C'=-1+A, D'=-2+2*A, [ B>=2 && B>=-1+2*A && -1+A==1 ], cost: 7-6*A+3*B 42: eval1 -> eval2 : B'=2*A, C'=A, D'=2*A, [ -1+B>=2 && -1+B>=1+2*A && A==1 ], cost: -2-6*A+3*B 43: eval1 -> eval2 : A'=-1+A, B'=-2+2*A, C'=-1+A, D'=-1+2*A, [ B>=2 && B>=-1+2*A && -1+A==1 ], cost: 7-6*A+3*B 44: eval1 -> eval2 : B'=2*A, C'=A, D'=1+2*A, [ -1+B>=2 && -1+B>=1+2*A && A==1 ], cost: -2-6*A+3*B 45: eval1 -> eval2 : A'=-1-k_2+A, C'=2^k+2^k*(-1+A)-2^k*k_2, D'=2*2^k+2*2^k*(-1+A)-2*2^k*k_2, [ B>=2 && B>=-1+2*A && -2+2*A>=1 && k>0 && B>=1+2*2^(-1+k)*(-1+A) && 2*2^(-1+k)*(-1+A)>=1 && B>=1+2*2^k*(-1+A) && -1+A>=2 && k_2>0 && B>=1-2*k_2+2*A && -2*k_2+2*A>=1 && B>=1-2*2^(-1+k)*(k_2-A) && -2*2^(-1+k)*(k_2-A)>=1 && B>=1-2*2^k*(k_2-A) && -k_2+A>=2 ], cost: 1+3*k_2+k_2*k 46: eval1 -> eval2 : A'=-1+A, B'=-k_3+B, C'=2^k*(-1+A), D'=2*2^k*(-1+A), [ B>=2 && B>=-1+2*A && -2+2*A>=1 && k>0 && B>=1+2*2^(-1+k)*(-1+A) && 2*2^(-1+k)*(-1+A)>=1 && B>=1+2*2^k*(-1+A) && -1+A==1 && k_3>0 && 1-k_3+B>=2 && 1-k_3+B>=-1+2*A && 1-k_3+B>=1+2*2^(-1+k)*(-1+A) && 1-k_3+B>=1+2*2^k*(-1+A) ], cost: 1+3*k_3+k_3*k 47: eval1 -> eval2 : B'=-1-k_3+B, C'=2^k*A, D'=2*2^k*A, [ -1+B>=2 && -1+B>=1+2*A && 2*A>=1 && k>0 && -1+B>=1+2*2^(-1+k)*A && 2*2^(-1+k)*A>=1 && -1+B>=1+2*2^k*A && A==1 && k_3>0 && -k_3+B>=2 && -k_3+B>=1+2*A && -k_3+B>=1+2*2^(-1+k)*A && -k_3+B>=1+2*2^k*A ], cost: 1+3*k_3+k_3*k Removed unreachable locations (and leaf rules with constant cost): Start location: eval1 40: eval1 -> eval2 : A'=1, C'=2, D'=4, [ B>=2 && B>=-1+2*A && -1+A>=2 ], cost: -5+3*A 41: eval1 -> eval2 : A'=-1+A, B'=-2+2*A, C'=-1+A, D'=-2+2*A, [ B>=2 && B>=-1+2*A && -1+A==1 ], cost: 7-6*A+3*B 42: eval1 -> eval2 : B'=2*A, C'=A, D'=2*A, [ -1+B>=2 && -1+B>=1+2*A && A==1 ], cost: -2-6*A+3*B 43: eval1 -> eval2 : A'=-1+A, B'=-2+2*A, C'=-1+A, D'=-1+2*A, [ B>=2 && B>=-1+2*A && -1+A==1 ], cost: 7-6*A+3*B 44: eval1 -> eval2 : B'=2*A, C'=A, D'=1+2*A, [ -1+B>=2 && -1+B>=1+2*A && A==1 ], cost: -2-6*A+3*B 45: eval1 -> eval2 : A'=-1-k_2+A, C'=2^k+2^k*(-1+A)-2^k*k_2, D'=2*2^k+2*2^k*(-1+A)-2*2^k*k_2, [ B>=2 && B>=-1+2*A && -2+2*A>=1 && k>0 && B>=1+2*2^(-1+k)*(-1+A) && 2*2^(-1+k)*(-1+A)>=1 && B>=1+2*2^k*(-1+A) && -1+A>=2 && k_2>0 && B>=1-2*k_2+2*A && -2*k_2+2*A>=1 && B>=1-2*2^(-1+k)*(k_2-A) && -2*2^(-1+k)*(k_2-A)>=1 && B>=1-2*2^k*(k_2-A) && -k_2+A>=2 ], cost: 1+3*k_2+k_2*k 46: eval1 -> eval2 : A'=-1+A, B'=-k_3+B, C'=2^k*(-1+A), D'=2*2^k*(-1+A), [ B>=2 && B>=-1+2*A && -2+2*A>=1 && k>0 && B>=1+2*2^(-1+k)*(-1+A) && 2*2^(-1+k)*(-1+A)>=1 && B>=1+2*2^k*(-1+A) && -1+A==1 && k_3>0 && 1-k_3+B>=2 && 1-k_3+B>=-1+2*A && 1-k_3+B>=1+2*2^(-1+k)*(-1+A) && 1-k_3+B>=1+2*2^k*(-1+A) ], cost: 1+3*k_3+k_3*k 47: eval1 -> eval2 : B'=-1-k_3+B, C'=2^k*A, D'=2*2^k*A, [ -1+B>=2 && -1+B>=1+2*A && 2*A>=1 && k>0 && -1+B>=1+2*2^(-1+k)*A && 2*2^(-1+k)*A>=1 && -1+B>=1+2*2^k*A && A==1 && k_3>0 && -k_3+B>=2 && -k_3+B>=1+2*A && -k_3+B>=1+2*2^(-1+k)*A && -k_3+B>=1+2*2^k*A ], cost: 1+3*k_3+k_3*k ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: eval1 40: eval1 -> eval2 : A'=1, C'=2, D'=4, [ B>=2 && B>=-1+2*A && -1+A>=2 ], cost: -5+3*A 43: eval1 -> eval2 : A'=-1+A, B'=-2+2*A, C'=-1+A, D'=-1+2*A, [ B>=2 && B>=-1+2*A && -1+A==1 ], cost: 7-6*A+3*B 44: eval1 -> eval2 : B'=2*A, C'=A, D'=1+2*A, [ -1+B>=2 && -1+B>=1+2*A && A==1 ], cost: -2-6*A+3*B 45: eval1 -> eval2 : A'=-1-k_2+A, C'=2^k+2^k*(-1+A)-2^k*k_2, D'=2*2^k+2*2^k*(-1+A)-2*2^k*k_2, [ B>=2 && B>=-1+2*A && -2+2*A>=1 && k>0 && B>=1+2*2^(-1+k)*(-1+A) && 2*2^(-1+k)*(-1+A)>=1 && B>=1+2*2^k*(-1+A) && -1+A>=2 && k_2>0 && B>=1-2*k_2+2*A && -2*k_2+2*A>=1 && B>=1-2*2^(-1+k)*(k_2-A) && -2*2^(-1+k)*(k_2-A)>=1 && B>=1-2*2^k*(k_2-A) && -k_2+A>=2 ], cost: 1+3*k_2+k_2*k 46: eval1 -> eval2 : A'=-1+A, B'=-k_3+B, C'=2^k*(-1+A), D'=2*2^k*(-1+A), [ B>=2 && B>=-1+2*A && -2+2*A>=1 && k>0 && B>=1+2*2^(-1+k)*(-1+A) && 2*2^(-1+k)*(-1+A)>=1 && B>=1+2*2^k*(-1+A) && -1+A==1 && k_3>0 && 1-k_3+B>=2 && 1-k_3+B>=-1+2*A && 1-k_3+B>=1+2*2^(-1+k)*(-1+A) && 1-k_3+B>=1+2*2^k*(-1+A) ], cost: 1+3*k_3+k_3*k 47: eval1 -> eval2 : B'=-1-k_3+B, C'=2^k*A, D'=2*2^k*A, [ -1+B>=2 && -1+B>=1+2*A && 2*A>=1 && k>0 && -1+B>=1+2*2^(-1+k)*A && 2*2^(-1+k)*A>=1 && -1+B>=1+2*2^k*A && A==1 && k_3>0 && -k_3+B>=2 && -k_3+B>=1+2*A && -k_3+B>=1+2*2^(-1+k)*A && -k_3+B>=1+2*2^k*A ], cost: 1+3*k_3+k_3*k Computing asymptotic complexity for rule 40 Simplified the guard: 40: eval1 -> eval2 : A'=1, C'=2, D'=4, [ B>=-1+2*A && -1+A>=2 ], cost: -5+3*A Solved the limit problem by the following transformations: Created initial limit problem: 2-2*A+B (+/+!), -2+A (+/+!), -5+3*A (+) [not solved] applying transformation rule (C) using substitution {B==-1+2*A} resulting limit problem: 1 (+/+!), -2+A (+/+!), -5+3*A (+) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: -2+A (+/+!), -5+3*A (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {A==n} resulting limit problem: [solved] Solution: A / n B / -1+2*n Resulting cost -5+3*n has complexity: Poly(n^1) Found new complexity Poly(n^1). Computing asymptotic complexity for rule 45 Simplified the guard: 45: eval1 -> eval2 : A'=-1-k_2+A, C'=2^k+2^k*(-1+A)-2^k*k_2, D'=2*2^k+2*2^k*(-1+A)-2*2^k*k_2, [ B>=-1+2*A && k>0 && B>=1+2*2^(-1+k)*(-1+A) && 2*2^(-1+k)*(-1+A)>=1 && B>=1+2*2^k*(-1+A) && k_2>0 && -k_2+A>=2 ], cost: 1+3*k_2+k_2*k Solved the limit problem by the following transformations: Created initial limit problem: k_2 (+/+!), -1-k_2+A (+/+!), k (+/+!), 2*2^(-1+k)*(-1+A) (+/+!), 2-2*A+B (+/+!), 1+3*k_2+k_2*k (+), -2*2^k*(-1+A)+B (+/+!), -2*2^(-1+k)*(-1+A)+B (+/+!) [not solved] applying transformation rule (C) using substitution {k==1} resulting limit problem: 1 (+/+!), k_2 (+/+!), -1-k_2+A (+/+!), 1+4*k_2 (+), 2-2*A+B (+/+!), 4-4*A+B (+/+!), -2+2*A (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: k_2 (+/+!), -1-k_2+A (+/+!), 1+4*k_2 (+), 2-2*A+B (+/+!), 4-4*A+B (+/+!), -2+2*A (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {k_2==n,A==2+n,B==5+4*n} resulting limit problem: [solved] Solution: k_2 / n k / 1 A / 2+n B / 5+4*n Resulting cost 1+4*n has complexity: Poly(n^1) Computing asymptotic complexity for rule 46 Simplified the guard: 46: eval1 -> eval2 : A'=-1+A, B'=-k_3+B, C'=2^k*(-1+A), D'=2*2^k*(-1+A), [ k>0 && 2*2^(-1+k)*(-1+A)>=1 && -1+A==1 && k_3>0 && 1-k_3+B>=2 && 1-k_3+B>=-1+2*A && 1-k_3+B>=1+2*2^(-1+k)*(-1+A) && 1-k_3+B>=1+2*2^k*(-1+A) ], cost: 1+3*k_3+k_3*k Solved the limit problem by the following transformations: Created initial limit problem: k_3 (+/+!), k (+/+!), 2*2^(-1+k)*(-1+A) (+/+!), -1+A (+/+!), 3-A (+/+!), 3-k_3-2*A+B (+/+!), -k_3+B (+/+!), 1-k_3-2*2^(-1+k)*(-1+A)+B (+/+!), 1+3*k_3+k_3*k (+), 1-k_3-2*2^k*(-1+A)+B (+/+!) [not solved] applying transformation rule (C) using substitution {A==2} resulting limit problem: 1 (+/+!), k_3 (+/+!), k (+/+!), 1-k_3-2*2^(-1+k)+B (+/+!), 2*2^(-1+k) (+/+!), -k_3+B (+/+!), -1-k_3+B (+/+!), 1+3*k_3+k_3*k (+), 1-k_3-2*2^k+B (+/+!) [not solved] applying transformation rule (C) using substitution {k==1} resulting limit problem: 1 (+/+!), k_3 (+/+!), 1+4*k_3 (+), 2 (+/+!), -3-k_3+B (+/+!), -k_3+B (+/+!), -1-k_3+B (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: k_3 (+/+!), 1+4*k_3 (+), 2 (+/+!), -3-k_3+B (+/+!), -k_3+B (+/+!), -1-k_3+B (+/+!) [not solved] applying transformation rule (B), deleting 2 (+/+!) resulting limit problem: k_3 (+/+!), 1+4*k_3 (+), -3-k_3+B (+/+!), -k_3+B (+/+!), -1-k_3+B (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {k_3==n,B==2*n} resulting limit problem: [solved] Solution: k_3 / n k / 1 A / 2 B / 2*n Resulting cost 1+4*n has complexity: Poly(n^1) Computing asymptotic complexity for rule 47 Simplified the guard: 47: eval1 -> eval2 : B'=-1-k_3+B, C'=2^k*A, D'=2*2^k*A, [ k>0 && 2*2^(-1+k)*A>=1 && A==1 && k_3>0 && -k_3+B>=2 && -k_3+B>=1+2*A && -k_3+B>=1+2*2^(-1+k)*A && -k_3+B>=1+2*2^k*A ], cost: 1+3*k_3+k_3*k Solved the limit problem by the following transformations: Created initial limit problem: -k_3-2*2^(-1+k)*A+B (+/+!), 2*2^(-1+k)*A (+/+!), k_3 (+/+!), k (+/+!), -k_3-2*A+B (+/+!), 2-A (+/+!), -k_3-2*2^k*A+B (+/+!), A (+/+!), -1-k_3+B (+/+!), 1+3*k_3+k_3*k (+) [not solved] applying transformation rule (C) using substitution {A==1} resulting limit problem: 1 (+/+!), k_3 (+/+!), -k_3-2*2^(-1+k)+B (+/+!), k (+/+!), -2-k_3+B (+/+!), 2*2^(-1+k) (+/+!), -1-k_3+B (+/+!), 1+3*k_3+k_3*k (+), -k_3-2*2^k+B (+/+!) [not solved] applying transformation rule (C) using substitution {k==1} resulting limit problem: -4-k_3+B (+/+!), 1 (+/+!), k_3 (+/+!), 1+4*k_3 (+), -2-k_3+B (+/+!), 2 (+/+!), -1-k_3+B (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: -4-k_3+B (+/+!), k_3 (+/+!), 1+4*k_3 (+), -2-k_3+B (+/+!), 2 (+/+!), -1-k_3+B (+/+!) [not solved] applying transformation rule (B), deleting 2 (+/+!) resulting limit problem: -4-k_3+B (+/+!), k_3 (+/+!), 1+4*k_3 (+), -2-k_3+B (+/+!), -1-k_3+B (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {k_3==n,B==5+n} resulting limit problem: [solved] Solution: k_3 / n k / 1 A / 1 B / 5+n Resulting cost 1+4*n has complexity: Poly(n^1) Obtained the following overall complexity (w.r.t. the length of the input n): Complexity: Poly(n^1) Cpx degree: 1 Solved cost: -5+3*n Rule cost: -5+3*A Rule guard: [ B>=-1+2*A && -1+A>=2 ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (4) BOUNDS(n^1, INF)