154.10/40.16	WORST_CASE(Omega(n^1), O(n^1))
154.15/40.17	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
154.15/40.17	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
154.15/40.17	
154.15/40.17	
154.15/40.17	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
154.15/40.17	
154.15/40.17	(0) CpxTRS
154.15/40.17	(1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
154.15/40.17	(2) CpxWeightedTrs
154.15/40.17	    (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
154.15/40.17	    (4) CpxTypedWeightedTrs
154.15/40.17	    (5) CompletionProof [UPPER BOUND(ID), 0 ms]
154.15/40.17	    (6) CpxTypedWeightedCompleteTrs
154.15/40.17	    (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 11 ms]
154.15/40.17	    (8) CpxRNTS
154.15/40.17	    (9) CompleteCoflocoProof [FINISHED, 717 ms]
154.15/40.17	    (10) BOUNDS(1, n^1)
154.15/40.17	(11) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
154.15/40.17	(12) TRS for Loop Detection
154.15/40.17	    (13) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
154.15/40.17	    (14) BEST
154.15/40.17	        (15) proven lower bound
154.15/40.17	            (16) LowerBoundPropagationProof [FINISHED, 0 ms]
154.15/40.17	            (17) BOUNDS(n^1, INF)
154.15/40.17	        (18) TRS for Loop Detection
154.15/40.17	
154.15/40.17	
154.15/40.17	----------------------------------------
154.15/40.17	
154.15/40.17	(0)
154.15/40.17	Obligation:
154.15/40.17	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
154.15/40.17	
154.15/40.17	
154.15/40.17	The TRS R consists of the following rules:
154.15/40.17	
154.15/40.17	   p(s(x)) -> x
154.15/40.17	   p(0) -> 0
154.15/40.17	   le(0, y) -> true
154.15/40.17	   le(s(x), 0) -> false
154.15/40.17	   le(s(x), s(y)) -> le(x, y)
154.15/40.17	   average(x, y) -> if(le(x, 0), le(y, 0), le(y, s(0)), le(y, s(s(0))), x, y)
154.15/40.17	   if(true, b1, b2, b3, x, y) -> if2(b1, b2, b3, x, y)
154.15/40.17	   if(false, b1, b2, b3, x, y) -> average(p(x), s(y))
154.15/40.17	   if2(true, b2, b3, x, y) -> 0
154.15/40.17	   if2(false, b2, b3, x, y) -> if3(b2, b3, x, y)
154.15/40.17	   if3(true, b3, x, y) -> 0
154.15/40.17	   if3(false, b3, x, y) -> if4(b3, x, y)
154.15/40.17	   if4(true, x, y) -> s(0)
154.15/40.17	   if4(false, x, y) -> average(s(x), p(p(y)))
154.15/40.17	
154.15/40.17	S is empty.
154.15/40.17	Rewrite Strategy: INNERMOST
154.15/40.17	----------------------------------------
154.15/40.17	
154.15/40.17	(1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
154.15/40.17	Transformed relative TRS to weighted TRS
154.15/40.17	----------------------------------------
154.15/40.17	
154.15/40.17	(2)
154.15/40.17	Obligation:
154.15/40.17	The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1).
154.15/40.17	
154.15/40.17	
154.15/40.17	The TRS R consists of the following rules:
154.15/40.17	
154.15/40.17	   p(s(x)) -> x [1]
154.15/40.17	   p(0) -> 0 [1]
154.15/40.17	   le(0, y) -> true [1]
154.15/40.17	   le(s(x), 0) -> false [1]
154.15/40.17	   le(s(x), s(y)) -> le(x, y) [1]
154.15/40.17	   average(x, y) -> if(le(x, 0), le(y, 0), le(y, s(0)), le(y, s(s(0))), x, y) [1]
154.15/40.17	   if(true, b1, b2, b3, x, y) -> if2(b1, b2, b3, x, y) [1]
154.15/40.17	   if(false, b1, b2, b3, x, y) -> average(p(x), s(y)) [1]
154.15/40.17	   if2(true, b2, b3, x, y) -> 0 [1]
154.15/40.17	   if2(false, b2, b3, x, y) -> if3(b2, b3, x, y) [1]
154.15/40.17	   if3(true, b3, x, y) -> 0 [1]
154.15/40.17	   if3(false, b3, x, y) -> if4(b3, x, y) [1]
154.15/40.17	   if4(true, x, y) -> s(0) [1]
154.15/40.17	   if4(false, x, y) -> average(s(x), p(p(y))) [1]
154.15/40.17	
154.15/40.17	Rewrite Strategy: INNERMOST
154.15/40.17	----------------------------------------
154.15/40.17	
154.15/40.17	(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
154.15/40.17	Infered types.
154.15/40.17	----------------------------------------
154.15/40.17	
154.15/40.17	(4)
154.15/40.17	Obligation:
154.15/40.17	Runtime Complexity Weighted TRS with Types.
154.15/40.17	The TRS R consists of the following rules:
154.15/40.17	
154.15/40.17	   p(s(x)) -> x [1]
154.15/40.17	   p(0) -> 0 [1]
154.15/40.17	   le(0, y) -> true [1]
154.15/40.17	   le(s(x), 0) -> false [1]
154.15/40.17	   le(s(x), s(y)) -> le(x, y) [1]
154.15/40.17	   average(x, y) -> if(le(x, 0), le(y, 0), le(y, s(0)), le(y, s(s(0))), x, y) [1]
154.15/40.17	   if(true, b1, b2, b3, x, y) -> if2(b1, b2, b3, x, y) [1]
154.15/40.17	   if(false, b1, b2, b3, x, y) -> average(p(x), s(y)) [1]
154.15/40.17	   if2(true, b2, b3, x, y) -> 0 [1]
154.15/40.17	   if2(false, b2, b3, x, y) -> if3(b2, b3, x, y) [1]
154.15/40.17	   if3(true, b3, x, y) -> 0 [1]
154.15/40.17	   if3(false, b3, x, y) -> if4(b3, x, y) [1]
154.15/40.17	   if4(true, x, y) -> s(0) [1]
154.15/40.17	   if4(false, x, y) -> average(s(x), p(p(y))) [1]
154.15/40.17	
154.15/40.17	The TRS has the following type information:
154.15/40.17	p :: s:0 -> s:0
154.15/40.17	s :: s:0 -> s:0
154.15/40.17	0 :: s:0
154.15/40.17	le :: s:0 -> s:0 -> true:false
154.15/40.17	true :: true:false
154.15/40.17	false :: true:false
154.15/40.17	average :: s:0 -> s:0 -> s:0
154.15/40.17	if :: true:false -> true:false -> true:false -> true:false -> s:0 -> s:0 -> s:0
154.15/40.17	if2 :: true:false -> true:false -> true:false -> s:0 -> s:0 -> s:0
154.15/40.17	if3 :: true:false -> true:false -> s:0 -> s:0 -> s:0
154.15/40.17	if4 :: true:false -> s:0 -> s:0 -> s:0
154.15/40.17	
154.15/40.17	Rewrite Strategy: INNERMOST
154.15/40.17	----------------------------------------
154.15/40.17	
154.15/40.17	(5) CompletionProof (UPPER BOUND(ID))
154.15/40.17	The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added:
154.15/40.17	none
154.15/40.17	
154.15/40.17	And the following fresh constants: none
154.15/40.17	
154.15/40.17	----------------------------------------
154.15/40.17	
154.15/40.17	(6)
154.15/40.17	Obligation:
154.15/40.17	Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is:
154.15/40.17	
154.15/40.17	Runtime Complexity Weighted TRS with Types.
154.15/40.17	The TRS R consists of the following rules:
154.15/40.17	
154.15/40.17	   p(s(x)) -> x [1]
154.15/40.17	   p(0) -> 0 [1]
154.15/40.17	   le(0, y) -> true [1]
154.15/40.17	   le(s(x), 0) -> false [1]
154.15/40.17	   le(s(x), s(y)) -> le(x, y) [1]
154.15/40.17	   average(x, y) -> if(le(x, 0), le(y, 0), le(y, s(0)), le(y, s(s(0))), x, y) [1]
154.15/40.17	   if(true, b1, b2, b3, x, y) -> if2(b1, b2, b3, x, y) [1]
154.15/40.17	   if(false, b1, b2, b3, x, y) -> average(p(x), s(y)) [1]
154.15/40.17	   if2(true, b2, b3, x, y) -> 0 [1]
154.15/40.17	   if2(false, b2, b3, x, y) -> if3(b2, b3, x, y) [1]
154.15/40.17	   if3(true, b3, x, y) -> 0 [1]
154.15/40.17	   if3(false, b3, x, y) -> if4(b3, x, y) [1]
154.15/40.17	   if4(true, x, y) -> s(0) [1]
154.15/40.17	   if4(false, x, y) -> average(s(x), p(p(y))) [1]
154.15/40.17	
154.15/40.17	The TRS has the following type information:
154.15/40.17	p :: s:0 -> s:0
154.15/40.17	s :: s:0 -> s:0
154.15/40.17	0 :: s:0
154.15/40.17	le :: s:0 -> s:0 -> true:false
154.15/40.17	true :: true:false
154.15/40.17	false :: true:false
154.15/40.17	average :: s:0 -> s:0 -> s:0
154.15/40.17	if :: true:false -> true:false -> true:false -> true:false -> s:0 -> s:0 -> s:0
154.15/40.17	if2 :: true:false -> true:false -> true:false -> s:0 -> s:0 -> s:0
154.15/40.17	if3 :: true:false -> true:false -> s:0 -> s:0 -> s:0
154.15/40.17	if4 :: true:false -> s:0 -> s:0 -> s:0
154.15/40.17	
154.15/40.17	Rewrite Strategy: INNERMOST
154.15/40.17	----------------------------------------
154.15/40.17	
154.15/40.17	(7) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
154.15/40.17	Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
154.15/40.17	The constant constructors are abstracted as follows:
154.15/40.17	
154.15/40.17	   0 => 0
154.15/40.17	   true => 1
154.15/40.17	   false => 0
154.15/40.17	
154.15/40.17	----------------------------------------
154.15/40.17	
154.15/40.17	(8)
154.15/40.17	Obligation:
154.15/40.17	Complexity RNTS consisting of the following rules:
154.15/40.17	
154.15/40.17	   average(z, z') -{ 1 }-> if(le(x, 0), le(y, 0), le(y, 1 + 0), le(y, 1 + (1 + 0)), x, y) :|: x >= 0, y >= 0, z = x, z' = y
154.15/40.17	   if(z, z', z'', z1, z2, z3) -{ 1 }-> if2(b1, b2, b3, x, y) :|: b2 >= 0, z2 = x, b1 >= 0, z = 1, z1 = b3, z3 = y, x >= 0, y >= 0, z' = b1, z'' = b2, b3 >= 0
154.15/40.17	   if(z, z', z'', z1, z2, z3) -{ 1 }-> average(p(x), 1 + y) :|: b2 >= 0, z2 = x, b1 >= 0, z1 = b3, z3 = y, x >= 0, y >= 0, z' = b1, z = 0, z'' = b2, b3 >= 0
154.15/40.17	   if2(z, z', z'', z1, z2) -{ 1 }-> if3(b2, b3, x, y) :|: b2 >= 0, z2 = y, x >= 0, y >= 0, z' = b2, z = 0, z'' = b3, z1 = x, b3 >= 0
154.15/40.17	   if2(z, z', z'', z1, z2) -{ 1 }-> 0 :|: b2 >= 0, z2 = y, z = 1, x >= 0, y >= 0, z' = b2, z'' = b3, z1 = x, b3 >= 0
154.15/40.17	   if3(z, z', z'', z1) -{ 1 }-> if4(b3, x, y) :|: z1 = y, z' = b3, x >= 0, y >= 0, z'' = x, z = 0, b3 >= 0
154.15/40.17	   if3(z, z', z'', z1) -{ 1 }-> 0 :|: z1 = y, z' = b3, z = 1, x >= 0, y >= 0, z'' = x, b3 >= 0
154.15/40.17	   if4(z, z', z'') -{ 1 }-> average(1 + x, p(p(y))) :|: z' = x, z'' = y, x >= 0, y >= 0, z = 0
154.15/40.17	   if4(z, z', z'') -{ 1 }-> 1 + 0 :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0
154.15/40.17	   le(z, z') -{ 1 }-> le(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x
154.15/40.17	   le(z, z') -{ 1 }-> 1 :|: y >= 0, z = 0, z' = y
154.15/40.17	   le(z, z') -{ 1 }-> 0 :|: x >= 0, z = 1 + x, z' = 0
154.15/40.17	   p(z) -{ 1 }-> x :|: x >= 0, z = 1 + x
154.15/40.17	   p(z) -{ 1 }-> 0 :|: z = 0
154.15/40.17	
154.15/40.17	Only complete derivations are relevant for the runtime complexity.
154.15/40.17	
154.15/40.17	----------------------------------------
154.15/40.17	
154.15/40.17	(9) CompleteCoflocoProof (FINISHED)
154.15/40.17	Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo:
154.15/40.17	
154.15/40.17	eq(start(V, V2, V11, V17, V15, V16),0,[p(V, Out)],[V >= 0]).
154.15/40.17	eq(start(V, V2, V11, V17, V15, V16),0,[le(V, V2, Out)],[V >= 0,V2 >= 0]).
154.15/40.17	eq(start(V, V2, V11, V17, V15, V16),0,[average(V, V2, Out)],[V >= 0,V2 >= 0]).
154.15/40.17	eq(start(V, V2, V11, V17, V15, V16),0,[if(V, V2, V11, V17, V15, V16, Out)],[V >= 0,V2 >= 0,V11 >= 0,V17 >= 0,V15 >= 0,V16 >= 0]).
154.15/40.17	eq(start(V, V2, V11, V17, V15, V16),0,[if2(V, V2, V11, V17, V15, Out)],[V >= 0,V2 >= 0,V11 >= 0,V17 >= 0,V15 >= 0]).
154.15/40.17	eq(start(V, V2, V11, V17, V15, V16),0,[if3(V, V2, V11, V17, Out)],[V >= 0,V2 >= 0,V11 >= 0,V17 >= 0]).
154.15/40.17	eq(start(V, V2, V11, V17, V15, V16),0,[if4(V, V2, V11, Out)],[V >= 0,V2 >= 0,V11 >= 0]).
154.15/40.17	eq(p(V, Out),1,[],[Out = V1,V1 >= 0,V = 1 + V1]).
154.15/40.17	eq(p(V, Out),1,[],[Out = 0,V = 0]).
154.15/40.17	eq(le(V, V2, Out),1,[],[Out = 1,V3 >= 0,V = 0,V2 = V3]).
154.15/40.18	eq(le(V, V2, Out),1,[],[Out = 0,V4 >= 0,V = 1 + V4,V2 = 0]).
154.15/40.18	eq(le(V, V2, Out),1,[le(V5, V6, Ret)],[Out = Ret,V2 = 1 + V6,V5 >= 0,V6 >= 0,V = 1 + V5]).
154.15/40.18	eq(average(V, V2, Out),1,[le(V7, 0, Ret0),le(V8, 0, Ret1),le(V8, 1 + 0, Ret2),le(V8, 1 + (1 + 0), Ret3),if(Ret0, Ret1, Ret2, Ret3, V7, V8, Ret4)],[Out = Ret4,V7 >= 0,V8 >= 0,V = V7,V2 = V8]).
154.15/40.18	eq(if(V, V2, V11, V17, V15, V16, Out),1,[if2(V14, V12, V13, V9, V10, Ret5)],[Out = Ret5,V12 >= 0,V15 = V9,V14 >= 0,V = 1,V17 = V13,V16 = V10,V9 >= 0,V10 >= 0,V2 = V14,V11 = V12,V13 >= 0]).
154.15/40.18	eq(if(V, V2, V11, V17, V15, V16, Out),1,[p(V20, Ret01),average(Ret01, 1 + V18, Ret6)],[Out = Ret6,V22 >= 0,V15 = V20,V21 >= 0,V17 = V19,V16 = V18,V20 >= 0,V18 >= 0,V2 = V21,V = 0,V11 = V22,V19 >= 0]).
154.15/40.18	eq(if2(V, V2, V11, V17, V15, Out),1,[],[Out = 0,V25 >= 0,V15 = V23,V = 1,V24 >= 0,V23 >= 0,V2 = V25,V11 = V26,V17 = V24,V26 >= 0]).
154.15/40.18	eq(if2(V, V2, V11, V17, V15, Out),1,[if3(V29, V30, V27, V28, Ret7)],[Out = Ret7,V29 >= 0,V15 = V28,V27 >= 0,V28 >= 0,V2 = V29,V = 0,V11 = V30,V17 = V27,V30 >= 0]).
154.15/40.18	eq(if3(V, V2, V11, V17, Out),1,[],[Out = 0,V17 = V32,V2 = V33,V = 1,V31 >= 0,V32 >= 0,V11 = V31,V33 >= 0]).
154.15/40.18	eq(if3(V, V2, V11, V17, Out),1,[if4(V35, V36, V34, Ret8)],[Out = Ret8,V17 = V34,V2 = V35,V36 >= 0,V34 >= 0,V11 = V36,V = 0,V35 >= 0]).
154.15/40.18	eq(if4(V, V2, V11, Out),1,[],[Out = 1,V2 = V37,V11 = V38,V = 1,V37 >= 0,V38 >= 0]).
154.15/40.18	eq(if4(V, V2, V11, Out),1,[p(V40, Ret10),p(Ret10, Ret11),average(1 + V39, Ret11, Ret9)],[Out = Ret9,V2 = V39,V11 = V40,V39 >= 0,V40 >= 0,V = 0]).
154.15/40.18	input_output_vars(p(V,Out),[V],[Out]).
154.15/40.18	input_output_vars(le(V,V2,Out),[V,V2],[Out]).
154.15/40.18	input_output_vars(average(V,V2,Out),[V,V2],[Out]).
154.15/40.18	input_output_vars(if(V,V2,V11,V17,V15,V16,Out),[V,V2,V11,V17,V15,V16],[Out]).
154.15/40.18	input_output_vars(if2(V,V2,V11,V17,V15,Out),[V,V2,V11,V17,V15],[Out]).
154.15/40.18	input_output_vars(if3(V,V2,V11,V17,Out),[V,V2,V11,V17],[Out]).
154.15/40.18	input_output_vars(if4(V,V2,V11,Out),[V,V2,V11],[Out]).
154.15/40.18	
154.15/40.18	
154.15/40.18	CoFloCo proof output:
154.15/40.18	Preprocessing Cost Relations
154.15/40.18	=====================================
154.15/40.18	
154.15/40.18	#### Computed strongly connected components 
154.15/40.18	0. non_recursive  : [p/2]
154.15/40.18	1. recursive  : [le/3]
154.15/40.18	2. recursive  : [average/3,if/7,if2/6,if3/5,if4/4]
154.15/40.18	3. non_recursive  : [start/6]
154.15/40.18	
154.15/40.18	#### Obtained direct recursion through partial evaluation 
154.15/40.18	0. SCC is partially evaluated into p/2
154.15/40.18	1. SCC is partially evaluated into le/3
154.15/40.18	2. SCC is partially evaluated into average/3
154.15/40.18	3. SCC is partially evaluated into start/6
154.15/40.18	
154.15/40.18	Control-Flow Refinement of Cost Relations
154.15/40.18	=====================================
154.15/40.18	
154.15/40.18	### Specialization of cost equations p/2 
154.15/40.18	* CE 15 is refined into CE [25] 
154.15/40.18	* CE 16 is refined into CE [26] 
154.15/40.18	
154.15/40.18	
154.15/40.18	### Cost equations --> "Loop" of p/2 
154.15/40.18	* CEs [25] --> Loop 17 
154.15/40.18	* CEs [26] --> Loop 18 
154.15/40.18	
154.15/40.18	### Ranking functions of CR p(V,Out) 
154.15/40.18	
154.15/40.18	#### Partial ranking functions of CR p(V,Out) 
154.15/40.18	
154.15/40.18	
154.15/40.18	### Specialization of cost equations le/3 
154.15/40.18	* CE 24 is refined into CE [27] 
154.15/40.18	* CE 23 is refined into CE [28] 
154.15/40.18	* CE 22 is refined into CE [29] 
154.15/40.18	
154.15/40.18	
154.15/40.18	### Cost equations --> "Loop" of le/3 
154.15/40.18	* CEs [28] --> Loop 19 
154.15/40.18	* CEs [29] --> Loop 20 
154.15/40.18	* CEs [27] --> Loop 21 
154.15/40.18	
154.15/40.18	### Ranking functions of CR le(V,V2,Out) 
154.15/40.18	* RF of phase [21]: [V,V2]
154.15/40.18	
154.15/40.18	#### Partial ranking functions of CR le(V,V2,Out) 
154.15/40.18	* Partial RF of phase [21]:
154.15/40.18	  - RF of loop [21:1]:
154.15/40.18	    V
154.15/40.18	    V2
154.15/40.18	
154.15/40.18	
154.15/40.18	### Specialization of cost equations average/3 
154.15/40.18	* CE 18 is refined into CE [30] 
154.15/40.18	* CE 17 is refined into CE [31] 
154.15/40.18	* CE 21 is refined into CE [32] 
154.15/40.18	* CE 20 is refined into CE [33,34,35,36] 
154.15/40.18	* CE 19 is refined into CE [37] 
154.15/40.18	
154.15/40.18	
154.15/40.18	### Cost equations --> "Loop" of average/3 
154.15/40.18	* CEs [34] --> Loop 22 
154.15/40.18	* CEs [35] --> Loop 23 
154.15/40.18	* CEs [36] --> Loop 24 
154.15/40.18	* CEs [33] --> Loop 25 
154.15/40.18	* CEs [37] --> Loop 26 
154.15/40.18	* CEs [30] --> Loop 27 
154.15/40.18	* CEs [31] --> Loop 28 
154.15/40.18	* CEs [32] --> Loop 29 
154.15/40.18	
154.15/40.18	### Ranking functions of CR average(V,V2,Out) 
154.15/40.18	* RF of phase [22,23,24,26]: [3*V+2*V2-4]
154.15/40.18	
154.15/40.18	#### Partial ranking functions of CR average(V,V2,Out) 
154.15/40.18	* Partial RF of phase [22,23,24,26]:
154.15/40.18	  - RF of loop [22:1,23:1,24:1]:
154.15/40.18	    V depends on loops [26:1] 
154.15/40.18	  - RF of loop [23:1]:
154.15/40.18	    -V2+3 depends on loops [26:1] 
154.15/40.18	  - RF of loop [24:1]:
154.15/40.18	    -V2+2 depends on loops [26:1] 
154.15/40.18	  - RF of loop [26:1]:
154.15/40.18	    -V+1 depends on loops [22:1,23:1,24:1] 
154.15/40.18	    V2/2-1 depends on loops [22:1,23:1,24:1] 
154.15/40.18	
154.15/40.18	
154.15/40.18	### Specialization of cost equations start/6 
154.15/40.18	* CE 10 is refined into CE [38] 
154.15/40.18	* CE 1 is refined into CE [39] 
154.15/40.18	* CE 4 is refined into CE [40] 
154.15/40.18	* CE 3 is refined into CE [41] 
154.15/40.18	* CE 6 is refined into CE [42,43,44,45,46,47,48] 
154.15/40.18	* CE 2 is refined into CE [49] 
154.15/40.18	* CE 5 is refined into CE [50] 
154.15/40.18	* CE 7 is refined into CE [51,52,53,54,55,56,57] 
154.15/40.18	* CE 8 is refined into CE [58,59,60,61,62,63,64] 
154.15/40.18	* CE 9 is refined into CE [65,66,67,68,69,70] 
154.15/40.18	* CE 11 is refined into CE [71,72,73,74,75,76,77] 
154.15/40.18	* CE 12 is refined into CE [78,79] 
154.15/40.18	* CE 13 is refined into CE [80,81,82,83] 
154.15/40.18	* CE 14 is refined into CE [84,85,86,87,88,89] 
154.15/40.18	
154.15/40.18	
154.15/40.18	### Cost equations --> "Loop" of start/6 
154.15/40.18	* CEs [89] --> Loop 30 
154.15/40.18	* CEs [38,41] --> Loop 31 
154.15/40.18	* CEs [39,40,42,43,44,45,46,47,48,79,81,82,83,87,88] --> Loop 32 
154.15/40.18	* CEs [49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,80,84,85,86] --> Loop 33 
154.15/40.18	
154.15/40.18	### Ranking functions of CR start(V,V2,V11,V17,V15,V16) 
154.15/40.18	
154.15/40.18	#### Partial ranking functions of CR start(V,V2,V11,V17,V15,V16) 
154.15/40.18	
154.15/40.18	
154.15/40.18	Computing Bounds
154.15/40.18	=====================================
154.15/40.18	
154.15/40.18	#### Cost of chains of p(V,Out):
154.15/40.18	* Chain [18]: 1
154.15/40.18	  with precondition: [V=0,Out=0] 
154.15/40.18	
154.15/40.18	* Chain [17]: 1
154.15/40.18	  with precondition: [V=Out+1,V>=1] 
154.15/40.18	
154.15/40.18	
154.15/40.18	#### Cost of chains of le(V,V2,Out):
154.15/40.18	* Chain [[21],20]: 1*it(21)+1
154.15/40.18	  Such that:it(21) =< V
154.15/40.18	
154.15/40.18	  with precondition: [Out=1,V>=1,V2>=V] 
154.15/40.18	
154.15/40.18	* Chain [[21],19]: 1*it(21)+1
154.15/40.18	  Such that:it(21) =< V2
154.15/40.18	
154.15/40.18	  with precondition: [Out=0,V2>=1,V>=V2+1] 
154.15/40.18	
154.15/40.18	* Chain [20]: 1
154.15/40.18	  with precondition: [V=0,Out=1,V2>=0] 
154.15/40.18	
154.15/40.18	* Chain [19]: 1
154.15/40.18	  with precondition: [V2=0,Out=0,V>=1] 
154.15/40.18	
154.15/40.18	
154.15/40.18	#### Cost of chains of average(V,V2,Out):
154.15/40.18	* Chain [[22,23,24,26],27]: 37*it(22)+1*s(1)+1*s(2)+3*s(20)+9
154.15/40.18	  Such that:s(1) =< 1
154.15/40.18	s(2) =< 2
154.15/40.18	aux(28) =< 3*V+2*V2
154.15/40.18	it(22) =< aux(28)
154.15/40.18	s(20) =< aux(28)*2
154.15/40.18	
154.15/40.18	  with precondition: [Out=1,V>=0,V2>=1,V2+2*V>=3] 
154.15/40.18	
154.15/40.18	* Chain [29]: 7
154.15/40.18	  with precondition: [V=0,V2=0,Out=0] 
154.15/40.18	
154.15/40.18	* Chain [28]: 2*s(27)+8
154.15/40.18	  Such that:aux(29) =< 1
154.15/40.18	s(27) =< aux(29)
154.15/40.18	
154.15/40.18	  with precondition: [V=0,V2=1,Out=0] 
154.15/40.18	
154.15/40.18	* Chain [27]: 1*s(1)+1*s(2)+9
154.15/40.18	  Such that:s(1) =< 1
154.15/40.18	s(2) =< 2
154.15/40.18	
154.15/40.18	  with precondition: [V=0,V2=2,Out=1] 
154.15/40.18	
154.15/40.18	* Chain [25,[22,23,24,26],27]: 37*it(22)+1*s(1)+1*s(2)+3*s(20)+16
154.15/40.18	  Such that:s(1) =< 1
154.15/40.18	s(2) =< 2
154.15/40.18	aux(28) =< 3*V
154.15/40.18	it(22) =< aux(28)
154.15/40.18	s(20) =< aux(28)*2
154.15/40.18	
154.15/40.18	  with precondition: [V2=0,Out=1,V>=2] 
154.15/40.18	
154.15/40.18	* Chain [25,28]: 2*s(27)+15
154.15/40.18	  Such that:aux(29) =< 1
154.15/40.18	s(27) =< aux(29)
154.15/40.18	
154.15/40.18	  with precondition: [V=1,V2=0,Out=0] 
154.15/40.18	
154.15/40.18	
154.15/40.18	#### Cost of chains of start(V,V2,V11,V17,V15,V16):
154.15/40.18	* Chain [33]: 41*s(30)+17*s(32)+111*s(34)+9*s(35)+37*s(53)+3*s(54)+111*s(60)+9*s(61)+37*s(79)+3*s(80)+37*s(88)+3*s(89)+37*s(97)+3*s(98)+111*s(104)+9*s(105)+37*s(123)+3*s(124)+21
154.15/40.18	  Such that:s(122) =< 3*V2+2*V11
154.15/40.18	s(78) =< 3*V11+2*V17
154.15/40.18	s(52) =< 3*V17+2*V15
154.15/40.18	s(96) =< 3*V15+2*V16
154.15/40.18	s(87) =< 2*V16+2
154.15/40.18	aux(30) =< 1
154.15/40.18	aux(31) =< 2
154.15/40.18	aux(32) =< 3*V2+3
154.15/40.18	aux(33) =< 3*V11+3
154.15/40.18	aux(34) =< 3*V17+3
154.15/40.18	s(30) =< aux(30)
154.15/40.18	s(32) =< aux(31)
154.15/40.18	s(34) =< aux(34)
154.15/40.18	s(35) =< aux(34)*2
154.15/40.18	s(53) =< s(52)
154.15/40.18	s(54) =< s(52)*2
154.15/40.18	s(60) =< aux(33)
154.15/40.18	s(61) =< aux(33)*2
154.15/40.18	s(79) =< s(78)
154.15/40.18	s(80) =< s(78)*2
154.15/40.18	s(88) =< s(87)
154.15/40.18	s(89) =< s(87)*2
154.15/40.18	s(97) =< s(96)
154.15/40.18	s(98) =< s(96)*2
154.15/40.18	s(104) =< aux(32)
154.15/40.18	s(105) =< aux(32)*2
154.15/40.18	s(123) =< s(122)
154.15/40.18	s(124) =< s(122)*2
154.15/40.18	
154.15/40.18	  with precondition: [V=0] 
154.15/40.18	
154.15/40.18	* Chain [32]: 13*s(130)+5*s(132)+111*s(134)+9*s(135)+37*s(153)+3*s(154)+1*s(155)+1*s(156)+37*s(162)+3*s(163)+22
154.15/40.18	  Such that:s(156) =< V
154.15/40.18	s(161) =< 3*V
154.15/40.18	s(155) =< V2
154.15/40.18	s(152) =< 3*V15+2*V16
154.15/40.18	aux(35) =< 1
154.15/40.18	aux(36) =< 2
154.15/40.18	aux(37) =< 3*V15+3
154.15/40.18	s(130) =< aux(35)
154.15/40.18	s(132) =< aux(36)
154.15/40.18	s(134) =< aux(37)
154.15/40.18	s(135) =< aux(37)*2
154.15/40.18	s(153) =< s(152)
154.15/40.18	s(154) =< s(152)*2
154.15/40.18	s(162) =< s(161)
154.15/40.18	s(163) =< s(161)*2
154.15/40.18	
154.15/40.18	  with precondition: [V>=1] 
154.15/40.18	
154.15/40.18	* Chain [31]: 2
154.15/40.18	  with precondition: [V=1,V2>=0,V11>=0] 
154.15/40.18	
154.15/40.18	* Chain [30]: 1*s(164)+1*s(165)+37*s(167)+3*s(168)+9
154.15/40.18	  Such that:s(164) =< 1
154.15/40.18	s(165) =< 2
154.15/40.18	s(166) =< 3*V+2*V2
154.15/40.18	s(167) =< s(166)
154.15/40.18	s(168) =< s(166)*2
154.15/40.18	
154.15/40.18	  with precondition: [V>=0,V2>=1,V2+2*V>=3] 
154.15/40.18	
154.15/40.18	
154.15/40.18	Closed-form bounds of start(V,V2,V11,V17,V15,V16): 
154.15/40.18	-------------------------------------
154.15/40.18	* Chain [33] with precondition: [V=0] 
154.15/40.18	    - Upper bound: nat(2*V16+2)*43+96+nat(3*V2+3)*129+nat(3*V2+2*V11)*43+nat(3*V11+3)*129+nat(3*V11+2*V17)*43+nat(3*V17+3)*129+nat(3*V17+2*V15)*43+nat(3*V15+2*V16)*43 
154.15/40.18	    - Complexity: n 
154.15/40.18	* Chain [32] with precondition: [V>=1] 
154.15/40.18	    - Upper bound: V+45+nat(V2)+129*V+nat(3*V15+3)*129+nat(3*V15+2*V16)*43 
154.15/40.18	    - Complexity: n 
154.15/40.18	* Chain [31] with precondition: [V=1,V2>=0,V11>=0] 
154.15/40.18	    - Upper bound: 2 
154.15/40.18	    - Complexity: constant 
154.15/40.18	* Chain [30] with precondition: [V>=0,V2>=1,V2+2*V>=3] 
154.15/40.18	    - Upper bound: 129*V+86*V2+12 
154.15/40.18	    - Complexity: n 
154.15/40.18	
154.15/40.18	### Maximum cost of start(V,V2,V11,V17,V15,V16): max([nat(3*V+2*V2)*43+10,nat(3*V15+2*V16)*43+43+max([nat(V2)+V+129*V+nat(3*V15+3)*129,nat(2*V16+2)*43+51+nat(3*V2+3)*129+nat(3*V2+2*V11)*43+nat(3*V11+3)*129+nat(3*V11+2*V17)*43+nat(3*V17+3)*129+nat(3*V17+2*V15)*43])])+2 
154.15/40.18	Asymptotic class: n 
154.15/40.18	* Total analysis performed in 594 ms.
154.15/40.18	
154.15/40.18	
154.15/40.18	----------------------------------------
154.15/40.18	
154.15/40.18	(10)
154.15/40.18	BOUNDS(1, n^1)
154.15/40.18	
154.15/40.18	----------------------------------------
154.15/40.18	
154.15/40.18	(11) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
154.15/40.18	Transformed a relative TRS into a decreasing-loop problem.
154.15/40.18	----------------------------------------
154.15/40.18	
154.15/40.18	(12)
154.15/40.18	Obligation:
154.15/40.18	Analyzing the following TRS for decreasing loops:
154.15/40.18	
154.15/40.18	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
154.15/40.18	
154.15/40.18	
154.15/40.18	The TRS R consists of the following rules:
154.15/40.18	
154.15/40.18	   p(s(x)) -> x
154.15/40.18	   p(0) -> 0
154.15/40.18	   le(0, y) -> true
154.15/40.18	   le(s(x), 0) -> false
154.15/40.18	   le(s(x), s(y)) -> le(x, y)
154.15/40.18	   average(x, y) -> if(le(x, 0), le(y, 0), le(y, s(0)), le(y, s(s(0))), x, y)
154.15/40.18	   if(true, b1, b2, b3, x, y) -> if2(b1, b2, b3, x, y)
154.15/40.18	   if(false, b1, b2, b3, x, y) -> average(p(x), s(y))
154.15/40.18	   if2(true, b2, b3, x, y) -> 0
154.15/40.18	   if2(false, b2, b3, x, y) -> if3(b2, b3, x, y)
154.15/40.18	   if3(true, b3, x, y) -> 0
154.15/40.18	   if3(false, b3, x, y) -> if4(b3, x, y)
154.15/40.18	   if4(true, x, y) -> s(0)
154.15/40.18	   if4(false, x, y) -> average(s(x), p(p(y)))
154.15/40.18	
154.15/40.18	S is empty.
154.15/40.18	Rewrite Strategy: INNERMOST
154.15/40.18	----------------------------------------
154.15/40.18	
154.15/40.18	(13) DecreasingLoopProof (LOWER BOUND(ID))
154.15/40.18	The following loop(s) give(s) rise to the lower bound Omega(n^1):
154.15/40.18	
154.15/40.18	The rewrite sequence
154.15/40.18	
154.15/40.18	le(s(x), s(y)) ->^+ le(x, y)
154.15/40.18	
154.15/40.18	gives rise to a decreasing loop by considering the right hand sides subterm at position [].
154.15/40.18	
154.15/40.18	The pumping substitution is [x / s(x), y / s(y)].
154.15/40.18	
154.15/40.18	The result substitution is [ ].
154.15/40.18	
154.15/40.18	
154.15/40.18	
154.15/40.18	
154.15/40.18	----------------------------------------
154.15/40.18	
154.15/40.18	(14)
154.15/40.18	Complex Obligation (BEST)
154.15/40.18	
154.15/40.18	----------------------------------------
154.15/40.18	
154.15/40.18	(15)
154.15/40.18	Obligation:
154.15/40.18	Proved the lower bound n^1 for the following obligation:
154.15/40.18	
154.15/40.18	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
154.15/40.18	
154.15/40.18	
154.15/40.18	The TRS R consists of the following rules:
154.15/40.18	
154.15/40.18	   p(s(x)) -> x
154.15/40.18	   p(0) -> 0
154.15/40.18	   le(0, y) -> true
154.15/40.18	   le(s(x), 0) -> false
154.15/40.18	   le(s(x), s(y)) -> le(x, y)
154.15/40.18	   average(x, y) -> if(le(x, 0), le(y, 0), le(y, s(0)), le(y, s(s(0))), x, y)
154.15/40.18	   if(true, b1, b2, b3, x, y) -> if2(b1, b2, b3, x, y)
154.15/40.18	   if(false, b1, b2, b3, x, y) -> average(p(x), s(y))
154.15/40.18	   if2(true, b2, b3, x, y) -> 0
154.15/40.18	   if2(false, b2, b3, x, y) -> if3(b2, b3, x, y)
154.15/40.18	   if3(true, b3, x, y) -> 0
154.15/40.18	   if3(false, b3, x, y) -> if4(b3, x, y)
154.15/40.18	   if4(true, x, y) -> s(0)
154.15/40.18	   if4(false, x, y) -> average(s(x), p(p(y)))
154.15/40.18	
154.15/40.18	S is empty.
154.15/40.18	Rewrite Strategy: INNERMOST
154.15/40.18	----------------------------------------
154.15/40.18	
154.15/40.18	(16) LowerBoundPropagationProof (FINISHED)
154.15/40.18	Propagated lower bound.
154.15/40.18	----------------------------------------
154.15/40.18	
154.15/40.18	(17)
154.15/40.18	BOUNDS(n^1, INF)
154.15/40.18	
154.15/40.18	----------------------------------------
154.15/40.18	
154.15/40.18	(18)
154.15/40.18	Obligation:
154.15/40.18	Analyzing the following TRS for decreasing loops:
154.15/40.18	
154.15/40.18	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
154.15/40.18	
154.15/40.18	
154.15/40.18	The TRS R consists of the following rules:
154.15/40.18	
154.15/40.18	   p(s(x)) -> x
154.15/40.18	   p(0) -> 0
154.15/40.18	   le(0, y) -> true
154.15/40.18	   le(s(x), 0) -> false
154.15/40.18	   le(s(x), s(y)) -> le(x, y)
154.15/40.18	   average(x, y) -> if(le(x, 0), le(y, 0), le(y, s(0)), le(y, s(s(0))), x, y)
154.15/40.18	   if(true, b1, b2, b3, x, y) -> if2(b1, b2, b3, x, y)
154.15/40.18	   if(false, b1, b2, b3, x, y) -> average(p(x), s(y))
154.15/40.18	   if2(true, b2, b3, x, y) -> 0
154.15/40.18	   if2(false, b2, b3, x, y) -> if3(b2, b3, x, y)
154.15/40.18	   if3(true, b3, x, y) -> 0
154.15/40.18	   if3(false, b3, x, y) -> if4(b3, x, y)
154.15/40.18	   if4(true, x, y) -> s(0)
154.15/40.18	   if4(false, x, y) -> average(s(x), p(p(y)))
154.15/40.18	
154.15/40.18	S is empty.
154.15/40.18	Rewrite Strategy: INNERMOST
154.15/40.21	EOF