6.69/2.93	WORST_CASE(NON_POLY, ?)
6.69/2.94	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
6.69/2.94	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
6.69/2.94	
6.69/2.94	
6.69/2.94	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF).
6.69/2.94	
6.69/2.94	(0) CpxIntTrs
6.69/2.94	(1) Loat Proof [FINISHED, 1330 ms]
6.69/2.94	(2) BOUNDS(INF, INF)
6.69/2.94	
6.69/2.94	
6.69/2.94	----------------------------------------
6.69/2.94	
6.69/2.94	(0)
6.69/2.94	Obligation:
6.69/2.94	Complexity Int TRS consisting of the following rules:
6.69/2.94	f26(A, B) -> Com_1(f2(A, B)) :|: TRUE
6.69/2.94	f2(A, B) -> Com_1(f2(A, B)) :|: TRUE
6.69/2.94	f9(A, B) -> Com_1(f12(A, C)) :|: 5 >= A && 0 >= C + 1
6.69/2.94	f9(A, B) -> Com_1(f12(A, C)) :|: 5 >= A && C >= 1
6.69/2.94	f12(A, B) -> Com_1(f9(A + 1, B)) :|: A >= 6
6.69/2.94	f28(A, B) -> Com_1(f30(A, B)) :|: TRUE
6.69/2.94	f20(A, B) -> Com_1(f20(A - 1, B)) :|: A >= 3
6.69/2.94	f20(A, B) -> Com_1(f9(A, B)) :|: 2 >= A
6.69/2.94	f12(A, B) -> Com_1(f9(A + 1, B)) :|: 5 >= A
6.69/2.94	f9(A, B) -> Com_1(f20(A, 0)) :|: 5 >= A
6.69/2.94	f9(A, B) -> Com_1(f20(A, B)) :|: A >= 6
6.69/2.94	f0(A, B) -> Com_1(f9(C, B)) :|: TRUE
6.69/2.94	
6.69/2.94	The start-symbols are:[f0_2]
6.69/2.94	
6.69/2.94	
6.69/2.94	----------------------------------------
6.69/2.94	
6.69/2.94	(1) Loat Proof (FINISHED)
6.69/2.94	
6.69/2.94	
6.69/2.94	### Pre-processing the ITS problem ###
6.69/2.94	
6.69/2.94	
6.69/2.94	
6.69/2.94	Initial linear ITS problem
6.69/2.94	
6.69/2.94	   Start location: f0
6.69/2.94	
6.69/2.94	      0: f26 -> f2 : [], cost: 1
6.69/2.94	
6.69/2.94	      1: f2 -> f2 : [], cost: 1
6.69/2.94	
6.69/2.94	      2: f9 -> f12 : B'=free, [ 5>=A && 0>=1+free ], cost: 1
6.69/2.94	
6.69/2.94	      3: f9 -> f12 : B'=free_1, [ 5>=A && free_1>=1 ], cost: 1
6.69/2.94	
6.69/2.94	      9: f9 -> f20 : B'=0, [ 5>=A ], cost: 1
6.69/2.94	
6.69/2.94	     10: f9 -> f20 : [ A>=6 ], cost: 1
6.69/2.94	
6.69/2.94	      4: f12 -> f9 : A'=1+A, [ A>=6 ], cost: 1
6.69/2.94	
6.69/2.94	      8: f12 -> f9 : A'=1+A, [ 5>=A ], cost: 1
6.69/2.94	
6.69/2.94	      5: f28 -> f30 : [], cost: 1
6.69/2.94	
6.69/2.94	      6: f20 -> f20 : A'=-1+A, [ A>=3 ], cost: 1
6.69/2.94	
6.69/2.94	      7: f20 -> f9 : [ 2>=A ], cost: 1
6.69/2.94	
6.69/2.94	     11: f0 -> f9 : A'=free_2, [], cost: 1
6.69/2.94	
6.69/2.94	
6.69/2.94	
6.69/2.94	Removed unreachable and leaf rules:
6.69/2.94	
6.69/2.94	   Start location: f0
6.69/2.94	
6.69/2.94	      2: f9 -> f12 : B'=free, [ 5>=A && 0>=1+free ], cost: 1
6.69/2.94	
6.69/2.94	      3: f9 -> f12 : B'=free_1, [ 5>=A && free_1>=1 ], cost: 1
6.69/2.94	
6.69/2.94	      9: f9 -> f20 : B'=0, [ 5>=A ], cost: 1
6.69/2.94	
6.69/2.94	     10: f9 -> f20 : [ A>=6 ], cost: 1
6.69/2.94	
6.69/2.94	      4: f12 -> f9 : A'=1+A, [ A>=6 ], cost: 1
6.69/2.94	
6.69/2.94	      8: f12 -> f9 : A'=1+A, [ 5>=A ], cost: 1
6.69/2.94	
6.69/2.94	      6: f20 -> f20 : A'=-1+A, [ A>=3 ], cost: 1
6.69/2.94	
6.69/2.94	      7: f20 -> f9 : [ 2>=A ], cost: 1
6.69/2.94	
6.69/2.94	     11: f0 -> f9 : A'=free_2, [], cost: 1
6.69/2.94	
6.69/2.94	
6.69/2.94	
6.69/2.94	### Simplification by acceleration and chaining ###
6.69/2.94	
6.69/2.94	
6.69/2.94	
6.69/2.94	Accelerating simple loops of location 5.
6.69/2.94	
6.69/2.94	   Accelerating the following rules:
6.69/2.94	
6.69/2.94	      6: f20 -> f20 : A'=-1+A, [ A>=3 ], cost: 1
6.69/2.94	
6.69/2.94	
6.69/2.94	
6.69/2.94	   Accelerated rule 6 with metering function -2+A, yielding the new rule 12.
6.69/2.94	
6.69/2.94	   Removing the simple loops: 6.
6.69/2.94	
6.69/2.94	
6.69/2.94	
6.69/2.94	Accelerated all simple loops using metering functions (where possible):
6.69/2.94	
6.69/2.94	   Start location: f0
6.69/2.94	
6.69/2.94	      2: f9 -> f12 : B'=free, [ 5>=A && 0>=1+free ], cost: 1
6.69/2.94	
6.69/2.94	      3: f9 -> f12 : B'=free_1, [ 5>=A && free_1>=1 ], cost: 1
6.69/2.94	
6.69/2.94	      9: f9 -> f20 : B'=0, [ 5>=A ], cost: 1
6.69/2.94	
6.69/2.94	     10: f9 -> f20 : [ A>=6 ], cost: 1
6.69/2.94	
6.69/2.94	      4: f12 -> f9 : A'=1+A, [ A>=6 ], cost: 1
6.69/2.94	
6.69/2.94	      8: f12 -> f9 : A'=1+A, [ 5>=A ], cost: 1
6.69/2.94	
6.69/2.94	      7: f20 -> f9 : [ 2>=A ], cost: 1
6.69/2.94	
6.69/2.94	     12: f20 -> f20 : A'=2, [ A>=3 ], cost: -2+A
6.69/2.94	
6.69/2.94	     11: f0 -> f9 : A'=free_2, [], cost: 1
6.69/2.94	
6.69/2.94	
6.69/2.94	
6.69/2.94	Chained accelerated rules (with incoming rules):
6.69/2.94	
6.69/2.94	   Start location: f0
6.69/2.94	
6.69/2.94	      2: f9 -> f12 : B'=free, [ 5>=A && 0>=1+free ], cost: 1
6.69/2.94	
6.69/2.94	      3: f9 -> f12 : B'=free_1, [ 5>=A && free_1>=1 ], cost: 1
6.69/2.94	
6.69/2.94	      9: f9 -> f20 : B'=0, [ 5>=A ], cost: 1
6.69/2.94	
6.69/2.94	     10: f9 -> f20 : [ A>=6 ], cost: 1
6.69/2.94	
6.69/2.94	     13: f9 -> f20 : A'=2, B'=0, [ 5>=A && A>=3 ], cost: -1+A
6.69/2.94	
6.69/2.94	     14: f9 -> f20 : A'=2, [ A>=6 ], cost: -1+A
6.69/2.94	
6.69/2.94	      4: f12 -> f9 : A'=1+A, [ A>=6 ], cost: 1
6.69/2.94	
6.69/2.94	      8: f12 -> f9 : A'=1+A, [ 5>=A ], cost: 1
6.69/2.94	
6.69/2.94	      7: f20 -> f9 : [ 2>=A ], cost: 1
6.69/2.94	
6.69/2.94	     11: f0 -> f9 : A'=free_2, [], cost: 1
6.69/2.94	
6.69/2.94	
6.69/2.94	
6.69/2.94	Eliminated locations (on tree-shaped paths):
6.69/2.94	
6.69/2.94	   Start location: f0
6.69/2.94	
6.69/2.94	     15: f9 -> f9 : A'=1+A, B'=free, [ 5>=A && 0>=1+free ], cost: 2
6.69/2.94	
6.69/2.94	     16: f9 -> f9 : A'=1+A, B'=free_1, [ 5>=A && free_1>=1 ], cost: 2
6.69/2.94	
6.69/2.94	     17: f9 -> f9 : B'=0, [ 2>=A ], cost: 2
6.69/2.94	
6.69/2.94	     18: f9 -> f9 : A'=2, B'=0, [ 5>=A && A>=3 ], cost: A
6.69/2.94	
6.69/2.94	     19: f9 -> f9 : A'=2, [ A>=6 ], cost: A
6.69/2.94	
6.69/2.94	     11: f0 -> f9 : A'=free_2, [], cost: 1
6.69/2.94	
6.69/2.94	
6.69/2.94	
6.69/2.94	Accelerating simple loops of location 2.
6.69/2.94	
6.69/2.94	   Accelerating the following rules:
6.69/2.94	
6.69/2.94	     15: f9 -> f9 : A'=1+A, B'=free, [ 5>=A && 0>=1+free ], cost: 2
6.69/2.94	
6.69/2.94	     16: f9 -> f9 : A'=1+A, B'=free_1, [ 5>=A && free_1>=1 ], cost: 2
6.69/2.94	
6.69/2.94	     17: f9 -> f9 : B'=0, [ 2>=A ], cost: 2
6.69/2.94	
6.69/2.94	     18: f9 -> f9 : A'=2, B'=0, [ 5>=A && A>=3 ], cost: A
6.69/2.94	
6.69/2.94	     19: f9 -> f9 : A'=2, [ A>=6 ], cost: A
6.69/2.94	
6.69/2.94	
6.69/2.94	
6.69/2.94	   Accelerated rule 15 with metering function 6-A, yielding the new rule 20.
6.69/2.94	
6.69/2.94	   Accelerated rule 16 with metering function 6-A, yielding the new rule 21.
6.69/2.94	
6.69/2.94	   Accelerated rule 17 with NONTERM, yielding the new rule 22.
6.69/2.94	
6.69/2.94	   Accelerated rule 18 with metering function meter (where 3*meter==-2+A), yielding the new rule 23.
6.69/2.94	
6.69/2.94	   Found no metering function for rule 19.
6.69/2.94	
6.69/2.94	   Nested simple loops 19 (outer loop) and 20 (inner loop) with NONTERM, resulting in the new rules: 24, 25.
6.69/2.94	
6.69/2.94	   Nested simple loops 19 (outer loop) and 21 (inner loop) with NONTERM, resulting in the new rules: 26, 27.
6.69/2.94	
6.69/2.94	   Nested simple loops 15 (outer loop) and 23 (inner loop) with metering function meter_3 (where 2*meter_3==-4+A-meter), resulting in the new rules: 28.
6.69/2.94	
6.69/2.94	   Nested simple loops 16 (outer loop) and 23 (inner loop) with metering function meter_4 (where 2*meter_4==-4+A-meter), resulting in the new rules: 29.
6.69/2.94	
6.69/2.94	   Removing the simple loops: 15 16 17 18 19.
6.69/2.94	
6.69/2.94	
6.69/2.94	
6.69/2.94	Accelerated all simple loops using metering functions (where possible):
6.69/2.94	
6.69/2.94	   Start location: f0
6.69/2.94	
6.69/2.94	     20: f9 -> f9 : A'=6, B'=free, [ 5>=A && 0>=1+free ], cost: 12-2*A
6.69/2.94	
6.69/2.94	     21: f9 -> f9 : A'=6, B'=free_1, [ 5>=A && free_1>=1 ], cost: 12-2*A
6.69/2.94	
6.69/2.94	     22: f9 -> [9] : [ 2>=A ], cost: INF
6.69/2.94	
6.69/2.94	     23: f9 -> f9 : A'=2, B'=0, [ 5>=A && A>=3 && 3*meter==-2+A && meter>=1 ], cost: 2*meter
6.69/2.94	
6.69/2.94	     24: f9 -> [9] : [ 5>=A && 0>=1+free && 18-2*A>=1 ], cost: INF
6.69/2.94	
6.69/2.94	     25: f9 -> [9] : A'=2, [ A>=6 && 0>=1+free ], cost: INF
6.69/2.94	
6.69/2.94	     26: f9 -> [9] : [ 5>=A && free_1>=1 && 18-2*A>=1 ], cost: INF
6.69/2.94	
6.69/2.94	     27: f9 -> [9] : A'=2, [ A>=6 && free_1>=1 ], cost: INF
6.69/2.94	
6.69/2.94	     28: f9 -> f9 : A'=3, B'=free, [ 5>=A && A>=3 && 3*meter==-2+A && meter>=1 && 0>=1+free && 2*meter_3==-4+A-meter && meter_3>=1 ], cost: 2*meter*meter_3+2*meter_3
6.69/2.94	
6.69/2.94	     29: f9 -> f9 : A'=3, B'=free_1, [ 5>=A && A>=3 && 3*meter==-2+A && meter>=1 && free_1>=1 && 2*meter_4==-4+A-meter && meter_4>=1 ], cost: 2*meter_4+2*meter_4*meter
6.69/2.94	
6.69/2.94	     11: f0 -> f9 : A'=free_2, [], cost: 1
6.69/2.94	
6.69/2.94	
6.69/2.94	
6.69/2.94	Chained accelerated rules (with incoming rules):
6.69/2.94	
6.69/2.94	   Start location: f0
6.69/2.94	
6.69/2.94	     11: f0 -> f9 : A'=free_2, [], cost: 1
6.69/2.94	
6.69/2.94	     30: f0 -> f9 : A'=6, B'=free, [ 5>=free_2 && 0>=1+free ], cost: 13-2*free_2
6.69/2.94	
6.69/2.94	     31: f0 -> f9 : A'=6, B'=free_1, [ 5>=free_2 && free_1>=1 ], cost: 13-2*free_2
6.69/2.94	
6.69/2.94	     32: f0 -> [9] : A'=free_2, [ 2>=free_2 ], cost: INF
6.69/2.94	
6.69/2.94	     33: f0 -> f9 : A'=2, B'=0, [ 5>=2+3*meter && 2+3*meter>=3 && meter>=1 ], cost: 1+2*meter
6.69/2.94	
6.69/2.94	     34: f0 -> [9] : A'=free_2, [ 5>=free_2 && 18-2*free_2>=1 ], cost: INF
6.69/2.94	
6.69/2.94	     35: f0 -> [9] : A'=2, [], cost: INF
6.69/2.94	
6.69/2.94	     36: f0 -> [9] : A'=free_2, [ 5>=free_2 && 18-2*free_2>=1 ], cost: INF
6.69/2.94	
6.69/2.94	     37: f0 -> [9] : A'=2, [], cost: INF
6.69/2.94	
6.69/2.94	
6.69/2.94	
6.69/2.94	Removed unreachable locations (and leaf rules with constant cost):
6.69/2.94	
6.69/2.94	   Start location: f0
6.69/2.94	
6.69/2.94	     30: f0 -> f9 : A'=6, B'=free, [ 5>=free_2 && 0>=1+free ], cost: 13-2*free_2
6.69/2.94	
6.69/2.94	     31: f0 -> f9 : A'=6, B'=free_1, [ 5>=free_2 && free_1>=1 ], cost: 13-2*free_2
6.69/2.94	
6.69/2.94	     32: f0 -> [9] : A'=free_2, [ 2>=free_2 ], cost: INF
6.69/2.94	
6.69/2.94	     33: f0 -> f9 : A'=2, B'=0, [ 5>=2+3*meter && 2+3*meter>=3 && meter>=1 ], cost: 1+2*meter
6.69/2.94	
6.69/2.94	     34: f0 -> [9] : A'=free_2, [ 5>=free_2 && 18-2*free_2>=1 ], cost: INF
6.69/2.94	
6.69/2.94	     35: f0 -> [9] : A'=2, [], cost: INF
6.69/2.94	
6.69/2.94	     36: f0 -> [9] : A'=free_2, [ 5>=free_2 && 18-2*free_2>=1 ], cost: INF
6.69/2.94	
6.69/2.94	     37: f0 -> [9] : A'=2, [], cost: INF
6.69/2.94	
6.69/2.94	
6.69/2.94	
6.69/2.94	### Computing asymptotic complexity ###
6.69/2.94	
6.69/2.94	
6.69/2.94	
6.69/2.94	Fully simplified ITS problem
6.69/2.94	
6.69/2.94	   Start location: f0
6.69/2.94	
6.69/2.94	     30: f0 -> f9 : A'=6, B'=free, [ 5>=free_2 && 0>=1+free ], cost: 13-2*free_2
6.69/2.94	
6.69/2.94	     31: f0 -> f9 : A'=6, B'=free_1, [ 5>=free_2 && free_1>=1 ], cost: 13-2*free_2
6.69/2.94	
6.69/2.94	     32: f0 -> [9] : A'=free_2, [ 2>=free_2 ], cost: INF
6.69/2.94	
6.69/2.94	     33: f0 -> f9 : A'=2, B'=0, [ 5>=2+3*meter && 2+3*meter>=3 && meter>=1 ], cost: 1+2*meter
6.69/2.94	
6.69/2.94	     36: f0 -> [9] : A'=free_2, [ 5>=free_2 && 18-2*free_2>=1 ], cost: INF
6.69/2.94	
6.69/2.94	     37: f0 -> [9] : A'=2, [], cost: INF
6.69/2.94	
6.69/2.94	
6.69/2.94	
6.69/2.94	Computing asymptotic complexity for rule 30
6.69/2.94	
6.69/2.94	   Solved the limit problem by the following transformations:
6.69/2.94	
6.69/2.94	      Created initial limit problem:
6.69/2.94	
6.69/2.94	      6-free_2 (+/+!), -free (+/+!), 13-2*free_2 (+) [not solved]
6.69/2.94	
6.69/2.94	
6.69/2.94	
6.69/2.94	      removing all constraints (solved by SMT)
6.69/2.94	
6.69/2.94	      resulting limit problem: [solved]
6.69/2.94	
6.69/2.94	
6.69/2.94	
6.69/2.94	      applying transformation rule (C) using substitution {free_2==-n,free==-1}
6.69/2.94	
6.69/2.94	      resulting limit problem:
6.69/2.94	
6.69/2.94	      [solved]
6.69/2.94	
6.69/2.94	
6.69/2.94	
6.69/2.94	   Solution:
6.69/2.94	
6.69/2.94	      free_2 / -n
6.69/2.94	
6.69/2.94	      free / -1
6.69/2.94	
6.69/2.94	   Resulting cost 13+2*n has complexity: Unbounded
6.69/2.94	
6.69/2.94	
6.69/2.94	
6.69/2.94	Found new complexity Unbounded.
6.69/2.94	
6.69/2.94	
6.69/2.94	
6.69/2.94	Obtained the following overall complexity (w.r.t. the length of the input n):
6.69/2.94	
6.69/2.94	   Complexity:  Unbounded
6.69/2.94	
6.69/2.94	   Cpx degree:  Unbounded
6.69/2.94	
6.69/2.94	   Solved cost: 13+2*n
6.69/2.94	
6.69/2.94	   Rule cost:   13-2*free_2
6.69/2.94	
6.69/2.94	   Rule guard:  [ 5>=free_2 && 0>=1+free ]
6.69/2.94	
6.69/2.94	
6.69/2.94	
6.69/2.94	WORST_CASE(INF,?)
6.69/2.94	
6.69/2.94	
6.69/2.94	----------------------------------------
6.69/2.94	
6.69/2.94	(2)
6.69/2.94	BOUNDS(INF, INF)
6.69/2.96	EOF