4.89/2.49	WORST_CASE(NON_POLY, ?)
4.89/2.50	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
4.89/2.50	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.89/2.50	
4.89/2.50	
4.89/2.50	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF).
4.89/2.50	
4.89/2.50	(0) CpxIntTrs
4.89/2.50	(1) Loat Proof [FINISHED, 691 ms]
4.89/2.50	(2) BOUNDS(INF, INF)
4.89/2.50	
4.89/2.50	
4.89/2.50	----------------------------------------
4.89/2.50	
4.89/2.50	(0)
4.89/2.50	Obligation:
4.89/2.50	Complexity Int TRS consisting of the following rules:
4.89/2.50	f2(A, B) -> Com_1(f1(C, D)) :|: 0 >= C + 1 && A >= 14 && A <= 14
4.89/2.50	f2(A, B) -> Com_1(f2(C, B)) :|: C >= 0 && A >= 14 && A <= 14
4.89/2.50	f2(A, B) -> Com_1(f1(-(1) + A, C)) :|: A >= 15 && 0 >= A
4.89/2.50	f2(A, B) -> Com_1(f1(-(1) + A, C)) :|: 13 >= A && 0 >= A
4.89/2.50	f2(A, B) -> Com_1(f2(-(1) + A, B)) :|: A >= 15 && A >= 1
4.89/2.50	f2(A, B) -> Com_1(f2(-(1) + A, B)) :|: 13 >= A && A >= 1
4.89/2.50	f300(A, B) -> Com_1(f2(A, B)) :|: TRUE
4.89/2.50	
4.89/2.50	The start-symbols are:[f300_2]
4.89/2.50	
4.89/2.50	
4.89/2.50	----------------------------------------
4.89/2.50	
4.89/2.50	(1) Loat Proof (FINISHED)
4.89/2.50	
4.89/2.50	
4.89/2.50	### Pre-processing the ITS problem ###
4.89/2.50	
4.89/2.50	
4.89/2.50	
4.89/2.50	Initial linear ITS problem
4.89/2.50	
4.89/2.50	   Start location: f300
4.89/2.50	
4.89/2.50	      0: f2 -> f1 : A'=free, B'=free_1, [ 0>=1+free && A==14 ], cost: 1
4.89/2.50	
4.89/2.50	      1: f2 -> f2 : A'=free_2, [ free_2>=0 && A==14 ], cost: 1
4.89/2.50	
4.89/2.50	      2: f2 -> f1 : A'=-1+A, B'=free_3, [ A>=15 && 0>=A ], cost: 1
4.89/2.50	
4.89/2.50	      3: f2 -> f1 : A'=-1+A, B'=free_4, [ 13>=A && 0>=A ], cost: 1
4.89/2.50	
4.89/2.50	      4: f2 -> f2 : A'=-1+A, [ A>=15 && A>=1 ], cost: 1
4.89/2.50	
4.89/2.50	      5: f2 -> f2 : A'=-1+A, [ 13>=A && A>=1 ], cost: 1
4.89/2.50	
4.89/2.50	      6: f300 -> f2 : [], cost: 1
4.89/2.50	
4.89/2.50	
4.89/2.50	
4.89/2.50	Removed unreachable and leaf rules:
4.89/2.50	
4.89/2.50	   Start location: f300
4.89/2.50	
4.89/2.50	      1: f2 -> f2 : A'=free_2, [ free_2>=0 && A==14 ], cost: 1
4.89/2.50	
4.89/2.50	      4: f2 -> f2 : A'=-1+A, [ A>=15 && A>=1 ], cost: 1
4.89/2.50	
4.89/2.50	      5: f2 -> f2 : A'=-1+A, [ 13>=A && A>=1 ], cost: 1
4.89/2.50	
4.89/2.50	      6: f300 -> f2 : [], cost: 1
4.89/2.50	
4.89/2.50	
4.89/2.50	
4.89/2.50	Simplified all rules, resulting in:
4.89/2.50	
4.89/2.50	   Start location: f300
4.89/2.50	
4.89/2.50	      1: f2 -> f2 : A'=free_2, [ free_2>=0 && A==14 ], cost: 1
4.89/2.50	
4.89/2.50	      4: f2 -> f2 : A'=-1+A, [ A>=15 ], cost: 1
4.89/2.50	
4.89/2.50	      5: f2 -> f2 : A'=-1+A, [ 13>=A && A>=1 ], cost: 1
4.89/2.50	
4.89/2.50	      6: f300 -> f2 : [], cost: 1
4.89/2.50	
4.89/2.50	
4.89/2.50	
4.89/2.50	### Simplification by acceleration and chaining ###
4.89/2.50	
4.89/2.50	
4.89/2.50	
4.89/2.50	Accelerating simple loops of location 0.
4.89/2.50	
4.89/2.50	   Accelerating the following rules:
4.89/2.50	
4.89/2.50	      1: f2 -> f2 : A'=free_2, [ free_2>=0 && A==14 ], cost: 1
4.89/2.50	
4.89/2.50	      4: f2 -> f2 : A'=-1+A, [ A>=15 ], cost: 1
4.89/2.50	
4.89/2.50	      5: f2 -> f2 : A'=-1+A, [ 13>=A && A>=1 ], cost: 1
4.89/2.50	
4.89/2.50	
4.89/2.50	
4.89/2.50	      During metering: Instantiating temporary variables by {free_2==0}
4.89/2.50	
4.89/2.50	   Accelerated rule 1 with metering function meter (where 14*meter==-13+A), yielding the new rule 7.
4.89/2.50	
4.89/2.50	   Accelerated rule 4 with metering function -14+A, yielding the new rule 8.
4.89/2.50	
4.89/2.50	   Accelerated rule 5 with metering function A, yielding the new rule 9.
4.89/2.50	
4.89/2.50	   Nested simple loops 1 (outer loop) and 8 (inner loop) with NONTERM, resulting in the new rules: 10, 11.
4.89/2.50	
4.89/2.50	   Nested simple loops 1 (outer loop) and 9 (inner loop) with metering function meter_1 (where 14*meter_1==-13+A), resulting in the new rules: 12.
4.89/2.50	
4.89/2.50	   Removing the simple loops: 1 4 5.
4.89/2.50	
4.89/2.50	
4.89/2.50	
4.89/2.50	Accelerated all simple loops using metering functions (where possible):
4.89/2.50	
4.89/2.50	   Start location: f300
4.89/2.50	
4.89/2.50	      7: f2 -> f2 : A'=0, [ A==14 && 14*meter==-13+A && meter>=1 ], cost: meter
4.89/2.50	
4.89/2.50	      8: f2 -> f2 : A'=14, [ A>=15 ], cost: -14+A
4.89/2.50	
4.89/2.50	      9: f2 -> f2 : A'=0, [ 13>=A && A>=1 ], cost: A
4.89/2.50	
4.89/2.50	     10: f2 -> [3] : [ A==14 && free_2>=15 ], cost: INF
4.89/2.50	
4.89/2.50	     11: f2 -> [3] : A'=14, [ A>=15 && free_2>=15 ], cost: INF
4.89/2.50	
4.89/2.50	     12: f2 -> f2 : A'=0, [ A==14 && 13>=free_2 && free_2>=1 && 14*meter_1==-13+A && meter_1>=1 ], cost: meter_1+meter_1*free_2
4.89/2.50	
4.89/2.50	      6: f300 -> f2 : [], cost: 1
4.89/2.50	
4.89/2.50	
4.89/2.50	
4.89/2.50	Chained accelerated rules (with incoming rules):
4.89/2.50	
4.89/2.50	   Start location: f300
4.89/2.50	
4.89/2.50	      6: f300 -> f2 : [], cost: 1
4.89/2.50	
4.89/2.50	     13: f300 -> f2 : A'=14, [ A>=15 ], cost: -13+A
4.89/2.50	
4.89/2.50	     14: f300 -> f2 : A'=0, [ 13>=A && A>=1 ], cost: 1+A
4.89/2.50	
4.89/2.50	     15: f300 -> [3] : [ A==14 ], cost: INF
4.89/2.50	
4.89/2.50	     16: f300 -> [3] : A'=14, [ A>=15 ], cost: INF
4.89/2.50	
4.89/2.50	
4.89/2.50	
4.89/2.50	Removed unreachable locations (and leaf rules with constant cost):
4.89/2.50	
4.89/2.50	   Start location: f300
4.89/2.50	
4.89/2.50	     13: f300 -> f2 : A'=14, [ A>=15 ], cost: -13+A
4.89/2.50	
4.89/2.50	     14: f300 -> f2 : A'=0, [ 13>=A && A>=1 ], cost: 1+A
4.89/2.50	
4.89/2.50	     15: f300 -> [3] : [ A==14 ], cost: INF
4.89/2.50	
4.89/2.50	     16: f300 -> [3] : A'=14, [ A>=15 ], cost: INF
4.89/2.50	
4.89/2.50	
4.89/2.50	
4.89/2.50	### Computing asymptotic complexity ###
4.89/2.50	
4.89/2.50	
4.89/2.50	
4.89/2.50	Fully simplified ITS problem
4.89/2.50	
4.89/2.50	   Start location: f300
4.89/2.50	
4.89/2.50	     13: f300 -> f2 : A'=14, [ A>=15 ], cost: -13+A
4.89/2.50	
4.89/2.50	     14: f300 -> f2 : A'=0, [ 13>=A && A>=1 ], cost: 1+A
4.89/2.50	
4.89/2.50	     15: f300 -> [3] : [ A==14 ], cost: INF
4.89/2.50	
4.89/2.50	     16: f300 -> [3] : A'=14, [ A>=15 ], cost: INF
4.89/2.50	
4.89/2.50	
4.89/2.50	
4.89/2.50	Computing asymptotic complexity for rule 13
4.89/2.50	
4.89/2.50	   Solved the limit problem by the following transformations:
4.89/2.50	
4.89/2.50	      Created initial limit problem:
4.89/2.50	
4.89/2.50	      -14+A (+/+!), -13+A (+) [not solved]
4.89/2.50	
4.89/2.50	
4.89/2.50	
4.89/2.50	      removing all constraints (solved by SMT)
4.89/2.50	
4.89/2.50	      resulting limit problem: [solved]
4.89/2.50	
4.89/2.50	
4.89/2.50	
4.89/2.50	      applying transformation rule (C) using substitution {A==n}
4.89/2.50	
4.89/2.50	      resulting limit problem:
4.89/2.50	
4.89/2.50	      [solved]
4.89/2.50	
4.89/2.50	
4.89/2.50	
4.89/2.50	   Solution:
4.89/2.50	
4.89/2.50	      A / n
4.89/2.50	
4.89/2.50	   Resulting cost -13+n has complexity: Poly(n^1)
4.89/2.50	
4.89/2.50	
4.89/2.50	
4.89/2.50	Found new complexity Poly(n^1).
4.89/2.50	
4.89/2.50	
4.89/2.50	
4.89/2.50	Computing asymptotic complexity for rule 15
4.89/2.50	
4.89/2.50	   Resulting cost INF has complexity: Nonterm
4.89/2.50	
4.89/2.50	
4.89/2.50	
4.89/2.50	Found new complexity Nonterm.
4.89/2.50	
4.89/2.50	
4.89/2.50	
4.89/2.50	Obtained the following overall complexity (w.r.t. the length of the input n):
4.89/2.50	
4.89/2.50	   Complexity:  Nonterm
4.89/2.50	
4.89/2.50	   Cpx degree:  Nonterm
4.89/2.50	
4.89/2.50	   Solved cost: INF
4.89/2.50	
4.89/2.50	   Rule cost:   INF
4.89/2.50	
4.89/2.50	   Rule guard:  [ A==14 ]
4.89/2.50	
4.89/2.50	
4.89/2.50	
4.89/2.50	NO
4.89/2.50	
4.89/2.50	
4.89/2.50	----------------------------------------
4.89/2.50	
4.89/2.50	(2)
4.89/2.50	BOUNDS(INF, INF)
4.89/2.52	EOF