5.50/2.48	WORST_CASE(NON_POLY, ?)
5.50/2.48	proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat
5.50/2.48	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
5.50/2.48	
5.50/2.48	
5.50/2.48	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF).
5.50/2.48	
5.50/2.48	(0) CpxIntTrs
5.50/2.48	(1) Loat Proof [FINISHED, 809 ms]
5.50/2.48	(2) BOUNDS(INF, INF)
5.50/2.48	
5.50/2.48	
5.50/2.48	----------------------------------------
5.50/2.48	
5.50/2.48	(0)
5.50/2.48	Obligation:
5.50/2.48	Complexity Int TRS consisting of the following rules:
5.50/2.48	f0(A, B, C) -> Com_1(f1(0, B, C)) :|: TRUE
5.50/2.48	f1(A, B, C) -> Com_1(f1(A, B - 1, D)) :|: B >= 1 && D >= 1
5.50/2.48	f1(A, B, C) -> Com_1(f1(A, B - 2, D)) :|: B >= 1 && 0 >= D
5.50/2.48	f1(A, B, C) -> Com_1(f4(A, B, D)) :|: 0 >= B
5.50/2.48	f4(A, B, C) -> Com_1(f4(1, B, D)) :|: C >= 1
5.50/2.48	f4(A, B, C) -> Com_1(f4(2, B, D)) :|: 0 >= C
5.50/2.48	
5.50/2.48	The start-symbols are:[f0_3]
5.50/2.48	
5.50/2.48	
5.50/2.48	----------------------------------------
5.50/2.48	
5.50/2.48	(1) Loat Proof (FINISHED)
5.50/2.48	
5.50/2.48	
5.50/2.48	### Pre-processing the ITS problem ###
5.50/2.48	
5.50/2.48	
5.50/2.48	
5.50/2.48	Initial linear ITS problem
5.50/2.48	
5.50/2.48	   Start location: f0
5.50/2.48	
5.50/2.48	      0: f0 -> f1 : A'=0, [], cost: 1
5.50/2.48	
5.50/2.48	      1: f1 -> f1 : B'=-1+B, C'=free, [ B>=1 && free>=1 ], cost: 1
5.50/2.48	
5.50/2.48	      2: f1 -> f1 : B'=-2+B, C'=free_1, [ B>=1 && 0>=free_1 ], cost: 1
5.50/2.48	
5.50/2.48	      3: f1 -> f4 : C'=free_2, [ 0>=B ], cost: 1
5.50/2.48	
5.50/2.48	      4: f4 -> f4 : A'=1, C'=free_3, [ C>=1 ], cost: 1
5.50/2.48	
5.50/2.48	      5: f4 -> f4 : A'=2, C'=free_4, [ 0>=C ], cost: 1
5.50/2.48	
5.50/2.48	
5.50/2.48	
5.50/2.48	### Simplification by acceleration and chaining ###
5.50/2.48	
5.50/2.48	
5.50/2.48	
5.50/2.48	Accelerating simple loops of location 1.
5.50/2.48	
5.50/2.48	   Accelerating the following rules:
5.50/2.48	
5.50/2.48	      1: f1 -> f1 : B'=-1+B, C'=free, [ B>=1 && free>=1 ], cost: 1
5.50/2.48	
5.50/2.48	      2: f1 -> f1 : B'=-2+B, C'=free_1, [ B>=1 && 0>=free_1 ], cost: 1
5.50/2.48	
5.50/2.48	
5.50/2.48	
5.50/2.48	   Accelerated rule 1 with metering function B, yielding the new rule 6.
5.50/2.48	
5.50/2.48	   Accelerated rule 2 with metering function meter (where 2*meter==B), yielding the new rule 7.
5.50/2.48	
5.50/2.48	      During metering: Instantiating temporary variables by {meter==1}
5.50/2.48	
5.50/2.48	   Removing the simple loops: 1 2.
5.50/2.48	
5.50/2.48	
5.50/2.48	
5.50/2.48	Accelerating simple loops of location 2.
5.50/2.48	
5.50/2.48	   Accelerating the following rules:
5.50/2.48	
5.50/2.48	      4: f4 -> f4 : A'=1, C'=free_3, [ C>=1 ], cost: 1
5.50/2.48	
5.50/2.48	      5: f4 -> f4 : A'=2, C'=free_4, [ 0>=C ], cost: 1
5.50/2.48	
5.50/2.48	
5.50/2.48	
5.50/2.48	   Accelerated rule 4 with NONTERM (after strengthening guard), yielding the new rule 8.
5.50/2.48	
5.50/2.48	   Accelerated rule 5 with NONTERM (after strengthening guard), yielding the new rule 9.
5.50/2.48	
5.50/2.48	   Removing the simple loops:.
5.50/2.48	
5.50/2.48	
5.50/2.48	
5.50/2.48	Accelerated all simple loops using metering functions (where possible):
5.50/2.48	
5.50/2.48	   Start location: f0
5.50/2.48	
5.50/2.48	      0: f0 -> f1 : A'=0, [], cost: 1
5.50/2.48	
5.50/2.48	      3: f1 -> f4 : C'=free_2, [ 0>=B ], cost: 1
5.50/2.48	
5.50/2.48	      6: f1 -> f1 : B'=0, C'=free, [ B>=1 && free>=1 ], cost: B
5.50/2.48	
5.50/2.48	      7: f1 -> f1 : B'=-2*meter+B, C'=free_1, [ B>=1 && 0>=free_1 && 2*meter==B && meter>=1 ], cost: meter
5.50/2.48	
5.50/2.48	      4: f4 -> f4 : A'=1, C'=free_3, [ C>=1 ], cost: 1
5.50/2.48	
5.50/2.48	      5: f4 -> f4 : A'=2, C'=free_4, [ 0>=C ], cost: 1
5.50/2.48	
5.50/2.48	      8: f4 -> [4] : [ C>=1 && free_3>=1 ], cost: INF
5.50/2.48	
5.50/2.48	      9: f4 -> [4] : [ 0>=C && 0>=free_4 ], cost: INF
5.50/2.48	
5.50/2.48	
5.50/2.48	
5.50/2.48	Chained accelerated rules (with incoming rules):
5.50/2.48	
5.50/2.48	   Start location: f0
5.50/2.48	
5.50/2.48	      0: f0 -> f1 : A'=0, [], cost: 1
5.50/2.48	
5.50/2.48	     10: f0 -> f1 : A'=0, B'=0, C'=free, [ B>=1 && free>=1 ], cost: 1+B
5.50/2.48	
5.50/2.48	     11: f0 -> f1 : A'=0, B'=-2*meter+B, C'=free_1, [ B>=1 && 0>=free_1 && 2*meter==B && meter>=1 ], cost: 1+meter
5.50/2.48	
5.50/2.48	      3: f1 -> f4 : C'=free_2, [ 0>=B ], cost: 1
5.50/2.48	
5.50/2.48	     12: f1 -> f4 : A'=1, C'=free_3, [ 0>=B ], cost: 2
5.50/2.48	
5.50/2.48	     13: f1 -> f4 : A'=2, C'=free_4, [ 0>=B ], cost: 2
5.50/2.48	
5.50/2.48	     14: f1 -> [4] : C'=free_2, [ 0>=B && free_2>=1 ], cost: INF
5.50/2.48	
5.50/2.48	     15: f1 -> [4] : C'=free_2, [ 0>=B && 0>=free_2 ], cost: INF
5.50/2.48	
5.50/2.48	
5.50/2.48	
5.50/2.48	Removed unreachable locations (and leaf rules with constant cost):
5.50/2.48	
5.50/2.48	   Start location: f0
5.50/2.48	
5.50/2.48	      0: f0 -> f1 : A'=0, [], cost: 1
5.50/2.48	
5.50/2.48	     10: f0 -> f1 : A'=0, B'=0, C'=free, [ B>=1 && free>=1 ], cost: 1+B
5.50/2.48	
5.50/2.48	     11: f0 -> f1 : A'=0, B'=-2*meter+B, C'=free_1, [ B>=1 && 0>=free_1 && 2*meter==B && meter>=1 ], cost: 1+meter
5.50/2.48	
5.50/2.48	     14: f1 -> [4] : C'=free_2, [ 0>=B && free_2>=1 ], cost: INF
5.50/2.48	
5.50/2.48	     15: f1 -> [4] : C'=free_2, [ 0>=B && 0>=free_2 ], cost: INF
5.50/2.48	
5.50/2.48	
5.50/2.48	
5.50/2.48	Eliminated locations (on tree-shaped paths):
5.50/2.48	
5.50/2.48	   Start location: f0
5.50/2.48	
5.50/2.48	     16: f0 -> [4] : A'=0, C'=free_2, [ 0>=B && free_2>=1 ], cost: INF
5.50/2.48	
5.50/2.48	     17: f0 -> [4] : A'=0, C'=free_2, [ 0>=B && 0>=free_2 ], cost: INF
5.50/2.48	
5.50/2.48	     18: f0 -> [4] : A'=0, B'=0, C'=free_2, [ B>=1 && free>=1 && free_2>=1 ], cost: INF
5.50/2.48	
5.50/2.48	     19: f0 -> [4] : A'=0, B'=0, C'=free_2, [ B>=1 && free>=1 && 0>=free_2 ], cost: INF
5.50/2.48	
5.50/2.48	     20: f0 -> [4] : A'=0, B'=-2*meter+B, C'=free_2, [ B>=1 && 0>=free_1 && 2*meter==B && meter>=1 && free_2>=1 ], cost: INF
5.50/2.48	
5.50/2.48	     21: f0 -> [4] : A'=0, B'=-2*meter+B, C'=free_2, [ B>=1 && 0>=free_1 && 2*meter==B && meter>=1 && 0>=free_2 ], cost: INF
5.50/2.48	
5.50/2.48	
5.50/2.48	
5.50/2.48	Applied pruning (of leafs and parallel rules):
5.50/2.48	
5.50/2.48	   Start location: f0
5.50/2.48	
5.50/2.48	     16: f0 -> [4] : A'=0, C'=free_2, [ 0>=B && free_2>=1 ], cost: INF
5.50/2.48	
5.50/2.48	     17: f0 -> [4] : A'=0, C'=free_2, [ 0>=B && 0>=free_2 ], cost: INF
5.50/2.48	
5.50/2.48	     18: f0 -> [4] : A'=0, B'=0, C'=free_2, [ B>=1 && free>=1 && free_2>=1 ], cost: INF
5.50/2.48	
5.50/2.48	     19: f0 -> [4] : A'=0, B'=0, C'=free_2, [ B>=1 && free>=1 && 0>=free_2 ], cost: INF
5.50/2.48	
5.50/2.48	     21: f0 -> [4] : A'=0, B'=-2*meter+B, C'=free_2, [ B>=1 && 0>=free_1 && 2*meter==B && meter>=1 && 0>=free_2 ], cost: INF
5.50/2.48	
5.50/2.48	
5.50/2.48	
5.50/2.48	### Computing asymptotic complexity ###
5.50/2.48	
5.50/2.48	
5.50/2.48	
5.50/2.48	Fully simplified ITS problem
5.50/2.48	
5.50/2.48	   Start location: f0
5.50/2.48	
5.50/2.48	     16: f0 -> [4] : A'=0, C'=free_2, [ 0>=B && free_2>=1 ], cost: INF
5.50/2.48	
5.50/2.48	     17: f0 -> [4] : A'=0, C'=free_2, [ 0>=B && 0>=free_2 ], cost: INF
5.50/2.48	
5.50/2.48	     18: f0 -> [4] : A'=0, B'=0, C'=free_2, [ B>=1 && free>=1 && free_2>=1 ], cost: INF
5.50/2.48	
5.50/2.48	     19: f0 -> [4] : A'=0, B'=0, C'=free_2, [ B>=1 && free>=1 && 0>=free_2 ], cost: INF
5.50/2.48	
5.50/2.48	     21: f0 -> [4] : A'=0, B'=-2*meter+B, C'=free_2, [ B>=1 && 0>=free_1 && 2*meter==B && meter>=1 && 0>=free_2 ], cost: INF
5.50/2.48	
5.50/2.48	
5.50/2.48	
5.50/2.48	Computing asymptotic complexity for rule 16
5.50/2.48	
5.50/2.48	   Resulting cost INF has complexity: Nonterm
5.50/2.48	
5.50/2.48	
5.50/2.48	
5.50/2.48	Found new complexity Nonterm.
5.50/2.48	
5.50/2.48	
5.50/2.48	
5.50/2.48	Obtained the following overall complexity (w.r.t. the length of the input n):
5.50/2.48	
5.50/2.48	   Complexity:  Nonterm
5.50/2.48	
5.50/2.48	   Cpx degree:  Nonterm
5.50/2.48	
5.50/2.48	   Solved cost: INF
5.50/2.48	
5.50/2.48	   Rule cost:   INF
5.50/2.48	
5.50/2.48	   Rule guard:  [ 0>=B && free_2>=1 ]
5.50/2.48	
5.50/2.48	
5.50/2.48	
5.50/2.48	NO
5.50/2.48	
5.50/2.48	
5.50/2.48	----------------------------------------
5.50/2.48	
5.50/2.48	(2)
5.50/2.48	BOUNDS(INF, INF)
5.55/6.62	EOF