21.57/6.33	WORST_CASE(Omega(n^1), O(n^1))
21.57/6.34	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
21.57/6.34	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
21.57/6.34	
21.57/6.34	
21.57/6.34	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
21.57/6.34	
21.57/6.34	(0) CpxTRS
21.57/6.34	(1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
21.57/6.34	(2) CpxWeightedTrs
21.57/6.34	    (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
21.57/6.34	    (4) CpxTypedWeightedTrs
21.57/6.34	    (5) CompletionProof [UPPER BOUND(ID), 0 ms]
21.57/6.34	    (6) CpxTypedWeightedCompleteTrs
21.57/6.34	    (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
21.57/6.34	    (8) CpxRNTS
21.57/6.34	    (9) CompleteCoflocoProof [FINISHED, 129 ms]
21.57/6.34	    (10) BOUNDS(1, n^1)
21.57/6.34	(11) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
21.57/6.34	(12) TRS for Loop Detection
21.57/6.34	    (13) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
21.57/6.34	    (14) BEST
21.57/6.34	        (15) proven lower bound
21.57/6.34	            (16) LowerBoundPropagationProof [FINISHED, 0 ms]
21.57/6.34	            (17) BOUNDS(n^1, INF)
21.57/6.34	        (18) TRS for Loop Detection
21.57/6.34	
21.57/6.34	
21.57/6.34	----------------------------------------
21.57/6.34	
21.57/6.34	(0)
21.57/6.34	Obligation:
21.57/6.34	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
21.57/6.34	
21.57/6.34	
21.57/6.34	The TRS R consists of the following rules:
21.57/6.34	
21.57/6.34	   half(0) -> 0
21.57/6.34	   half(s(s(x))) -> s(half(x))
21.57/6.34	   log(s(0)) -> 0
21.57/6.34	   log(s(s(x))) -> s(log(s(half(x))))
21.57/6.34	
21.57/6.34	S is empty.
21.57/6.34	Rewrite Strategy: INNERMOST
21.57/6.34	----------------------------------------
21.57/6.34	
21.57/6.34	(1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
21.57/6.34	Transformed relative TRS to weighted TRS
21.57/6.34	----------------------------------------
21.57/6.34	
21.57/6.34	(2)
21.57/6.34	Obligation:
21.57/6.34	The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1).
21.57/6.34	
21.57/6.34	
21.57/6.34	The TRS R consists of the following rules:
21.57/6.34	
21.57/6.34	   half(0) -> 0 [1]
21.57/6.34	   half(s(s(x))) -> s(half(x)) [1]
21.57/6.34	   log(s(0)) -> 0 [1]
21.57/6.34	   log(s(s(x))) -> s(log(s(half(x)))) [1]
21.57/6.34	
21.57/6.34	Rewrite Strategy: INNERMOST
21.57/6.34	----------------------------------------
21.57/6.34	
21.57/6.34	(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
21.57/6.34	Infered types.
21.57/6.34	----------------------------------------
21.57/6.34	
21.57/6.34	(4)
21.57/6.34	Obligation:
21.57/6.34	Runtime Complexity Weighted TRS with Types.
21.57/6.34	The TRS R consists of the following rules:
21.57/6.34	
21.57/6.34	   half(0) -> 0 [1]
21.57/6.34	   half(s(s(x))) -> s(half(x)) [1]
21.57/6.34	   log(s(0)) -> 0 [1]
21.57/6.34	   log(s(s(x))) -> s(log(s(half(x)))) [1]
21.57/6.34	
21.57/6.34	The TRS has the following type information:
21.57/6.34	half :: 0:s -> 0:s
21.57/6.34	0 :: 0:s
21.57/6.34	s :: 0:s -> 0:s
21.57/6.34	log :: 0:s -> 0:s
21.57/6.34	
21.57/6.34	Rewrite Strategy: INNERMOST
21.57/6.34	----------------------------------------
21.57/6.34	
21.57/6.34	(5) CompletionProof (UPPER BOUND(ID))
21.57/6.34	The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added:
21.57/6.34	
21.57/6.34	   half(v0) -> null_half [0]
21.57/6.34	   log(v0) -> null_log [0]
21.57/6.34	
21.57/6.34	And the following fresh constants:    null_half, null_log
21.57/6.34	
21.57/6.34	----------------------------------------
21.57/6.34	
21.57/6.34	(6)
21.57/6.34	Obligation:
21.57/6.34	Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is:
21.57/6.34	
21.57/6.34	Runtime Complexity Weighted TRS with Types.
21.57/6.34	The TRS R consists of the following rules:
21.57/6.34	
21.57/6.34	   half(0) -> 0 [1]
21.57/6.34	   half(s(s(x))) -> s(half(x)) [1]
21.57/6.34	   log(s(0)) -> 0 [1]
21.57/6.34	   log(s(s(x))) -> s(log(s(half(x)))) [1]
21.57/6.34	   half(v0) -> null_half [0]
21.57/6.34	   log(v0) -> null_log [0]
21.57/6.34	
21.57/6.34	The TRS has the following type information:
21.57/6.34	half :: 0:s:null_half:null_log -> 0:s:null_half:null_log
21.57/6.34	0 :: 0:s:null_half:null_log
21.57/6.34	s :: 0:s:null_half:null_log -> 0:s:null_half:null_log
21.57/6.34	log :: 0:s:null_half:null_log -> 0:s:null_half:null_log
21.57/6.34	null_half :: 0:s:null_half:null_log
21.57/6.34	null_log :: 0:s:null_half:null_log
21.57/6.34	
21.57/6.34	Rewrite Strategy: INNERMOST
21.57/6.34	----------------------------------------
21.57/6.34	
21.57/6.34	(7) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
21.57/6.34	Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
21.57/6.34	The constant constructors are abstracted as follows:
21.57/6.34	
21.57/6.34	   0 => 0
21.57/6.34	   null_half => 0
21.57/6.34	   null_log => 0
21.57/6.34	
21.57/6.34	----------------------------------------
21.57/6.34	
21.57/6.34	(8)
21.57/6.34	Obligation:
21.57/6.34	Complexity RNTS consisting of the following rules:
21.57/6.34	
21.57/6.34	   half(z) -{ 1 }-> 0 :|: z = 0
21.57/6.34	   half(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
21.57/6.34	   half(z) -{ 1 }-> 1 + half(x) :|: x >= 0, z = 1 + (1 + x)
21.57/6.34	   log(z) -{ 1 }-> 0 :|: z = 1 + 0
21.57/6.34	   log(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
21.57/6.34	   log(z) -{ 1 }-> 1 + log(1 + half(x)) :|: x >= 0, z = 1 + (1 + x)
21.57/6.34	
21.57/6.34	Only complete derivations are relevant for the runtime complexity.
21.57/6.34	
21.57/6.34	----------------------------------------
21.57/6.34	
21.57/6.34	(9) CompleteCoflocoProof (FINISHED)
21.57/6.34	Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo:
21.57/6.34	
21.57/6.34	eq(start(V),0,[half(V, Out)],[V >= 0]).
21.57/6.34	eq(start(V),0,[log(V, Out)],[V >= 0]).
21.57/6.34	eq(half(V, Out),1,[],[Out = 0,V = 0]).
21.57/6.34	eq(half(V, Out),1,[half(V1, Ret1)],[Out = 1 + Ret1,V1 >= 0,V = 2 + V1]).
21.57/6.34	eq(log(V, Out),1,[],[Out = 0,V = 1]).
21.57/6.34	eq(log(V, Out),1,[half(V2, Ret101),log(1 + Ret101, Ret11)],[Out = 1 + Ret11,V2 >= 0,V = 2 + V2]).
21.57/6.34	eq(half(V, Out),0,[],[Out = 0,V3 >= 0,V = V3]).
21.57/6.34	eq(log(V, Out),0,[],[Out = 0,V4 >= 0,V = V4]).
21.57/6.34	input_output_vars(half(V,Out),[V],[Out]).
21.57/6.34	input_output_vars(log(V,Out),[V],[Out]).
21.57/6.34	
21.57/6.34	
21.57/6.34	CoFloCo proof output:
21.57/6.34	Preprocessing Cost Relations
21.57/6.34	=====================================
21.57/6.34	
21.57/6.34	#### Computed strongly connected components 
21.57/6.34	0. recursive  : [half/2]
21.57/6.34	1. recursive  : [log/2]
21.57/6.34	2. non_recursive  : [start/1]
21.57/6.34	
21.57/6.34	#### Obtained direct recursion through partial evaluation 
21.57/6.34	0. SCC is partially evaluated into half/2
21.57/6.34	1. SCC is partially evaluated into log/2
21.57/6.34	2. SCC is partially evaluated into start/1
21.57/6.34	
21.57/6.34	Control-Flow Refinement of Cost Relations
21.57/6.34	=====================================
21.57/6.34	
21.57/6.34	### Specialization of cost equations half/2 
21.57/6.34	* CE 3 is refined into CE [9] 
21.57/6.34	* CE 5 is refined into CE [10] 
21.57/6.34	* CE 4 is refined into CE [11] 
21.57/6.34	
21.57/6.34	
21.57/6.34	### Cost equations --> "Loop" of half/2 
21.57/6.34	* CEs [11] --> Loop 6 
21.57/6.34	* CEs [9,10] --> Loop 7 
21.57/6.34	
21.57/6.34	### Ranking functions of CR half(V,Out) 
21.57/6.34	* RF of phase [6]: [V-1]
21.57/6.34	
21.57/6.34	#### Partial ranking functions of CR half(V,Out) 
21.57/6.34	* Partial RF of phase [6]:
21.57/6.34	  - RF of loop [6:1]:
21.57/6.34	    V-1
21.57/6.34	
21.57/6.34	
21.57/6.34	### Specialization of cost equations log/2 
21.57/6.34	* CE 6 is refined into CE [12] 
21.57/6.34	* CE 8 is refined into CE [13] 
21.57/6.34	* CE 7 is refined into CE [14,15] 
21.57/6.34	
21.57/6.34	
21.57/6.34	### Cost equations --> "Loop" of log/2 
21.57/6.34	* CEs [15] --> Loop 8 
21.57/6.34	* CEs [14] --> Loop 9 
21.57/6.34	* CEs [12,13] --> Loop 10 
21.57/6.34	
21.57/6.34	### Ranking functions of CR log(V,Out) 
21.57/6.34	* RF of phase [8]: [V-3]
21.57/6.34	
21.57/6.34	#### Partial ranking functions of CR log(V,Out) 
21.57/6.34	* Partial RF of phase [8]:
21.57/6.34	  - RF of loop [8:1]:
21.57/6.34	    V-3
21.57/6.34	
21.57/6.34	
21.57/6.34	### Specialization of cost equations start/1 
21.57/6.34	* CE 1 is refined into CE [16,17] 
21.57/6.34	* CE 2 is refined into CE [18,19,20,21] 
21.57/6.34	
21.57/6.34	
21.57/6.34	### Cost equations --> "Loop" of start/1 
21.57/6.34	* CEs [16,17,18,19,20,21] --> Loop 11 
21.57/6.34	
21.57/6.34	### Ranking functions of CR start(V) 
21.57/6.34	
21.57/6.34	#### Partial ranking functions of CR start(V) 
21.57/6.34	
21.57/6.34	
21.57/6.34	Computing Bounds
21.57/6.34	=====================================
21.57/6.34	
21.57/6.34	#### Cost of chains of half(V,Out):
21.57/6.34	* Chain [[6],7]: 1*it(6)+1
21.57/6.34	  Such that:it(6) =< 2*Out
21.57/6.34	
21.57/6.34	  with precondition: [Out>=1,V>=2*Out] 
21.57/6.34	
21.57/6.34	* Chain [7]: 1
21.57/6.34	  with precondition: [Out=0,V>=0] 
21.57/6.34	
21.57/6.34	
21.57/6.34	#### Cost of chains of log(V,Out):
21.57/6.34	* Chain [[8],10]: 2*it(8)+1*s(3)+1
21.57/6.34	  Such that:it(8) =< V
21.57/6.34	s(3) =< 2*V
21.57/6.34	
21.57/6.34	  with precondition: [Out>=1,V>=4*Out] 
21.57/6.34	
21.57/6.34	* Chain [[8],9,10]: 2*it(8)+1*s(3)+3
21.57/6.34	  Such that:it(8) =< V
21.57/6.34	s(3) =< 2*V
21.57/6.34	
21.57/6.34	  with precondition: [Out>=2,V+4>=4*Out] 
21.57/6.34	
21.57/6.34	* Chain [10]: 1
21.57/6.34	  with precondition: [Out=0,V>=0] 
21.57/6.34	
21.57/6.34	* Chain [9,10]: 3
21.57/6.34	  with precondition: [Out=1,V>=2] 
21.57/6.34	
21.57/6.34	
21.57/6.34	#### Cost of chains of start(V):
21.57/6.34	* Chain [11]: 5*s(4)+2*s(6)+3
21.57/6.34	  Such that:aux(1) =< V
21.57/6.34	aux(2) =< 2*V
21.57/6.34	s(4) =< aux(1)
21.57/6.34	s(6) =< aux(2)
21.57/6.34	
21.57/6.34	  with precondition: [V>=0] 
21.57/6.34	
21.57/6.34	
21.57/6.34	Closed-form bounds of start(V): 
21.57/6.34	-------------------------------------
21.57/6.34	* Chain [11] with precondition: [V>=0] 
21.57/6.34	    - Upper bound: 9*V+3 
21.57/6.34	    - Complexity: n 
21.57/6.34	
21.57/6.34	### Maximum cost of start(V): 9*V+3 
21.57/6.34	Asymptotic class: n 
21.57/6.34	* Total analysis performed in 82 ms.
21.57/6.34	
21.57/6.34	
21.57/6.34	----------------------------------------
21.57/6.34	
21.57/6.34	(10)
21.57/6.34	BOUNDS(1, n^1)
21.57/6.34	
21.57/6.34	----------------------------------------
21.57/6.34	
21.57/6.34	(11) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
21.57/6.34	Transformed a relative TRS into a decreasing-loop problem.
21.57/6.34	----------------------------------------
21.57/6.34	
21.57/6.34	(12)
21.57/6.34	Obligation:
21.57/6.34	Analyzing the following TRS for decreasing loops:
21.57/6.34	
21.57/6.34	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
21.57/6.34	
21.57/6.34	
21.57/6.34	The TRS R consists of the following rules:
21.57/6.34	
21.57/6.34	   half(0) -> 0
21.57/6.34	   half(s(s(x))) -> s(half(x))
21.57/6.34	   log(s(0)) -> 0
21.57/6.34	   log(s(s(x))) -> s(log(s(half(x))))
21.57/6.34	
21.57/6.34	S is empty.
21.57/6.34	Rewrite Strategy: INNERMOST
21.57/6.34	----------------------------------------
21.57/6.34	
21.57/6.34	(13) DecreasingLoopProof (LOWER BOUND(ID))
21.57/6.34	The following loop(s) give(s) rise to the lower bound Omega(n^1):
21.57/6.34	
21.57/6.34	The rewrite sequence
21.57/6.34	
21.57/6.34	half(s(s(x))) ->^+ s(half(x))
21.57/6.34	
21.57/6.34	gives rise to a decreasing loop by considering the right hand sides subterm at position [0].
21.57/6.34	
21.57/6.34	The pumping substitution is [x / s(s(x))].
21.57/6.34	
21.57/6.34	The result substitution is [ ].
21.57/6.34	
21.57/6.34	
21.57/6.34	
21.57/6.34	
21.57/6.34	----------------------------------------
21.57/6.34	
21.57/6.34	(14)
21.57/6.34	Complex Obligation (BEST)
21.57/6.34	
21.57/6.34	----------------------------------------
21.57/6.34	
21.57/6.34	(15)
21.57/6.34	Obligation:
21.57/6.34	Proved the lower bound n^1 for the following obligation:
21.57/6.34	
21.57/6.34	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
21.57/6.34	
21.57/6.34	
21.57/6.34	The TRS R consists of the following rules:
21.57/6.34	
21.57/6.34	   half(0) -> 0
21.57/6.34	   half(s(s(x))) -> s(half(x))
21.57/6.34	   log(s(0)) -> 0
21.57/6.34	   log(s(s(x))) -> s(log(s(half(x))))
21.57/6.34	
21.57/6.34	S is empty.
21.57/6.34	Rewrite Strategy: INNERMOST
21.57/6.34	----------------------------------------
21.57/6.34	
21.57/6.34	(16) LowerBoundPropagationProof (FINISHED)
21.57/6.34	Propagated lower bound.
21.57/6.34	----------------------------------------
21.57/6.34	
21.57/6.34	(17)
21.57/6.34	BOUNDS(n^1, INF)
21.57/6.34	
21.57/6.34	----------------------------------------
21.57/6.34	
21.57/6.34	(18)
21.57/6.34	Obligation:
21.57/6.34	Analyzing the following TRS for decreasing loops:
21.57/6.34	
21.57/6.34	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
21.57/6.34	
21.57/6.34	
21.57/6.34	The TRS R consists of the following rules:
21.57/6.34	
21.57/6.34	   half(0) -> 0
21.57/6.34	   half(s(s(x))) -> s(half(x))
21.57/6.34	   log(s(0)) -> 0
21.57/6.34	   log(s(s(x))) -> s(log(s(half(x))))
21.57/6.34	
21.57/6.34	S is empty.
21.57/6.34	Rewrite Strategy: INNERMOST
23.69/9.90	EOF