5.45/2.29	WORST_CASE(NON_POLY, ?)
5.45/2.29	proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat
5.45/2.29	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
5.45/2.29	
5.45/2.29	
5.45/2.29	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF).
5.45/2.29	
5.45/2.29	(0) CpxIntTrs
5.45/2.29	(1) Loat Proof [FINISHED, 628 ms]
5.45/2.29	(2) BOUNDS(INF, INF)
5.45/2.29	
5.45/2.29	
5.45/2.29	----------------------------------------
5.45/2.29	
5.45/2.29	(0)
5.45/2.29	Obligation:
5.45/2.29	Complexity Int TRS consisting of the following rules:
5.45/2.29	evalcousot9start(A, B, C) -> Com_1(evalcousot9entryin(A, B, C)) :|: TRUE
5.45/2.29	evalcousot9entryin(A, B, C) -> Com_1(evalcousot9bb3in(D, C, C)) :|: TRUE
5.45/2.29	evalcousot9bb3in(A, B, C) -> Com_1(evalcousot9bbin(A, B, C)) :|: B >= 1
5.45/2.29	evalcousot9bb3in(A, B, C) -> Com_1(evalcousot9returnin(A, B, C)) :|: 0 >= B
5.45/2.29	evalcousot9bbin(A, B, C) -> Com_1(evalcousot9bb1in(A, B, C)) :|: A >= 1
5.45/2.29	evalcousot9bbin(A, B, C) -> Com_1(evalcousot9bb2in(A, B, C)) :|: 0 >= A
5.45/2.29	evalcousot9bb1in(A, B, C) -> Com_1(evalcousot9bb3in(A - 1, B, C)) :|: TRUE
5.45/2.29	evalcousot9bb2in(A, B, C) -> Com_1(evalcousot9bb3in(C, B - 1, C)) :|: TRUE
5.45/2.29	evalcousot9returnin(A, B, C) -> Com_1(evalcousot9stop(A, B, C)) :|: TRUE
5.45/2.29	
5.45/2.29	The start-symbols are:[evalcousot9start_3]
5.45/2.29	
5.45/2.29	
5.45/2.29	----------------------------------------
5.45/2.29	
5.45/2.29	(1) Loat Proof (FINISHED)
5.45/2.29	
5.45/2.29	
5.45/2.29	### Pre-processing the ITS problem ###
5.45/2.29	
5.45/2.29	
5.45/2.29	
5.45/2.29	Initial linear ITS problem
5.45/2.29	
5.45/2.29	   Start location: evalcousot9start
5.45/2.29	
5.45/2.29	      0: evalcousot9start -> evalcousot9entryin : [], cost: 1
5.45/2.29	
5.45/2.29	      1: evalcousot9entryin -> evalcousot9bb3in : A'=free, B'=C, [], cost: 1
5.45/2.29	
5.45/2.29	      2: evalcousot9bb3in -> evalcousot9bbin : [ B>=1 ], cost: 1
5.45/2.29	
5.45/2.29	      3: evalcousot9bb3in -> evalcousot9returnin : [ 0>=B ], cost: 1
5.45/2.29	
5.45/2.29	      4: evalcousot9bbin -> evalcousot9bb1in : [ A>=1 ], cost: 1
5.45/2.29	
5.45/2.29	      5: evalcousot9bbin -> evalcousot9bb2in : [ 0>=A ], cost: 1
5.45/2.29	
5.45/2.29	      6: evalcousot9bb1in -> evalcousot9bb3in : A'=-1+A, [], cost: 1
5.45/2.29	
5.45/2.29	      7: evalcousot9bb2in -> evalcousot9bb3in : A'=C, B'=-1+B, [], cost: 1
5.45/2.29	
5.45/2.29	      8: evalcousot9returnin -> evalcousot9stop : [], cost: 1
5.45/2.29	
5.45/2.29	
5.45/2.29	
5.45/2.29	Removed unreachable and leaf rules:
5.45/2.29	
5.45/2.29	   Start location: evalcousot9start
5.45/2.29	
5.45/2.29	      0: evalcousot9start -> evalcousot9entryin : [], cost: 1
5.45/2.29	
5.45/2.29	      1: evalcousot9entryin -> evalcousot9bb3in : A'=free, B'=C, [], cost: 1
5.45/2.29	
5.45/2.29	      2: evalcousot9bb3in -> evalcousot9bbin : [ B>=1 ], cost: 1
5.45/2.29	
5.45/2.29	      4: evalcousot9bbin -> evalcousot9bb1in : [ A>=1 ], cost: 1
5.45/2.29	
5.45/2.29	      5: evalcousot9bbin -> evalcousot9bb2in : [ 0>=A ], cost: 1
5.45/2.29	
5.45/2.29	      6: evalcousot9bb1in -> evalcousot9bb3in : A'=-1+A, [], cost: 1
5.45/2.29	
5.45/2.29	      7: evalcousot9bb2in -> evalcousot9bb3in : A'=C, B'=-1+B, [], cost: 1
5.45/2.29	
5.45/2.29	
5.45/2.29	
5.45/2.29	### Simplification by acceleration and chaining ###
5.45/2.29	
5.45/2.29	
5.45/2.29	
5.45/2.29	Eliminated locations (on linear paths):
5.45/2.29	
5.45/2.29	   Start location: evalcousot9start
5.45/2.29	
5.45/2.29	      9: evalcousot9start -> evalcousot9bb3in : A'=free, B'=C, [], cost: 2
5.45/2.29	
5.45/2.29	      2: evalcousot9bb3in -> evalcousot9bbin : [ B>=1 ], cost: 1
5.45/2.29	
5.45/2.29	     10: evalcousot9bbin -> evalcousot9bb3in : A'=-1+A, [ A>=1 ], cost: 2
5.45/2.29	
5.45/2.29	     11: evalcousot9bbin -> evalcousot9bb3in : A'=C, B'=-1+B, [ 0>=A ], cost: 2
5.45/2.29	
5.45/2.29	
5.45/2.29	
5.45/2.29	Eliminated locations (on tree-shaped paths):
5.45/2.29	
5.45/2.29	   Start location: evalcousot9start
5.45/2.29	
5.45/2.29	      9: evalcousot9start -> evalcousot9bb3in : A'=free, B'=C, [], cost: 2
5.45/2.29	
5.45/2.29	     12: evalcousot9bb3in -> evalcousot9bb3in : A'=-1+A, [ B>=1 && A>=1 ], cost: 3
5.45/2.29	
5.45/2.29	     13: evalcousot9bb3in -> evalcousot9bb3in : A'=C, B'=-1+B, [ B>=1 && 0>=A ], cost: 3
5.45/2.29	
5.45/2.29	
5.45/2.29	
5.45/2.29	Accelerating simple loops of location 2.
5.45/2.29	
5.45/2.29	   Accelerating the following rules:
5.45/2.29	
5.45/2.29	     12: evalcousot9bb3in -> evalcousot9bb3in : A'=-1+A, [ B>=1 && A>=1 ], cost: 3
5.45/2.29	
5.45/2.29	     13: evalcousot9bb3in -> evalcousot9bb3in : A'=C, B'=-1+B, [ B>=1 && 0>=A ], cost: 3
5.45/2.29	
5.45/2.29	
5.45/2.29	
5.45/2.29	   Accelerated rule 12 with metering function A, yielding the new rule 14.
5.45/2.29	
5.45/2.29	   Accelerated rule 13 with metering function B (after strengthening guard), yielding the new rule 15.
5.45/2.29	
5.45/2.29	   Nested simple loops 13 (outer loop) and 14 (inner loop) with metering function -1+B, resulting in the new rules: 16, 17.
5.45/2.29	
5.45/2.29	   Removing the simple loops: 12 13.
5.45/2.29	
5.45/2.29	
5.45/2.29	
5.45/2.29	Accelerated all simple loops using metering functions (where possible):
5.45/2.29	
5.45/2.29	   Start location: evalcousot9start
5.45/2.29	
5.45/2.29	      9: evalcousot9start -> evalcousot9bb3in : A'=free, B'=C, [], cost: 2
5.45/2.29	
5.45/2.29	     14: evalcousot9bb3in -> evalcousot9bb3in : A'=0, [ B>=1 && A>=1 ], cost: 3*A
5.45/2.29	
5.45/2.29	     15: evalcousot9bb3in -> evalcousot9bb3in : A'=C, B'=0, [ B>=1 && 0>=A && 0>=C ], cost: 3*B
5.45/2.29	
5.45/2.29	     16: evalcousot9bb3in -> evalcousot9bb3in : A'=0, B'=1, [ 0>=A && -1+B>=1 && C>=1 ], cost: -3+3*C*(-1+B)+3*B
5.45/2.29	
5.45/2.29	     17: evalcousot9bb3in -> evalcousot9bb3in : A'=0, B'=1, [ A>=1 && -1+B>=1 && C>=1 ], cost: -3+3*C*(-1+B)+3*A+3*B
5.45/2.29	
5.45/2.29	
5.45/2.29	
5.45/2.29	Chained accelerated rules (with incoming rules):
5.45/2.29	
5.45/2.29	   Start location: evalcousot9start
5.45/2.29	
5.45/2.29	      9: evalcousot9start -> evalcousot9bb3in : A'=free, B'=C, [], cost: 2
5.45/2.29	
5.45/2.29	     18: evalcousot9start -> evalcousot9bb3in : A'=0, B'=C, [ C>=1 && free>=1 ], cost: 2+3*free
5.45/2.29	
5.45/2.29	     19: evalcousot9start -> evalcousot9bb3in : A'=0, B'=1, [ -1+C>=1 ], cost: -1+3*C+3*C*(-1+C)
5.45/2.29	
5.45/2.29	     20: evalcousot9start -> evalcousot9bb3in : A'=0, B'=1, [ free>=1 && -1+C>=1 ], cost: -1+3*C+3*C*(-1+C)+3*free
5.45/2.29	
5.45/2.29	
5.45/2.29	
5.45/2.29	Removed unreachable locations (and leaf rules with constant cost):
5.45/2.29	
5.45/2.29	   Start location: evalcousot9start
5.45/2.29	
5.45/2.29	     18: evalcousot9start -> evalcousot9bb3in : A'=0, B'=C, [ C>=1 && free>=1 ], cost: 2+3*free
5.45/2.29	
5.45/2.29	     19: evalcousot9start -> evalcousot9bb3in : A'=0, B'=1, [ -1+C>=1 ], cost: -1+3*C+3*C*(-1+C)
5.45/2.29	
5.45/2.29	     20: evalcousot9start -> evalcousot9bb3in : A'=0, B'=1, [ free>=1 && -1+C>=1 ], cost: -1+3*C+3*C*(-1+C)+3*free
5.45/2.29	
5.45/2.29	
5.45/2.29	
5.45/2.29	### Computing asymptotic complexity ###
5.45/2.29	
5.45/2.29	
5.45/2.29	
5.45/2.29	Fully simplified ITS problem
5.45/2.29	
5.45/2.29	   Start location: evalcousot9start
5.45/2.29	
5.45/2.29	     18: evalcousot9start -> evalcousot9bb3in : A'=0, B'=C, [ C>=1 && free>=1 ], cost: 2+3*free
5.45/2.29	
5.45/2.29	     19: evalcousot9start -> evalcousot9bb3in : A'=0, B'=1, [ -1+C>=1 ], cost: -1+3*C+3*C*(-1+C)
5.45/2.29	
5.45/2.29	     20: evalcousot9start -> evalcousot9bb3in : A'=0, B'=1, [ free>=1 && -1+C>=1 ], cost: -1+3*C+3*C*(-1+C)+3*free
5.45/2.29	
5.45/2.29	
5.45/2.29	
5.45/2.29	Computing asymptotic complexity for rule 18
5.45/2.29	
5.45/2.29	   Solved the limit problem by the following transformations:
5.45/2.29	
5.45/2.29	      Created initial limit problem:
5.45/2.29	
5.45/2.29	      C (+/+!), 2+3*free (+), free (+/+!) [not solved]
5.45/2.29	
5.45/2.29	
5.45/2.29	
5.45/2.29	      removing all constraints (solved by SMT)
5.45/2.29	
5.45/2.29	      resulting limit problem: [solved]
5.45/2.29	
5.45/2.29	
5.45/2.29	
5.45/2.29	      applying transformation rule (C) using substitution {C==1,free==n}
5.45/2.29	
5.45/2.29	      resulting limit problem:
5.45/2.29	
5.45/2.29	      [solved]
5.45/2.29	
5.45/2.29	
5.45/2.29	
5.45/2.29	   Solution:
5.45/2.29	
5.45/2.29	      C / 1
5.45/2.29	
5.45/2.29	      free / n
5.45/2.29	
5.45/2.29	   Resulting cost 2+3*n has complexity: Unbounded
5.45/2.29	
5.45/2.29	
5.45/2.29	
5.45/2.29	Found new complexity Unbounded.
5.45/2.29	
5.45/2.29	
5.45/2.29	
5.45/2.29	Obtained the following overall complexity (w.r.t. the length of the input n):
5.45/2.29	
5.45/2.29	   Complexity:  Unbounded
5.45/2.29	
5.45/2.29	   Cpx degree:  Unbounded
5.45/2.29	
5.45/2.29	   Solved cost: 2+3*n
5.45/2.29	
5.45/2.29	   Rule cost:   2+3*free
5.45/2.29	
5.45/2.29	   Rule guard:  [ C>=1 && free>=1 ]
5.45/2.29	
5.45/2.29	
5.45/2.29	
5.45/2.29	WORST_CASE(INF,?)
5.45/2.29	
5.45/2.29	
5.45/2.29	----------------------------------------
5.45/2.29	
5.45/2.29	(2)
5.45/2.29	BOUNDS(INF, INF)
5.45/2.31	EOF