/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.koat /export/starexec/sandbox2/output/output_files


--------------------------------------------------------------------------------


WORST_CASE(Omega(n^3), O(n^5))
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^3, nat(Arg_1^2) + nat(max(Arg_1 * (nat(Arg_1^2) * nat(nat(Arg_1^2) + nat(Arg_1)) + nat(Arg_1) * nat(nat(Arg_1^2) + nat(Arg_1))) + Arg_1 * nat(nat(Arg_1^2) + nat(Arg_1)), Arg_1 * nat(nat(Arg_1^2) + nat(Arg_1)) + Arg_1 * (-1 * min(-1 * Arg_1^2, 0) * nat(nat(Arg_1^2) + nat(Arg_1)) + nat(Arg_1) * nat(nat(Arg_1^2) + nat(Arg_1))), 0) + nat(nat(nat(Arg_1^2) + nat(Arg_1)) + nat(Arg_1^2) * nat(nat(Arg_1^2) + nat(Arg_1)) + nat(Arg_1) * nat(nat(Arg_1^2) + nat(Arg_1)))) + max(2, 3 + 2 * Arg_1) + nat(2 * Arg_1)).

(0) CpxIntTrs
(1) Koat2 Proof [FINISHED, 1010 ms]
(2) BOUNDS(1, nat(Arg_1^2) + nat(max(Arg_1 * (nat(Arg_1^2) * nat(nat(Arg_1^2) + nat(Arg_1)) + nat(Arg_1) * nat(nat(Arg_1^2) + nat(Arg_1))) + Arg_1 * nat(nat(Arg_1^2) + nat(Arg_1)), Arg_1 * nat(nat(Arg_1^2) + nat(Arg_1)) + Arg_1 * (-1 * min(-1 * Arg_1^2, 0) * nat(nat(Arg_1^2) + nat(Arg_1)) + nat(Arg_1) * nat(nat(Arg_1^2) + nat(Arg_1))), 0) + nat(nat(nat(Arg_1^2) + nat(Arg_1)) + nat(Arg_1^2) * nat(nat(Arg_1^2) + nat(Arg_1)) + nat(Arg_1) * nat(nat(Arg_1^2) + nat(Arg_1)))) + max(2, 3 + 2 * Arg_1) + nat(2 * Arg_1))
(3) Loat Proof [FINISHED, 471 ms]
(4) BOUNDS(n^3, INF)


----------------------------------------

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
l0(A, B, C, D) -> Com_1(l1(0, B, C, D)) :|: TRUE
l1(A, B, C, D) -> Com_1(l2(A, B, 0, 0)) :|: B > 0
l2(A, B, C, D) -> Com_1(l2(A, B, C + 1, D + C)) :|: C < B
l2(A, B, C, D) -> Com_1(l1(A + D, B - 1, C, D)) :|: C >= B
l1(A, B, C, D) -> Com_1(l3(A, B, C, D)) :|: B <= 0
l3(A, B, C, D) -> Com_1(l3(A - 1, B, C, D)) :|: A > 0

The start-symbols are:[l0_4]


----------------------------------------

(1) Koat2 Proof (FINISHED)
YES( ?, max([0, max([0, max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]), max([(max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])+max([0, max([Arg_1*(min([-((min([0, -(-(Arg_1)*-(Arg_1))])-max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), min([-((min([0, -(-(Arg_1)*-(Arg_1))])-max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])), min([-((min([0, -(Arg_1*Arg_1)])-max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), -((min([0, -(Arg_1*Arg_1)])-max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]))])])])+max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), Arg_1*(max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]), max([(max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]))])])])+max([0, Arg_1])+max([0, Arg_1])+max([2, 3+2*Arg_1])+max([0, Arg_1*Arg_1]) {O(n^5)})



Initial Complexity Problem:

  Start:  l0  

  Program_Vars:  Arg_0, Arg_1, Arg_2, Arg_3  

  Temp_Vars:    

  Locations:  l0, l1, l2, l3  

  Transitions:

  l0(Arg_0,Arg_1,Arg_2,Arg_3) -> l1(0,Arg_1,Arg_2,Arg_3):|:

  l1(Arg_0,Arg_1,Arg_2,Arg_3) -> l2(Arg_0,Arg_1,0,0):|:0 <= Arg_0 && 1 <= Arg_1

  l1(Arg_0,Arg_1,Arg_2,Arg_3) -> l3(Arg_0,Arg_1,Arg_2,Arg_3):|:0 <= Arg_0 && Arg_1 <= 0

  l2(Arg_0,Arg_1,Arg_2,Arg_3) -> l1(Arg_0+Arg_3,Arg_1-1,Arg_2,Arg_3):|:0 <= Arg_3 && 0 <= Arg_2+Arg_3 && 1 <= Arg_1+Arg_3 && 0 <= Arg_0+Arg_3 && 0 <= Arg_2 && 1 <= Arg_1+Arg_2 && 0 <= Arg_0+Arg_2 && 1 <= Arg_1 && 1 <= Arg_0+Arg_1 && 0 <= Arg_0 && Arg_1 <= Arg_2

  l2(Arg_0,Arg_1,Arg_2,Arg_3) -> l2(Arg_0,Arg_1,Arg_2+1,Arg_3+Arg_2):|:0 <= Arg_3 && 0 <= Arg_2+Arg_3 && 1 <= Arg_1+Arg_3 && 0 <= Arg_0+Arg_3 && 0 <= Arg_2 && 1 <= Arg_1+Arg_2 && 0 <= Arg_0+Arg_2 && 1 <= Arg_1 && 1 <= Arg_0+Arg_1 && 0 <= Arg_0 && Arg_2+1 <= Arg_1

  l3(Arg_0,Arg_1,Arg_2,Arg_3) -> l3(Arg_0-1,Arg_1,Arg_2,Arg_3):|:Arg_1 <= 0 && Arg_1 <= Arg_0 && 0 <= Arg_0 && 1 <= Arg_0  



Timebounds: 

  Overall timebound: max([0, max([0, max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]), max([(max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])+max([0, max([Arg_1*(min([-((min([0, -(-(Arg_1)*-(Arg_1))])-max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), min([-((min([0, -(-(Arg_1)*-(Arg_1))])-max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])), min([-((min([0, -(Arg_1*Arg_1)])-max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), -((min([0, -(Arg_1*Arg_1)])-max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]))])])])+max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), Arg_1*(max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]), max([(max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]))])])])+max([0, Arg_1])+max([0, Arg_1])+max([2, 3+2*Arg_1])+max([0, Arg_1*Arg_1]) {O(n^5)}

  0: l0->l1: 1 {O(1)}

  1: l1->l2: max([0, 1+2*Arg_1]) {O(n)}

  4: l1->l3: 1 {O(1)}

  2: l2->l2: max([0, Arg_1*Arg_1])+max([0, Arg_1]) {O(n^2)}

  3: l2->l1: max([0, Arg_1]) {O(n)}

  5: l3->l3: max([0, max([0, max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]), max([(max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])+max([0, max([Arg_1*(min([-((min([0, -(-(Arg_1)*-(Arg_1))])-max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), min([-((min([0, -(-(Arg_1)*-(Arg_1))])-max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])), min([-((min([0, -(Arg_1*Arg_1)])-max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), -((min([0, -(Arg_1*Arg_1)])-max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]))])])])+max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), Arg_1*(max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]), max([(max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]))])])]) {O(n^5)}



Costbounds:

  Overall costbound: max([0, max([0, max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]), max([(max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])+max([0, max([Arg_1*(min([-((min([0, -(-(Arg_1)*-(Arg_1))])-max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), min([-((min([0, -(-(Arg_1)*-(Arg_1))])-max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])), min([-((min([0, -(Arg_1*Arg_1)])-max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), -((min([0, -(Arg_1*Arg_1)])-max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]))])])])+max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), Arg_1*(max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]), max([(max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]))])])])+max([0, Arg_1])+max([0, Arg_1])+max([2, 3+2*Arg_1])+max([0, Arg_1*Arg_1]) {O(n^5)}

  0: l0->l1: 1 {O(1)}

  1: l1->l2: max([0, 1+2*Arg_1]) {O(n)}

  4: l1->l3: 1 {O(1)}

  2: l2->l2: max([0, Arg_1*Arg_1])+max([0, Arg_1]) {O(n^2)}

  3: l2->l1: max([0, Arg_1]) {O(n)}

  5: l3->l3: max([0, max([0, max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]), max([(max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])+max([0, max([Arg_1*(min([-((min([0, -(-(Arg_1)*-(Arg_1))])-max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), min([-((min([0, -(-(Arg_1)*-(Arg_1))])-max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])), min([-((min([0, -(Arg_1*Arg_1)])-max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), -((min([0, -(Arg_1*Arg_1)])-max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]))])])])+max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])])), Arg_1*(max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), max([(max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]), max([(max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, -(Arg_1)*-(Arg_1)])+max([0, Arg_1])]), (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]))])])]) {O(n^5)}



Sizebounds:

`Lower:

  0: l0->l1, Arg_0: 0 {O(1)}

  0: l0->l1, Arg_1: Arg_1 {O(n)}

  0: l0->l1, Arg_2: Arg_2 {O(n)}

  0: l0->l1, Arg_3: Arg_3 {O(n)}

  1: l1->l2, Arg_0: 0 {O(1)}

  1: l1->l2, Arg_1: 1 {O(1)}

  1: l1->l2, Arg_2: 0 {O(1)}

  1: l1->l2, Arg_3: 0 {O(1)}

  4: l1->l3, Arg_0: 0 {O(1)}

  4: l1->l3, Arg_1: min([0, Arg_1]) {O(n)}

  4: l1->l3, Arg_2: min([1, Arg_2]) {O(n)}

  4: l1->l3, Arg_3: min([0, Arg_3]) {O(n)}

  2: l2->l2, Arg_0: 0 {O(1)}

  2: l2->l2, Arg_1: 1 {O(1)}

  2: l2->l2, Arg_2: 1 {O(1)}

  2: l2->l2, Arg_3: 0 {O(1)}

  3: l2->l1, Arg_0: 0 {O(1)}

  3: l2->l1, Arg_1: 0 {O(1)}

  3: l2->l1, Arg_2: 1 {O(1)}

  3: l2->l1, Arg_3: 0 {O(1)}

  5: l3->l3, Arg_0: 0 {O(1)}

  5: l3->l3, Arg_1: min([0, Arg_1]) {O(n)}

  5: l3->l3, Arg_2: min([1, Arg_2]) {O(n)}

  5: l3->l3, Arg_3: min([0, Arg_3]) {O(n)}

`Upper:

  0: l0->l1, Arg_0: 0 {O(1)}

  0: l0->l1, Arg_1: Arg_1 {O(n)}

  0: l0->l1, Arg_2: Arg_2 {O(n)}

  0: l0->l1, Arg_3: Arg_3 {O(n)}

  1: l1->l2, Arg_0: max([0, (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])+max([0, Arg_1*((max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]))]) {O(n^5)}

  1: l1->l2, Arg_1: Arg_1 {O(n)}

  1: l1->l2, Arg_2: 0 {O(1)}

  1: l1->l2, Arg_3: 0 {O(1)}

  4: l1->l3, Arg_0: max([0, max([0, (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])+max([0, Arg_1*((max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]))])]) {O(n^5)}

  4: l1->l3, Arg_1: 0 {O(1)}

  4: l1->l3, Arg_2: max([Arg_2, max([0, Arg_1*Arg_1])+max([0, Arg_1])]) {O(n^2)}

  4: l1->l3, Arg_3: max([Arg_3, (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])]) {O(n^4)}

  2: l2->l2, Arg_0: max([0, (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])+max([0, Arg_1*((max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]))]) {O(n^5)}

  2: l2->l2, Arg_1: Arg_1 {O(n)}

  2: l2->l2, Arg_2: max([0, Arg_1*Arg_1])+max([0, Arg_1]) {O(n^2)}

  2: l2->l2, Arg_3: (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]) {O(n^4)}

  3: l2->l1, Arg_0: max([0, (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])+max([0, Arg_1*((max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]))]) {O(n^5)}

  3: l2->l1, Arg_1: Arg_1 {O(n)}

  3: l2->l1, Arg_2: max([0, Arg_1*Arg_1])+max([0, Arg_1]) {O(n^2)}

  3: l2->l1, Arg_3: (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]) {O(n^4)}

  5: l3->l3, Arg_0: max([0, max([0, (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])])+max([0, Arg_1*((max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])]))])]) {O(n^5)}

  5: l3->l3, Arg_1: 0 {O(1)}

  5: l3->l3, Arg_2: max([Arg_2, max([0, Arg_1*Arg_1])+max([0, Arg_1])]) {O(n^2)}

  5: l3->l3, Arg_3: max([Arg_3, (max([0, Arg_1*Arg_1])+max([0, Arg_1]))*max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])+max([0, max([0, Arg_1*Arg_1])+max([0, Arg_1])])]) {O(n^4)}


----------------------------------------

(2)
BOUNDS(1, nat(Arg_1^2) + nat(max(Arg_1 * (nat(Arg_1^2) * nat(nat(Arg_1^2) + nat(Arg_1)) + nat(Arg_1) * nat(nat(Arg_1^2) + nat(Arg_1))) + Arg_1 * nat(nat(Arg_1^2) + nat(Arg_1)), Arg_1 * nat(nat(Arg_1^2) + nat(Arg_1)) + Arg_1 * (-1 * min(-1 * Arg_1^2, 0) * nat(nat(Arg_1^2) + nat(Arg_1)) + nat(Arg_1) * nat(nat(Arg_1^2) + nat(Arg_1))), 0) + nat(nat(nat(Arg_1^2) + nat(Arg_1)) + nat(Arg_1^2) * nat(nat(Arg_1^2) + nat(Arg_1)) + nat(Arg_1) * nat(nat(Arg_1^2) + nat(Arg_1)))) + max(2, 3 + 2 * Arg_1) + nat(2 * Arg_1))

----------------------------------------

(3) Loat Proof (FINISHED)


### Pre-processing the ITS problem ###



Initial linear ITS problem

   Start location: l0

      0: l0 -> l1 : A'=0, [], cost: 1

      1: l1 -> l2 : C'=0, D'=0, [ B>=1 ], cost: 1

      4: l1 -> l3 : [ 0>=B ], cost: 1

      2: l2 -> l2 : C'=1+C, D'=C+D, [ B>=1+C ], cost: 1

      3: l2 -> l1 : A'=D+A, B'=-1+B, [ C>=B ], cost: 1

      5: l3 -> l3 : A'=-1+A, [ A>=1 ], cost: 1



### Simplification by acceleration and chaining ###



Accelerating simple loops of location 2.

   Accelerating the following rules:

      2: l2 -> l2 : C'=1+C, D'=C+D, [ B>=1+C ], cost: 1



   Accelerated rule 2 with metering function -C+B, yielding the new rule 6.

   Removing the simple loops: 2.



Accelerating simple loops of location 3.

   Accelerating the following rules:

      5: l3 -> l3 : A'=-1+A, [ A>=1 ], cost: 1



   Accelerated rule 5 with metering function A, yielding the new rule 7.

   Removing the simple loops: 5.



Accelerated all simple loops using metering functions (where possible):

   Start location: l0

      0: l0 -> l1 : A'=0, [], cost: 1

      1: l1 -> l2 : C'=0, D'=0, [ B>=1 ], cost: 1

      4: l1 -> l3 : [ 0>=B ], cost: 1

      3: l2 -> l1 : A'=D+A, B'=-1+B, [ C>=B ], cost: 1

      6: l2 -> l2 : C'=B, D'=-1-1/2*C-C*(C-B)+1/2*(C-B)^2+D+1/2*B, [ B>=1+C ], cost: -C+B

      7: l3 -> l3 : A'=0, [ A>=1 ], cost: A



Chained accelerated rules (with incoming rules):

   Start location: l0

      0: l0 -> l1 : A'=0, [], cost: 1

      1: l1 -> l2 : C'=0, D'=0, [ B>=1 ], cost: 1

      4: l1 -> l3 : [ 0>=B ], cost: 1

      8: l1 -> l2 : C'=B, D'=-1+1/2*B^2+1/2*B, [ B>=1 ], cost: 1+B

      9: l1 -> l3 : A'=0, [ 0>=B && A>=1 ], cost: 1+A

      3: l2 -> l1 : A'=D+A, B'=-1+B, [ C>=B ], cost: 1



Removed unreachable locations (and leaf rules with constant cost):

   Start location: l0

      0: l0 -> l1 : A'=0, [], cost: 1

      1: l1 -> l2 : C'=0, D'=0, [ B>=1 ], cost: 1

      8: l1 -> l2 : C'=B, D'=-1+1/2*B^2+1/2*B, [ B>=1 ], cost: 1+B

      9: l1 -> l3 : A'=0, [ 0>=B && A>=1 ], cost: 1+A

      3: l2 -> l1 : A'=D+A, B'=-1+B, [ C>=B ], cost: 1



Eliminated locations (on tree-shaped paths):

   Start location: l0

      0: l0 -> l1 : A'=0, [], cost: 1

      9: l1 -> l3 : A'=0, [ 0>=B && A>=1 ], cost: 1+A

     10: l1 -> l1 : A'=-1+1/2*B^2+A+1/2*B, B'=-1+B, C'=B, D'=-1+1/2*B^2+1/2*B, [ B>=1 ], cost: 2+B



Accelerating simple loops of location 1.

   Accelerating the following rules:

     10: l1 -> l1 : A'=-1+1/2*B^2+A+1/2*B, B'=-1+B, C'=B, D'=-1+1/2*B^2+1/2*B, [ B>=1 ], cost: 2+B



   Accelerated rule 10 with metering function B, yielding the new rule 11.

   Removing the simple loops: 10.



Accelerated all simple loops using metering functions (where possible):

   Start location: l0

      0: l0 -> l1 : A'=0, [], cost: 1

      9: l1 -> l3 : A'=0, [ 0>=B && A>=1 ], cost: 1+A

     11: l1 -> l1 : A'=1+1/6*B^3+A-7/6*B, B'=0, C'=1, D'=0, [ B>=1 ], cost: 1/2*B^2+5/2*B



Chained accelerated rules (with incoming rules):

   Start location: l0

      0: l0 -> l1 : A'=0, [], cost: 1

     12: l0 -> l1 : A'=1+1/6*B^3-7/6*B, B'=0, C'=1, D'=0, [ B>=1 ], cost: 1+1/2*B^2+5/2*B

      9: l1 -> l3 : A'=0, [ 0>=B && A>=1 ], cost: 1+A



Eliminated locations (on tree-shaped paths):

   Start location: l0

     13: l0 -> l3 : A'=0, B'=0, C'=1, D'=0, [ B>=1 && 1+1/6*B^3-7/6*B>=1 ], cost: 3+1/6*B^3+1/2*B^2+4/3*B



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: l0

     13: l0 -> l3 : A'=0, B'=0, C'=1, D'=0, [ B>=1 && 1+1/6*B^3-7/6*B>=1 ], cost: 3+1/6*B^3+1/2*B^2+4/3*B



Computing asymptotic complexity for rule 13

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      1+1/6*B^3-7/6*B (+/+!), 3+1/6*B^3+1/2*B^2+4/3*B (+), B (+/+!) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



      applying transformation rule (C) using substitution {B==n}

      resulting limit problem:

      [solved]



   Solution:

      B / n

   Resulting cost 3+4/3*n+1/6*n^3+1/2*n^2 has complexity: Poly(n^3)



Found new complexity Poly(n^3).



Obtained the following overall complexity (w.r.t. the length of the input n):

   Complexity:  Poly(n^3)

   Cpx degree:  3

   Solved cost: 3+4/3*n+1/6*n^3+1/2*n^2

   Rule cost:   3+1/6*B^3+1/2*B^2+4/3*B

   Rule guard:  [ B>=1 && 1+1/6*B^3-7/6*B>=1 ]



WORST_CASE(Omega(n^3),?)


----------------------------------------

(4)
BOUNDS(n^3, INF)