8.12/5.57	WORST_CASE(Omega(n^1), O(n^1))
8.12/5.58	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
8.12/5.58	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
8.12/5.58	
8.12/5.58	
8.12/5.58	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, max(5, 10 + 5 * Arg_1 + -5 * Arg_2) + nat(1 + 2 * Arg_1 + -2 * Arg_2)).
8.12/5.58	
8.12/5.58	(0) CpxIntTrs
8.12/5.58	(1) Koat2 Proof [FINISHED, 1019 ms]
8.12/5.58	(2) BOUNDS(1, max(5, 10 + 5 * Arg_1 + -5 * Arg_2) + nat(1 + 2 * Arg_1 + -2 * Arg_2))
8.12/5.58	(3) Loat Proof [FINISHED, 3239 ms]
8.12/5.58	(4) BOUNDS(n^1, INF)
8.12/5.58	
8.12/5.58	
8.12/5.58	----------------------------------------
8.12/5.58	
8.12/5.58	(0)
8.12/5.58	Obligation:
8.12/5.58	Complexity Int TRS consisting of the following rules:
8.12/5.58	evalaaron2start(A, B, C) -> Com_1(evalaaron2entryin(A, B, C)) :|: TRUE
8.12/5.58	evalaaron2entryin(A, B, C) -> Com_1(evalaaron2bb6in(A, C, B)) :|: A >= 0
8.12/5.58	evalaaron2entryin(A, B, C) -> Com_1(evalaaron2returnin(A, B, C)) :|: 0 >= A + 1
8.12/5.58	evalaaron2bb6in(A, B, C) -> Com_1(evalaaron2returnin(A, B, C)) :|: B >= C + 1
8.12/5.58	evalaaron2bb6in(A, B, C) -> Com_1(evalaaron2returnin(A, B, C)) :|: 0 >= A + 1
8.12/5.58	evalaaron2bb6in(A, B, C) -> Com_1(evalaaron2bb3in(A, B, C)) :|: C >= B && A >= 0
8.12/5.58	evalaaron2bb3in(A, B, C) -> Com_1(evalaaron2bb4in(A, B, C)) :|: 0 >= D + 1
8.12/5.58	evalaaron2bb3in(A, B, C) -> Com_1(evalaaron2bb4in(A, B, C)) :|: D >= 1
8.12/5.58	evalaaron2bb3in(A, B, C) -> Com_1(evalaaron2bb5in(A, B, C)) :|: TRUE
8.12/5.58	evalaaron2bb4in(A, B, C) -> Com_1(evalaaron2bb6in(A, B, C - A - 1)) :|: TRUE
8.12/5.58	evalaaron2bb5in(A, B, C) -> Com_1(evalaaron2bb6in(A, B + A + 1, C)) :|: TRUE
8.12/5.58	evalaaron2returnin(A, B, C) -> Com_1(evalaaron2stop(A, B, C)) :|: TRUE
8.12/5.58	
8.12/5.58	The start-symbols are:[evalaaron2start_3]
8.12/5.58	
8.12/5.58	
8.12/5.58	----------------------------------------
8.12/5.58	
8.12/5.58	(1) Koat2 Proof (FINISHED)
8.12/5.58	YES( ?, 5+2*2*max([0, 1+Arg_1-Arg_2])+max([0, 1+Arg_1-Arg_2])+max([0, 1+-2*Arg_2+2*Arg_1]) {O(n)})
8.12/5.58	
8.12/5.58	
8.12/5.58	
8.12/5.58	Initial Complexity Problem:
8.12/5.58	
8.12/5.58	  Start:  evalaaron2start  
8.12/5.58	
8.12/5.58	  Program_Vars:  Arg_0, Arg_1, Arg_2  
8.12/5.58	
8.12/5.58	  Temp_Vars:  D  
8.12/5.58	
8.12/5.58	  Locations:  evalaaron2bb3in, evalaaron2bb4in, evalaaron2bb5in, evalaaron2bb6in, evalaaron2entryin, evalaaron2returnin, evalaaron2start, evalaaron2stop  
8.12/5.58	
8.12/5.58	  Transitions:
8.12/5.58	
8.12/5.58	  evalaaron2bb3in(Arg_0,Arg_1,Arg_2) -> evalaaron2bb4in(Arg_0,Arg_1,Arg_2):|:Arg_1 <= Arg_2 && 0 <= Arg_0 && D+1 <= 0
8.12/5.58	
8.12/5.58	  evalaaron2bb3in(Arg_0,Arg_1,Arg_2) -> evalaaron2bb4in(Arg_0,Arg_1,Arg_2):|:Arg_1 <= Arg_2 && 0 <= Arg_0 && 1 <= D
8.12/5.58	
8.12/5.58	  evalaaron2bb3in(Arg_0,Arg_1,Arg_2) -> evalaaron2bb5in(Arg_0,Arg_1,Arg_2):|:Arg_1 <= Arg_2 && 0 <= Arg_0
8.12/5.58	
8.12/5.58	  evalaaron2bb4in(Arg_0,Arg_1,Arg_2) -> evalaaron2bb6in(Arg_0,Arg_1,Arg_2-Arg_0-1):|:Arg_1 <= Arg_2 && 0 <= Arg_0
8.12/5.58	
8.12/5.58	  evalaaron2bb5in(Arg_0,Arg_1,Arg_2) -> evalaaron2bb6in(Arg_0,Arg_1+Arg_0+1,Arg_2):|:Arg_1 <= Arg_2 && 0 <= Arg_0
8.12/5.58	
8.12/5.58	  evalaaron2bb6in(Arg_0,Arg_1,Arg_2) -> evalaaron2bb3in(Arg_0,Arg_1,Arg_2):|:0 <= Arg_0 && Arg_1 <= Arg_2 && 0 <= Arg_0
8.12/5.58	
8.12/5.58	  evalaaron2bb6in(Arg_0,Arg_1,Arg_2) -> evalaaron2returnin(Arg_0,Arg_1,Arg_2):|:0 <= Arg_0 && Arg_2+1 <= Arg_1
8.12/5.58	
8.12/5.58	  evalaaron2entryin(Arg_0,Arg_1,Arg_2) -> evalaaron2bb6in(Arg_0,Arg_2,Arg_1):|:0 <= Arg_0
8.12/5.58	
8.12/5.58	  evalaaron2entryin(Arg_0,Arg_1,Arg_2) -> evalaaron2returnin(Arg_0,Arg_1,Arg_2):|:Arg_0+1 <= 0
8.12/5.58	
8.12/5.58	  evalaaron2returnin(Arg_0,Arg_1,Arg_2) -> evalaaron2stop(Arg_0,Arg_1,Arg_2):|:
8.12/5.58	
8.12/5.58	  evalaaron2start(Arg_0,Arg_1,Arg_2) -> evalaaron2entryin(Arg_0,Arg_1,Arg_2):|:  
8.12/5.58	
8.12/5.58	
8.12/5.58	
8.12/5.58	Timebounds: 
8.12/5.58	
8.12/5.58	  Overall timebound: 5+2*2*max([0, 1+Arg_1-Arg_2])+max([0, 1+Arg_1-Arg_2])+max([0, 1+-2*Arg_2+2*Arg_1]) {O(n)}
8.12/5.58	
8.12/5.58	  6: evalaaron2bb3in->evalaaron2bb4in: max([0, 1+Arg_1-Arg_2]) {O(n)}
8.12/5.58	
8.12/5.58	  7: evalaaron2bb3in->evalaaron2bb4in: max([0, 1+Arg_1-Arg_2]) {O(n)}
8.12/5.58	
8.12/5.58	  8: evalaaron2bb3in->evalaaron2bb5in: max([0, 1+Arg_1-Arg_2]) {O(n)}
8.12/5.58	
8.12/5.58	  9: evalaaron2bb4in->evalaaron2bb6in: max([0, 1+-2*Arg_2+2*Arg_1]) {O(n)}
8.12/5.58	
8.12/5.58	  10: evalaaron2bb5in->evalaaron2bb6in: max([0, 1+Arg_1-Arg_2]) {O(n)}
8.12/5.58	
8.12/5.58	  3: evalaaron2bb6in->evalaaron2returnin: 1 {O(1)}
8.12/5.58	
8.12/5.58	  5: evalaaron2bb6in->evalaaron2bb3in: max([0, 1+Arg_1-Arg_2]) {O(n)}
8.12/5.58	
8.12/5.58	  1: evalaaron2entryin->evalaaron2bb6in: 1 {O(1)}
8.12/5.58	
8.12/5.58	  2: evalaaron2entryin->evalaaron2returnin: 1 {O(1)}
8.12/5.58	
8.12/5.58	  11: evalaaron2returnin->evalaaron2stop: 1 {O(1)}
8.12/5.58	
8.12/5.58	  0: evalaaron2start->evalaaron2entryin: 1 {O(1)}
8.12/5.58	
8.12/5.58	
8.12/5.58	
8.12/5.58	Costbounds:
8.12/5.58	
8.12/5.58	  Overall costbound: 5+2*2*max([0, 1+Arg_1-Arg_2])+max([0, 1+Arg_1-Arg_2])+max([0, 1+-2*Arg_2+2*Arg_1]) {O(n)}
8.12/5.58	
8.12/5.58	  6: evalaaron2bb3in->evalaaron2bb4in: max([0, 1+Arg_1-Arg_2]) {O(n)}
8.12/5.58	
8.12/5.58	  7: evalaaron2bb3in->evalaaron2bb4in: max([0, 1+Arg_1-Arg_2]) {O(n)}
8.12/5.58	
8.12/5.58	  8: evalaaron2bb3in->evalaaron2bb5in: max([0, 1+Arg_1-Arg_2]) {O(n)}
8.12/5.58	
8.12/5.58	  9: evalaaron2bb4in->evalaaron2bb6in: max([0, 1+-2*Arg_2+2*Arg_1]) {O(n)}
8.12/5.58	
8.12/5.58	  10: evalaaron2bb5in->evalaaron2bb6in: max([0, 1+Arg_1-Arg_2]) {O(n)}
8.12/5.58	
8.12/5.58	  3: evalaaron2bb6in->evalaaron2returnin: 1 {O(1)}
8.12/5.58	
8.12/5.58	  5: evalaaron2bb6in->evalaaron2bb3in: max([0, 1+Arg_1-Arg_2]) {O(n)}
8.12/5.58	
8.12/5.58	  1: evalaaron2entryin->evalaaron2bb6in: 1 {O(1)}
8.12/5.58	
8.12/5.58	  2: evalaaron2entryin->evalaaron2returnin: 1 {O(1)}
8.12/5.58	
8.12/5.58	  11: evalaaron2returnin->evalaaron2stop: 1 {O(1)}
8.12/5.58	
8.12/5.58	  0: evalaaron2start->evalaaron2entryin: 1 {O(1)}
8.12/5.58	
8.12/5.58	
8.12/5.58	
8.12/5.58	Sizebounds:
8.12/5.58	
8.12/5.58	`Lower:
8.12/5.58	
8.12/5.58	  6: evalaaron2bb3in->evalaaron2bb4in, Arg_0: 0 {O(1)}
8.12/5.58	
8.12/5.58	  6: evalaaron2bb3in->evalaaron2bb4in, Arg_1: Arg_2 {O(n)}
8.12/5.58	
8.12/5.58	  6: evalaaron2bb3in->evalaaron2bb4in, Arg_2: min([0, Arg_1])-max([0, (1+-2*Arg_2+2*Arg_1)*max([1, 1+Arg_0])]) {O(n^2)}
8.12/5.58	
8.12/5.58	  7: evalaaron2bb3in->evalaaron2bb4in, Arg_0: 0 {O(1)}
8.12/5.58	
8.12/5.58	  7: evalaaron2bb3in->evalaaron2bb4in, Arg_1: Arg_2 {O(n)}
8.12/5.58	
8.12/5.58	  7: evalaaron2bb3in->evalaaron2bb4in, Arg_2: min([0, Arg_1])-max([0, (1+-2*Arg_2+2*Arg_1)*max([1, 1+Arg_0])]) {O(n^2)}
8.12/5.58	
8.12/5.58	  8: evalaaron2bb3in->evalaaron2bb5in, Arg_0: 0 {O(1)}
8.12/5.58	
8.12/5.58	  8: evalaaron2bb3in->evalaaron2bb5in, Arg_1: Arg_2 {O(n)}
8.12/5.58	
8.12/5.58	  8: evalaaron2bb3in->evalaaron2bb5in, Arg_2: min([0, Arg_1])-max([0, (1+-2*Arg_2+2*Arg_1)*max([1, 1+Arg_0])]) {O(n^2)}
8.12/5.58	
8.12/5.58	  9: evalaaron2bb4in->evalaaron2bb6in, Arg_0: 0 {O(1)}
8.12/5.58	
8.12/5.58	  9: evalaaron2bb4in->evalaaron2bb6in, Arg_1: Arg_2 {O(n)}
8.12/5.58	
8.12/5.58	  9: evalaaron2bb4in->evalaaron2bb6in, Arg_2: min([0, Arg_1])-max([0, (1+-2*Arg_2+2*Arg_1)*max([1, 1+Arg_0])]) {O(n^2)}
8.12/5.58	
8.12/5.58	  10: evalaaron2bb5in->evalaaron2bb6in, Arg_0: 0 {O(1)}
8.12/5.58	
8.12/5.58	  10: evalaaron2bb5in->evalaaron2bb6in, Arg_1: Arg_2 {O(n)}
8.12/5.58	
8.12/5.58	  10: evalaaron2bb5in->evalaaron2bb6in, Arg_2: min([0, Arg_1])-max([0, (1+-2*Arg_2+2*Arg_1)*max([1, 1+Arg_0])]) {O(n^2)}
8.12/5.58	
8.12/5.58	  3: evalaaron2bb6in->evalaaron2returnin, Arg_0: 0 {O(1)}
8.12/5.58	
8.12/5.58	  3: evalaaron2bb6in->evalaaron2returnin, Arg_1: Arg_2 {O(n)}
8.12/5.58	
8.12/5.58	  3: evalaaron2bb6in->evalaaron2returnin, Arg_2: min([Arg_1, -(max([0, -(Arg_1)])+max([0, (1+-2*Arg_2+2*Arg_1)*max([1, 1+Arg_0])]))]) {O(n^2)}
8.12/5.58	
8.12/5.58	  5: evalaaron2bb6in->evalaaron2bb3in, Arg_0: 0 {O(1)}
8.12/5.58	
8.12/5.58	  5: evalaaron2bb6in->evalaaron2bb3in, Arg_1: Arg_2 {O(n)}
8.12/5.58	
8.12/5.58	  5: evalaaron2bb6in->evalaaron2bb3in, Arg_2: min([0, Arg_1])-max([0, (1+-2*Arg_2+2*Arg_1)*max([1, 1+Arg_0])]) {O(n^2)}
8.12/5.58	
8.12/5.58	  1: evalaaron2entryin->evalaaron2bb6in, Arg_0: 0 {O(1)}
8.12/5.58	
8.12/5.58	  1: evalaaron2entryin->evalaaron2bb6in, Arg_1: Arg_2 {O(n)}
8.12/5.58	
8.12/5.58	  1: evalaaron2entryin->evalaaron2bb6in, Arg_2: Arg_1 {O(n)}
8.12/5.58	
8.12/5.58	  2: evalaaron2entryin->evalaaron2returnin, Arg_0: Arg_0 {O(n)}
8.12/5.58	
8.12/5.58	  2: evalaaron2entryin->evalaaron2returnin, Arg_1: Arg_1 {O(n)}
8.12/5.58	
8.12/5.58	  2: evalaaron2entryin->evalaaron2returnin, Arg_2: Arg_2 {O(n)}
8.12/5.58	
8.12/5.58	  11: evalaaron2returnin->evalaaron2stop, Arg_0: min([0, Arg_0]) {O(n)}
8.12/5.58	
8.12/5.58	  11: evalaaron2returnin->evalaaron2stop, Arg_1: min([Arg_1, Arg_2]) {O(n)}
8.12/5.58	
8.12/5.58	  11: evalaaron2returnin->evalaaron2stop, Arg_2: min([Arg_2, min([Arg_1, -(max([0, -(Arg_1)])+max([0, (1+-2*Arg_2+2*Arg_1)*max([1, 1+Arg_0])]))])]) {O(n^2)}
8.12/5.58	
8.12/5.58	  0: evalaaron2start->evalaaron2entryin, Arg_0: Arg_0 {O(n)}
8.12/5.58	
8.12/5.58	  0: evalaaron2start->evalaaron2entryin, Arg_1: Arg_1 {O(n)}
8.12/5.58	
8.12/5.58	  0: evalaaron2start->evalaaron2entryin, Arg_2: Arg_2 {O(n)}
8.12/5.58	
8.12/5.58	`Upper:
8.12/5.58	
8.12/5.58	  6: evalaaron2bb3in->evalaaron2bb4in, Arg_0: Arg_0 {O(n)}
8.12/5.58	
8.12/5.58	  6: evalaaron2bb3in->evalaaron2bb4in, Arg_1: max([Arg_2, Arg_0])+max([0, (1+Arg_1-Arg_2)*max([1, 1+Arg_0])]) {O(n^2)}
8.12/5.58	
8.12/5.58	  6: evalaaron2bb3in->evalaaron2bb4in, Arg_2: Arg_1 {O(n)}
8.12/5.58	
8.12/5.58	  7: evalaaron2bb3in->evalaaron2bb4in, Arg_0: Arg_0 {O(n)}
8.12/5.58	
8.12/5.58	  7: evalaaron2bb3in->evalaaron2bb4in, Arg_1: max([Arg_2, Arg_0])+max([0, (1+Arg_1-Arg_2)*max([1, 1+Arg_0])]) {O(n^2)}
8.12/5.58	
8.12/5.58	  7: evalaaron2bb3in->evalaaron2bb4in, Arg_2: Arg_1 {O(n)}
8.12/5.58	
8.12/5.58	  8: evalaaron2bb3in->evalaaron2bb5in, Arg_0: Arg_0 {O(n)}
8.12/5.58	
8.12/5.58	  8: evalaaron2bb3in->evalaaron2bb5in, Arg_1: max([Arg_2, Arg_0])+max([0, (1+Arg_1-Arg_2)*max([1, 1+Arg_0])]) {O(n^2)}
8.12/5.58	
8.12/5.58	  8: evalaaron2bb3in->evalaaron2bb5in, Arg_2: Arg_1 {O(n)}
8.12/5.58	
8.12/5.58	  9: evalaaron2bb4in->evalaaron2bb6in, Arg_0: Arg_0 {O(n)}
8.12/5.58	
8.12/5.58	  9: evalaaron2bb4in->evalaaron2bb6in, Arg_1: max([Arg_2, Arg_0])+max([0, (1+Arg_1-Arg_2)*max([1, 1+Arg_0])]) {O(n^2)}
8.12/5.58	
8.12/5.58	  9: evalaaron2bb4in->evalaaron2bb6in, Arg_2: Arg_1 {O(n)}
8.12/5.58	
8.12/5.58	  10: evalaaron2bb5in->evalaaron2bb6in, Arg_0: Arg_0 {O(n)}
8.12/5.58	
8.12/5.58	  10: evalaaron2bb5in->evalaaron2bb6in, Arg_1: max([Arg_2, Arg_0])+max([0, (1+Arg_1-Arg_2)*max([1, 1+Arg_0])]) {O(n^2)}
8.12/5.58	
8.12/5.58	  10: evalaaron2bb5in->evalaaron2bb6in, Arg_2: Arg_1 {O(n)}
8.12/5.58	
8.12/5.58	  3: evalaaron2bb6in->evalaaron2returnin, Arg_0: Arg_0 {O(n)}
8.12/5.58	
8.12/5.58	  3: evalaaron2bb6in->evalaaron2returnin, Arg_1: max([Arg_2, max([Arg_2, Arg_0])+max([0, (1+Arg_1-Arg_2)*max([1, 1+Arg_0])])]) {O(n^2)}
8.12/5.58	
8.12/5.58	  3: evalaaron2bb6in->evalaaron2returnin, Arg_2: Arg_1 {O(n)}
8.12/5.58	
8.12/5.58	  5: evalaaron2bb6in->evalaaron2bb3in, Arg_0: Arg_0 {O(n)}
8.12/5.58	
8.12/5.58	  5: evalaaron2bb6in->evalaaron2bb3in, Arg_1: max([Arg_2, Arg_0])+max([0, (1+Arg_1-Arg_2)*max([1, 1+Arg_0])]) {O(n^2)}
8.12/5.58	
8.12/5.58	  5: evalaaron2bb6in->evalaaron2bb3in, Arg_2: Arg_1 {O(n)}
8.12/5.58	
8.12/5.58	  1: evalaaron2entryin->evalaaron2bb6in, Arg_0: Arg_0 {O(n)}
8.12/5.58	
8.12/5.58	  1: evalaaron2entryin->evalaaron2bb6in, Arg_1: Arg_2 {O(n)}
8.12/5.58	
8.12/5.58	  1: evalaaron2entryin->evalaaron2bb6in, Arg_2: Arg_1 {O(n)}
8.12/5.58	
8.12/5.58	  2: evalaaron2entryin->evalaaron2returnin, Arg_0: -1 {O(1)}
8.12/5.58	
8.12/5.58	  2: evalaaron2entryin->evalaaron2returnin, Arg_1: Arg_1 {O(n)}
8.12/5.58	
8.12/5.58	  2: evalaaron2entryin->evalaaron2returnin, Arg_2: Arg_2 {O(n)}
8.12/5.58	
8.12/5.58	  11: evalaaron2returnin->evalaaron2stop, Arg_0: max([-1, Arg_0]) {O(n)}
8.12/5.58	
8.12/5.58	  11: evalaaron2returnin->evalaaron2stop, Arg_1: max([Arg_1, max([Arg_2, max([Arg_2, Arg_0])+max([0, (1+Arg_1-Arg_2)*max([1, 1+Arg_0])])])]) {O(n^2)}
8.12/5.58	
8.12/5.58	  11: evalaaron2returnin->evalaaron2stop, Arg_2: max([Arg_2, Arg_1]) {O(n)}
8.12/5.58	
8.12/5.58	  0: evalaaron2start->evalaaron2entryin, Arg_0: Arg_0 {O(n)}
8.12/5.58	
8.12/5.58	  0: evalaaron2start->evalaaron2entryin, Arg_1: Arg_1 {O(n)}
8.12/5.58	
8.12/5.58	  0: evalaaron2start->evalaaron2entryin, Arg_2: Arg_2 {O(n)}
8.12/5.58	
8.12/5.58	
8.12/5.58	----------------------------------------
8.12/5.58	
8.12/5.58	(2)
8.12/5.58	BOUNDS(1, max(5, 10 + 5 * Arg_1 + -5 * Arg_2) + nat(1 + 2 * Arg_1 + -2 * Arg_2))
8.12/5.58	
8.12/5.58	----------------------------------------
8.12/5.58	
8.12/5.58	(3) Loat Proof (FINISHED)
8.12/5.58	
8.12/5.58	
8.12/5.58	### Pre-processing the ITS problem ###
8.12/5.58	
8.12/5.58	
8.12/5.58	
8.12/5.58	Initial linear ITS problem
8.12/5.58	
8.12/5.58	   Start location: evalaaron2start
8.12/5.58	
8.12/5.58	      0: evalaaron2start -> evalaaron2entryin : [], cost: 1
8.12/5.58	
8.12/5.58	      1: evalaaron2entryin -> evalaaron2bb6in : B'=C, C'=B, [ A>=0 ], cost: 1
8.12/5.58	
8.12/5.58	      2: evalaaron2entryin -> evalaaron2returnin : [ 0>=1+A ], cost: 1
8.12/5.58	
8.12/5.58	      3: evalaaron2bb6in -> evalaaron2returnin : [ B>=1+C ], cost: 1
8.12/5.58	
8.12/5.58	      4: evalaaron2bb6in -> evalaaron2returnin : [ 0>=1+A ], cost: 1
8.12/5.58	
8.12/5.58	      5: evalaaron2bb6in -> evalaaron2bb3in : [ C>=B && A>=0 ], cost: 1
8.12/5.58	
8.12/5.58	      6: evalaaron2bb3in -> evalaaron2bb4in : [ 0>=1+free ], cost: 1
8.12/5.58	
8.12/5.58	      7: evalaaron2bb3in -> evalaaron2bb4in : [ free_1>=1 ], cost: 1
8.12/5.58	
8.12/5.58	      8: evalaaron2bb3in -> evalaaron2bb5in : [], cost: 1
8.12/5.58	
8.12/5.58	      9: evalaaron2bb4in -> evalaaron2bb6in : C'=-1+C-A, [], cost: 1
8.12/5.58	
8.12/5.58	     10: evalaaron2bb5in -> evalaaron2bb6in : B'=1+A+B, [], cost: 1
8.12/5.58	
8.12/5.58	     11: evalaaron2returnin -> evalaaron2stop : [], cost: 1
8.12/5.58	
8.12/5.58	
8.12/5.58	
8.12/5.58	Removed unreachable and leaf rules:
8.12/5.58	
8.12/5.58	   Start location: evalaaron2start
8.12/5.58	
8.12/5.58	      0: evalaaron2start -> evalaaron2entryin : [], cost: 1
8.12/5.58	
8.12/5.58	      1: evalaaron2entryin -> evalaaron2bb6in : B'=C, C'=B, [ A>=0 ], cost: 1
8.12/5.58	
8.12/5.58	      5: evalaaron2bb6in -> evalaaron2bb3in : [ C>=B && A>=0 ], cost: 1
8.12/5.58	
8.12/5.58	      6: evalaaron2bb3in -> evalaaron2bb4in : [ 0>=1+free ], cost: 1
8.12/5.58	
8.12/5.58	      7: evalaaron2bb3in -> evalaaron2bb4in : [ free_1>=1 ], cost: 1
8.12/5.58	
8.12/5.58	      8: evalaaron2bb3in -> evalaaron2bb5in : [], cost: 1
8.12/5.58	
8.12/5.58	      9: evalaaron2bb4in -> evalaaron2bb6in : C'=-1+C-A, [], cost: 1
8.12/5.58	
8.12/5.58	     10: evalaaron2bb5in -> evalaaron2bb6in : B'=1+A+B, [], cost: 1
8.12/5.58	
8.12/5.58	
8.12/5.58	
8.12/5.58	Simplified all rules, resulting in:
8.12/5.58	
8.12/5.58	   Start location: evalaaron2start
8.12/5.58	
8.12/5.58	      0: evalaaron2start -> evalaaron2entryin : [], cost: 1
8.12/5.58	
8.12/5.58	      1: evalaaron2entryin -> evalaaron2bb6in : B'=C, C'=B, [ A>=0 ], cost: 1
8.12/5.58	
8.12/5.58	      5: evalaaron2bb6in -> evalaaron2bb3in : [ C>=B && A>=0 ], cost: 1
8.12/5.58	
8.12/5.58	      7: evalaaron2bb3in -> evalaaron2bb4in : [], cost: 1
8.12/5.58	
8.12/5.58	      8: evalaaron2bb3in -> evalaaron2bb5in : [], cost: 1
8.12/5.58	
8.12/5.58	      9: evalaaron2bb4in -> evalaaron2bb6in : C'=-1+C-A, [], cost: 1
8.12/5.58	
8.12/5.58	     10: evalaaron2bb5in -> evalaaron2bb6in : B'=1+A+B, [], cost: 1
8.12/5.58	
8.12/5.58	
8.12/5.58	
8.12/5.58	### Simplification by acceleration and chaining ###
8.12/5.58	
8.12/5.58	
8.12/5.58	
8.12/5.58	Eliminated locations (on linear paths):
8.12/5.58	
8.12/5.58	   Start location: evalaaron2start
8.12/5.58	
8.12/5.58	     12: evalaaron2start -> evalaaron2bb6in : B'=C, C'=B, [ A>=0 ], cost: 2
8.12/5.58	
8.12/5.58	      5: evalaaron2bb6in -> evalaaron2bb3in : [ C>=B && A>=0 ], cost: 1
8.12/5.58	
8.12/5.58	     13: evalaaron2bb3in -> evalaaron2bb6in : C'=-1+C-A, [], cost: 2
8.12/5.58	
8.12/5.58	     14: evalaaron2bb3in -> evalaaron2bb6in : B'=1+A+B, [], cost: 2
8.12/5.58	
8.12/5.58	
8.12/5.58	
8.12/5.58	Eliminated locations (on tree-shaped paths):
8.12/5.58	
8.12/5.58	   Start location: evalaaron2start
8.12/5.58	
8.12/5.58	     12: evalaaron2start -> evalaaron2bb6in : B'=C, C'=B, [ A>=0 ], cost: 2
8.12/5.58	
8.12/5.58	     15: evalaaron2bb6in -> evalaaron2bb6in : C'=-1+C-A, [ C>=B && A>=0 ], cost: 3
8.12/5.58	
8.12/5.58	     16: evalaaron2bb6in -> evalaaron2bb6in : B'=1+A+B, [ C>=B && A>=0 ], cost: 3
8.12/5.58	
8.12/5.58	
8.12/5.58	
8.12/5.58	Accelerating simple loops of location 2.
8.12/5.58	
8.12/5.58	   Accelerating the following rules:
8.12/5.58	
8.12/5.58	     15: evalaaron2bb6in -> evalaaron2bb6in : C'=-1+C-A, [ C>=B && A>=0 ], cost: 3
8.12/5.58	
8.12/5.58	     16: evalaaron2bb6in -> evalaaron2bb6in : B'=1+A+B, [ C>=B && A>=0 ], cost: 3
8.12/5.58	
8.12/5.58	
8.12/5.58	
8.12/5.58	   Accelerated rule 15 with backward acceleration, yielding the new rule 17.
8.12/5.58	
8.12/5.58	   Accelerated rule 16 with backward acceleration, yielding the new rule 18.
8.12/5.58	
8.12/5.58	   Removing the simple loops: 15 16.
8.12/5.58	
8.12/5.58	
8.12/5.58	
8.12/5.58	Accelerated all simple loops using metering functions (where possible):
8.12/5.58	
8.12/5.58	   Start location: evalaaron2start
8.12/5.58	
8.12/5.58	     12: evalaaron2start -> evalaaron2bb6in : B'=C, C'=B, [ A>=0 ], cost: 2
8.12/5.58	
8.12/5.58	     17: evalaaron2bb6in -> evalaaron2bb6in : C'=C-A*k-k, [ C>=B && A>=0 && k>0 && 1+C-A*(-1+k)-k>=B ], cost: 3*k
8.12/5.58	
8.12/5.58	     18: evalaaron2bb6in -> evalaaron2bb6in : B'=A*k_1+k_1+B, [ C>=B && A>=0 && k_1>0 && C>=-1+k_1+(-1+k_1)*A+B ], cost: 3*k_1
8.12/5.58	
8.12/5.58	
8.12/5.58	
8.12/5.58	Chained accelerated rules (with incoming rules):
8.12/5.58	
8.12/5.58	   Start location: evalaaron2start
8.12/5.58	
8.12/5.58	     12: evalaaron2start -> evalaaron2bb6in : B'=C, C'=B, [ A>=0 ], cost: 2
8.12/5.58	
8.12/5.58	     19: evalaaron2start -> evalaaron2bb6in : B'=C, C'=-A*k-k+B, [ A>=0 && B>=C && k>0 && 1-A*(-1+k)-k+B>=C ], cost: 2+3*k
8.12/5.58	
8.12/5.58	     20: evalaaron2start -> evalaaron2bb6in : B'=C+A*k_1+k_1, C'=B, [ A>=0 && B>=C && k_1>0 && B>=-1+C+k_1+(-1+k_1)*A ], cost: 2+3*k_1
8.12/5.58	
8.12/5.58	
8.12/5.58	
8.12/5.58	Removed unreachable locations (and leaf rules with constant cost):
8.12/5.58	
8.12/5.58	   Start location: evalaaron2start
8.12/5.58	
8.12/5.58	     19: evalaaron2start -> evalaaron2bb6in : B'=C, C'=-A*k-k+B, [ A>=0 && B>=C && k>0 && 1-A*(-1+k)-k+B>=C ], cost: 2+3*k
8.12/5.58	
8.12/5.58	     20: evalaaron2start -> evalaaron2bb6in : B'=C+A*k_1+k_1, C'=B, [ A>=0 && B>=C && k_1>0 && B>=-1+C+k_1+(-1+k_1)*A ], cost: 2+3*k_1
8.12/5.58	
8.12/5.58	
8.12/5.58	
8.12/5.58	### Computing asymptotic complexity ###
8.12/5.58	
8.12/5.58	
8.12/5.58	
8.12/5.58	Fully simplified ITS problem
8.12/5.58	
8.12/5.58	   Start location: evalaaron2start
8.12/5.58	
8.12/5.58	     19: evalaaron2start -> evalaaron2bb6in : B'=C, C'=-A*k-k+B, [ A>=0 && B>=C && k>0 && 1-A*(-1+k)-k+B>=C ], cost: 2+3*k
8.12/5.58	
8.12/5.58	     20: evalaaron2start -> evalaaron2bb6in : B'=C+A*k_1+k_1, C'=B, [ A>=0 && B>=C && k_1>0 && B>=-1+C+k_1+(-1+k_1)*A ], cost: 2+3*k_1
8.12/5.58	
8.12/5.58	
8.12/5.58	
8.12/5.58	Computing asymptotic complexity for rule 19
8.12/5.58	
8.12/5.58	   Solved the limit problem by the following transformations:
8.12/5.58	
8.12/5.58	      Created initial limit problem:
8.12/5.58	
8.12/5.58	      2-C-A*(-1+k)-k+B (+/+!), 1-C+B (+/+!), 2+3*k (+), k (+/+!), 1+A (+/+!) [not solved]
8.12/5.58	
8.12/5.58	
8.12/5.58	
8.12/5.58	      removing all constraints (solved by SMT)
8.12/5.58	
8.12/5.58	      resulting limit problem: [solved]
8.12/5.58	
8.12/5.58	
8.12/5.58	
8.12/5.58	      applying transformation rule (C) using substitution {C==0,A==0,k==n,B==2*n}
8.12/5.58	
8.12/5.58	      resulting limit problem:
8.12/5.58	
8.12/5.58	      [solved]
8.12/5.58	
8.12/5.58	
8.12/5.58	
8.12/5.58	   Solved the limit problem by the following transformations:
8.12/5.58	
8.12/5.58	      Created initial limit problem:
8.12/5.58	
8.12/5.58	      2-C-A*(-1+k)-k+B (+/+!), 1-C+B (+/+!), 2+3*k (+), k (+/+!), 1+A (+/+!) [not solved]
8.12/5.58	
8.12/5.58	
8.12/5.58	
8.12/5.58	      applying transformation rule (C) using substitution {A==0}
8.12/5.58	
8.12/5.58	      resulting limit problem:
8.12/5.58	
8.12/5.58	      1 (+/+!), 1-C+B (+/+!), 2+3*k (+), 2-C-k+B (+/+!), k (+/+!) [not solved]
8.12/5.58	
8.12/5.58	
8.12/5.58	
8.12/5.58	      applying transformation rule (C) using substitution {C==1-A*(-1+k)-k+B}
8.12/5.58	
8.12/5.58	      resulting limit problem:
8.12/5.58	
8.12/5.58	      1 (+/+!), 2+3*k (+), A*(-1+k)+k (+/+!), k (+/+!), 1+A*(-1+k) (+/+!) [not solved]
8.12/5.58	
8.12/5.58	
8.12/5.58	
8.12/5.58	      applying transformation rule (B), deleting 1 (+/+!)
8.12/5.58	
8.12/5.58	      resulting limit problem:
8.12/5.58	
8.12/5.58	      2+3*k (+), A*(-1+k)+k (+/+!), k (+/+!), 1+A*(-1+k) (+/+!) [not solved]
8.12/5.58	
8.12/5.58	
8.12/5.58	
8.12/5.58	      removing all constraints (solved by SMT)
8.12/5.58	
8.12/5.58	      resulting limit problem: [solved]
8.12/5.58	
8.12/5.58	
8.12/5.58	
8.12/5.58	      applying transformation rule (C) using substitution {A==1,k==n}
8.12/5.59	
8.12/5.59	      resulting limit problem:
8.12/5.59	
8.12/5.59	      [solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	   Solved the limit problem by the following transformations:
8.12/5.59	
8.12/5.59	      Created initial limit problem:
8.12/5.59	
8.12/5.59	      2-C-A*(-1+k)-k+B (+/+!), 1-C+B (+/+!), 2+3*k (+), k (+/+!), 1+A (+/+!) [not solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	      applying transformation rule (C) using substitution {C==1-A*(-1+k)-k+B}
8.12/5.59	
8.12/5.59	      resulting limit problem:
8.12/5.59	
8.12/5.59	      1 (+/+!), 2+3*k (+), A*(-1+k)+k (+/+!), k (+/+!), 1+A (+/+!) [not solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	      applying transformation rule (B), deleting 1 (+/+!)
8.12/5.59	
8.12/5.59	      resulting limit problem:
8.12/5.59	
8.12/5.59	      2+3*k (+), A*(-1+k)+k (+/+!), k (+/+!), 1+A (+/+!) [not solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	      removing all constraints (solved by SMT)
8.12/5.59	
8.12/5.59	      resulting limit problem: [solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	      applying transformation rule (C) using substitution {A==0,k==n}
8.12/5.59	
8.12/5.59	      resulting limit problem:
8.12/5.59	
8.12/5.59	      [solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	   Solved the limit problem by the following transformations:
8.12/5.59	
8.12/5.59	      Created initial limit problem:
8.12/5.59	
8.12/5.59	      2-C-A*(-1+k)-k+B (+/+!), 1-C+B (+/+!), 2+3*k (+), k (+/+!), 1+A (+/+!) [not solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	      applying transformation rule (C) using substitution {A==0}
8.12/5.59	
8.12/5.59	      resulting limit problem:
8.12/5.59	
8.12/5.59	      1 (+/+!), 1-C+B (+/+!), 2+3*k (+), 2-C-k+B (+/+!), k (+/+!) [not solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	      applying transformation rule (B), deleting 1 (+/+!)
8.12/5.59	
8.12/5.59	      resulting limit problem:
8.12/5.59	
8.12/5.59	      1-C+B (+/+!), 2+3*k (+), 2-C-k+B (+/+!), k (+/+!) [not solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	      removing all constraints (solved by SMT)
8.12/5.59	
8.12/5.59	      resulting limit problem: [solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	      applying transformation rule (C) using substitution {C==0,k==n,B==n}
8.12/5.59	
8.12/5.59	      resulting limit problem:
8.12/5.59	
8.12/5.59	      [solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	   Solution:
8.12/5.59	
8.12/5.59	      C / 0
8.12/5.59	
8.12/5.59	      A / 0
8.12/5.59	
8.12/5.59	      k / n
8.12/5.59	
8.12/5.59	      B / 2*n
8.12/5.59	
8.12/5.59	   Resulting cost 2+3*n has complexity: Poly(n^1)
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	Found new complexity Poly(n^1).
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	Computing asymptotic complexity for rule 20
8.12/5.59	
8.12/5.59	   Solved the limit problem by the following transformations:
8.12/5.59	
8.12/5.59	      Created initial limit problem:
8.12/5.59	
8.12/5.59	      1-C+B (+/+!), 2-C-k_1-(-1+k_1)*A+B (+/+!), k_1 (+/+!), 2+3*k_1 (+), 1+A (+/+!) [not solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	      removing all constraints (solved by SMT)
8.12/5.59	
8.12/5.59	      resulting limit problem: [solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	      applying transformation rule (C) using substitution {C==0,A==0,k_1==n,B==2*n}
8.12/5.59	
8.12/5.59	      resulting limit problem:
8.12/5.59	
8.12/5.59	      [solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	   Solved the limit problem by the following transformations:
8.12/5.59	
8.12/5.59	      Created initial limit problem:
8.12/5.59	
8.12/5.59	      1-C+B (+/+!), 2-C-k_1-(-1+k_1)*A+B (+/+!), k_1 (+/+!), 2+3*k_1 (+), 1+A (+/+!) [not solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	      applying transformation rule (C) using substitution {A==0}
8.12/5.59	
8.12/5.59	      resulting limit problem:
8.12/5.59	
8.12/5.59	      1 (+/+!), 1-C+B (+/+!), 2-C-k_1+B (+/+!), k_1 (+/+!), 2+3*k_1 (+) [not solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	      applying transformation rule (C) using substitution {B==-1+C+k_1+(-1+k_1)*A}
8.12/5.59	
8.12/5.59	      resulting limit problem:
8.12/5.59	
8.12/5.59	      1 (+/+!), k_1+(-1+k_1)*A (+/+!), 1+(-1+k_1)*A (+/+!), k_1 (+/+!), 2+3*k_1 (+) [not solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	      applying transformation rule (B), deleting 1 (+/+!)
8.12/5.59	
8.12/5.59	      resulting limit problem:
8.12/5.59	
8.12/5.59	      k_1+(-1+k_1)*A (+/+!), 1+(-1+k_1)*A (+/+!), k_1 (+/+!), 2+3*k_1 (+) [not solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	      removing all constraints (solved by SMT)
8.12/5.59	
8.12/5.59	      resulting limit problem: [solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	      applying transformation rule (C) using substitution {A==1,k_1==n}
8.12/5.59	
8.12/5.59	      resulting limit problem:
8.12/5.59	
8.12/5.59	      [solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	   Solved the limit problem by the following transformations:
8.12/5.59	
8.12/5.59	      Created initial limit problem:
8.12/5.59	
8.12/5.59	      1-C+B (+/+!), 2-C-k_1-(-1+k_1)*A+B (+/+!), k_1 (+/+!), 2+3*k_1 (+), 1+A (+/+!) [not solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	      applying transformation rule (C) using substitution {B==-1+C+k_1+(-1+k_1)*A}
8.12/5.59	
8.12/5.59	      resulting limit problem:
8.12/5.59	
8.12/5.59	      1 (+/+!), k_1+(-1+k_1)*A (+/+!), k_1 (+/+!), 2+3*k_1 (+), 1+A (+/+!) [not solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	      applying transformation rule (B), deleting 1 (+/+!)
8.12/5.59	
8.12/5.59	      resulting limit problem:
8.12/5.59	
8.12/5.59	      k_1+(-1+k_1)*A (+/+!), k_1 (+/+!), 2+3*k_1 (+), 1+A (+/+!) [not solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	      removing all constraints (solved by SMT)
8.12/5.59	
8.12/5.59	      resulting limit problem: [solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	      applying transformation rule (C) using substitution {A==0,k_1==n}
8.12/5.59	
8.12/5.59	      resulting limit problem:
8.12/5.59	
8.12/5.59	      [solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	   Solved the limit problem by the following transformations:
8.12/5.59	
8.12/5.59	      Created initial limit problem:
8.12/5.59	
8.12/5.59	      1-C+B (+/+!), 2-C-k_1-(-1+k_1)*A+B (+/+!), k_1 (+/+!), 2+3*k_1 (+), 1+A (+/+!) [not solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	      applying transformation rule (C) using substitution {A==0}
8.12/5.59	
8.12/5.59	      resulting limit problem:
8.12/5.59	
8.12/5.59	      1 (+/+!), 1-C+B (+/+!), 2-C-k_1+B (+/+!), k_1 (+/+!), 2+3*k_1 (+) [not solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	      applying transformation rule (B), deleting 1 (+/+!)
8.12/5.59	
8.12/5.59	      resulting limit problem:
8.12/5.59	
8.12/5.59	      1-C+B (+/+!), 2-C-k_1+B (+/+!), k_1 (+/+!), 2+3*k_1 (+) [not solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	      removing all constraints (solved by SMT)
8.12/5.59	
8.12/5.59	      resulting limit problem: [solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	      applying transformation rule (C) using substitution {C==0,k_1==n,B==n}
8.12/5.59	
8.12/5.59	      resulting limit problem:
8.12/5.59	
8.12/5.59	      [solved]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	   Solution:
8.12/5.59	
8.12/5.59	      C / 0
8.12/5.59	
8.12/5.59	      A / 0
8.12/5.59	
8.12/5.59	      k_1 / n
8.12/5.59	
8.12/5.59	      B / 2*n
8.12/5.59	
8.12/5.59	   Resulting cost 2+3*n has complexity: Poly(n^1)
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	Obtained the following overall complexity (w.r.t. the length of the input n):
8.12/5.59	
8.12/5.59	   Complexity:  Poly(n^1)
8.12/5.59	
8.12/5.59	   Cpx degree:  1
8.12/5.59	
8.12/5.59	   Solved cost: 2+3*n
8.12/5.59	
8.12/5.59	   Rule cost:   2+3*k
8.12/5.59	
8.12/5.59	   Rule guard:  [ A>=0 && B>=C && k>0 && 1-A*(-1+k)-k+B>=C ]
8.12/5.59	
8.12/5.59	
8.12/5.59	
8.12/5.59	WORST_CASE(Omega(n^1),?)
8.12/5.59	
8.12/5.59	
8.12/5.59	----------------------------------------
8.12/5.59	
8.12/5.59	(4)
8.12/5.59	BOUNDS(n^1, INF)
8.12/5.61	EOF