6.65/3.06	MAYBE
6.65/3.07	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
6.65/3.07	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
6.65/3.07	
6.65/3.07	
6.65/3.07	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(1, INF).
6.65/3.07	
6.65/3.07	(0) CpxIntTrs
6.65/3.07	(1) Loat Proof [FINISHED, 1411 ms]
6.65/3.07	(2) BOUNDS(1, INF)
6.65/3.07	
6.65/3.07	
6.65/3.07	----------------------------------------
6.65/3.07	
6.65/3.07	(0)
6.65/3.07	Obligation:
6.65/3.07	Complexity Int TRS consisting of the following rules:
6.65/3.07	f0(A, B) -> Com_1(f2(C, D)) :|: C >= 1 && C >= 5 && C >= 2 && C >= 3
6.65/3.07	f0(A, B) -> Com_1(f2(1, C)) :|: 0 >= 4 && 0 >= 1
6.65/3.07	f0(A, B) -> Com_1(f2(C, D)) :|: C >= 1 && C >= 5 && 0 >= C && C >= 3
6.65/3.07	f0(A, B) -> Com_1(f2(3, C)) :|: TRUE
6.65/3.07	f0(A, B) -> Com_1(f2(1, C)) :|: 0 >= 1
6.65/3.07	f0(A, B) -> Com_1(f2(3, C)) :|: 0 >= 3
6.65/3.07	f2(A, B) -> Com_1(f2(B, C)) :|: B >= 5 && B >= 2 && B >= 3 && A >= 2 * B && A <= 2 * B
6.65/3.07	f2(A, B) -> Com_1(f2(B, C)) :|: B >= 5 && B >= 2 && 1 >= B && A >= 2 * B && A <= 2 * B
6.65/3.07	f2(A, B) -> Com_1(f2(B, C)) :|: B >= 5 && 0 >= B && B >= 3 && A >= 2 * B && A <= 2 * B
6.65/3.07	f2(A, B) -> Com_1(f2(B, C)) :|: B >= 5 && 0 >= B && 1 >= B && A >= 2 * B && A <= 2 * B
6.65/3.07	f2(A, B) -> Com_1(f2(B, C)) :|: B >= 3 && B <= 3 && A >= 6 && A <= 6
6.65/3.07	f2(A, B) -> Com_1(f2(B, C)) :|: 3 >= B && B >= 2 && 1 >= B && A >= 2 * B && A <= 2 * B
6.65/3.07	f2(A, B) -> Com_1(f2(B, C)) :|: 0 >= 3 && B >= 3 && B <= 3 && A >= 6 && A <= 6
6.65/3.07	f2(A, B) -> Com_1(f2(B, C)) :|: 3 >= B && 0 >= B && 1 >= B && A >= 2 * B && A <= 2 * B
6.65/3.07	f2(A, B) -> Com_1(f2(6 * B + 4, C)) :|: 6 * B >= 1 && 6 * B + 2 >= 0 && 6 * B + 1 >= 0 && A >= 2 * B + 1 && A <= 2 * B + 1
6.65/3.07	f2(A, B) -> Com_1(f2(6 * B + 4, C)) :|: 6 * B >= 1 && 6 * B + 2 >= 0 && 0 >= 3 + 6 * B && A >= 2 * B + 1 && A <= 2 * B + 1
6.65/3.07	f2(A, B) -> Com_1(f2(6 * B + 4, C)) :|: 6 * B >= 1 && 0 >= 4 + 6 * B && 6 * B + 1 >= 0 && A >= 2 * B + 1 && A <= 2 * B + 1
6.65/3.07	f2(A, B) -> Com_1(f2(6 * B + 4, C)) :|: 6 * B >= 1 && 0 >= 4 + 6 * B && 0 >= 3 + 6 * B && A >= 2 * B + 1 && A <= 2 * B + 1
6.65/3.07	f2(A, B) -> Com_1(f2(6 * B + 4, C)) :|: 0 >= 6 * B + 1 && 6 * B + 2 >= 0 && 6 * B + 1 >= 0 && A >= 2 * B + 1 && A <= 2 * B + 1
6.65/3.07	f2(A, B) -> Com_1(f2(6 * B + 4, C)) :|: 0 >= 6 * B + 1 && 6 * B + 2 >= 0 && 0 >= 3 + 6 * B && A >= 2 * B + 1 && A <= 2 * B + 1
6.65/3.07	f2(A, B) -> Com_1(f2(6 * B + 4, C)) :|: 0 >= 6 * B + 1 && 0 >= 4 + 6 * B && 6 * B + 1 >= 0 && A >= 2 * B + 1 && A <= 2 * B + 1
6.65/3.07	f2(A, B) -> Com_1(f2(6 * B + 4, C)) :|: 0 >= 6 * B + 1 && 0 >= 4 + 6 * B && 0 >= 3 + 6 * B && A >= 2 * B + 1 && A <= 2 * B + 1
6.65/3.07	
6.65/3.07	The start-symbols are:[f0_2]
6.65/3.07	
6.65/3.07	
6.65/3.07	----------------------------------------
6.65/3.07	
6.65/3.07	(1) Loat Proof (FINISHED)
6.65/3.07	
6.65/3.07	
6.65/3.07	### Pre-processing the ITS problem ###
6.65/3.07	
6.65/3.07	
6.65/3.07	
6.65/3.07	Initial linear ITS problem
6.65/3.07	
6.65/3.07	   Start location: f0
6.65/3.07	
6.65/3.07	      0: f0 -> f2 : A'=free, B'=free_1, [ free>=1 && free>=5 && free>=2 && free>=3 ], cost: 1
6.65/3.07	
6.65/3.07	      1: f0 -> f2 : A'=1, B'=free_2, [ 0>=4 && 0>=1 ], cost: 1
6.65/3.07	
6.65/3.07	      2: f0 -> f2 : A'=free_3, B'=free_4, [ free_3>=1 && free_3>=5 && 0>=free_3 && free_3>=3 ], cost: 1
6.65/3.07	
6.65/3.07	      3: f0 -> f2 : A'=3, B'=free_5, [], cost: 1
6.65/3.07	
6.65/3.07	      4: f0 -> f2 : A'=1, B'=free_6, [ 0>=1 ], cost: 1
6.65/3.07	
6.65/3.07	      5: f0 -> f2 : A'=3, B'=free_7, [ 0>=3 ], cost: 1
6.65/3.07	
6.65/3.07	      6: f2 -> f2 : A'=B, B'=free_8, [ B>=5 && B>=2 && B>=3 && A==2*B ], cost: 1
6.65/3.07	
6.65/3.07	      7: f2 -> f2 : A'=B, B'=free_9, [ B>=5 && B>=2 && 1>=B && A==2*B ], cost: 1
6.65/3.07	
6.65/3.07	      8: f2 -> f2 : A'=B, B'=free_10, [ B>=5 && 0>=B && B>=3 && A==2*B ], cost: 1
6.65/3.07	
6.65/3.07	      9: f2 -> f2 : A'=B, B'=free_11, [ B>=5 && 0>=B && 1>=B && A==2*B ], cost: 1
6.65/3.07	
6.65/3.07	     10: f2 -> f2 : A'=B, B'=free_12, [ B==3 && A==6 ], cost: 1
6.65/3.07	
6.65/3.07	     11: f2 -> f2 : A'=B, B'=free_13, [ 3>=B && B>=2 && 1>=B && A==2*B ], cost: 1
6.65/3.07	
6.65/3.07	     12: f2 -> f2 : A'=B, B'=free_14, [ 0>=3 && B==3 && A==6 ], cost: 1
6.65/3.07	
6.65/3.07	     13: f2 -> f2 : A'=B, B'=free_15, [ 3>=B && 0>=B && 1>=B && A==2*B ], cost: 1
6.65/3.07	
6.65/3.07	     14: f2 -> f2 : A'=4+6*B, B'=free_16, [ 6*B>=1 && 2+6*B>=0 && 1+6*B>=0 && A==1+2*B ], cost: 1
6.65/3.07	
6.65/3.07	     15: f2 -> f2 : A'=4+6*B, B'=free_17, [ 6*B>=1 && 2+6*B>=0 && 0>=3+6*B && A==1+2*B ], cost: 1
6.65/3.07	
6.65/3.07	     16: f2 -> f2 : A'=4+6*B, B'=free_18, [ 6*B>=1 && 0>=4+6*B && 1+6*B>=0 && A==1+2*B ], cost: 1
6.65/3.07	
6.65/3.07	     17: f2 -> f2 : A'=4+6*B, B'=free_19, [ 6*B>=1 && 0>=4+6*B && 0>=3+6*B && A==1+2*B ], cost: 1
6.65/3.07	
6.65/3.07	     18: f2 -> f2 : A'=4+6*B, B'=free_20, [ 0>=1+6*B && 2+6*B>=0 && 1+6*B>=0 && A==1+2*B ], cost: 1
6.65/3.07	
6.65/3.07	     19: f2 -> f2 : A'=4+6*B, B'=free_21, [ 0>=1+6*B && 2+6*B>=0 && 0>=3+6*B && A==1+2*B ], cost: 1
6.65/3.07	
6.65/3.07	     20: f2 -> f2 : A'=4+6*B, B'=free_22, [ 0>=1+6*B && 0>=4+6*B && 1+6*B>=0 && A==1+2*B ], cost: 1
6.65/3.07	
6.65/3.07	     21: f2 -> f2 : A'=4+6*B, B'=free_23, [ 0>=1+6*B && 0>=4+6*B && 0>=3+6*B && A==1+2*B ], cost: 1
6.65/3.07	
6.65/3.07	
6.65/3.07	
6.65/3.07	Removed rules with unsatisfiable guard:
6.65/3.07	
6.65/3.07	   Start location: f0
6.65/3.07	
6.65/3.07	      0: f0 -> f2 : A'=free, B'=free_1, [ free>=1 && free>=5 && free>=2 && free>=3 ], cost: 1
6.65/3.07	
6.65/3.07	      3: f0 -> f2 : A'=3, B'=free_5, [], cost: 1
6.65/3.07	
6.65/3.07	      6: f2 -> f2 : A'=B, B'=free_8, [ B>=5 && B>=2 && B>=3 && A==2*B ], cost: 1
6.65/3.07	
6.65/3.07	     10: f2 -> f2 : A'=B, B'=free_12, [ B==3 && A==6 ], cost: 1
6.65/3.07	
6.65/3.07	     13: f2 -> f2 : A'=B, B'=free_15, [ 3>=B && 0>=B && 1>=B && A==2*B ], cost: 1
6.65/3.07	
6.65/3.07	     14: f2 -> f2 : A'=4+6*B, B'=free_16, [ 6*B>=1 && 2+6*B>=0 && 1+6*B>=0 && A==1+2*B ], cost: 1
6.65/3.07	
6.65/3.07	     21: f2 -> f2 : A'=4+6*B, B'=free_23, [ 0>=1+6*B && 0>=4+6*B && 0>=3+6*B && A==1+2*B ], cost: 1
6.65/3.07	
6.65/3.07	
6.65/3.07	
6.65/3.07	Simplified all rules, resulting in:
6.65/3.07	
6.65/3.07	   Start location: f0
6.65/3.07	
6.65/3.07	      0: f0 -> f2 : A'=free, B'=free_1, [ free>=5 ], cost: 1
6.65/3.07	
6.65/3.07	      3: f0 -> f2 : A'=3, B'=free_5, [], cost: 1
6.65/3.07	
6.65/3.07	      6: f2 -> f2 : A'=B, B'=free_8, [ B>=5 && A==2*B ], cost: 1
6.65/3.07	
6.65/3.07	     10: f2 -> f2 : A'=B, B'=free_12, [ B==3 && A==6 ], cost: 1
6.65/3.07	
6.65/3.07	     13: f2 -> f2 : A'=B, B'=free_15, [ 0>=B && A==2*B ], cost: 1
6.65/3.07	
6.65/3.07	     14: f2 -> f2 : A'=4+6*B, B'=free_16, [ 6*B>=1 && A==1+2*B ], cost: 1
6.65/3.07	
6.65/3.07	     21: f2 -> f2 : A'=4+6*B, B'=free_23, [ 0>=4+6*B && A==1+2*B ], cost: 1
6.65/3.07	
6.65/3.07	
6.65/3.07	
6.65/3.07	### Simplification by acceleration and chaining ###
6.65/3.07	
6.65/3.07	
6.65/3.07	
6.65/3.07	Accelerating simple loops of location 1.
6.65/3.07	
6.65/3.07	   Accelerating the following rules:
6.65/3.07	
6.65/3.07	      6: f2 -> f2 : A'=B, B'=free_8, [ B>=5 && A==2*B ], cost: 1
6.65/3.07	
6.65/3.07	     10: f2 -> f2 : A'=B, B'=free_12, [ B==3 && A==6 ], cost: 1
6.65/3.07	
6.65/3.07	     13: f2 -> f2 : A'=B, B'=free_15, [ 0>=B && A==2*B ], cost: 1
6.65/3.07	
6.65/3.07	     14: f2 -> f2 : A'=4+6*B, B'=free_16, [ 6*B>=1 && A==1+2*B ], cost: 1
6.65/3.07	
6.65/3.07	     21: f2 -> f2 : A'=4+6*B, B'=free_23, [ 0>=4+6*B && A==1+2*B ], cost: 1
6.65/3.07	
6.65/3.07	
6.65/3.07	
6.65/3.07	      During metering: Instantiating temporary variables by {free_8==5}
6.65/3.07	
6.65/3.07	   Accelerated rule 6 with metering function meter (where 5*meter==-9+B) (after strengthening guard), yielding the new rule 22.
6.65/3.07	
6.65/3.07	   Accelerated rule 10 with metering function meter_1 (where 3*meter_1==-6+A), yielding the new rule 23.
6.65/3.07	
6.65/3.07	   Found no metering function for rule 13.
6.65/3.07	
6.65/3.07	   Accelerated rule 14 with NONTERM (after strengthening guard), yielding the new rule 24.
6.65/3.07	
6.65/3.07	   Accelerated rule 21 with NONTERM (after strengthening guard), yielding the new rule 25.
6.65/3.07	
6.65/3.07	   Removing the simple loops: 10.
6.65/3.07	
6.65/3.07	
6.65/3.07	
6.65/3.07	Accelerated all simple loops using metering functions (where possible):
6.65/3.07	
6.65/3.07	   Start location: f0
6.65/3.07	
6.65/3.07	      0: f0 -> f2 : A'=free, B'=free_1, [ free>=5 ], cost: 1
6.65/3.07	
6.65/3.07	      3: f0 -> f2 : A'=3, B'=free_5, [], cost: 1
6.65/3.07	
6.65/3.07	      6: f2 -> f2 : A'=B, B'=free_8, [ B>=5 && A==2*B ], cost: 1
6.65/3.07	
6.65/3.07	     13: f2 -> f2 : A'=B, B'=free_15, [ 0>=B && A==2*B ], cost: 1
6.65/3.07	
6.65/3.07	     14: f2 -> f2 : A'=4+6*B, B'=free_16, [ 6*B>=1 && A==1+2*B ], cost: 1
6.65/3.07	
6.65/3.07	     21: f2 -> f2 : A'=4+6*B, B'=free_23, [ 0>=4+6*B && A==1+2*B ], cost: 1
6.65/3.07	
6.65/3.07	     22: f2 -> f2 : A'=5, B'=5, [ A==2*B && B==10 && 5*meter==-9+B && meter>=1 ], cost: meter
6.65/3.07	
6.65/3.07	     23: f2 -> f2 : A'=free_12, B'=free_12, [ B==3 && A==6 && 3*meter_1==-6+A && meter_1>=1 ], cost: meter_1
6.65/3.07	
6.65/3.07	     24: f2 -> [2] : [ 6*B>=1 && A==1+2*B && 6*free_16>=1 && 4+6*B==1+2*free_16 ], cost: INF
6.65/3.07	
6.65/3.07	     25: f2 -> [2] : [ 0>=4+6*B && A==1+2*B && 0>=4+6*free_23 && 4+6*B==1+2*free_23 ], cost: INF
6.65/3.07	
6.65/3.07	
6.65/3.07	
6.65/3.07	Chained accelerated rules (with incoming rules):
6.65/3.07	
6.65/3.07	   Start location: f0
6.65/3.07	
6.65/3.07	      0: f0 -> f2 : A'=free, B'=free_1, [ free>=5 ], cost: 1
6.65/3.07	
6.65/3.07	      3: f0 -> f2 : A'=3, B'=free_5, [], cost: 1
6.65/3.07	
6.65/3.07	     26: f0 -> f2 : A'=free_1, B'=free_8, [ 2*free_1>=5 && free_1>=5 ], cost: 2
6.65/3.07	
6.65/3.07	     27: f0 -> f2 : A'=4+6*free_1, B'=free_16, [ 1+2*free_1>=5 && 6*free_1>=1 ], cost: 2
6.65/3.07	
6.65/3.07	     28: f0 -> f2 : A'=10, B'=free_16, [], cost: 2
6.65/3.07	
6.65/3.07	
6.65/3.07	
6.65/3.07	Removed unreachable locations (and leaf rules with constant cost):
6.65/3.07	
6.65/3.07	   Start location: f0
6.65/3.07	
6.65/3.07	
6.65/3.07	
6.65/3.07	### Computing asymptotic complexity ###
6.65/3.07	
6.65/3.07	
6.65/3.07	
6.65/3.07	Fully simplified ITS problem
6.65/3.07	
6.65/3.07	   Start location: f0
6.65/3.07	
6.65/3.07	
6.65/3.07	
6.65/3.07	Obtained the following overall complexity (w.r.t. the length of the input n):
6.65/3.07	
6.65/3.07	   Complexity:  Unknown
6.65/3.07	
6.65/3.07	   Cpx degree:  ?
6.65/3.07	
6.65/3.07	   Solved cost: 0
6.65/3.07	
6.65/3.07	   Rule cost:   0
6.65/3.07	
6.65/3.07	   Rule guard:  []
6.65/3.07	
6.65/3.07	
6.65/3.07	
6.65/3.07	WORST_CASE(Omega(0),?)
6.65/3.07	
6.65/3.07	
6.65/3.07	----------------------------------------
6.65/3.07	
6.65/3.07	(2)
6.65/3.07	BOUNDS(1, INF)
6.76/3.11	EOF