4.91/2.23	WORST_CASE(NON_POLY, ?)
4.91/2.23	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
4.91/2.23	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.91/2.23	
4.91/2.23	
4.91/2.23	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF).
4.91/2.23	
4.91/2.23	(0) CpxIntTrs
4.91/2.23	(1) Loat Proof [FINISHED, 421 ms]
4.91/2.23	(2) BOUNDS(INF, INF)
4.91/2.23	
4.91/2.23	
4.91/2.23	----------------------------------------
4.91/2.23	
4.91/2.23	(0)
4.91/2.23	Obligation:
4.91/2.23	Complexity Int TRS consisting of the following rules:
4.91/2.23	eval_speedFails2_start(v_i_0, v_n, v_x) -> Com_1(eval_speedFails2_bb0_in(v_i_0, v_n, v_x)) :|: TRUE
4.91/2.23	eval_speedFails2_bb0_in(v_i_0, v_n, v_x) -> Com_1(eval_speedFails2_0(v_i_0, v_n, v_x)) :|: TRUE
4.91/2.23	eval_speedFails2_0(v_i_0, v_n, v_x) -> Com_1(eval_speedFails2_1(v_i_0, v_n, v_x)) :|: TRUE
4.91/2.23	eval_speedFails2_1(v_i_0, v_n, v_x) -> Com_1(eval_speedFails2_2(v_i_0, v_n, v_x)) :|: TRUE
4.91/2.23	eval_speedFails2_2(v_i_0, v_n, v_x) -> Com_1(eval_speedFails2_3(v_i_0, v_n, v_x)) :|: TRUE
4.91/2.23	eval_speedFails2_3(v_i_0, v_n, v_x) -> Com_1(eval_speedFails2_4(v_i_0, v_n, v_x)) :|: TRUE
4.91/2.23	eval_speedFails2_4(v_i_0, v_n, v_x) -> Com_1(eval_speedFails2_bb1_in(v_x, v_n, v_x)) :|: TRUE
4.91/2.23	eval_speedFails2_bb1_in(v_i_0, v_n, v_x) -> Com_1(eval_speedFails2_bb2_in(v_i_0, v_n, v_x)) :|: v_i_0 < v_n
4.91/2.23	eval_speedFails2_bb1_in(v_i_0, v_n, v_x) -> Com_1(eval_speedFails2_bb2_in(v_i_0, v_n, v_x)) :|: v_i_0 > v_n
4.91/2.23	eval_speedFails2_bb1_in(v_i_0, v_n, v_x) -> Com_1(eval_speedFails2_bb3_in(v_i_0, v_n, v_x)) :|: v_i_0 >= v_n && v_i_0 <= v_n
4.91/2.23	eval_speedFails2_bb2_in(v_i_0, v_n, v_x) -> Com_1(eval_speedFails2_bb1_in(v_i_0 + 1, v_n, v_x)) :|: TRUE
4.91/2.23	eval_speedFails2_bb3_in(v_i_0, v_n, v_x) -> Com_1(eval_speedFails2_stop(v_i_0, v_n, v_x)) :|: TRUE
4.91/2.23	
4.91/2.23	The start-symbols are:[eval_speedFails2_start_3]
4.91/2.23	
4.91/2.23	
4.91/2.23	----------------------------------------
4.91/2.23	
4.91/2.23	(1) Loat Proof (FINISHED)
4.91/2.23	
4.91/2.23	
4.91/2.23	### Pre-processing the ITS problem ###
4.91/2.23	
4.91/2.23	
4.91/2.23	
4.91/2.23	Initial linear ITS problem
4.91/2.23	
4.91/2.23	   Start location: evalspeedFails2start
4.91/2.23	
4.91/2.23	      0: evalspeedFails2start -> evalspeedFails2bb0in : [], cost: 1
4.91/2.23	
4.91/2.23	      1: evalspeedFails2bb0in -> evalspeedFails20 : [], cost: 1
4.91/2.23	
4.91/2.23	      2: evalspeedFails20 -> evalspeedFails21 : [], cost: 1
4.91/2.23	
4.91/2.23	      3: evalspeedFails21 -> evalspeedFails22 : [], cost: 1
4.91/2.23	
4.91/2.23	      4: evalspeedFails22 -> evalspeedFails23 : [], cost: 1
4.91/2.23	
4.91/2.23	      5: evalspeedFails23 -> evalspeedFails24 : [], cost: 1
4.91/2.23	
4.91/2.23	      6: evalspeedFails24 -> evalspeedFails2bb1in : A'=B, [], cost: 1
4.91/2.23	
4.91/2.23	      7: evalspeedFails2bb1in -> evalspeedFails2bb2in : [ C>=1+A ], cost: 1
4.91/2.23	
4.91/2.23	      8: evalspeedFails2bb1in -> evalspeedFails2bb2in : [ A>=1+C ], cost: 1
4.91/2.23	
4.91/2.23	      9: evalspeedFails2bb1in -> evalspeedFails2bb3in : [ A==C ], cost: 1
4.91/2.23	
4.91/2.23	     10: evalspeedFails2bb2in -> evalspeedFails2bb1in : A'=1+A, [], cost: 1
4.91/2.23	
4.91/2.23	     11: evalspeedFails2bb3in -> evalspeedFails2stop : [], cost: 1
4.91/2.23	
4.91/2.23	
4.91/2.23	
4.91/2.23	Removed unreachable and leaf rules:
4.91/2.23	
4.91/2.23	   Start location: evalspeedFails2start
4.91/2.23	
4.91/2.23	      0: evalspeedFails2start -> evalspeedFails2bb0in : [], cost: 1
4.91/2.23	
4.91/2.23	      1: evalspeedFails2bb0in -> evalspeedFails20 : [], cost: 1
4.91/2.23	
4.91/2.23	      2: evalspeedFails20 -> evalspeedFails21 : [], cost: 1
4.91/2.23	
4.91/2.23	      3: evalspeedFails21 -> evalspeedFails22 : [], cost: 1
4.91/2.23	
4.91/2.23	      4: evalspeedFails22 -> evalspeedFails23 : [], cost: 1
4.91/2.23	
4.91/2.23	      5: evalspeedFails23 -> evalspeedFails24 : [], cost: 1
4.91/2.23	
4.91/2.23	      6: evalspeedFails24 -> evalspeedFails2bb1in : A'=B, [], cost: 1
4.91/2.23	
4.91/2.23	      7: evalspeedFails2bb1in -> evalspeedFails2bb2in : [ C>=1+A ], cost: 1
4.91/2.23	
4.91/2.23	      8: evalspeedFails2bb1in -> evalspeedFails2bb2in : [ A>=1+C ], cost: 1
4.91/2.23	
4.91/2.23	     10: evalspeedFails2bb2in -> evalspeedFails2bb1in : A'=1+A, [], cost: 1
4.91/2.23	
4.91/2.23	
4.91/2.23	
4.91/2.23	### Simplification by acceleration and chaining ###
4.91/2.23	
4.91/2.23	
4.91/2.23	
4.91/2.23	Eliminated locations (on linear paths):
4.91/2.23	
4.91/2.23	   Start location: evalspeedFails2start
4.91/2.23	
4.91/2.23	     17: evalspeedFails2start -> evalspeedFails2bb1in : A'=B, [], cost: 7
4.91/2.23	
4.91/2.23	      7: evalspeedFails2bb1in -> evalspeedFails2bb2in : [ C>=1+A ], cost: 1
4.91/2.23	
4.91/2.23	      8: evalspeedFails2bb1in -> evalspeedFails2bb2in : [ A>=1+C ], cost: 1
4.91/2.23	
4.91/2.23	     10: evalspeedFails2bb2in -> evalspeedFails2bb1in : A'=1+A, [], cost: 1
4.91/2.23	
4.91/2.23	
4.91/2.23	
4.91/2.23	Eliminated locations (on tree-shaped paths):
4.91/2.23	
4.91/2.23	   Start location: evalspeedFails2start
4.91/2.23	
4.91/2.23	     17: evalspeedFails2start -> evalspeedFails2bb1in : A'=B, [], cost: 7
4.91/2.23	
4.91/2.23	     18: evalspeedFails2bb1in -> evalspeedFails2bb1in : A'=1+A, [ C>=1+A ], cost: 2
4.91/2.23	
4.91/2.23	     19: evalspeedFails2bb1in -> evalspeedFails2bb1in : A'=1+A, [ A>=1+C ], cost: 2
4.91/2.23	
4.91/2.23	
4.91/2.23	
4.91/2.23	Accelerating simple loops of location 7.
4.91/2.23	
4.91/2.23	   Accelerating the following rules:
4.91/2.23	
4.91/2.23	     18: evalspeedFails2bb1in -> evalspeedFails2bb1in : A'=1+A, [ C>=1+A ], cost: 2
4.91/2.23	
4.91/2.23	     19: evalspeedFails2bb1in -> evalspeedFails2bb1in : A'=1+A, [ A>=1+C ], cost: 2
4.91/2.23	
4.91/2.23	
4.91/2.23	
4.91/2.23	   Accelerated rule 18 with metering function C-A, yielding the new rule 20.
4.91/2.23	
4.91/2.23	   Accelerated rule 19 with NONTERM, yielding the new rule 21.
4.91/2.23	
4.91/2.23	   Removing the simple loops: 18 19.
4.91/2.23	
4.91/2.23	
4.91/2.23	
4.91/2.23	Accelerated all simple loops using metering functions (where possible):
4.91/2.23	
4.91/2.23	   Start location: evalspeedFails2start
4.91/2.23	
4.91/2.23	     17: evalspeedFails2start -> evalspeedFails2bb1in : A'=B, [], cost: 7
4.91/2.23	
4.91/2.23	     20: evalspeedFails2bb1in -> evalspeedFails2bb1in : A'=C, [ C>=1+A ], cost: 2*C-2*A
4.91/2.23	
4.91/2.23	     21: evalspeedFails2bb1in -> [11] : [ A>=1+C ], cost: INF
4.91/2.23	
4.91/2.23	
4.91/2.23	
4.91/2.23	Chained accelerated rules (with incoming rules):
4.91/2.23	
4.91/2.23	   Start location: evalspeedFails2start
4.91/2.23	
4.91/2.23	     17: evalspeedFails2start -> evalspeedFails2bb1in : A'=B, [], cost: 7
4.91/2.23	
4.91/2.23	     22: evalspeedFails2start -> evalspeedFails2bb1in : A'=C, [ C>=1+B ], cost: 7+2*C-2*B
4.91/2.23	
4.91/2.23	     23: evalspeedFails2start -> [11] : A'=B, [ B>=1+C ], cost: INF
4.91/2.23	
4.91/2.23	
4.91/2.23	
4.91/2.23	Removed unreachable locations (and leaf rules with constant cost):
4.91/2.23	
4.91/2.23	   Start location: evalspeedFails2start
4.91/2.23	
4.91/2.23	     22: evalspeedFails2start -> evalspeedFails2bb1in : A'=C, [ C>=1+B ], cost: 7+2*C-2*B
4.91/2.23	
4.91/2.23	     23: evalspeedFails2start -> [11] : A'=B, [ B>=1+C ], cost: INF
4.91/2.23	
4.91/2.23	
4.91/2.23	
4.91/2.23	### Computing asymptotic complexity ###
4.91/2.23	
4.91/2.23	
4.91/2.23	
4.91/2.23	Fully simplified ITS problem
4.91/2.23	
4.91/2.23	   Start location: evalspeedFails2start
4.91/2.23	
4.91/2.23	     22: evalspeedFails2start -> evalspeedFails2bb1in : A'=C, [ C>=1+B ], cost: 7+2*C-2*B
4.91/2.23	
4.91/2.23	     23: evalspeedFails2start -> [11] : A'=B, [ B>=1+C ], cost: INF
4.91/2.23	
4.91/2.23	
4.91/2.23	
4.91/2.23	Computing asymptotic complexity for rule 22
4.91/2.23	
4.91/2.23	   Solved the limit problem by the following transformations:
4.91/2.23	
4.91/2.23	      Created initial limit problem:
4.91/2.23	
4.91/2.23	      C-B (+/+!), 7+2*C-2*B (+) [not solved]
4.91/2.23	
4.91/2.23	
4.91/2.23	
4.91/2.23	      removing all constraints (solved by SMT)
4.91/2.23	
4.91/2.23	      resulting limit problem: [solved]
4.91/2.23	
4.91/2.23	
4.91/2.23	
4.91/2.23	      applying transformation rule (C) using substitution {C==0,B==-n}
4.91/2.23	
4.91/2.23	      resulting limit problem:
4.91/2.23	
4.91/2.23	      [solved]
4.91/2.23	
4.91/2.23	
4.91/2.23	
4.91/2.23	   Solution:
4.91/2.23	
4.91/2.23	      C / 0
4.91/2.23	
4.91/2.23	      B / -n
4.91/2.23	
4.91/2.23	   Resulting cost 7+2*n has complexity: Poly(n^1)
4.91/2.23	
4.91/2.23	
4.91/2.23	
4.91/2.23	Found new complexity Poly(n^1).
4.91/2.23	
4.91/2.23	
4.91/2.23	
4.91/2.23	Computing asymptotic complexity for rule 23
4.91/2.23	
4.91/2.23	   Resulting cost INF has complexity: Nonterm
4.91/2.23	
4.91/2.23	
4.91/2.23	
4.91/2.23	Found new complexity Nonterm.
4.91/2.23	
4.91/2.23	
4.91/2.23	
4.91/2.23	Obtained the following overall complexity (w.r.t. the length of the input n):
4.91/2.23	
4.91/2.23	   Complexity:  Nonterm
4.91/2.23	
4.91/2.23	   Cpx degree:  Nonterm
4.91/2.23	
4.91/2.23	   Solved cost: INF
4.91/2.23	
4.91/2.23	   Rule cost:   INF
4.91/2.23	
4.91/2.23	   Rule guard:  [ B>=1+C ]
4.91/2.23	
4.91/2.23	
4.91/2.23	
4.91/2.23	NO
4.91/2.23	
4.91/2.23	
4.91/2.23	----------------------------------------
4.91/2.23	
4.91/2.23	(2)
4.91/2.23	BOUNDS(INF, INF)
4.91/2.26	EOF