5.50/3.24	WORST_CASE(Omega(n^1), O(n^1))
5.50/3.25	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
5.50/3.25	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
5.50/3.25	
5.50/3.25	
5.50/3.25	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, nat(2 * Arg_2) + max(1, 1 + Arg_0 + -1 * Arg_1)).
5.50/3.25	
5.50/3.25	(0) CpxIntTrs
5.50/3.25	(1) Koat2 Proof [FINISHED, 296 ms]
5.50/3.25	(2) BOUNDS(1, nat(2 * Arg_2) + max(1, 1 + Arg_0 + -1 * Arg_1))
5.50/3.25	(3) Loat Proof [FINISHED, 1515 ms]
5.50/3.25	(4) BOUNDS(n^1, INF)
5.50/3.25	
5.50/3.25	
5.50/3.25	----------------------------------------
5.50/3.25	
5.50/3.25	(0)
5.50/3.25	Obligation:
5.50/3.25	Complexity Int TRS consisting of the following rules:
5.50/3.25	eval0(A, B, C) -> Com_1(eval1(A, B, C)) :|: A >= 1
5.50/3.25	eval1(A, B, C) -> Com_1(eval1(A, B + A, C)) :|: A >= B + 1 && C >= A + 1 && A >= 1
5.50/3.25	eval1(A, B, C) -> Com_1(eval1(A, B, B - A)) :|: A >= B + 1 && C >= A + 1 && A >= 1
5.50/3.25	
5.50/3.25	The start-symbols are:[eval0_3]
5.50/3.25	
5.50/3.25	
5.50/3.25	----------------------------------------
5.50/3.25	
5.50/3.25	(1) Koat2 Proof (FINISHED)
5.50/3.25	YES( ?, max([0, 2*Arg_2])+max([1, 1+Arg_0-Arg_1]) {O(n)})
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	Initial Complexity Problem:
5.50/3.25	
5.50/3.25	  Start:  eval0  
5.50/3.25	
5.50/3.25	  Program_Vars:  Arg_0, Arg_1, Arg_2  
5.50/3.25	
5.50/3.25	  Temp_Vars:    
5.50/3.25	
5.50/3.25	  Locations:  eval0, eval1  
5.50/3.25	
5.50/3.25	  Transitions:
5.50/3.25	
5.50/3.25	  eval0(Arg_0,Arg_1,Arg_2) -> eval1(Arg_0,Arg_1,Arg_2):|:1 <= Arg_0
5.50/3.25	
5.50/3.25	  eval1(Arg_0,Arg_1,Arg_2) -> eval1(Arg_0,Arg_1+Arg_0,Arg_2):|:1 <= Arg_0 && Arg_1+1 <= Arg_0 && Arg_0+1 <= Arg_2 && 1 <= Arg_0
5.50/3.25	
5.50/3.25	  eval1(Arg_0,Arg_1,Arg_2) -> eval1(Arg_0,Arg_1,Arg_1-Arg_0):|:1 <= Arg_0 && Arg_1+1 <= Arg_0 && Arg_0+1 <= Arg_2 && 1 <= Arg_0  
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	Timebounds: 
5.50/3.25	
5.50/3.25	  Overall timebound: max([0, 2*Arg_2])+max([1, 1+Arg_0-Arg_1]) {O(n)}
5.50/3.25	
5.50/3.25	  0: eval0->eval1: 1 {O(1)}
5.50/3.25	
5.50/3.25	  1: eval1->eval1: max([0, Arg_0-Arg_1]) {O(n)}
5.50/3.25	
5.50/3.25	  2: eval1->eval1: max([0, 2*Arg_2]) {O(n)}
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	Costbounds:
5.50/3.25	
5.50/3.25	  Overall costbound: max([0, 2*Arg_2])+max([1, 1+Arg_0-Arg_1]) {O(n)}
5.50/3.25	
5.50/3.25	  0: eval0->eval1: 1 {O(1)}
5.50/3.25	
5.50/3.25	  1: eval1->eval1: max([0, Arg_0-Arg_1]) {O(n)}
5.50/3.25	
5.50/3.25	  2: eval1->eval1: max([0, 2*Arg_2]) {O(n)}
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	Sizebounds:
5.50/3.25	
5.50/3.25	`Lower:
5.50/3.25	
5.50/3.25	  0: eval0->eval1, Arg_0: 1 {O(1)}
5.50/3.25	
5.50/3.25	  0: eval0->eval1, Arg_1: Arg_1 {O(n)}
5.50/3.25	
5.50/3.25	  0: eval0->eval1, Arg_2: Arg_2 {O(n)}
5.50/3.25	
5.50/3.25	  1: eval1->eval1, Arg_0: 1 {O(1)}
5.50/3.25	
5.50/3.25	  1: eval1->eval1, Arg_1: Arg_1 {O(n)}
5.50/3.25	
5.50/3.25	  1: eval1->eval1, Arg_2: 2 {O(1)}
5.50/3.25	
5.50/3.25	  2: eval1->eval1, Arg_0: 1 {O(1)}
5.50/3.25	
5.50/3.25	  2: eval1->eval1, Arg_1: Arg_1 {O(n)}
5.50/3.25	
5.50/3.25	  2: eval1->eval1, Arg_2: Arg_1-Arg_0 {O(n)}
5.50/3.25	
5.50/3.25	`Upper:
5.50/3.25	
5.50/3.25	  0: eval0->eval1, Arg_0: Arg_0 {O(n)}
5.50/3.25	
5.50/3.25	  0: eval0->eval1, Arg_1: Arg_1 {O(n)}
5.50/3.25	
5.50/3.25	  0: eval0->eval1, Arg_2: Arg_2 {O(n)}
5.50/3.25	
5.50/3.25	  1: eval1->eval1, Arg_0: Arg_0 {O(n)}
5.50/3.25	
5.50/3.25	  1: eval1->eval1, Arg_1: 2*Arg_0 {O(n)}
5.50/3.25	
5.50/3.25	  1: eval1->eval1, Arg_2: Arg_2 {O(n)}
5.50/3.25	
5.50/3.25	  2: eval1->eval1, Arg_0: Arg_0 {O(n)}
5.50/3.25	
5.50/3.25	  2: eval1->eval1, Arg_1: max([Arg_1, 2*Arg_0]) {O(n)}
5.50/3.25	
5.50/3.25	  2: eval1->eval1, Arg_2: -1 {O(1)}
5.50/3.25	
5.50/3.25	
5.50/3.25	----------------------------------------
5.50/3.25	
5.50/3.25	(2)
5.50/3.25	BOUNDS(1, nat(2 * Arg_2) + max(1, 1 + Arg_0 + -1 * Arg_1))
5.50/3.25	
5.50/3.25	----------------------------------------
5.50/3.25	
5.50/3.25	(3) Loat Proof (FINISHED)
5.50/3.25	
5.50/3.25	
5.50/3.25	### Pre-processing the ITS problem ###
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	Initial linear ITS problem
5.50/3.25	
5.50/3.25	   Start location: eval0
5.50/3.25	
5.50/3.25	      0: eval0 -> eval1 : [ A>=1 ], cost: 1
5.50/3.25	
5.50/3.25	      1: eval1 -> eval1 : B'=A+B, [ A>=1+B && C>=1+A && A>=1 ], cost: 1
5.50/3.25	
5.50/3.25	      2: eval1 -> eval1 : C'=-A+B, [ A>=1+B && C>=1+A && A>=1 ], cost: 1
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	### Simplification by acceleration and chaining ###
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	Accelerating simple loops of location 1.
5.50/3.25	
5.50/3.25	   Accelerating the following rules:
5.50/3.25	
5.50/3.25	      1: eval1 -> eval1 : B'=A+B, [ A>=1+B && C>=1+A && A>=1 ], cost: 1
5.50/3.25	
5.50/3.25	      2: eval1 -> eval1 : C'=-A+B, [ A>=1+B && C>=1+A && A>=1 ], cost: 1
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	   Accelerated rule 1 with backward acceleration, yielding the new rule 3.
5.50/3.25	
5.50/3.25	   Accelerated rule 2 with NONTERM (after strengthening guard), yielding the new rule 4.
5.50/3.25	
5.50/3.25	   Removing the simple loops: 1.
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	Accelerated all simple loops using metering functions (where possible):
5.50/3.25	
5.50/3.25	   Start location: eval0
5.50/3.25	
5.50/3.25	      0: eval0 -> eval1 : [ A>=1 ], cost: 1
5.50/3.25	
5.50/3.25	      2: eval1 -> eval1 : C'=-A+B, [ A>=1+B && C>=1+A && A>=1 ], cost: 1
5.50/3.25	
5.50/3.25	      3: eval1 -> eval1 : B'=A*k+B, [ A>=1+B && C>=1+A && A>=1 && k>0 && A>=1+A*(-1+k)+B ], cost: k
5.50/3.25	
5.50/3.25	      4: eval1 -> [2] : [ A>=1+B && C>=1+A && A>=1 && -A+B>=1+A ], cost: INF
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	Chained accelerated rules (with incoming rules):
5.50/3.25	
5.50/3.25	   Start location: eval0
5.50/3.25	
5.50/3.25	      0: eval0 -> eval1 : [ A>=1 ], cost: 1
5.50/3.25	
5.50/3.25	      5: eval0 -> eval1 : C'=-A+B, [ A>=1 && A>=1+B && C>=1+A ], cost: 2
5.50/3.25	
5.50/3.25	      6: eval0 -> eval1 : B'=A*k+B, [ A>=1 && A>=1+B && C>=1+A && k>0 && A>=1+A*(-1+k)+B ], cost: 1+k
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	Removed unreachable locations (and leaf rules with constant cost):
5.50/3.25	
5.50/3.25	   Start location: eval0
5.50/3.25	
5.50/3.25	      6: eval0 -> eval1 : B'=A*k+B, [ A>=1 && A>=1+B && C>=1+A && k>0 && A>=1+A*(-1+k)+B ], cost: 1+k
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	### Computing asymptotic complexity ###
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	Fully simplified ITS problem
5.50/3.25	
5.50/3.25	   Start location: eval0
5.50/3.25	
5.50/3.25	      6: eval0 -> eval1 : B'=A*k+B, [ A>=1 && A>=1+B && C>=1+A && k>0 && A>=1+A*(-1+k)+B ], cost: 1+k
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	Computing asymptotic complexity for rule 6
5.50/3.25	
5.50/3.25	   Solved the limit problem by the following transformations:
5.50/3.25	
5.50/3.25	      Created initial limit problem:
5.50/3.25	
5.50/3.25	      1+k (+), -A*(-1+k)+A-B (+/+!), A (+/+!), C-A (+/+!), k (+/+!), A-B (+/+!) [not solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	      removing all constraints (solved by SMT)
5.50/3.25	
5.50/3.25	      resulting limit problem: [solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	      applying transformation rule (C) using substitution {C==n,A==1,k==1+n,B==-n}
5.50/3.25	
5.50/3.25	      resulting limit problem:
5.50/3.25	
5.50/3.25	      [solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	   Solved the limit problem by the following transformations:
5.50/3.25	
5.50/3.25	      Created initial limit problem:
5.50/3.25	
5.50/3.25	      1+k (+), -A*(-1+k)+A-B (+/+!), A (+/+!), C-A (+/+!), k (+/+!), A-B (+/+!) [not solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	      applying transformation rule (C) using substitution {A==1}
5.50/3.25	
5.50/3.25	      resulting limit problem:
5.50/3.25	
5.50/3.25	      2-k-B (+/+!), 1 (+/+!), 1+k (+), 1-B (+/+!), k (+/+!), -1+C (+/+!) [not solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	      applying transformation rule (C) using substitution {A==1+B}
5.50/3.25	
5.50/3.25	      resulting limit problem:
5.50/3.25	
5.50/3.25	      2-k-B (+/+!), 1 (+/+!), 1+k (+), 1-B (+/+!), k (+/+!), -1+C (+/+!) [not solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	      applying transformation rule (C) using substitution {C==1+A}
5.50/3.25	
5.50/3.25	      resulting limit problem:
5.50/3.25	
5.50/3.25	      2-k-B (+/+!), 1 (+/+!), 1+k (+), 1-B (+/+!), A (+/+!), k (+/+!) [not solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	      applying transformation rule (B), deleting 1 (+/+!)
5.50/3.25	
5.50/3.25	      resulting limit problem:
5.50/3.25	
5.50/3.25	      2-k-B (+/+!), 1+k (+), 1-B (+/+!), A (+/+!), k (+/+!) [not solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	      removing all constraints (solved by SMT)
5.50/3.25	
5.50/3.25	      resulting limit problem: [solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	      applying transformation rule (C) using substitution {A==n,k==n,B==-n}
5.50/3.25	
5.50/3.25	      resulting limit problem:
5.50/3.25	
5.50/3.25	      [solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	   Solved the limit problem by the following transformations:
5.50/3.25	
5.50/3.25	      Created initial limit problem:
5.50/3.25	
5.50/3.25	      1+k (+), -A*(-1+k)+A-B (+/+!), A (+/+!), C-A (+/+!), k (+/+!), A-B (+/+!) [not solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	      applying transformation rule (C) using substitution {A==1}
5.50/3.25	
5.50/3.25	      resulting limit problem:
5.50/3.25	
5.50/3.25	      2-k-B (+/+!), 1 (+/+!), 1+k (+), 1-B (+/+!), k (+/+!), -1+C (+/+!) [not solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	      applying transformation rule (C) using substitution {C==1+A}
5.50/3.25	
5.50/3.25	      resulting limit problem:
5.50/3.25	
5.50/3.25	      2-k-B (+/+!), 1 (+/+!), 1+k (+), 1-B (+/+!), A (+/+!), k (+/+!) [not solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	      applying transformation rule (B), deleting 1 (+/+!)
5.50/3.25	
5.50/3.25	      resulting limit problem:
5.50/3.25	
5.50/3.25	      2-k-B (+/+!), 1+k (+), 1-B (+/+!), A (+/+!), k (+/+!) [not solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	      removing all constraints (solved by SMT)
5.50/3.25	
5.50/3.25	      resulting limit problem: [solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	      applying transformation rule (C) using substitution {A==n,k==n,B==-n}
5.50/3.25	
5.50/3.25	      resulting limit problem:
5.50/3.25	
5.50/3.25	      [solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	   Solved the limit problem by the following transformations:
5.50/3.25	
5.50/3.25	      Created initial limit problem:
5.50/3.25	
5.50/3.25	      1+k (+), -A*(-1+k)+A-B (+/+!), A (+/+!), C-A (+/+!), k (+/+!), A-B (+/+!) [not solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	      applying transformation rule (C) using substitution {C==1+A}
5.50/3.25	
5.50/3.25	      resulting limit problem:
5.50/3.25	
5.50/3.25	      1 (+/+!), 1+k (+), -A*(-1+k)+A-B (+/+!), A (+/+!), k (+/+!), A-B (+/+!) [not solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	      applying transformation rule (B), deleting 1 (+/+!)
5.50/3.25	
5.50/3.25	      resulting limit problem:
5.50/3.25	
5.50/3.25	      1+k (+), -A*(-1+k)+A-B (+/+!), A (+/+!), k (+/+!), A-B (+/+!) [not solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	      removing all constraints (solved by SMT)
5.50/3.25	
5.50/3.25	      resulting limit problem: [solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	      applying transformation rule (C) using substitution {A==1,k==n,B==1-n}
5.50/3.25	
5.50/3.25	      resulting limit problem:
5.50/3.25	
5.50/3.25	      [solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	   Solved the limit problem by the following transformations:
5.50/3.25	
5.50/3.25	      Created initial limit problem:
5.50/3.25	
5.50/3.25	      1+k (+), -A*(-1+k)+A-B (+/+!), A (+/+!), C-A (+/+!), k (+/+!), A-B (+/+!) [not solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	      applying transformation rule (C) using substitution {A==1}
5.50/3.25	
5.50/3.25	      resulting limit problem:
5.50/3.25	
5.50/3.25	      2-k-B (+/+!), 1 (+/+!), 1+k (+), 1-B (+/+!), k (+/+!), -1+C (+/+!) [not solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	      applying transformation rule (C) using substitution {A==1+B}
5.50/3.25	
5.50/3.25	      resulting limit problem:
5.50/3.25	
5.50/3.25	      2-k-B (+/+!), 1 (+/+!), 1+k (+), 1-B (+/+!), k (+/+!), -1+C (+/+!) [not solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	      applying transformation rule (B), deleting 1 (+/+!)
5.50/3.25	
5.50/3.25	      resulting limit problem:
5.50/3.25	
5.50/3.25	      2-k-B (+/+!), 1+k (+), 1-B (+/+!), k (+/+!), -1+C (+/+!) [not solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	      removing all constraints (solved by SMT)
5.50/3.25	
5.50/3.25	      resulting limit problem: [solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	      applying transformation rule (C) using substitution {C==n,k==n,B==-n}
5.50/3.25	
5.50/3.25	      resulting limit problem:
5.50/3.25	
5.50/3.25	      [solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	   Solved the limit problem by the following transformations:
5.50/3.25	
5.50/3.25	      Created initial limit problem:
5.50/3.25	
5.50/3.25	      1+k (+), -A*(-1+k)+A-B (+/+!), A (+/+!), C-A (+/+!), k (+/+!), A-B (+/+!) [not solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	      applying transformation rule (C) using substitution {A==1}
5.50/3.25	
5.50/3.25	      resulting limit problem:
5.50/3.25	
5.50/3.25	      2-k-B (+/+!), 1 (+/+!), 1+k (+), 1-B (+/+!), k (+/+!), -1+C (+/+!) [not solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	      applying transformation rule (B), deleting 1 (+/+!)
5.50/3.25	
5.50/3.25	      resulting limit problem:
5.50/3.25	
5.50/3.25	      2-k-B (+/+!), 1+k (+), 1-B (+/+!), k (+/+!), -1+C (+/+!) [not solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	      removing all constraints (solved by SMT)
5.50/3.25	
5.50/3.25	      resulting limit problem: [solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	      applying transformation rule (C) using substitution {C==n,k==n,B==-n}
5.50/3.25	
5.50/3.25	      resulting limit problem:
5.50/3.25	
5.50/3.25	      [solved]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	   Solution:
5.50/3.25	
5.50/3.25	      C / n
5.50/3.25	
5.50/3.25	      A / 1
5.50/3.25	
5.50/3.25	      k / 1+n
5.50/3.25	
5.50/3.25	      B / -n
5.50/3.25	
5.50/3.25	   Resulting cost 2+n has complexity: Poly(n^1)
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	Found new complexity Poly(n^1).
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	Obtained the following overall complexity (w.r.t. the length of the input n):
5.50/3.25	
5.50/3.25	   Complexity:  Poly(n^1)
5.50/3.25	
5.50/3.25	   Cpx degree:  1
5.50/3.25	
5.50/3.25	   Solved cost: 2+n
5.50/3.25	
5.50/3.25	   Rule cost:   1+k
5.50/3.25	
5.50/3.25	   Rule guard:  [ A>=1 && A>=1+B && C>=1+A && k>0 && A>=1+A*(-1+k)+B ]
5.50/3.25	
5.50/3.25	
5.50/3.25	
5.50/3.25	WORST_CASE(Omega(n^1),?)
5.50/3.25	
5.50/3.25	
5.50/3.25	----------------------------------------
5.50/3.25	
5.50/3.25	(4)
5.50/3.25	BOUNDS(n^1, INF)
5.60/3.28	EOF