6.50/3.05	WORST_CASE(Omega(n^1), ?)
6.50/3.06	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
6.50/3.06	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
6.50/3.06	
6.50/3.06	
6.50/3.06	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, INF).
6.50/3.06	
6.50/3.06	(0) CpxIntTrs
6.50/3.06	(1) Loat Proof [FINISHED, 1339 ms]
6.50/3.06	(2) BOUNDS(n^1, INF)
6.50/3.06	
6.50/3.06	
6.50/3.06	----------------------------------------
6.50/3.06	
6.50/3.06	(0)
6.50/3.06	Obligation:
6.50/3.06	Complexity Int TRS consisting of the following rules:
6.50/3.06	evalcyclicstart(A, B, C) -> Com_1(evalcyclicentryin(A, B, C)) :|: TRUE
6.50/3.06	evalcyclicentryin(A, B, C) -> Com_1(evalcyclicbb3in(A, B, A + 1)) :|: A >= 0 && B >= A + 1
6.50/3.06	evalcyclicbb3in(A, B, C) -> Com_1(evalcyclicreturnin(A, B, C)) :|: C >= A && C <= A
6.50/3.06	evalcyclicbb3in(A, B, C) -> Com_1(evalcyclicbb4in(A, B, C)) :|: A >= C + 1
6.50/3.06	evalcyclicbb3in(A, B, C) -> Com_1(evalcyclicbb4in(A, B, C)) :|: C >= A + 1
6.50/3.06	evalcyclicbb4in(A, B, C) -> Com_1(evalcyclicbbin(A, B, C)) :|: 0 >= D + 1
6.50/3.06	evalcyclicbb4in(A, B, C) -> Com_1(evalcyclicbbin(A, B, C)) :|: D >= 1
6.50/3.06	evalcyclicbb4in(A, B, C) -> Com_1(evalcyclicreturnin(A, B, C)) :|: TRUE
6.50/3.06	evalcyclicbbin(A, B, C) -> Com_1(evalcyclicbb3in(A, B, C + 1)) :|: B >= C
6.50/3.06	evalcyclicbbin(A, B, C) -> Com_1(evalcyclicbb3in(A, B, 0)) :|: C >= B + 1
6.50/3.06	evalcyclicreturnin(A, B, C) -> Com_1(evalcyclicstop(A, B, C)) :|: TRUE
6.50/3.06	
6.50/3.06	The start-symbols are:[evalcyclicstart_3]
6.50/3.06	
6.50/3.06	
6.50/3.06	----------------------------------------
6.50/3.06	
6.50/3.06	(1) Loat Proof (FINISHED)
6.50/3.06	
6.50/3.06	
6.50/3.06	### Pre-processing the ITS problem ###
6.50/3.06	
6.50/3.06	
6.50/3.06	
6.50/3.06	Initial linear ITS problem
6.50/3.06	
6.50/3.06	   Start location: evalcyclicstart
6.50/3.06	
6.50/3.06	      0: evalcyclicstart -> evalcyclicentryin : [], cost: 1
6.50/3.06	
6.50/3.06	      1: evalcyclicentryin -> evalcyclicbb3in : C'=1+A, [ A>=0 && B>=1+A ], cost: 1
6.50/3.06	
6.50/3.06	      2: evalcyclicbb3in -> evalcyclicreturnin : [ C==A ], cost: 1
6.50/3.06	
6.50/3.06	      3: evalcyclicbb3in -> evalcyclicbb4in : [ A>=1+C ], cost: 1
6.50/3.06	
6.50/3.06	      4: evalcyclicbb3in -> evalcyclicbb4in : [ C>=1+A ], cost: 1
6.50/3.06	
6.50/3.06	      5: evalcyclicbb4in -> evalcyclicbbin : [ 0>=1+free ], cost: 1
6.50/3.06	
6.50/3.06	      6: evalcyclicbb4in -> evalcyclicbbin : [ free_1>=1 ], cost: 1
6.50/3.06	
6.50/3.06	      7: evalcyclicbb4in -> evalcyclicreturnin : [], cost: 1
6.50/3.06	
6.50/3.06	      8: evalcyclicbbin -> evalcyclicbb3in : C'=1+C, [ B>=C ], cost: 1
6.50/3.06	
6.50/3.06	      9: evalcyclicbbin -> evalcyclicbb3in : C'=0, [ C>=1+B ], cost: 1
6.50/3.06	
6.50/3.06	     10: evalcyclicreturnin -> evalcyclicstop : [], cost: 1
6.50/3.06	
6.50/3.06	
6.50/3.06	
6.50/3.06	Removed unreachable and leaf rules:
6.50/3.06	
6.50/3.06	   Start location: evalcyclicstart
6.50/3.06	
6.50/3.06	      0: evalcyclicstart -> evalcyclicentryin : [], cost: 1
6.50/3.06	
6.50/3.06	      1: evalcyclicentryin -> evalcyclicbb3in : C'=1+A, [ A>=0 && B>=1+A ], cost: 1
6.50/3.06	
6.50/3.06	      3: evalcyclicbb3in -> evalcyclicbb4in : [ A>=1+C ], cost: 1
6.50/3.06	
6.50/3.06	      4: evalcyclicbb3in -> evalcyclicbb4in : [ C>=1+A ], cost: 1
6.50/3.06	
6.50/3.06	      5: evalcyclicbb4in -> evalcyclicbbin : [ 0>=1+free ], cost: 1
6.50/3.06	
6.50/3.06	      6: evalcyclicbb4in -> evalcyclicbbin : [ free_1>=1 ], cost: 1
6.50/3.06	
6.50/3.06	      8: evalcyclicbbin -> evalcyclicbb3in : C'=1+C, [ B>=C ], cost: 1
6.50/3.06	
6.50/3.06	      9: evalcyclicbbin -> evalcyclicbb3in : C'=0, [ C>=1+B ], cost: 1
6.50/3.06	
6.50/3.06	
6.50/3.06	
6.50/3.06	Simplified all rules, resulting in:
6.50/3.06	
6.50/3.06	   Start location: evalcyclicstart
6.50/3.06	
6.50/3.06	      0: evalcyclicstart -> evalcyclicentryin : [], cost: 1
6.50/3.06	
6.50/3.06	      1: evalcyclicentryin -> evalcyclicbb3in : C'=1+A, [ A>=0 && B>=1+A ], cost: 1
6.50/3.06	
6.50/3.06	      3: evalcyclicbb3in -> evalcyclicbb4in : [ A>=1+C ], cost: 1
6.50/3.06	
6.50/3.06	      4: evalcyclicbb3in -> evalcyclicbb4in : [ C>=1+A ], cost: 1
6.50/3.06	
6.50/3.06	      6: evalcyclicbb4in -> evalcyclicbbin : [], cost: 1
6.50/3.06	
6.50/3.06	      8: evalcyclicbbin -> evalcyclicbb3in : C'=1+C, [ B>=C ], cost: 1
6.50/3.06	
6.50/3.06	      9: evalcyclicbbin -> evalcyclicbb3in : C'=0, [ C>=1+B ], cost: 1
6.50/3.06	
6.50/3.06	
6.50/3.06	
6.50/3.06	### Simplification by acceleration and chaining ###
6.50/3.06	
6.50/3.06	
6.50/3.06	
6.50/3.06	Eliminated locations (on linear paths):
6.50/3.06	
6.50/3.06	   Start location: evalcyclicstart
6.50/3.06	
6.50/3.06	     11: evalcyclicstart -> evalcyclicbb3in : C'=1+A, [ A>=0 && B>=1+A ], cost: 2
6.50/3.06	
6.50/3.06	      3: evalcyclicbb3in -> evalcyclicbb4in : [ A>=1+C ], cost: 1
6.50/3.06	
6.50/3.06	      4: evalcyclicbb3in -> evalcyclicbb4in : [ C>=1+A ], cost: 1
6.50/3.06	
6.50/3.06	      6: evalcyclicbb4in -> evalcyclicbbin : [], cost: 1
6.50/3.06	
6.50/3.06	      8: evalcyclicbbin -> evalcyclicbb3in : C'=1+C, [ B>=C ], cost: 1
6.50/3.06	
6.50/3.06	      9: evalcyclicbbin -> evalcyclicbb3in : C'=0, [ C>=1+B ], cost: 1
6.50/3.06	
6.50/3.06	
6.50/3.06	
6.50/3.06	Eliminated locations (on tree-shaped paths):
6.50/3.06	
6.50/3.06	   Start location: evalcyclicstart
6.50/3.06	
6.50/3.06	     11: evalcyclicstart -> evalcyclicbb3in : C'=1+A, [ A>=0 && B>=1+A ], cost: 2
6.50/3.06	
6.50/3.06	     12: evalcyclicbb3in -> evalcyclicbbin : [ A>=1+C ], cost: 2
6.50/3.06	
6.50/3.06	     13: evalcyclicbb3in -> evalcyclicbbin : [ C>=1+A ], cost: 2
6.50/3.06	
6.50/3.06	      8: evalcyclicbbin -> evalcyclicbb3in : C'=1+C, [ B>=C ], cost: 1
6.50/3.06	
6.50/3.06	      9: evalcyclicbbin -> evalcyclicbb3in : C'=0, [ C>=1+B ], cost: 1
6.50/3.06	
6.50/3.06	
6.50/3.06	
6.50/3.06	Eliminated locations (on tree-shaped paths):
6.50/3.06	
6.50/3.06	   Start location: evalcyclicstart
6.50/3.06	
6.50/3.06	     11: evalcyclicstart -> evalcyclicbb3in : C'=1+A, [ A>=0 && B>=1+A ], cost: 2
6.50/3.06	
6.50/3.06	     14: evalcyclicbb3in -> evalcyclicbb3in : C'=1+C, [ A>=1+C && B>=C ], cost: 3
6.50/3.06	
6.50/3.06	     15: evalcyclicbb3in -> evalcyclicbb3in : C'=0, [ A>=1+C && C>=1+B ], cost: 3
6.50/3.06	
6.50/3.06	     16: evalcyclicbb3in -> evalcyclicbb3in : C'=1+C, [ C>=1+A && B>=C ], cost: 3
6.50/3.06	
6.50/3.06	     17: evalcyclicbb3in -> evalcyclicbb3in : C'=0, [ C>=1+A && C>=1+B ], cost: 3
6.50/3.06	
6.50/3.06	
6.50/3.06	
6.50/3.06	Accelerating simple loops of location 2.
6.50/3.06	
6.50/3.06	   Accelerating the following rules:
6.50/3.06	
6.50/3.06	     14: evalcyclicbb3in -> evalcyclicbb3in : C'=1+C, [ A>=1+C && B>=C ], cost: 3
6.50/3.06	
6.50/3.06	     15: evalcyclicbb3in -> evalcyclicbb3in : C'=0, [ A>=1+C && C>=1+B ], cost: 3
6.50/3.06	
6.50/3.06	     16: evalcyclicbb3in -> evalcyclicbb3in : C'=1+C, [ C>=1+A && B>=C ], cost: 3
6.50/3.06	
6.50/3.06	     17: evalcyclicbb3in -> evalcyclicbb3in : C'=0, [ C>=1+A && C>=1+B ], cost: 3
6.50/3.06	
6.50/3.06	
6.50/3.06	
6.50/3.06	   Accelerated rule 14 with backward acceleration, yielding the new rule 18.
6.50/3.06	
6.50/3.06	   Accelerated rule 14 with backward acceleration, yielding the new rule 19.
6.50/3.06	
6.50/3.06	   Accelerated rule 15 with NONTERM (after strengthening guard), yielding the new rule 20.
6.50/3.06	
6.50/3.06	   Accelerated rule 16 with metering function 1-C+B, yielding the new rule 21.
6.50/3.06	
6.50/3.06	   Accelerated rule 17 with NONTERM (after strengthening guard), yielding the new rule 22.
6.50/3.06	
6.50/3.06	   Nested simple loops 15 (outer loop) and 19 (inner loop) with NONTERM, resulting in the new rules: 23, 24.
6.50/3.06	
6.50/3.06	   Nested simple loops 17 (outer loop) and 21 (inner loop) with NONTERM, resulting in the new rules: 25, 26.
6.50/3.06	
6.50/3.06	   Removing the simple loops: 14 15 16 17.
6.50/3.06	
6.50/3.06	
6.50/3.06	
6.50/3.06	Accelerated all simple loops using metering functions (where possible):
6.50/3.06	
6.50/3.06	   Start location: evalcyclicstart
6.50/3.06	
6.50/3.06	     11: evalcyclicstart -> evalcyclicbb3in : C'=1+A, [ A>=0 && B>=1+A ], cost: 2
6.50/3.06	
6.50/3.06	     18: evalcyclicbb3in -> evalcyclicbb3in : C'=A, [ A>=1+C && B>=C && B>=-1+A ], cost: -3*C+3*A
6.50/3.06	
6.50/3.06	     19: evalcyclicbb3in -> evalcyclicbb3in : C'=1+B, [ A>=1+C && B>=C && A>=1+B ], cost: 3-3*C+3*B
6.50/3.06	
6.50/3.06	     20: evalcyclicbb3in -> [7] : [ A>=1+C && C>=1+B && A>=1 && 0>=1+B ], cost: INF
6.50/3.06	
6.50/3.06	     21: evalcyclicbb3in -> evalcyclicbb3in : C'=1+B, [ C>=1+A && B>=C ], cost: 3-3*C+3*B
6.50/3.06	
6.50/3.06	     22: evalcyclicbb3in -> [7] : [ C>=1+A && C>=1+B && 0>=1+A && 0>=1+B ], cost: INF
6.50/3.06	
6.50/3.06	     23: evalcyclicbb3in -> [7] : [ A>=1+C && C>=1+B && A>=1 && B>=0 && A>=1+B && 6+3*B>=1 ], cost: INF
6.50/3.06	
6.50/3.06	     24: evalcyclicbb3in -> [7] : C'=1+B, [ A>=1+C && B>=C && A>=2+B && A>=1 && B>=0 && 6+3*B>=1 ], cost: INF
6.50/3.06	
6.50/3.06	     25: evalcyclicbb3in -> [7] : [ C>=1+A && C>=1+B && 0>=1+A && B>=0 && 6+3*B>=1 ], cost: INF
6.50/3.06	
6.50/3.06	     26: evalcyclicbb3in -> [7] : C'=1+B, [ C>=1+A && B>=C && 1+B>=1+A && 0>=1+A && B>=0 && 6+3*B>=1 ], cost: INF
6.50/3.06	
6.50/3.06	
6.50/3.06	
6.50/3.06	Chained accelerated rules (with incoming rules):
6.50/3.06	
6.50/3.06	   Start location: evalcyclicstart
6.50/3.06	
6.50/3.06	     11: evalcyclicstart -> evalcyclicbb3in : C'=1+A, [ A>=0 && B>=1+A ], cost: 2
6.50/3.06	
6.50/3.06	     27: evalcyclicstart -> evalcyclicbb3in : C'=1+B, [ A>=0 && B>=1+A ], cost: 2-3*A+3*B
6.50/3.06	
6.50/3.06	
6.50/3.06	
6.50/3.06	Removed unreachable locations (and leaf rules with constant cost):
6.50/3.06	
6.50/3.06	   Start location: evalcyclicstart
6.50/3.06	
6.50/3.06	     27: evalcyclicstart -> evalcyclicbb3in : C'=1+B, [ A>=0 && B>=1+A ], cost: 2-3*A+3*B
6.50/3.06	
6.50/3.06	
6.50/3.06	
6.50/3.06	### Computing asymptotic complexity ###
6.50/3.06	
6.50/3.06	
6.50/3.06	
6.50/3.06	Fully simplified ITS problem
6.50/3.06	
6.50/3.06	   Start location: evalcyclicstart
6.50/3.06	
6.50/3.06	     27: evalcyclicstart -> evalcyclicbb3in : C'=1+B, [ A>=0 && B>=1+A ], cost: 2-3*A+3*B
6.50/3.06	
6.50/3.06	
6.50/3.06	
6.50/3.06	Computing asymptotic complexity for rule 27
6.50/3.06	
6.50/3.06	   Solved the limit problem by the following transformations:
6.50/3.06	
6.50/3.06	      Created initial limit problem:
6.50/3.06	
6.50/3.06	      2-3*A+3*B (+), -A+B (+/+!), 1+A (+/+!) [not solved]
6.50/3.06	
6.50/3.06	
6.50/3.06	
6.50/3.06	      applying transformation rule (C) using substitution {A==0}
6.50/3.06	
6.50/3.06	      resulting limit problem:
6.50/3.06	
6.50/3.06	      1 (+/+!), 2+3*B (+), B (+/+!) [not solved]
6.50/3.06	
6.50/3.06	
6.50/3.06	
6.50/3.06	      applying transformation rule (C) using substitution {B==1+A}
6.50/3.06	
6.50/3.06	      resulting limit problem:
6.50/3.06	
6.50/3.06	      1 (+/+!), 5+3*A (+), 1+A (+/+!) [not solved]
6.50/3.06	
6.50/3.06	
6.50/3.06	
6.50/3.06	      applying transformation rule (B), deleting 1 (+/+!)
6.50/3.06	
6.50/3.06	      resulting limit problem:
6.50/3.06	
6.50/3.06	      5+3*A (+), 1+A (+/+!) [not solved]
6.50/3.06	
6.50/3.06	
6.50/3.06	
6.50/3.06	      applying transformation rule (D), replacing 5+3*A (+) by 3*A (+)
6.50/3.06	
6.50/3.06	      resulting limit problem:
6.50/3.06	
6.50/3.06	      3*A (+), 1+A (+/+!) [not solved]
6.50/3.06	
6.50/3.06	
6.50/3.06	
6.50/3.06	      applying transformation rule (D), replacing 1+A (+/+!) by A (+)
6.50/3.06	
6.50/3.06	      resulting limit problem:
6.50/3.06	
6.50/3.06	      3*A (+), A (+) [not solved]
6.50/3.06	
6.50/3.06	
6.50/3.06	
6.50/3.06	      applying transformation rule (A), replacing 3*A (+) by A (+) and 3 (+!) using + limit vector (+,+!)
6.50/3.06	
6.50/3.06	      resulting limit problem:
6.50/3.06	
6.50/3.06	      3 (+!), A (+) [not solved]
6.50/3.06	
6.50/3.06	
6.50/3.06	
6.50/3.06	      applying transformation rule (B), deleting 3 (+!)
6.50/3.06	
6.50/3.06	      resulting limit problem:
6.50/3.06	
6.50/3.06	      A (+) [solved]
6.50/3.06	
6.50/3.06	
6.50/3.06	
6.50/3.06	   Solution:
6.50/3.06	
6.50/3.06	      A / 0
6.50/3.06	
6.50/3.06	      B / 1+n
6.50/3.06	
6.50/3.06	   Resulting cost 5+3*n has complexity: Poly(n^1)
6.50/3.06	
6.50/3.06	
6.50/3.06	
6.50/3.06	Found new complexity Poly(n^1).
6.50/3.06	
6.50/3.06	
6.50/3.06	
6.50/3.06	Obtained the following overall complexity (w.r.t. the length of the input n):
6.50/3.06	
6.50/3.06	   Complexity:  Poly(n^1)
6.50/3.06	
6.50/3.06	   Cpx degree:  1
6.50/3.06	
6.50/3.06	   Solved cost: 5+3*n
6.50/3.06	
6.50/3.06	   Rule cost:   2-3*A+3*B
6.50/3.06	
6.50/3.06	   Rule guard:  [ A>=0 && B>=1+A ]
6.50/3.06	
6.50/3.06	
6.50/3.06	
6.50/3.06	WORST_CASE(Omega(n^1),?)
6.50/3.06	
6.50/3.06	
6.50/3.06	----------------------------------------
6.50/3.06	
6.50/3.06	(2)
6.50/3.06	BOUNDS(n^1, INF)
6.50/3.08	EOF