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