1009.80/291.86	WORST_CASE(Omega(n^1), O(n^2))
1009.80/291.87	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
1009.80/291.87	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
1009.80/291.87	
1009.80/291.87	(0) CpxTRS
1009.80/291.87	(1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
1009.80/291.87	(2) CpxWeightedTrs
1009.80/291.87	    (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
1009.80/291.87	    (4) CpxTypedWeightedTrs
1009.80/291.87	    (5) CompletionProof [UPPER BOUND(ID), 0 ms]
1009.80/291.87	    (6) CpxTypedWeightedCompleteTrs
1009.80/291.87	    (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
1009.80/291.87	    (8) CpxRNTS
1009.80/291.87	    (9) CompleteCoflocoProof [FINISHED, 531 ms]
1009.80/291.87	    (10) BOUNDS(1, n^2)
1009.80/291.87	(11) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
1009.80/291.87	(12) TRS for Loop Detection
1009.80/291.87	    (13) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
1009.80/291.87	    (14) BEST
1009.80/291.87	        (15) proven lower bound
1009.80/291.87	            (16) LowerBoundPropagationProof [FINISHED, 0 ms]
1009.80/291.87	            (17) BOUNDS(n^1, INF)
1009.80/291.87	        (18) TRS for Loop Detection
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	----------------------------------------
1009.80/291.87	
1009.80/291.87	(0)
1009.80/291.87	Obligation:
1009.80/291.87	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	The TRS R consists of the following rules:
1009.80/291.87	
1009.80/291.87	   half(0) -> 0
1009.80/291.87	   half(s(0)) -> 0
1009.80/291.87	   half(s(s(x))) -> s(half(x))
1009.80/291.87	   le(0, y) -> true
1009.80/291.87	   le(s(x), 0) -> false
1009.80/291.87	   le(s(x), s(y)) -> le(x, y)
1009.80/291.87	   inc(0) -> 0
1009.80/291.87	   inc(s(x)) -> s(inc(x))
1009.80/291.87	   log(x) -> log2(x, 0)
1009.80/291.87	   log2(x, y) -> if(le(x, s(0)), x, inc(y))
1009.80/291.87	   if(true, x, s(y)) -> y
1009.80/291.87	   if(false, x, y) -> log2(half(x), y)
1009.80/291.87	
1009.80/291.87	S is empty.
1009.80/291.87	Rewrite Strategy: INNERMOST
1009.80/291.87	----------------------------------------
1009.80/291.87	
1009.80/291.87	(1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
1009.80/291.87	Transformed relative TRS to weighted TRS
1009.80/291.87	----------------------------------------
1009.80/291.87	
1009.80/291.87	(2)
1009.80/291.87	Obligation:
1009.80/291.87	The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2).
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	The TRS R consists of the following rules:
1009.80/291.87	
1009.80/291.87	   half(0) -> 0 [1]
1009.80/291.87	   half(s(0)) -> 0 [1]
1009.80/291.87	   half(s(s(x))) -> s(half(x)) [1]
1009.80/291.87	   le(0, y) -> true [1]
1009.80/291.87	   le(s(x), 0) -> false [1]
1009.80/291.87	   le(s(x), s(y)) -> le(x, y) [1]
1009.80/291.87	   inc(0) -> 0 [1]
1009.80/291.87	   inc(s(x)) -> s(inc(x)) [1]
1009.80/291.87	   log(x) -> log2(x, 0) [1]
1009.80/291.87	   log2(x, y) -> if(le(x, s(0)), x, inc(y)) [1]
1009.80/291.87	   if(true, x, s(y)) -> y [1]
1009.80/291.87	   if(false, x, y) -> log2(half(x), y) [1]
1009.80/291.87	
1009.80/291.87	Rewrite Strategy: INNERMOST
1009.80/291.87	----------------------------------------
1009.80/291.87	
1009.80/291.87	(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
1009.80/291.87	Infered types.
1009.80/291.87	----------------------------------------
1009.80/291.87	
1009.80/291.87	(4)
1009.80/291.87	Obligation:
1009.80/291.87	Runtime Complexity Weighted TRS with Types.
1009.80/291.87	The TRS R consists of the following rules:
1009.80/291.87	
1009.80/291.87	   half(0) -> 0 [1]
1009.80/291.87	   half(s(0)) -> 0 [1]
1009.80/291.87	   half(s(s(x))) -> s(half(x)) [1]
1009.80/291.87	   le(0, y) -> true [1]
1009.80/291.87	   le(s(x), 0) -> false [1]
1009.80/291.87	   le(s(x), s(y)) -> le(x, y) [1]
1009.80/291.87	   inc(0) -> 0 [1]
1009.80/291.87	   inc(s(x)) -> s(inc(x)) [1]
1009.80/291.87	   log(x) -> log2(x, 0) [1]
1009.80/291.87	   log2(x, y) -> if(le(x, s(0)), x, inc(y)) [1]
1009.80/291.87	   if(true, x, s(y)) -> y [1]
1009.80/291.87	   if(false, x, y) -> log2(half(x), y) [1]
1009.80/291.87	
1009.80/291.87	The TRS has the following type information:
1009.80/291.87	half :: 0:s -> 0:s
1009.80/291.87	0 :: 0:s
1009.80/291.87	s :: 0:s -> 0:s
1009.80/291.87	le :: 0:s -> 0:s -> true:false
1009.80/291.87	true :: true:false
1009.80/291.87	false :: true:false
1009.80/291.87	inc :: 0:s -> 0:s
1009.80/291.87	log :: 0:s -> 0:s
1009.80/291.87	log2 :: 0:s -> 0:s -> 0:s
1009.80/291.87	if :: true:false -> 0:s -> 0:s -> 0:s
1009.80/291.87	
1009.80/291.87	Rewrite Strategy: INNERMOST
1009.80/291.87	----------------------------------------
1009.80/291.87	
1009.80/291.87	(5) CompletionProof (UPPER BOUND(ID))
1009.80/291.87	The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added:
1009.80/291.87	
1009.80/291.87	   if(v0, v1, v2) -> null_if [0]
1009.80/291.87	   half(v0) -> null_half [0]
1009.80/291.87	   le(v0, v1) -> null_le [0]
1009.80/291.87	   inc(v0) -> null_inc [0]
1009.80/291.87	
1009.80/291.87	And the following fresh constants:    null_if, null_half, null_le, null_inc
1009.80/291.87	
1009.80/291.87	----------------------------------------
1009.80/291.87	
1009.80/291.87	(6)
1009.80/291.87	Obligation:
1009.80/291.87	Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is:
1009.80/291.87	
1009.80/291.87	Runtime Complexity Weighted TRS with Types.
1009.80/291.87	The TRS R consists of the following rules:
1009.80/291.87	
1009.80/291.87	   half(0) -> 0 [1]
1009.80/291.87	   half(s(0)) -> 0 [1]
1009.80/291.87	   half(s(s(x))) -> s(half(x)) [1]
1009.80/291.87	   le(0, y) -> true [1]
1009.80/291.87	   le(s(x), 0) -> false [1]
1009.80/291.87	   le(s(x), s(y)) -> le(x, y) [1]
1009.80/291.87	   inc(0) -> 0 [1]
1009.80/291.87	   inc(s(x)) -> s(inc(x)) [1]
1009.80/291.87	   log(x) -> log2(x, 0) [1]
1009.80/291.87	   log2(x, y) -> if(le(x, s(0)), x, inc(y)) [1]
1009.80/291.87	   if(true, x, s(y)) -> y [1]
1009.80/291.87	   if(false, x, y) -> log2(half(x), y) [1]
1009.80/291.87	   if(v0, v1, v2) -> null_if [0]
1009.80/291.87	   half(v0) -> null_half [0]
1009.80/291.87	   le(v0, v1) -> null_le [0]
1009.80/291.87	   inc(v0) -> null_inc [0]
1009.80/291.87	
1009.80/291.87	The TRS has the following type information:
1009.80/291.87	half :: 0:s:null_if:null_half:null_inc -> 0:s:null_if:null_half:null_inc
1009.80/291.87	0 :: 0:s:null_if:null_half:null_inc
1009.80/291.87	s :: 0:s:null_if:null_half:null_inc -> 0:s:null_if:null_half:null_inc
1009.80/291.87	le :: 0:s:null_if:null_half:null_inc -> 0:s:null_if:null_half:null_inc -> true:false:null_le
1009.80/291.87	true :: true:false:null_le
1009.80/291.87	false :: true:false:null_le
1009.80/291.87	inc :: 0:s:null_if:null_half:null_inc -> 0:s:null_if:null_half:null_inc
1009.80/291.87	log :: 0:s:null_if:null_half:null_inc -> 0:s:null_if:null_half:null_inc
1009.80/291.87	log2 :: 0:s:null_if:null_half:null_inc -> 0:s:null_if:null_half:null_inc -> 0:s:null_if:null_half:null_inc
1009.80/291.87	if :: true:false:null_le -> 0:s:null_if:null_half:null_inc -> 0:s:null_if:null_half:null_inc -> 0:s:null_if:null_half:null_inc
1009.80/291.87	null_if :: 0:s:null_if:null_half:null_inc
1009.80/291.87	null_half :: 0:s:null_if:null_half:null_inc
1009.80/291.87	null_le :: true:false:null_le
1009.80/291.87	null_inc :: 0:s:null_if:null_half:null_inc
1009.80/291.87	
1009.80/291.87	Rewrite Strategy: INNERMOST
1009.80/291.87	----------------------------------------
1009.80/291.87	
1009.80/291.87	(7) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
1009.80/291.87	Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
1009.80/291.87	The constant constructors are abstracted as follows:
1009.80/291.87	
1009.80/291.87	   0 => 0
1009.80/291.87	   true => 2
1009.80/291.87	   false => 1
1009.80/291.87	   null_if => 0
1009.80/291.87	   null_half => 0
1009.80/291.87	   null_le => 0
1009.80/291.87	   null_inc => 0
1009.80/291.87	
1009.80/291.87	----------------------------------------
1009.80/291.87	
1009.80/291.87	(8)
1009.80/291.87	Obligation:
1009.80/291.87	Complexity RNTS consisting of the following rules:
1009.80/291.87	
1009.80/291.87	   half(z) -{ 1 }-> 0 :|: z = 0
1009.80/291.87	   half(z) -{ 1 }-> 0 :|: z = 1 + 0
1009.80/291.87	   half(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
1009.80/291.87	   half(z) -{ 1 }-> 1 + half(x) :|: x >= 0, z = 1 + (1 + x)
1009.80/291.87	   if(z, z', z'') -{ 1 }-> y :|: z = 2, z' = x, x >= 0, y >= 0, z'' = 1 + y
1009.80/291.87	   if(z, z', z'') -{ 1 }-> log2(half(x), y) :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0
1009.80/291.87	   if(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0
1009.80/291.87	   inc(z) -{ 1 }-> 0 :|: z = 0
1009.80/291.87	   inc(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
1009.80/291.87	   inc(z) -{ 1 }-> 1 + inc(x) :|: x >= 0, z = 1 + x
1009.80/291.87	   le(z, z') -{ 1 }-> le(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x
1009.80/291.87	   le(z, z') -{ 1 }-> 2 :|: y >= 0, z = 0, z' = y
1009.80/291.87	   le(z, z') -{ 1 }-> 1 :|: x >= 0, z = 1 + x, z' = 0
1009.80/291.87	   le(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
1009.80/291.87	   log(z) -{ 1 }-> log2(x, 0) :|: x >= 0, z = x
1009.80/291.87	   log2(z, z') -{ 1 }-> if(le(x, 1 + 0), x, inc(y)) :|: x >= 0, y >= 0, z = x, z' = y
1009.80/291.87	
1009.80/291.87	Only complete derivations are relevant for the runtime complexity.
1009.80/291.87	
1009.80/291.87	----------------------------------------
1009.80/291.87	
1009.80/291.87	(9) CompleteCoflocoProof (FINISHED)
1009.80/291.87	Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo:
1009.80/291.87	
1009.80/291.87	eq(start(V, V2, V12),0,[half(V, Out)],[V >= 0]).
1009.80/291.87	eq(start(V, V2, V12),0,[le(V, V2, Out)],[V >= 0,V2 >= 0]).
1009.80/291.87	eq(start(V, V2, V12),0,[inc(V, Out)],[V >= 0]).
1009.80/291.87	eq(start(V, V2, V12),0,[log(V, Out)],[V >= 0]).
1009.80/291.87	eq(start(V, V2, V12),0,[log2(V, V2, Out)],[V >= 0,V2 >= 0]).
1009.80/291.87	eq(start(V, V2, V12),0,[if(V, V2, V12, Out)],[V >= 0,V2 >= 0,V12 >= 0]).
1009.80/291.87	eq(half(V, Out),1,[],[Out = 0,V = 0]).
1009.80/291.87	eq(half(V, Out),1,[],[Out = 0,V = 1]).
1009.80/291.87	eq(half(V, Out),1,[half(V1, Ret1)],[Out = 1 + Ret1,V1 >= 0,V = 2 + V1]).
1009.80/291.87	eq(le(V, V2, Out),1,[],[Out = 2,V3 >= 0,V = 0,V2 = V3]).
1009.80/291.87	eq(le(V, V2, Out),1,[],[Out = 1,V4 >= 0,V = 1 + V4,V2 = 0]).
1009.80/291.87	eq(le(V, V2, Out),1,[le(V5, V6, Ret)],[Out = Ret,V2 = 1 + V6,V5 >= 0,V6 >= 0,V = 1 + V5]).
1009.80/291.87	eq(inc(V, Out),1,[],[Out = 0,V = 0]).
1009.80/291.87	eq(inc(V, Out),1,[inc(V7, Ret11)],[Out = 1 + Ret11,V7 >= 0,V = 1 + V7]).
1009.80/291.87	eq(log(V, Out),1,[log2(V8, 0, Ret2)],[Out = Ret2,V8 >= 0,V = V8]).
1009.80/291.87	eq(log2(V, V2, Out),1,[le(V10, 1 + 0, Ret0),inc(V9, Ret21),if(Ret0, V10, Ret21, Ret3)],[Out = Ret3,V10 >= 0,V9 >= 0,V = V10,V2 = V9]).
1009.80/291.87	eq(if(V, V2, V12, Out),1,[],[Out = V11,V = 2,V2 = V13,V13 >= 0,V11 >= 0,V12 = 1 + V11]).
1009.80/291.87	eq(if(V, V2, V12, Out),1,[half(V15, Ret01),log2(Ret01, V14, Ret4)],[Out = Ret4,V2 = V15,V12 = V14,V = 1,V15 >= 0,V14 >= 0]).
1009.80/291.87	eq(if(V, V2, V12, Out),0,[],[Out = 0,V17 >= 0,V12 = V18,V16 >= 0,V = V17,V2 = V16,V18 >= 0]).
1009.80/291.87	eq(half(V, Out),0,[],[Out = 0,V19 >= 0,V = V19]).
1009.80/291.87	eq(le(V, V2, Out),0,[],[Out = 0,V21 >= 0,V20 >= 0,V = V21,V2 = V20]).
1009.80/291.87	eq(inc(V, Out),0,[],[Out = 0,V22 >= 0,V = V22]).
1009.80/291.87	input_output_vars(half(V,Out),[V],[Out]).
1009.80/291.87	input_output_vars(le(V,V2,Out),[V,V2],[Out]).
1009.80/291.87	input_output_vars(inc(V,Out),[V],[Out]).
1009.80/291.87	input_output_vars(log(V,Out),[V],[Out]).
1009.80/291.87	input_output_vars(log2(V,V2,Out),[V,V2],[Out]).
1009.80/291.87	input_output_vars(if(V,V2,V12,Out),[V,V2,V12],[Out]).
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	CoFloCo proof output:
1009.80/291.87	Preprocessing Cost Relations
1009.80/291.87	=====================================
1009.80/291.87	
1009.80/291.87	#### Computed strongly connected components 
1009.80/291.87	0. recursive  : [half/2]
1009.80/291.87	1. recursive  : [inc/2]
1009.80/291.87	2. recursive  : [le/3]
1009.80/291.87	3. recursive  : [if/4,log2/3]
1009.80/291.87	4. non_recursive  : [log/2]
1009.80/291.87	5. non_recursive  : [start/3]
1009.80/291.87	
1009.80/291.87	#### Obtained direct recursion through partial evaluation 
1009.80/291.87	0. SCC is partially evaluated into half/2
1009.80/291.87	1. SCC is partially evaluated into inc/2
1009.80/291.87	2. SCC is partially evaluated into le/3
1009.80/291.87	3. SCC is partially evaluated into log2/3
1009.80/291.87	4. SCC is completely evaluated into other SCCs
1009.80/291.87	5. SCC is partially evaluated into start/3
1009.80/291.87	
1009.80/291.87	Control-Flow Refinement of Cost Relations
1009.80/291.87	=====================================
1009.80/291.87	
1009.80/291.87	### Specialization of cost equations half/2 
1009.80/291.87	* CE 10 is refined into CE [23] 
1009.80/291.87	* CE 9 is refined into CE [24] 
1009.80/291.87	* CE 12 is refined into CE [25] 
1009.80/291.87	* CE 11 is refined into CE [26] 
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	### Cost equations --> "Loop" of half/2 
1009.80/291.87	* CEs [26] --> Loop 14 
1009.80/291.87	* CEs [23] --> Loop 15 
1009.80/291.87	* CEs [24,25] --> Loop 16 
1009.80/291.87	
1009.80/291.87	### Ranking functions of CR half(V,Out) 
1009.80/291.87	* RF of phase [14]: [V-1]
1009.80/291.87	
1009.80/291.87	#### Partial ranking functions of CR half(V,Out) 
1009.80/291.87	* Partial RF of phase [14]:
1009.80/291.87	  - RF of loop [14:1]:
1009.80/291.87	    V-1
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	### Specialization of cost equations inc/2 
1009.80/291.87	* CE 20 is refined into CE [27] 
1009.80/291.87	* CE 22 is refined into CE [28] 
1009.80/291.87	* CE 21 is refined into CE [29] 
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	### Cost equations --> "Loop" of inc/2 
1009.80/291.87	* CEs [29] --> Loop 17 
1009.80/291.87	* CEs [27,28] --> Loop 18 
1009.80/291.87	
1009.80/291.87	### Ranking functions of CR inc(V,Out) 
1009.80/291.87	* RF of phase [17]: [V]
1009.80/291.87	
1009.80/291.87	#### Partial ranking functions of CR inc(V,Out) 
1009.80/291.87	* Partial RF of phase [17]:
1009.80/291.87	  - RF of loop [17:1]:
1009.80/291.87	    V
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	### Specialization of cost equations le/3 
1009.80/291.87	* CE 19 is refined into CE [30] 
1009.80/291.87	* CE 17 is refined into CE [31] 
1009.80/291.87	* CE 16 is refined into CE [32] 
1009.80/291.87	* CE 18 is refined into CE [33] 
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	### Cost equations --> "Loop" of le/3 
1009.80/291.87	* CEs [33] --> Loop 19 
1009.80/291.87	* CEs [30] --> Loop 20 
1009.80/291.87	* CEs [31] --> Loop 21 
1009.80/291.87	* CEs [32] --> Loop 22 
1009.80/291.87	
1009.80/291.87	### Ranking functions of CR le(V,V2,Out) 
1009.80/291.87	* RF of phase [19]: [V,V2]
1009.80/291.87	
1009.80/291.87	#### Partial ranking functions of CR le(V,V2,Out) 
1009.80/291.87	* Partial RF of phase [19]:
1009.80/291.87	  - RF of loop [19:1]:
1009.80/291.87	    V
1009.80/291.87	    V2
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	### Specialization of cost equations log2/3 
1009.80/291.87	* CE 13 is refined into CE [34,35,36,37,38,39,40,41] 
1009.80/291.87	* CE 15 is refined into CE [42,43] 
1009.80/291.87	* CE 14 is refined into CE [44,45,46,47] 
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	### Cost equations --> "Loop" of log2/3 
1009.80/291.87	* CEs [47] --> Loop 23 
1009.80/291.87	* CEs [45] --> Loop 24 
1009.80/291.87	* CEs [46] --> Loop 25 
1009.80/291.87	* CEs [44] --> Loop 26 
1009.80/291.87	* CEs [43] --> Loop 27 
1009.80/291.87	* CEs [40,41] --> Loop 28 
1009.80/291.87	* CEs [42] --> Loop 29 
1009.80/291.87	* CEs [34,35,36,37,38,39] --> Loop 30 
1009.80/291.87	
1009.80/291.87	### Ranking functions of CR log2(V,V2,Out) 
1009.80/291.87	* RF of phase [23]: [V-1]
1009.80/291.87	* RF of phase [24]: [V-1]
1009.80/291.87	
1009.80/291.87	#### Partial ranking functions of CR log2(V,V2,Out) 
1009.80/291.87	* Partial RF of phase [23]:
1009.80/291.87	  - RF of loop [23:1]:
1009.80/291.87	    V-1
1009.80/291.87	* Partial RF of phase [24]:
1009.80/291.87	  - RF of loop [24:1]:
1009.80/291.87	    V-1
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	### Specialization of cost equations start/3 
1009.80/291.87	* CE 3 is refined into CE [48] 
1009.80/291.87	* CE 1 is refined into CE [49] 
1009.80/291.87	* CE 2 is refined into CE [50,51,52,53,54] 
1009.80/291.87	* CE 4 is refined into CE [55,56] 
1009.80/291.87	* CE 5 is refined into CE [57,58,59,60,61] 
1009.80/291.87	* CE 6 is refined into CE [62,63] 
1009.80/291.87	* CE 7 is refined into CE [64] 
1009.80/291.87	* CE 8 is refined into CE [65,66,67,68] 
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	### Cost equations --> "Loop" of start/3 
1009.80/291.87	* CEs [58] --> Loop 31 
1009.80/291.87	* CEs [48] --> Loop 32 
1009.80/291.87	* CEs [67] --> Loop 33 
1009.80/291.87	* CEs [50,51,52,53,54] --> Loop 34 
1009.80/291.87	* CEs [49,55,56,57,59,60,61,62,63,64,65,66,68] --> Loop 35 
1009.80/291.87	
1009.80/291.87	### Ranking functions of CR start(V,V2,V12) 
1009.80/291.87	
1009.80/291.87	#### Partial ranking functions of CR start(V,V2,V12) 
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	Computing Bounds
1009.80/291.87	=====================================
1009.80/291.87	
1009.80/291.87	#### Cost of chains of half(V,Out):
1009.80/291.87	* Chain [[14],16]: 1*it(14)+1
1009.80/291.87	  Such that:it(14) =< 2*Out
1009.80/291.87	
1009.80/291.87	  with precondition: [Out>=1,V>=2*Out] 
1009.80/291.87	
1009.80/291.87	* Chain [[14],15]: 1*it(14)+1
1009.80/291.87	  Such that:it(14) =< 2*Out
1009.80/291.87	
1009.80/291.87	  with precondition: [V=2*Out+1,V>=3] 
1009.80/291.87	
1009.80/291.87	* Chain [16]: 1
1009.80/291.87	  with precondition: [Out=0,V>=0] 
1009.80/291.87	
1009.80/291.87	* Chain [15]: 1
1009.80/291.87	  with precondition: [V=1,Out=0] 
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	#### Cost of chains of inc(V,Out):
1009.80/291.87	* Chain [[17],18]: 1*it(17)+1
1009.80/291.87	  Such that:it(17) =< Out
1009.80/291.87	
1009.80/291.87	  with precondition: [Out>=1,V>=Out] 
1009.80/291.87	
1009.80/291.87	* Chain [18]: 1
1009.80/291.87	  with precondition: [Out=0,V>=0] 
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	#### Cost of chains of le(V,V2,Out):
1009.80/291.87	* Chain [[19],22]: 1*it(19)+1
1009.80/291.87	  Such that:it(19) =< V
1009.80/291.87	
1009.80/291.87	  with precondition: [Out=2,V>=1,V2>=V] 
1009.80/291.87	
1009.80/291.87	* Chain [[19],21]: 1*it(19)+1
1009.80/291.87	  Such that:it(19) =< V2
1009.80/291.87	
1009.80/291.87	  with precondition: [Out=1,V2>=1,V>=V2+1] 
1009.80/291.87	
1009.80/291.87	* Chain [[19],20]: 1*it(19)+0
1009.80/291.87	  Such that:it(19) =< V2
1009.80/291.87	
1009.80/291.87	  with precondition: [Out=0,V>=1,V2>=1] 
1009.80/291.87	
1009.80/291.87	* Chain [22]: 1
1009.80/291.87	  with precondition: [V=0,Out=2,V2>=0] 
1009.80/291.87	
1009.80/291.87	* Chain [21]: 1
1009.80/291.87	  with precondition: [V2=0,Out=1,V>=1] 
1009.80/291.87	
1009.80/291.87	* Chain [20]: 0
1009.80/291.87	  with precondition: [Out=0,V>=0,V2>=0] 
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	#### Cost of chains of log2(V,V2,Out):
1009.80/291.87	* Chain [[24],30]: 6*it(24)+4*s(5)+2*s(18)+3
1009.80/291.87	  Such that:aux(2) =< 1
1009.80/291.87	s(19) =< 2*V
1009.80/291.87	aux(7) =< V
1009.80/291.87	s(5) =< aux(2)
1009.80/291.87	it(24) =< aux(7)
1009.80/291.87	s(18) =< s(19)
1009.80/291.87	
1009.80/291.87	  with precondition: [Out=0,V>=2,V2>=0] 
1009.80/291.87	
1009.80/291.87	* Chain [[24],28]: 6*it(24)+2*s(18)+2*s(20)+3
1009.80/291.87	  Such that:aux(8) =< 1
1009.80/291.87	s(19) =< 2*V
1009.80/291.87	aux(9) =< V
1009.80/291.87	s(20) =< aux(8)
1009.80/291.87	it(24) =< aux(9)
1009.80/291.87	s(18) =< s(19)
1009.80/291.87	
1009.80/291.87	  with precondition: [Out=0,V>=2,V2>=0] 
1009.80/291.87	
1009.80/291.87	* Chain [[24],26,30]: 6*it(24)+5*s(5)+2*s(18)+8
1009.80/291.87	  Such that:aux(10) =< 1
1009.80/291.87	s(19) =< 2*V
1009.80/291.87	aux(11) =< V
1009.80/291.87	s(5) =< aux(10)
1009.80/291.87	it(24) =< aux(11)
1009.80/291.87	s(18) =< s(19)
1009.80/291.87	
1009.80/291.87	  with precondition: [Out=0,V>=4,V2>=0] 
1009.80/291.87	
1009.80/291.87	* Chain [[23],[24],30]: 6*it(23)+10*it(24)+4*s(5)+1*s(33)+3
1009.80/291.87	  Such that:aux(2) =< 1
1009.80/291.87	aux(13) =< V2
1009.80/291.87	aux(16) =< V
1009.80/291.87	aux(17) =< 2*V
1009.80/291.87	s(5) =< aux(2)
1009.80/291.87	it(24) =< aux(17)
1009.80/291.87	it(23) =< aux(16)
1009.80/291.87	s(33) =< it(23)*aux(13)
1009.80/291.87	
1009.80/291.87	  with precondition: [Out=0,V>=4,V2>=1] 
1009.80/291.87	
1009.80/291.87	* Chain [[23],[24],28]: 6*it(23)+10*it(24)+2*s(20)+1*s(33)+3
1009.80/291.87	  Such that:aux(8) =< 1
1009.80/291.87	aux(13) =< V2
1009.80/291.87	aux(18) =< V
1009.80/291.87	aux(19) =< 2*V
1009.80/291.87	s(20) =< aux(8)
1009.80/291.87	it(24) =< aux(19)
1009.80/291.87	it(23) =< aux(18)
1009.80/291.87	s(33) =< it(23)*aux(13)
1009.80/291.87	
1009.80/291.87	  with precondition: [Out=0,V>=4,V2>=1] 
1009.80/291.87	
1009.80/291.87	* Chain [[23],[24],26,30]: 6*it(23)+10*it(24)+5*s(5)+1*s(33)+8
1009.80/291.87	  Such that:aux(10) =< 1
1009.80/291.87	aux(13) =< V2
1009.80/291.87	aux(20) =< V
1009.80/291.87	aux(21) =< 2*V
1009.80/291.87	s(5) =< aux(10)
1009.80/291.87	it(24) =< aux(21)
1009.80/291.87	it(23) =< aux(20)
1009.80/291.87	s(33) =< it(23)*aux(13)
1009.80/291.87	
1009.80/291.87	  with precondition: [Out=0,V>=8,V2>=1] 
1009.80/291.87	
1009.80/291.87	* Chain [[23],30]: 6*it(23)+3*s(4)+4*s(5)+1*s(33)+2*s(34)+3
1009.80/291.87	  Such that:aux(2) =< 1
1009.80/291.87	s(35) =< 2*V
1009.80/291.87	aux(22) =< V
1009.80/291.87	aux(23) =< V2
1009.80/291.87	s(5) =< aux(2)
1009.80/291.87	s(4) =< aux(23)
1009.80/291.87	it(23) =< aux(22)
1009.80/291.87	s(33) =< it(23)*aux(23)
1009.80/291.87	s(34) =< s(35)
1009.80/291.87	
1009.80/291.87	  with precondition: [Out=0,V>=2,V2>=1] 
1009.80/291.87	
1009.80/291.87	* Chain [[23],28]: 6*it(23)+2*s(20)+1*s(22)+1*s(33)+2*s(34)+3
1009.80/291.87	  Such that:aux(8) =< 1
1009.80/291.87	s(35) =< 2*V
1009.80/291.87	aux(24) =< V
1009.80/291.87	aux(25) =< V2
1009.80/291.87	s(22) =< aux(25)
1009.80/291.87	s(20) =< aux(8)
1009.80/291.87	it(23) =< aux(24)
1009.80/291.87	s(33) =< it(23)*aux(25)
1009.80/291.87	s(34) =< s(35)
1009.80/291.87	
1009.80/291.87	  with precondition: [Out=0,V>=2,V2>=1] 
1009.80/291.87	
1009.80/291.87	* Chain [[23],27]: 6*it(23)+1*s(33)+2*s(34)+1*s(36)+1*s(37)+4
1009.80/291.87	  Such that:s(36) =< 1
1009.80/291.87	s(35) =< 2*V
1009.80/291.87	aux(26) =< V
1009.80/291.87	aux(27) =< V2
1009.80/291.87	s(37) =< aux(27)
1009.80/291.87	it(23) =< aux(26)
1009.80/291.87	s(33) =< it(23)*aux(27)
1009.80/291.87	s(34) =< s(35)
1009.80/291.87	
1009.80/291.87	  with precondition: [V>=2,Out>=0,V2>=Out+1] 
1009.80/291.87	
1009.80/291.87	* Chain [[23],26,30]: 6*it(23)+5*s(5)+1*s(33)+2*s(34)+8
1009.80/291.87	  Such that:aux(10) =< 1
1009.80/291.87	s(35) =< 2*V
1009.80/291.87	aux(13) =< V2
1009.80/291.87	aux(28) =< V
1009.80/291.87	s(5) =< aux(10)
1009.80/291.87	it(23) =< aux(28)
1009.80/291.87	s(33) =< it(23)*aux(13)
1009.80/291.87	s(34) =< s(35)
1009.80/291.87	
1009.80/291.87	  with precondition: [Out=0,V>=4,V2>=1] 
1009.80/291.87	
1009.80/291.87	* Chain [[23],25,30]: 6*it(23)+4*s(4)+5*s(5)+1*s(33)+2*s(34)+8
1009.80/291.87	  Such that:aux(29) =< 1
1009.80/291.87	s(35) =< 2*V
1009.80/291.87	aux(31) =< V
1009.80/291.87	aux(32) =< V2
1009.80/291.87	s(5) =< aux(29)
1009.80/291.87	s(4) =< aux(32)
1009.80/291.87	it(23) =< aux(31)
1009.80/291.87	s(33) =< it(23)*aux(32)
1009.80/291.87	s(34) =< s(35)
1009.80/291.87	
1009.80/291.87	  with precondition: [Out=0,V>=4,V2>=1] 
1009.80/291.87	
1009.80/291.87	* Chain [[23],25,29]: 6*it(23)+1*s(33)+2*s(34)+1*s(38)+2*s(39)+9
1009.80/291.87	  Such that:s(38) =< 1
1009.80/291.87	s(35) =< 2*V
1009.80/291.87	aux(34) =< V
1009.80/291.87	aux(35) =< V2
1009.80/291.87	s(39) =< aux(35)
1009.80/291.87	it(23) =< aux(34)
1009.80/291.87	s(33) =< it(23)*aux(35)
1009.80/291.87	s(34) =< s(35)
1009.80/291.87	
1009.80/291.87	  with precondition: [V>=4,Out>=0,V2>=Out+1] 
1009.80/291.87	
1009.80/291.87	* Chain [30]: 3*s(4)+4*s(5)+3
1009.80/291.87	  Such that:aux(2) =< 1
1009.80/291.87	aux(3) =< V2
1009.80/291.87	s(5) =< aux(2)
1009.80/291.87	s(4) =< aux(3)
1009.80/291.87	
1009.80/291.87	  with precondition: [Out=0,V>=0,V2>=0] 
1009.80/291.87	
1009.80/291.87	* Chain [29]: 1*s(40)+4
1009.80/291.87	  Such that:s(40) =< V2
1009.80/291.87	
1009.80/291.87	  with precondition: [V=0,Out>=0,V2>=Out+1] 
1009.80/291.87	
1009.80/291.87	* Chain [28]: 2*s(20)+1*s(22)+3
1009.80/291.87	  Such that:s(22) =< V2
1009.80/291.87	aux(8) =< 1
1009.80/291.87	s(20) =< aux(8)
1009.80/291.87	
1009.80/291.87	  with precondition: [V=1,Out=0,V2>=0] 
1009.80/291.87	
1009.80/291.87	* Chain [27]: 1*s(36)+1*s(37)+4
1009.80/291.87	  Such that:s(36) =< 1
1009.80/291.87	s(37) =< V2
1009.80/291.87	
1009.80/291.87	  with precondition: [V=1,Out>=0,V2>=Out+1] 
1009.80/291.87	
1009.80/291.87	* Chain [26,30]: 5*s(5)+8
1009.80/291.87	  Such that:aux(10) =< 1
1009.80/291.87	s(5) =< aux(10)
1009.80/291.87	
1009.80/291.87	  with precondition: [Out=0,V>=2,V2>=0] 
1009.80/291.87	
1009.80/291.87	* Chain [25,30]: 4*s(4)+5*s(5)+8
1009.80/291.87	  Such that:aux(29) =< 1
1009.80/291.87	aux(30) =< V2
1009.80/291.87	s(5) =< aux(29)
1009.80/291.87	s(4) =< aux(30)
1009.80/291.87	
1009.80/291.87	  with precondition: [Out=0,V>=2,V2>=1] 
1009.80/291.87	
1009.80/291.87	* Chain [25,29]: 1*s(38)+2*s(39)+9
1009.80/291.87	  Such that:s(38) =< 1
1009.80/291.87	aux(33) =< V2
1009.80/291.87	s(39) =< aux(33)
1009.80/291.87	
1009.80/291.87	  with precondition: [V>=2,Out>=0,V2>=Out+1] 
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	#### Cost of chains of start(V,V2,V12):
1009.80/291.87	* Chain [35]: 136*s(151)+24*s(152)+111*s(161)+92*s(164)+9*s(173)+9
1009.80/291.87	  Such that:aux(44) =< 1
1009.80/291.87	aux(45) =< V
1009.80/291.87	aux(46) =< 2*V
1009.80/291.87	aux(47) =< V2
1009.80/291.87	s(151) =< aux(45)
1009.80/291.87	s(152) =< aux(47)
1009.80/291.87	s(161) =< aux(44)
1009.80/291.87	s(164) =< aux(46)
1009.80/291.87	s(173) =< s(151)*aux(47)
1009.80/291.87	
1009.80/291.87	  with precondition: [V>=0] 
1009.80/291.87	
1009.80/291.87	* Chain [34]: 39*s(184)+112*s(190)+52*s(195)+72*s(202)+9*s(203)+2*s(206)+11
1009.80/291.87	  Such that:s(205) =< 2
1009.80/291.87	aux(51) =< 1
1009.80/291.87	aux(52) =< V2
1009.80/291.87	aux(53) =< V2/2
1009.80/291.87	aux(54) =< V12
1009.80/291.87	s(190) =< aux(51)
1009.80/291.87	s(184) =< aux(54)
1009.80/291.87	s(202) =< aux(53)
1009.80/291.87	s(203) =< s(202)*aux(54)
1009.80/291.87	s(195) =< aux(52)
1009.80/291.87	s(206) =< s(205)
1009.80/291.87	
1009.80/291.87	  with precondition: [V=1,V2>=0,V12>=0] 
1009.80/291.87	
1009.80/291.87	* Chain [33]: 1*s(220)+1*s(221)+4
1009.80/291.87	  Such that:s(220) =< 1
1009.80/291.87	s(221) =< V2
1009.80/291.87	
1009.80/291.87	  with precondition: [V=1,V2>=1] 
1009.80/291.87	
1009.80/291.87	* Chain [32]: 1
1009.80/291.87	  with precondition: [V=2,V2>=0,V12>=1] 
1009.80/291.87	
1009.80/291.87	* Chain [31]: 1
1009.80/291.87	  with precondition: [V2=0,V>=1] 
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	Closed-form bounds of start(V,V2,V12): 
1009.80/291.87	-------------------------------------
1009.80/291.87	* Chain [35] with precondition: [V>=0] 
1009.80/291.87	    - Upper bound: 136*V+120+9*V*nat(V2)+nat(V2)*24+184*V 
1009.80/291.87	    - Complexity: n^2 
1009.80/291.87	* Chain [34] with precondition: [V=1,V2>=0,V12>=0] 
1009.80/291.87	    - Upper bound: 52*V2+39*V12+127+V2/2*(9*V12)+36*V2 
1009.80/291.87	    - Complexity: n^2 
1009.80/291.87	* Chain [33] with precondition: [V=1,V2>=1] 
1009.80/291.87	    - Upper bound: V2+5 
1009.80/291.87	    - Complexity: n 
1009.80/291.87	* Chain [32] with precondition: [V=2,V2>=0,V12>=1] 
1009.80/291.87	    - Upper bound: 1 
1009.80/291.87	    - Complexity: constant 
1009.80/291.87	* Chain [31] with precondition: [V2=0,V>=1] 
1009.80/291.87	    - Upper bound: 1 
1009.80/291.87	    - Complexity: constant 
1009.80/291.87	
1009.80/291.87	### Maximum cost of start(V,V2,V12): nat(V2)*23+115+max([9*V*nat(V2)+136*V+184*V,nat(V2)*28+7+nat(V12)*39+nat(V12)*9*nat(V2/2)+nat(V2/2)*72])+(nat(V2)+4)+1 
1009.80/291.87	Asymptotic class: n^2 
1009.80/291.87	* Total analysis performed in 444 ms.
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	----------------------------------------
1009.80/291.87	
1009.80/291.87	(10)
1009.80/291.87	BOUNDS(1, n^2)
1009.80/291.87	
1009.80/291.87	----------------------------------------
1009.80/291.87	
1009.80/291.87	(11) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
1009.80/291.87	Transformed a relative TRS into a decreasing-loop problem.
1009.80/291.87	----------------------------------------
1009.80/291.87	
1009.80/291.87	(12)
1009.80/291.87	Obligation:
1009.80/291.87	Analyzing the following TRS for decreasing loops:
1009.80/291.87	
1009.80/291.87	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	The TRS R consists of the following rules:
1009.80/291.87	
1009.80/291.87	   half(0) -> 0
1009.80/291.87	   half(s(0)) -> 0
1009.80/291.87	   half(s(s(x))) -> s(half(x))
1009.80/291.87	   le(0, y) -> true
1009.80/291.87	   le(s(x), 0) -> false
1009.80/291.87	   le(s(x), s(y)) -> le(x, y)
1009.80/291.87	   inc(0) -> 0
1009.80/291.87	   inc(s(x)) -> s(inc(x))
1009.80/291.87	   log(x) -> log2(x, 0)
1009.80/291.87	   log2(x, y) -> if(le(x, s(0)), x, inc(y))
1009.80/291.87	   if(true, x, s(y)) -> y
1009.80/291.87	   if(false, x, y) -> log2(half(x), y)
1009.80/291.87	
1009.80/291.87	S is empty.
1009.80/291.87	Rewrite Strategy: INNERMOST
1009.80/291.87	----------------------------------------
1009.80/291.87	
1009.80/291.87	(13) DecreasingLoopProof (LOWER BOUND(ID))
1009.80/291.87	The following loop(s) give(s) rise to the lower bound Omega(n^1):
1009.80/291.87	
1009.80/291.87	The rewrite sequence
1009.80/291.87	
1009.80/291.87	half(s(s(x))) ->^+ s(half(x))
1009.80/291.87	
1009.80/291.87	gives rise to a decreasing loop by considering the right hand sides subterm at position [0].
1009.80/291.87	
1009.80/291.87	The pumping substitution is [x / s(s(x))].
1009.80/291.87	
1009.80/291.87	The result substitution is [ ].
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	----------------------------------------
1009.80/291.87	
1009.80/291.87	(14)
1009.80/291.87	Complex Obligation (BEST)
1009.80/291.87	
1009.80/291.87	----------------------------------------
1009.80/291.87	
1009.80/291.87	(15)
1009.80/291.87	Obligation:
1009.80/291.87	Proved the lower bound n^1 for the following obligation:
1009.80/291.87	
1009.80/291.87	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	The TRS R consists of the following rules:
1009.80/291.87	
1009.80/291.87	   half(0) -> 0
1009.80/291.87	   half(s(0)) -> 0
1009.80/291.87	   half(s(s(x))) -> s(half(x))
1009.80/291.87	   le(0, y) -> true
1009.80/291.87	   le(s(x), 0) -> false
1009.80/291.87	   le(s(x), s(y)) -> le(x, y)
1009.80/291.87	   inc(0) -> 0
1009.80/291.87	   inc(s(x)) -> s(inc(x))
1009.80/291.87	   log(x) -> log2(x, 0)
1009.80/291.87	   log2(x, y) -> if(le(x, s(0)), x, inc(y))
1009.80/291.87	   if(true, x, s(y)) -> y
1009.80/291.87	   if(false, x, y) -> log2(half(x), y)
1009.80/291.87	
1009.80/291.87	S is empty.
1009.80/291.87	Rewrite Strategy: INNERMOST
1009.80/291.87	----------------------------------------
1009.80/291.87	
1009.80/291.87	(16) LowerBoundPropagationProof (FINISHED)
1009.80/291.87	Propagated lower bound.
1009.80/291.87	----------------------------------------
1009.80/291.87	
1009.80/291.87	(17)
1009.80/291.87	BOUNDS(n^1, INF)
1009.80/291.87	
1009.80/291.87	----------------------------------------
1009.80/291.87	
1009.80/291.87	(18)
1009.80/291.87	Obligation:
1009.80/291.87	Analyzing the following TRS for decreasing loops:
1009.80/291.87	
1009.80/291.87	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
1009.80/291.87	
1009.80/291.87	
1009.80/291.87	The TRS R consists of the following rules:
1009.80/291.87	
1009.80/291.87	   half(0) -> 0
1009.80/291.87	   half(s(0)) -> 0
1009.80/291.87	   half(s(s(x))) -> s(half(x))
1009.80/291.87	   le(0, y) -> true
1009.80/291.87	   le(s(x), 0) -> false
1009.80/291.87	   le(s(x), s(y)) -> le(x, y)
1009.80/291.87	   inc(0) -> 0
1009.80/291.87	   inc(s(x)) -> s(inc(x))
1009.80/291.87	   log(x) -> log2(x, 0)
1009.80/291.87	   log2(x, y) -> if(le(x, s(0)), x, inc(y))
1009.80/291.87	   if(true, x, s(y)) -> y
1009.80/291.87	   if(false, x, y) -> log2(half(x), y)
1009.80/291.87	
1009.80/291.87	S is empty.
1009.80/291.87	Rewrite Strategy: INNERMOST
1010.11/291.92	EOF