6.81/3.48	WORST_CASE(Omega(n^3), O(n^5))
6.81/3.49	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
6.81/3.49	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
6.81/3.49	
6.81/3.49	
6.81/3.49	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^3, nat(Arg_1^2) + nat(max(Arg_1 * nat(nat(Arg_1^2) + nat(Arg_1)) + 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 * (-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)).
6.81/3.49	
6.81/3.49	(0) CpxIntTrs
6.81/3.49	(1) Koat2 Proof [FINISHED, 1117 ms]
6.81/3.49	(2) BOUNDS(1, nat(Arg_1^2) + nat(max(Arg_1 * nat(nat(Arg_1^2) + nat(Arg_1)) + 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 * (-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))
6.81/3.49	(3) Loat Proof [FINISHED, 444 ms]
6.81/3.49	(4) BOUNDS(n^3, INF)
6.81/3.49	
6.81/3.49	
6.81/3.49	----------------------------------------
6.81/3.49	
6.81/3.49	(0)
6.81/3.49	Obligation:
6.81/3.49	Complexity Int TRS consisting of the following rules:
6.81/3.49	l0(A, B, C, D) -> Com_1(l1(0, B, C, D)) :|: TRUE
6.81/3.49	l1(A, B, C, D) -> Com_1(l2(A, B, 0, 0)) :|: B > 0
6.81/3.49	l2(A, B, C, D) -> Com_1(l2(A, B, C + 1, D + C)) :|: C < B
6.81/3.49	l2(A, B, C, D) -> Com_1(l1(A + D, B - 1, C, D)) :|: C >= B
6.81/3.49	l1(A, B, C, D) -> Com_1(l3(A, B, C, D)) :|: B <= 0
6.81/3.49	l3(A, B, C, D) -> Com_1(l3(A - 1, B, C, D)) :|: A > 0
6.81/3.49	
6.81/3.49	The start-symbols are:[l0_4]
6.81/3.49	
6.81/3.49	
6.81/3.49	----------------------------------------
6.81/3.49	
6.81/3.49	(1) Koat2 Proof (FINISHED)
6.81/3.49	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)})
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	Initial Complexity Problem:
6.81/3.49	
6.81/3.49	  Start:  l0  
6.81/3.49	
6.81/3.49	  Program_Vars:  Arg_0, Arg_1, Arg_2, Arg_3  
6.81/3.49	
6.81/3.49	  Temp_Vars:    
6.81/3.49	
6.81/3.49	  Locations:  l0, l1, l2, l3  
6.81/3.49	
6.81/3.49	  Transitions:
6.81/3.49	
6.81/3.49	  l0(Arg_0,Arg_1,Arg_2,Arg_3) -> l1(0,Arg_1,Arg_2,Arg_3):|:
6.81/3.49	
6.81/3.49	  l1(Arg_0,Arg_1,Arg_2,Arg_3) -> l2(Arg_0,Arg_1,0,0):|:0 <= Arg_0 && 1 <= Arg_1
6.81/3.49	
6.81/3.49	  l1(Arg_0,Arg_1,Arg_2,Arg_3) -> l3(Arg_0,Arg_1,Arg_2,Arg_3):|:0 <= Arg_0 && Arg_1 <= 0
6.81/3.49	
6.81/3.49	  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
6.81/3.49	
6.81/3.49	  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
6.81/3.49	
6.81/3.49	  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  
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	Timebounds: 
6.81/3.49	
6.81/3.49	  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)}
6.81/3.49	
6.81/3.49	  0: l0->l1: 1 {O(1)}
6.81/3.49	
6.81/3.49	  1: l1->l2: max([0, 1+2*Arg_1]) {O(n)}
6.81/3.49	
6.81/3.49	  4: l1->l3: 1 {O(1)}
6.81/3.49	
6.81/3.49	  2: l2->l2: max([0, Arg_1*Arg_1])+max([0, Arg_1]) {O(n^2)}
6.81/3.49	
6.81/3.49	  3: l2->l1: max([0, Arg_1]) {O(n)}
6.81/3.49	
6.81/3.49	  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)}
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	Costbounds:
6.81/3.49	
6.81/3.49	  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)}
6.81/3.49	
6.81/3.49	  0: l0->l1: 1 {O(1)}
6.81/3.49	
6.81/3.49	  1: l1->l2: max([0, 1+2*Arg_1]) {O(n)}
6.81/3.49	
6.81/3.49	  4: l1->l3: 1 {O(1)}
6.81/3.49	
6.81/3.49	  2: l2->l2: max([0, Arg_1*Arg_1])+max([0, Arg_1]) {O(n^2)}
6.81/3.49	
6.81/3.49	  3: l2->l1: max([0, Arg_1]) {O(n)}
6.81/3.49	
6.81/3.49	  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)}
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	Sizebounds:
6.81/3.49	
6.81/3.49	`Lower:
6.81/3.49	
6.81/3.49	  0: l0->l1, Arg_0: 0 {O(1)}
6.81/3.49	
6.81/3.49	  0: l0->l1, Arg_1: Arg_1 {O(n)}
6.81/3.49	
6.81/3.49	  0: l0->l1, Arg_2: Arg_2 {O(n)}
6.81/3.49	
6.81/3.49	  0: l0->l1, Arg_3: Arg_3 {O(n)}
6.81/3.49	
6.81/3.49	  1: l1->l2, Arg_0: 0 {O(1)}
6.81/3.49	
6.81/3.49	  1: l1->l2, Arg_1: 1 {O(1)}
6.81/3.49	
6.81/3.49	  1: l1->l2, Arg_2: 0 {O(1)}
6.81/3.49	
6.81/3.49	  1: l1->l2, Arg_3: 0 {O(1)}
6.81/3.49	
6.81/3.49	  4: l1->l3, Arg_0: 0 {O(1)}
6.81/3.49	
6.81/3.49	  4: l1->l3, Arg_1: min([0, Arg_1]) {O(n)}
6.81/3.49	
6.81/3.49	  4: l1->l3, Arg_2: min([1, Arg_2]) {O(n)}
6.81/3.49	
6.81/3.49	  4: l1->l3, Arg_3: min([0, Arg_3]) {O(n)}
6.81/3.49	
6.81/3.49	  2: l2->l2, Arg_0: 0 {O(1)}
6.81/3.49	
6.81/3.49	  2: l2->l2, Arg_1: 1 {O(1)}
6.81/3.49	
6.81/3.49	  2: l2->l2, Arg_2: 1 {O(1)}
6.81/3.49	
6.81/3.49	  2: l2->l2, Arg_3: 0 {O(1)}
6.81/3.49	
6.81/3.49	  3: l2->l1, Arg_0: 0 {O(1)}
6.81/3.49	
6.81/3.49	  3: l2->l1, Arg_1: 0 {O(1)}
6.81/3.49	
6.81/3.49	  3: l2->l1, Arg_2: 1 {O(1)}
6.81/3.49	
6.81/3.49	  3: l2->l1, Arg_3: 0 {O(1)}
6.81/3.49	
6.81/3.49	  5: l3->l3, Arg_0: 0 {O(1)}
6.81/3.49	
6.81/3.49	  5: l3->l3, Arg_1: min([0, Arg_1]) {O(n)}
6.81/3.49	
6.81/3.49	  5: l3->l3, Arg_2: min([1, Arg_2]) {O(n)}
6.81/3.49	
6.81/3.49	  5: l3->l3, Arg_3: min([0, Arg_3]) {O(n)}
6.81/3.49	
6.81/3.49	`Upper:
6.81/3.49	
6.81/3.49	  0: l0->l1, Arg_0: 0 {O(1)}
6.81/3.49	
6.81/3.49	  0: l0->l1, Arg_1: Arg_1 {O(n)}
6.81/3.49	
6.81/3.49	  0: l0->l1, Arg_2: Arg_2 {O(n)}
6.81/3.49	
6.81/3.49	  0: l0->l1, Arg_3: Arg_3 {O(n)}
6.81/3.49	
6.81/3.49	  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)}
6.81/3.49	
6.81/3.49	  1: l1->l2, Arg_1: Arg_1 {O(n)}
6.81/3.49	
6.81/3.49	  1: l1->l2, Arg_2: 0 {O(1)}
6.81/3.49	
6.81/3.49	  1: l1->l2, Arg_3: 0 {O(1)}
6.81/3.49	
6.81/3.49	  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)}
6.81/3.49	
6.81/3.49	  4: l1->l3, Arg_1: 0 {O(1)}
6.81/3.49	
6.81/3.49	  4: l1->l3, Arg_2: max([Arg_2, max([0, Arg_1*Arg_1])+max([0, Arg_1])]) {O(n^2)}
6.81/3.49	
6.81/3.49	  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)}
6.81/3.49	
6.81/3.49	  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)}
6.81/3.49	
6.81/3.49	  2: l2->l2, Arg_1: Arg_1 {O(n)}
6.81/3.49	
6.81/3.49	  2: l2->l2, Arg_2: max([0, Arg_1*Arg_1])+max([0, Arg_1]) {O(n^2)}
6.81/3.49	
6.81/3.49	  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)}
6.81/3.49	
6.81/3.49	  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)}
6.81/3.49	
6.81/3.49	  3: l2->l1, Arg_1: Arg_1 {O(n)}
6.81/3.49	
6.81/3.49	  3: l2->l1, Arg_2: max([0, Arg_1*Arg_1])+max([0, Arg_1]) {O(n^2)}
6.81/3.49	
6.81/3.49	  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)}
6.81/3.49	
6.81/3.49	  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)}
6.81/3.49	
6.81/3.49	  5: l3->l3, Arg_1: 0 {O(1)}
6.81/3.49	
6.81/3.49	  5: l3->l3, Arg_2: max([Arg_2, max([0, Arg_1*Arg_1])+max([0, Arg_1])]) {O(n^2)}
6.81/3.49	
6.81/3.49	  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)}
6.81/3.49	
6.81/3.49	
6.81/3.49	----------------------------------------
6.81/3.49	
6.81/3.49	(2)
6.81/3.49	BOUNDS(1, nat(Arg_1^2) + nat(max(Arg_1 * nat(nat(Arg_1^2) + nat(Arg_1)) + 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 * (-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))
6.81/3.49	
6.81/3.49	----------------------------------------
6.81/3.49	
6.81/3.49	(3) Loat Proof (FINISHED)
6.81/3.49	
6.81/3.49	
6.81/3.49	### Pre-processing the ITS problem ###
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	Initial linear ITS problem
6.81/3.49	
6.81/3.49	   Start location: l0
6.81/3.49	
6.81/3.49	      0: l0 -> l1 : A'=0, [], cost: 1
6.81/3.49	
6.81/3.49	      1: l1 -> l2 : C'=0, D'=0, [ B>=1 ], cost: 1
6.81/3.49	
6.81/3.49	      4: l1 -> l3 : [ 0>=B ], cost: 1
6.81/3.49	
6.81/3.49	      2: l2 -> l2 : C'=1+C, D'=C+D, [ B>=1+C ], cost: 1
6.81/3.49	
6.81/3.49	      3: l2 -> l1 : A'=D+A, B'=-1+B, [ C>=B ], cost: 1
6.81/3.49	
6.81/3.49	      5: l3 -> l3 : A'=-1+A, [ A>=1 ], cost: 1
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	### Simplification by acceleration and chaining ###
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	Accelerating simple loops of location 2.
6.81/3.49	
6.81/3.49	   Accelerating the following rules:
6.81/3.49	
6.81/3.49	      2: l2 -> l2 : C'=1+C, D'=C+D, [ B>=1+C ], cost: 1
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	   Accelerated rule 2 with metering function -C+B, yielding the new rule 6.
6.81/3.49	
6.81/3.49	   Removing the simple loops: 2.
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	Accelerating simple loops of location 3.
6.81/3.49	
6.81/3.49	   Accelerating the following rules:
6.81/3.49	
6.81/3.49	      5: l3 -> l3 : A'=-1+A, [ A>=1 ], cost: 1
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	   Accelerated rule 5 with metering function A, yielding the new rule 7.
6.81/3.49	
6.81/3.49	   Removing the simple loops: 5.
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	Accelerated all simple loops using metering functions (where possible):
6.81/3.49	
6.81/3.49	   Start location: l0
6.81/3.49	
6.81/3.49	      0: l0 -> l1 : A'=0, [], cost: 1
6.81/3.49	
6.81/3.49	      1: l1 -> l2 : C'=0, D'=0, [ B>=1 ], cost: 1
6.81/3.49	
6.81/3.49	      4: l1 -> l3 : [ 0>=B ], cost: 1
6.81/3.49	
6.81/3.49	      3: l2 -> l1 : A'=D+A, B'=-1+B, [ C>=B ], cost: 1
6.81/3.49	
6.81/3.49	      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
6.81/3.49	
6.81/3.49	      7: l3 -> l3 : A'=0, [ A>=1 ], cost: A
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	Chained accelerated rules (with incoming rules):
6.81/3.49	
6.81/3.49	   Start location: l0
6.81/3.49	
6.81/3.49	      0: l0 -> l1 : A'=0, [], cost: 1
6.81/3.49	
6.81/3.49	      1: l1 -> l2 : C'=0, D'=0, [ B>=1 ], cost: 1
6.81/3.49	
6.81/3.49	      4: l1 -> l3 : [ 0>=B ], cost: 1
6.81/3.49	
6.81/3.49	      8: l1 -> l2 : C'=B, D'=-1+1/2*B^2+1/2*B, [ B>=1 ], cost: 1+B
6.81/3.49	
6.81/3.49	      9: l1 -> l3 : A'=0, [ 0>=B && A>=1 ], cost: 1+A
6.81/3.49	
6.81/3.49	      3: l2 -> l1 : A'=D+A, B'=-1+B, [ C>=B ], cost: 1
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	Removed unreachable locations (and leaf rules with constant cost):
6.81/3.49	
6.81/3.49	   Start location: l0
6.81/3.49	
6.81/3.49	      0: l0 -> l1 : A'=0, [], cost: 1
6.81/3.49	
6.81/3.49	      1: l1 -> l2 : C'=0, D'=0, [ B>=1 ], cost: 1
6.81/3.49	
6.81/3.49	      8: l1 -> l2 : C'=B, D'=-1+1/2*B^2+1/2*B, [ B>=1 ], cost: 1+B
6.81/3.49	
6.81/3.49	      9: l1 -> l3 : A'=0, [ 0>=B && A>=1 ], cost: 1+A
6.81/3.49	
6.81/3.49	      3: l2 -> l1 : A'=D+A, B'=-1+B, [ C>=B ], cost: 1
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	Eliminated locations (on tree-shaped paths):
6.81/3.49	
6.81/3.49	   Start location: l0
6.81/3.49	
6.81/3.49	      0: l0 -> l1 : A'=0, [], cost: 1
6.81/3.49	
6.81/3.49	      9: l1 -> l3 : A'=0, [ 0>=B && A>=1 ], cost: 1+A
6.81/3.49	
6.81/3.49	     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
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	Accelerating simple loops of location 1.
6.81/3.49	
6.81/3.49	   Accelerating the following rules:
6.81/3.49	
6.81/3.49	     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
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	   Accelerated rule 10 with metering function B, yielding the new rule 11.
6.81/3.49	
6.81/3.49	   Removing the simple loops: 10.
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	Accelerated all simple loops using metering functions (where possible):
6.81/3.49	
6.81/3.49	   Start location: l0
6.81/3.49	
6.81/3.49	      0: l0 -> l1 : A'=0, [], cost: 1
6.81/3.49	
6.81/3.49	      9: l1 -> l3 : A'=0, [ 0>=B && A>=1 ], cost: 1+A
6.81/3.49	
6.81/3.49	     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
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	Chained accelerated rules (with incoming rules):
6.81/3.49	
6.81/3.49	   Start location: l0
6.81/3.49	
6.81/3.49	      0: l0 -> l1 : A'=0, [], cost: 1
6.81/3.49	
6.81/3.49	     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
6.81/3.49	
6.81/3.49	      9: l1 -> l3 : A'=0, [ 0>=B && A>=1 ], cost: 1+A
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	Eliminated locations (on tree-shaped paths):
6.81/3.49	
6.81/3.49	   Start location: l0
6.81/3.49	
6.81/3.49	     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
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	### Computing asymptotic complexity ###
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	Fully simplified ITS problem
6.81/3.49	
6.81/3.49	   Start location: l0
6.81/3.49	
6.81/3.49	     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
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	Computing asymptotic complexity for rule 13
6.81/3.49	
6.81/3.49	   Solved the limit problem by the following transformations:
6.81/3.49	
6.81/3.49	      Created initial limit problem:
6.81/3.49	
6.81/3.49	      1+1/6*B^3-7/6*B (+/+!), 3+1/6*B^3+1/2*B^2+4/3*B (+), B (+/+!) [not solved]
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	      removing all constraints (solved by SMT)
6.81/3.49	
6.81/3.49	      resulting limit problem: [solved]
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	      applying transformation rule (C) using substitution {B==n}
6.81/3.49	
6.81/3.49	      resulting limit problem:
6.81/3.49	
6.81/3.49	      [solved]
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	   Solution:
6.81/3.49	
6.81/3.49	      B / n
6.81/3.49	
6.81/3.49	   Resulting cost 3+4/3*n+1/6*n^3+1/2*n^2 has complexity: Poly(n^3)
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	Found new complexity Poly(n^3).
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	Obtained the following overall complexity (w.r.t. the length of the input n):
6.81/3.49	
6.81/3.49	   Complexity:  Poly(n^3)
6.81/3.49	
6.81/3.49	   Cpx degree:  3
6.81/3.49	
6.81/3.49	   Solved cost: 3+4/3*n+1/6*n^3+1/2*n^2
6.81/3.49	
6.81/3.49	   Rule cost:   3+1/6*B^3+1/2*B^2+4/3*B
6.81/3.49	
6.81/3.49	   Rule guard:  [ B>=1 && 1+1/6*B^3-7/6*B>=1 ]
6.81/3.49	
6.81/3.49	
6.81/3.49	
6.81/3.49	WORST_CASE(Omega(n^3),?)
6.81/3.49	
6.81/3.49	
6.81/3.49	----------------------------------------
6.81/3.49	
6.81/3.49	(4)
6.81/3.49	BOUNDS(n^3, INF)
6.81/3.51	EOF