6.86/3.18	WORST_CASE(NON_POLY, ?)
6.86/3.18	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
6.86/3.18	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
6.86/3.18	
6.86/3.18	
6.86/3.18	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF).
6.86/3.18	
6.86/3.18	(0) CpxIntTrs
6.86/3.18	(1) Loat Proof [FINISHED, 1382 ms]
6.86/3.18	(2) BOUNDS(INF, INF)
6.86/3.18	
6.86/3.18	
6.86/3.18	----------------------------------------
6.86/3.18	
6.86/3.18	(0)
6.86/3.18	Obligation:
6.86/3.18	Complexity Int TRS consisting of the following rules:
6.86/3.18	f11(A, B, C) -> Com_1(f14(A, B, C)) :|: A >= 6
6.86/3.18	f11(A, B, C) -> Com_1(f14(A, B, C)) :|: 5 >= A && 0 >= B
6.86/3.18	f14(A, B, C) -> Com_1(f11(A + 1, D, C)) :|: A >= 6
6.86/3.18	f26(A, B, C) -> Com_1(f27(A, B, C)) :|: TRUE
6.86/3.18	f27(A, B, C) -> Com_1(f27(A, B, C)) :|: TRUE
6.86/3.18	f29(A, B, C) -> Com_1(f32(A, B, C)) :|: TRUE
6.86/3.18	f20(A, B, C) -> Com_1(f20(A - 1, B, C)) :|: A >= 3
6.86/3.18	f20(A, B, C) -> Com_1(f11(A, D, C)) :|: 2 >= A
6.86/3.18	f14(A, B, C) -> Com_1(f11(A + 1, D, C)) :|: 5 >= A
6.86/3.18	f11(A, B, C) -> Com_1(f20(A, B, C)) :|: 5 >= A && B >= 1
6.86/3.18	f0(A, B, C) -> Com_1(f11(D, E, D)) :|: TRUE
6.86/3.18	
6.86/3.18	The start-symbols are:[f0_3]
6.86/3.18	
6.86/3.18	
6.86/3.18	----------------------------------------
6.86/3.18	
6.86/3.18	(1) Loat Proof (FINISHED)
6.86/3.18	
6.86/3.18	
6.86/3.18	### Pre-processing the ITS problem ###
6.86/3.18	
6.86/3.18	
6.86/3.18	
6.86/3.18	Initial linear ITS problem
6.86/3.18	
6.86/3.18	   Start location: f0
6.86/3.18	
6.86/3.18	      0: f11 -> f14 : [ A>=6 ], cost: 1
6.86/3.18	
6.86/3.18	      1: f11 -> f14 : [ 5>=A && 0>=B ], cost: 1
6.86/3.18	
6.86/3.18	      9: f11 -> f20 : [ 5>=A && B>=1 ], cost: 1
6.86/3.18	
6.86/3.18	      2: f14 -> f11 : A'=1+A, B'=free, [ A>=6 ], cost: 1
6.86/3.18	
6.86/3.18	      8: f14 -> f11 : A'=1+A, B'=free_2, [ 5>=A ], cost: 1
6.86/3.18	
6.86/3.18	      3: f26 -> f27 : [], cost: 1
6.86/3.18	
6.86/3.18	      4: f27 -> f27 : [], cost: 1
6.86/3.18	
6.86/3.18	      5: f29 -> f32 : [], cost: 1
6.86/3.18	
6.86/3.18	      6: f20 -> f20 : A'=-1+A, [ A>=3 ], cost: 1
6.86/3.18	
6.86/3.18	      7: f20 -> f11 : B'=free_1, [ 2>=A ], cost: 1
6.86/3.18	
6.86/3.18	     10: f0 -> f11 : A'=free_3, B'=free_4, C'=free_3, [], cost: 1
6.86/3.18	
6.86/3.18	
6.86/3.18	
6.86/3.18	Removed unreachable and leaf rules:
6.86/3.18	
6.86/3.18	   Start location: f0
6.86/3.18	
6.86/3.18	      0: f11 -> f14 : [ A>=6 ], cost: 1
6.86/3.18	
6.86/3.18	      1: f11 -> f14 : [ 5>=A && 0>=B ], cost: 1
6.86/3.18	
6.86/3.18	      9: f11 -> f20 : [ 5>=A && B>=1 ], cost: 1
6.86/3.18	
6.86/3.18	      2: f14 -> f11 : A'=1+A, B'=free, [ A>=6 ], cost: 1
6.86/3.18	
6.86/3.18	      8: f14 -> f11 : A'=1+A, B'=free_2, [ 5>=A ], cost: 1
6.86/3.18	
6.86/3.18	      6: f20 -> f20 : A'=-1+A, [ A>=3 ], cost: 1
6.86/3.18	
6.86/3.18	      7: f20 -> f11 : B'=free_1, [ 2>=A ], cost: 1
6.86/3.18	
6.86/3.18	     10: f0 -> f11 : A'=free_3, B'=free_4, C'=free_3, [], cost: 1
6.86/3.18	
6.86/3.18	
6.86/3.18	
6.86/3.18	### Simplification by acceleration and chaining ###
6.86/3.18	
6.86/3.18	
6.86/3.18	
6.86/3.18	Accelerating simple loops of location 5.
6.86/3.18	
6.86/3.18	   Accelerating the following rules:
6.86/3.18	
6.86/3.18	      6: f20 -> f20 : A'=-1+A, [ A>=3 ], cost: 1
6.86/3.18	
6.86/3.18	
6.86/3.18	
6.86/3.18	   Accelerated rule 6 with metering function -2+A, yielding the new rule 11.
6.86/3.18	
6.86/3.18	   Removing the simple loops: 6.
6.86/3.18	
6.86/3.18	
6.86/3.18	
6.86/3.18	Accelerated all simple loops using metering functions (where possible):
6.86/3.18	
6.86/3.18	   Start location: f0
6.86/3.18	
6.86/3.18	      0: f11 -> f14 : [ A>=6 ], cost: 1
6.86/3.18	
6.86/3.18	      1: f11 -> f14 : [ 5>=A && 0>=B ], cost: 1
6.86/3.18	
6.86/3.18	      9: f11 -> f20 : [ 5>=A && B>=1 ], cost: 1
6.86/3.18	
6.86/3.18	      2: f14 -> f11 : A'=1+A, B'=free, [ A>=6 ], cost: 1
6.86/3.18	
6.86/3.18	      8: f14 -> f11 : A'=1+A, B'=free_2, [ 5>=A ], cost: 1
6.86/3.18	
6.86/3.18	      7: f20 -> f11 : B'=free_1, [ 2>=A ], cost: 1
6.86/3.18	
6.86/3.18	     11: f20 -> f20 : A'=2, [ A>=3 ], cost: -2+A
6.86/3.18	
6.86/3.18	     10: f0 -> f11 : A'=free_3, B'=free_4, C'=free_3, [], cost: 1
6.86/3.18	
6.86/3.18	
6.86/3.18	
6.86/3.18	Chained accelerated rules (with incoming rules):
6.86/3.18	
6.86/3.18	   Start location: f0
6.86/3.18	
6.86/3.18	      0: f11 -> f14 : [ A>=6 ], cost: 1
6.86/3.18	
6.86/3.18	      1: f11 -> f14 : [ 5>=A && 0>=B ], cost: 1
6.86/3.18	
6.86/3.18	      9: f11 -> f20 : [ 5>=A && B>=1 ], cost: 1
6.86/3.18	
6.86/3.18	     12: f11 -> f20 : A'=2, [ 5>=A && B>=1 && A>=3 ], cost: -1+A
6.86/3.18	
6.86/3.18	      2: f14 -> f11 : A'=1+A, B'=free, [ A>=6 ], cost: 1
6.86/3.18	
6.86/3.18	      8: f14 -> f11 : A'=1+A, B'=free_2, [ 5>=A ], cost: 1
6.86/3.18	
6.86/3.18	      7: f20 -> f11 : B'=free_1, [ 2>=A ], cost: 1
6.86/3.18	
6.86/3.18	     10: f0 -> f11 : A'=free_3, B'=free_4, C'=free_3, [], cost: 1
6.86/3.18	
6.86/3.18	
6.86/3.18	
6.86/3.18	Eliminated locations (on tree-shaped paths):
6.86/3.18	
6.86/3.18	   Start location: f0
6.86/3.18	
6.86/3.18	     13: f11 -> f11 : A'=1+A, B'=free, [ A>=6 ], cost: 2
6.86/3.18	
6.86/3.18	     14: f11 -> f11 : A'=1+A, B'=free_2, [ 5>=A && 0>=B ], cost: 2
6.86/3.18	
6.86/3.18	     15: f11 -> f11 : B'=free_1, [ B>=1 && 2>=A ], cost: 2
6.86/3.18	
6.86/3.18	     16: f11 -> f11 : A'=2, B'=free_1, [ 5>=A && B>=1 && A>=3 ], cost: A
6.86/3.18	
6.86/3.18	     10: f0 -> f11 : A'=free_3, B'=free_4, C'=free_3, [], cost: 1
6.86/3.18	
6.86/3.18	
6.86/3.18	
6.86/3.18	Accelerating simple loops of location 0.
6.86/3.18	
6.86/3.18	   Accelerating the following rules:
6.86/3.18	
6.86/3.18	     13: f11 -> f11 : A'=1+A, B'=free, [ A>=6 ], cost: 2
6.86/3.18	
6.86/3.18	     14: f11 -> f11 : A'=1+A, B'=free_2, [ 5>=A && 0>=B ], cost: 2
6.86/3.18	
6.86/3.18	     15: f11 -> f11 : B'=free_1, [ B>=1 && 2>=A ], cost: 2
6.86/3.18	
6.86/3.18	     16: f11 -> f11 : A'=2, B'=free_1, [ 5>=A && B>=1 && A>=3 ], cost: A
6.86/3.18	
6.86/3.18	
6.86/3.18	
6.86/3.18	   Accelerated rule 13 with NONTERM, yielding the new rule 17.
6.86/3.18	
6.86/3.18	   Accelerated rule 14 with metering function 6-A (after strengthening guard), yielding the new rule 18.
6.86/3.18	
6.86/3.18	   Accelerated rule 15 with NONTERM (after strengthening guard), yielding the new rule 19.
6.86/3.18	
6.86/3.18	   Accelerated rule 16 with metering function meter (where 3*meter==-2+A) (after strengthening guard), yielding the new rule 20.
6.86/3.18	
6.86/3.18	   Nested simple loops 14 (outer loop) and 20 (inner loop) with metering function meter_1 (where 2*meter_1==-3-meter+A), resulting in the new rules: 21.
6.86/3.18	
6.86/3.18	   Nested simple loops 15 (outer loop) and 20 (inner loop) with metering function meter_2 (where 3*meter_2==-4-meter+A), resulting in the new rules: 22.
6.86/3.18	
6.86/3.18	   Removing the simple loops: 13 14 15.
6.86/3.18	
6.86/3.18	
6.86/3.18	
6.86/3.18	Accelerated all simple loops using metering functions (where possible):
6.86/3.18	
6.86/3.18	   Start location: f0
6.86/3.18	
6.86/3.18	     16: f11 -> f11 : A'=2, B'=free_1, [ 5>=A && B>=1 && A>=3 ], cost: A
6.86/3.18	
6.86/3.18	     17: f11 -> [9] : [ A>=6 ], cost: INF
6.86/3.18	
6.86/3.18	     18: f11 -> f11 : A'=6, B'=free_2, [ 5>=A && 0>=B && 0>=free_2 ], cost: 12-2*A
6.86/3.18	
6.86/3.18	     19: f11 -> [9] : [ B>=1 && 2>=A && free_1>=1 ], cost: INF
6.86/3.18	
6.86/3.18	     20: f11 -> f11 : A'=2, B'=free_1, [ 5>=A && B>=1 && A>=3 && free_1>=1 && 3*meter==-2+A && meter>=1 ], cost: 2*meter
6.86/3.18	
6.86/3.18	     21: f11 -> f11 : A'=2, B'=free_1, [ 0>=B && 5>=1+A && 1+A>=3 && free_1>=1 && 3*meter==-1+A && meter>=1 && 2*meter_1==-3-meter+A && meter_1>=1 ], cost: 2*meter_1+2*meter*meter_1
6.86/3.18	
6.86/3.18	     22: f11 -> f11 : A'=2, B'=free_1, [ 5>=A && B>=1 && A>=3 && free_1>=1 && 3*meter==-2+A && meter>=1 && 3*meter_2==-4-meter+A && meter_2>=1 ], cost: 2*meter*meter_2+2*meter_2
6.86/3.18	
6.86/3.18	     10: f0 -> f11 : A'=free_3, B'=free_4, C'=free_3, [], cost: 1
6.86/3.18	
6.86/3.18	
6.86/3.18	
6.86/3.18	Chained accelerated rules (with incoming rules):
6.86/3.18	
6.86/3.18	   Start location: f0
6.86/3.18	
6.86/3.18	     10: f0 -> f11 : A'=free_3, B'=free_4, C'=free_3, [], cost: 1
6.86/3.18	
6.86/3.18	     23: f0 -> f11 : A'=2, B'=free_1, C'=free_3, [ 5>=free_3 && free_3>=3 ], cost: 1+free_3
6.86/3.18	
6.86/3.18	     24: f0 -> [9] : A'=free_3, B'=free_4, C'=free_3, [ free_3>=6 ], cost: INF
6.86/3.18	
6.86/3.18	     25: f0 -> f11 : A'=6, B'=free_2, C'=free_3, [ 5>=free_3 && 0>=free_2 ], cost: 13-2*free_3
6.86/3.18	
6.86/3.18	     26: f0 -> [9] : A'=free_3, B'=free_4, C'=free_3, [ free_4>=1 && 2>=free_3 ], cost: INF
6.86/3.18	
6.86/3.18	     27: f0 -> f11 : A'=2, B'=free_1, C'=2+3*meter, [ 5>=2+3*meter && 2+3*meter>=3 && free_1>=1 && meter>=1 ], cost: 1+2*meter
6.86/3.18	
6.86/3.18	
6.86/3.18	
6.86/3.18	Removed unreachable locations (and leaf rules with constant cost):
6.86/3.18	
6.86/3.18	   Start location: f0
6.86/3.18	
6.86/3.18	     23: f0 -> f11 : A'=2, B'=free_1, C'=free_3, [ 5>=free_3 && free_3>=3 ], cost: 1+free_3
6.86/3.18	
6.86/3.18	     24: f0 -> [9] : A'=free_3, B'=free_4, C'=free_3, [ free_3>=6 ], cost: INF
6.86/3.18	
6.86/3.18	     25: f0 -> f11 : A'=6, B'=free_2, C'=free_3, [ 5>=free_3 && 0>=free_2 ], cost: 13-2*free_3
6.86/3.18	
6.86/3.18	     26: f0 -> [9] : A'=free_3, B'=free_4, C'=free_3, [ free_4>=1 && 2>=free_3 ], cost: INF
6.86/3.18	
6.86/3.18	     27: f0 -> f11 : A'=2, B'=free_1, C'=2+3*meter, [ 5>=2+3*meter && 2+3*meter>=3 && free_1>=1 && meter>=1 ], cost: 1+2*meter
6.86/3.18	
6.86/3.18	
6.86/3.18	
6.86/3.18	### Computing asymptotic complexity ###
6.86/3.18	
6.86/3.18	
6.86/3.18	
6.86/3.18	Fully simplified ITS problem
6.86/3.18	
6.86/3.18	   Start location: f0
6.86/3.18	
6.86/3.18	     23: f0 -> f11 : A'=2, B'=free_1, C'=free_3, [ 5>=free_3 && free_3>=3 ], cost: 1+free_3
6.86/3.18	
6.86/3.18	     24: f0 -> [9] : A'=free_3, B'=free_4, C'=free_3, [ free_3>=6 ], cost: INF
6.86/3.18	
6.86/3.18	     25: f0 -> f11 : A'=6, B'=free_2, C'=free_3, [ 5>=free_3 && 0>=free_2 ], cost: 13-2*free_3
6.86/3.18	
6.86/3.18	     26: f0 -> [9] : A'=free_3, B'=free_4, C'=free_3, [ free_4>=1 && 2>=free_3 ], cost: INF
6.86/3.18	
6.86/3.18	     27: f0 -> f11 : A'=2, B'=free_1, C'=2+3*meter, [ 5>=2+3*meter && 2+3*meter>=3 && free_1>=1 && meter>=1 ], cost: 1+2*meter
6.86/3.18	
6.86/3.18	
6.86/3.18	
6.86/3.18	Computing asymptotic complexity for rule 23
6.86/3.18	
6.86/3.18	   Could not solve the limit problem.
6.86/3.18	
6.86/3.18	   Resulting cost 0 has complexity: Unknown
6.86/3.18	
6.86/3.18	
6.86/3.18	
6.86/3.18	Computing asymptotic complexity for rule 24
6.86/3.18	
6.86/3.18	   Resulting cost INF has complexity: Nonterm
6.86/3.18	
6.86/3.18	
6.86/3.18	
6.86/3.18	Found new complexity Nonterm.
6.86/3.18	
6.86/3.18	
6.86/3.18	
6.86/3.18	Obtained the following overall complexity (w.r.t. the length of the input n):
6.86/3.18	
6.86/3.18	   Complexity:  Nonterm
6.86/3.18	
6.86/3.18	   Cpx degree:  Nonterm
6.86/3.18	
6.86/3.18	   Solved cost: INF
6.86/3.18	
6.86/3.18	   Rule cost:   INF
6.86/3.18	
6.86/3.18	   Rule guard:  [ free_3>=6 ]
6.86/3.18	
6.86/3.18	
6.86/3.18	
6.86/3.18	NO
6.86/3.19	
6.86/3.19	
6.86/3.19	----------------------------------------
6.86/3.19	
6.86/3.19	(2)
6.86/3.19	BOUNDS(INF, INF)
6.86/3.20	EOF