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