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