38.36/11.57	WORST_CASE(Omega(n^1), O(n^1))
38.61/11.59	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
38.61/11.59	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
38.61/11.59	
38.61/11.59	
38.61/11.59	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
38.61/11.59	
38.61/11.59	(0) CpxTRS
38.61/11.59	(1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
38.61/11.59	(2) CpxWeightedTrs
38.61/11.59	    (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
38.61/11.59	    (4) CpxTypedWeightedTrs
38.61/11.59	    (5) CompletionProof [UPPER BOUND(ID), 2 ms]
38.61/11.59	    (6) CpxTypedWeightedCompleteTrs
38.61/11.59	    (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
38.61/11.59	    (8) CpxRNTS
38.61/11.59	    (9) CompleteCoflocoProof [FINISHED, 504 ms]
38.61/11.59	    (10) BOUNDS(1, n^1)
38.61/11.59	(11) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
38.61/11.59	(12) CpxTRS
38.61/11.59	    (13) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
38.61/11.59	    (14) typed CpxTrs
38.61/11.59	    (15) OrderProof [LOWER BOUND(ID), 0 ms]
38.61/11.59	    (16) typed CpxTrs
38.61/11.59	    (17) RewriteLemmaProof [LOWER BOUND(ID), 291 ms]
38.61/11.59	    (18) BEST
38.61/11.59	        (19) proven lower bound
38.61/11.59	            (20) LowerBoundPropagationProof [FINISHED, 0 ms]
38.61/11.59	            (21) BOUNDS(n^1, INF)
38.61/11.59	        (22) typed CpxTrs
38.61/11.59	            (23) RewriteLemmaProof [LOWER BOUND(ID), 56 ms]
38.61/11.59	            (24) typed CpxTrs
38.61/11.59	
38.61/11.59	
38.61/11.59	----------------------------------------
38.61/11.59	
38.61/11.59	(0)
38.61/11.59	Obligation:
38.61/11.59	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
38.61/11.59	
38.61/11.59	
38.61/11.59	The TRS R consists of the following rules:
38.61/11.59	
38.61/11.59	   le(0, y) -> true
38.61/11.59	   le(s(x), 0) -> false
38.61/11.59	   le(s(x), s(y)) -> le(x, y)
38.61/11.59	   minus(x, 0) -> x
38.61/11.59	   minus(s(x), s(y)) -> minus(x, y)
38.61/11.59	   mod(0, y) -> 0
38.61/11.59	   mod(s(x), 0) -> 0
38.61/11.59	   mod(s(x), s(y)) -> if_mod(le(y, x), s(x), s(y))
38.61/11.59	   if_mod(true, x, y) -> mod(minus(x, y), y)
38.61/11.59	   if_mod(false, s(x), s(y)) -> s(x)
38.61/11.59	
38.61/11.59	S is empty.
38.61/11.59	Rewrite Strategy: INNERMOST
38.61/11.59	----------------------------------------
38.61/11.59	
38.61/11.59	(1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
38.61/11.59	Transformed relative TRS to weighted TRS
38.61/11.59	----------------------------------------
38.61/11.59	
38.61/11.59	(2)
38.61/11.59	Obligation:
38.61/11.59	The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1).
38.61/11.59	
38.61/11.59	
38.61/11.59	The TRS R consists of the following rules:
38.61/11.59	
38.61/11.59	   le(0, y) -> true [1]
38.61/11.59	   le(s(x), 0) -> false [1]
38.61/11.59	   le(s(x), s(y)) -> le(x, y) [1]
38.61/11.59	   minus(x, 0) -> x [1]
38.61/11.59	   minus(s(x), s(y)) -> minus(x, y) [1]
38.61/11.59	   mod(0, y) -> 0 [1]
38.61/11.59	   mod(s(x), 0) -> 0 [1]
38.61/11.59	   mod(s(x), s(y)) -> if_mod(le(y, x), s(x), s(y)) [1]
38.61/11.59	   if_mod(true, x, y) -> mod(minus(x, y), y) [1]
38.61/11.59	   if_mod(false, s(x), s(y)) -> s(x) [1]
38.61/11.59	
38.61/11.59	Rewrite Strategy: INNERMOST
38.61/11.59	----------------------------------------
38.61/11.59	
38.61/11.59	(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
38.61/11.59	Infered types.
38.61/11.59	----------------------------------------
38.61/11.59	
38.61/11.59	(4)
38.61/11.59	Obligation:
38.61/11.59	Runtime Complexity Weighted TRS with Types.
38.61/11.59	The TRS R consists of the following rules:
38.61/11.59	
38.61/11.59	   le(0, y) -> true [1]
38.61/11.59	   le(s(x), 0) -> false [1]
38.61/11.59	   le(s(x), s(y)) -> le(x, y) [1]
38.61/11.59	   minus(x, 0) -> x [1]
38.61/11.59	   minus(s(x), s(y)) -> minus(x, y) [1]
38.61/11.59	   mod(0, y) -> 0 [1]
38.61/11.59	   mod(s(x), 0) -> 0 [1]
38.61/11.59	   mod(s(x), s(y)) -> if_mod(le(y, x), s(x), s(y)) [1]
38.61/11.59	   if_mod(true, x, y) -> mod(minus(x, y), y) [1]
38.61/11.59	   if_mod(false, s(x), s(y)) -> s(x) [1]
38.61/11.59	
38.61/11.59	The TRS has the following type information:
38.61/11.59	le :: 0:s -> 0:s -> true:false
38.61/11.59	0 :: 0:s
38.61/11.59	true :: true:false
38.61/11.59	s :: 0:s -> 0:s
38.61/11.59	false :: true:false
38.61/11.59	minus :: 0:s -> 0:s -> 0:s
38.61/11.59	mod :: 0:s -> 0:s -> 0:s
38.61/11.59	if_mod :: true:false -> 0:s -> 0:s -> 0:s
38.61/11.59	
38.61/11.59	Rewrite Strategy: INNERMOST
38.61/11.59	----------------------------------------
38.61/11.59	
38.61/11.59	(5) CompletionProof (UPPER BOUND(ID))
38.61/11.59	The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added:
38.61/11.59	
38.61/11.59	   minus(v0, v1) -> null_minus [0]
38.61/11.59	   if_mod(v0, v1, v2) -> null_if_mod [0]
38.61/11.59	   le(v0, v1) -> null_le [0]
38.61/11.59	   mod(v0, v1) -> null_mod [0]
38.61/11.59	
38.61/11.59	And the following fresh constants:    null_minus, null_if_mod, null_le, null_mod
38.61/11.59	
38.61/11.59	----------------------------------------
38.61/11.59	
38.61/11.59	(6)
38.61/11.59	Obligation:
38.61/11.59	Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is:
38.61/11.59	
38.61/11.59	Runtime Complexity Weighted TRS with Types.
38.61/11.59	The TRS R consists of the following rules:
38.61/11.59	
38.61/11.59	   le(0, y) -> true [1]
38.61/11.59	   le(s(x), 0) -> false [1]
38.61/11.59	   le(s(x), s(y)) -> le(x, y) [1]
38.61/11.59	   minus(x, 0) -> x [1]
38.61/11.59	   minus(s(x), s(y)) -> minus(x, y) [1]
38.61/11.59	   mod(0, y) -> 0 [1]
38.61/11.59	   mod(s(x), 0) -> 0 [1]
38.61/11.59	   mod(s(x), s(y)) -> if_mod(le(y, x), s(x), s(y)) [1]
38.61/11.59	   if_mod(true, x, y) -> mod(minus(x, y), y) [1]
38.61/11.59	   if_mod(false, s(x), s(y)) -> s(x) [1]
38.61/11.59	   minus(v0, v1) -> null_minus [0]
38.61/11.59	   if_mod(v0, v1, v2) -> null_if_mod [0]
38.61/11.59	   le(v0, v1) -> null_le [0]
38.61/11.59	   mod(v0, v1) -> null_mod [0]
38.61/11.59	
38.61/11.59	The TRS has the following type information:
38.61/11.59	le :: 0:s:null_minus:null_if_mod:null_mod -> 0:s:null_minus:null_if_mod:null_mod -> true:false:null_le
38.61/11.59	0 :: 0:s:null_minus:null_if_mod:null_mod
38.61/11.59	true :: true:false:null_le
38.61/11.59	s :: 0:s:null_minus:null_if_mod:null_mod -> 0:s:null_minus:null_if_mod:null_mod
38.61/11.59	false :: true:false:null_le
38.61/11.59	minus :: 0:s:null_minus:null_if_mod:null_mod -> 0:s:null_minus:null_if_mod:null_mod -> 0:s:null_minus:null_if_mod:null_mod
38.61/11.59	mod :: 0:s:null_minus:null_if_mod:null_mod -> 0:s:null_minus:null_if_mod:null_mod -> 0:s:null_minus:null_if_mod:null_mod
38.61/11.59	if_mod :: true:false:null_le -> 0:s:null_minus:null_if_mod:null_mod -> 0:s:null_minus:null_if_mod:null_mod -> 0:s:null_minus:null_if_mod:null_mod
38.61/11.59	null_minus :: 0:s:null_minus:null_if_mod:null_mod
38.61/11.59	null_if_mod :: 0:s:null_minus:null_if_mod:null_mod
38.61/11.59	null_le :: true:false:null_le
38.61/11.59	null_mod :: 0:s:null_minus:null_if_mod:null_mod
38.61/11.59	
38.61/11.59	Rewrite Strategy: INNERMOST
38.61/11.59	----------------------------------------
38.61/11.59	
38.61/11.59	(7) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
38.61/11.59	Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
38.61/11.59	The constant constructors are abstracted as follows:
38.61/11.59	
38.61/11.59	   0 => 0
38.61/11.59	   true => 2
38.61/11.59	   false => 1
38.61/11.59	   null_minus => 0
38.61/11.59	   null_if_mod => 0
38.61/11.59	   null_le => 0
38.61/11.59	   null_mod => 0
38.61/11.59	
38.61/11.59	----------------------------------------
38.61/11.59	
38.61/11.59	(8)
38.61/11.59	Obligation:
38.61/11.59	Complexity RNTS consisting of the following rules:
38.61/11.59	
38.61/11.59	   if_mod(z, z', z'') -{ 1 }-> mod(minus(x, y), y) :|: z = 2, z' = x, z'' = y, x >= 0, y >= 0
38.61/11.59	   if_mod(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0
38.61/11.59	   if_mod(z, z', z'') -{ 1 }-> 1 + x :|: z' = 1 + x, z = 1, x >= 0, y >= 0, z'' = 1 + y
38.61/11.59	   le(z, z') -{ 1 }-> le(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x
38.61/11.59	   le(z, z') -{ 1 }-> 2 :|: y >= 0, z = 0, z' = y
38.61/11.59	   le(z, z') -{ 1 }-> 1 :|: x >= 0, z = 1 + x, z' = 0
38.61/11.59	   le(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
38.61/11.59	   minus(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0
38.61/11.59	   minus(z, z') -{ 1 }-> minus(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x
38.61/11.59	   minus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
38.61/11.59	   mod(z, z') -{ 1 }-> if_mod(le(y, x), 1 + x, 1 + y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x
38.61/11.59	   mod(z, z') -{ 1 }-> 0 :|: y >= 0, z = 0, z' = y
38.61/11.59	   mod(z, z') -{ 1 }-> 0 :|: x >= 0, z = 1 + x, z' = 0
38.61/11.59	   mod(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
38.61/11.59	
38.61/11.59	Only complete derivations are relevant for the runtime complexity.
38.61/11.59	
38.61/11.59	----------------------------------------
38.61/11.59	
38.61/11.59	(9) CompleteCoflocoProof (FINISHED)
38.61/11.59	Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo:
38.61/11.59	
38.61/11.59	eq(start(V1, V, V14),0,[le(V1, V, Out)],[V1 >= 0,V >= 0]).
38.61/11.59	eq(start(V1, V, V14),0,[minus(V1, V, Out)],[V1 >= 0,V >= 0]).
38.61/11.59	eq(start(V1, V, V14),0,[mod(V1, V, Out)],[V1 >= 0,V >= 0]).
38.61/11.59	eq(start(V1, V, V14),0,[fun(V1, V, V14, Out)],[V1 >= 0,V >= 0,V14 >= 0]).
38.61/11.59	eq(le(V1, V, Out),1,[],[Out = 2,V2 >= 0,V1 = 0,V = V2]).
38.61/11.59	eq(le(V1, V, Out),1,[],[Out = 1,V3 >= 0,V1 = 1 + V3,V = 0]).
38.61/11.59	eq(le(V1, V, Out),1,[le(V4, V5, Ret)],[Out = Ret,V = 1 + V5,V4 >= 0,V5 >= 0,V1 = 1 + V4]).
38.61/11.59	eq(minus(V1, V, Out),1,[],[Out = V6,V6 >= 0,V1 = V6,V = 0]).
38.61/11.59	eq(minus(V1, V, Out),1,[minus(V7, V8, Ret1)],[Out = Ret1,V = 1 + V8,V7 >= 0,V8 >= 0,V1 = 1 + V7]).
38.61/11.59	eq(mod(V1, V, Out),1,[],[Out = 0,V9 >= 0,V1 = 0,V = V9]).
38.61/11.59	eq(mod(V1, V, Out),1,[],[Out = 0,V10 >= 0,V1 = 1 + V10,V = 0]).
38.61/11.59	eq(mod(V1, V, Out),1,[le(V11, V12, Ret0),fun(Ret0, 1 + V12, 1 + V11, Ret2)],[Out = Ret2,V = 1 + V11,V12 >= 0,V11 >= 0,V1 = 1 + V12]).
38.61/11.59	eq(fun(V1, V, V14, Out),1,[minus(V15, V13, Ret01),mod(Ret01, V13, Ret3)],[Out = Ret3,V1 = 2,V = V15,V14 = V13,V15 >= 0,V13 >= 0]).
38.61/11.59	eq(fun(V1, V, V14, Out),1,[],[Out = 1 + V16,V = 1 + V16,V1 = 1,V16 >= 0,V17 >= 0,V14 = 1 + V17]).
38.61/11.59	eq(minus(V1, V, Out),0,[],[Out = 0,V19 >= 0,V18 >= 0,V1 = V19,V = V18]).
38.61/11.59	eq(fun(V1, V, V14, Out),0,[],[Out = 0,V21 >= 0,V14 = V22,V20 >= 0,V1 = V21,V = V20,V22 >= 0]).
38.61/11.59	eq(le(V1, V, Out),0,[],[Out = 0,V24 >= 0,V23 >= 0,V1 = V24,V = V23]).
38.61/11.59	eq(mod(V1, V, Out),0,[],[Out = 0,V25 >= 0,V26 >= 0,V1 = V25,V = V26]).
38.61/11.59	input_output_vars(le(V1,V,Out),[V1,V],[Out]).
38.61/11.59	input_output_vars(minus(V1,V,Out),[V1,V],[Out]).
38.61/11.59	input_output_vars(mod(V1,V,Out),[V1,V],[Out]).
38.61/11.59	input_output_vars(fun(V1,V,V14,Out),[V1,V,V14],[Out]).
38.61/11.59	
38.61/11.59	
38.61/11.59	CoFloCo proof output:
38.61/11.59	Preprocessing Cost Relations
38.61/11.59	=====================================
38.61/11.59	
38.61/11.59	#### Computed strongly connected components 
38.61/11.59	0. recursive  : [minus/3]
38.61/11.59	1. recursive  : [le/3]
38.61/11.59	2. recursive  : [fun/4,(mod)/3]
38.61/11.59	3. non_recursive  : [start/3]
38.61/11.59	
38.61/11.59	#### Obtained direct recursion through partial evaluation 
38.61/11.59	0. SCC is partially evaluated into minus/3
38.61/11.59	1. SCC is partially evaluated into le/3
38.61/11.59	2. SCC is partially evaluated into (mod)/3
38.61/11.59	3. SCC is partially evaluated into start/3
38.61/11.59	
38.61/11.59	Control-Flow Refinement of Cost Relations
38.61/11.59	=====================================
38.61/11.59	
38.61/11.59	### Specialization of cost equations minus/3 
38.61/11.59	* CE 9 is refined into CE [20] 
38.61/11.59	* CE 7 is refined into CE [21] 
38.61/11.59	* CE 8 is refined into CE [22] 
38.61/11.59	
38.61/11.59	
38.61/11.59	### Cost equations --> "Loop" of minus/3 
38.61/11.59	* CEs [22] --> Loop 14 
38.61/11.59	* CEs [20] --> Loop 15 
38.61/11.59	* CEs [21] --> Loop 16 
38.61/11.59	
38.61/11.59	### Ranking functions of CR minus(V1,V,Out) 
38.61/11.59	* RF of phase [14]: [V,V1]
38.61/11.59	
38.61/11.59	#### Partial ranking functions of CR minus(V1,V,Out) 
38.61/11.59	* Partial RF of phase [14]:
38.61/11.59	  - RF of loop [14:1]:
38.61/11.59	    V
38.61/11.59	    V1
38.61/11.59	
38.61/11.59	
38.61/11.59	### Specialization of cost equations le/3 
38.61/11.59	* CE 19 is refined into CE [23] 
38.61/11.59	* CE 17 is refined into CE [24] 
38.61/11.59	* CE 16 is refined into CE [25] 
38.61/11.59	* CE 18 is refined into CE [26] 
38.61/11.59	
38.61/11.59	
38.61/11.59	### Cost equations --> "Loop" of le/3 
38.61/11.59	* CEs [26] --> Loop 17 
38.61/11.59	* CEs [23] --> Loop 18 
38.61/11.59	* CEs [24] --> Loop 19 
38.61/11.59	* CEs [25] --> Loop 20 
38.61/11.59	
38.61/11.59	### Ranking functions of CR le(V1,V,Out) 
38.61/11.59	* RF of phase [17]: [V,V1]
38.61/11.59	
38.61/11.59	#### Partial ranking functions of CR le(V1,V,Out) 
38.61/11.59	* Partial RF of phase [17]:
38.61/11.59	  - RF of loop [17:1]:
38.61/11.59	    V
38.61/11.59	    V1
38.61/11.59	
38.61/11.59	
38.61/11.59	### Specialization of cost equations (mod)/3 
38.61/11.59	* CE 11 is refined into CE [27,28] 
38.61/11.59	* CE 14 is refined into CE [29] 
38.61/11.59	* CE 10 is refined into CE [30,31,32,33,34] 
38.61/11.59	* CE 13 is refined into CE [35] 
38.61/11.59	* CE 15 is refined into CE [36] 
38.61/11.59	* CE 12 is refined into CE [37,38,39,40] 
38.61/11.59	
38.61/11.59	
38.61/11.59	### Cost equations --> "Loop" of (mod)/3 
38.61/11.59	* CEs [40] --> Loop 21 
38.61/11.59	* CEs [39] --> Loop 22 
38.61/11.59	* CEs [38] --> Loop 23 
38.61/11.59	* CEs [37] --> Loop 24 
38.61/11.59	* CEs [28] --> Loop 25 
38.61/11.59	* CEs [30] --> Loop 26 
38.61/11.59	* CEs [29] --> Loop 27 
38.61/11.59	* CEs [27] --> Loop 28 
38.61/11.59	* CEs [31] --> Loop 29 
38.61/11.59	* CEs [32,33,34,35,36] --> Loop 30 
38.61/11.59	
38.61/11.59	### Ranking functions of CR mod(V1,V,Out) 
38.61/11.59	* RF of phase [21]: [V1-1,V1-V+1]
38.61/11.59	* RF of phase [23]: [V1]
38.61/11.59	
38.61/11.59	#### Partial ranking functions of CR mod(V1,V,Out) 
38.61/11.59	* Partial RF of phase [21]:
38.61/11.59	  - RF of loop [21:1]:
38.61/11.59	    V1-1
38.61/11.59	    V1-V+1
38.61/11.59	* Partial RF of phase [23]:
38.61/11.59	  - RF of loop [23:1]:
38.61/11.59	    V1
38.61/11.59	
38.61/11.59	
38.61/11.59	### Specialization of cost equations start/3 
38.61/11.59	* CE 3 is refined into CE [41,42,43,44,45,46,47,48,49] 
38.61/11.59	* CE 1 is refined into CE [50] 
38.61/11.59	* CE 2 is refined into CE [51] 
38.61/11.59	* CE 4 is refined into CE [52,53,54,55,56] 
38.61/11.59	* CE 5 is refined into CE [57,58,59] 
38.61/11.59	* CE 6 is refined into CE [60,61,62,63,64,65,66] 
38.61/11.59	
38.61/11.59	
38.61/11.59	### Cost equations --> "Loop" of start/3 
38.61/11.59	* CEs [63] --> Loop 31 
38.61/11.59	* CEs [53,57,62] --> Loop 32 
38.61/11.59	* CEs [45] --> Loop 33 
38.61/11.59	* CEs [46] --> Loop 34 
38.61/11.59	* CEs [41,42,43,44,47,48,49] --> Loop 35 
38.61/11.59	* CEs [61] --> Loop 36 
38.61/11.59	* CEs [51] --> Loop 37 
38.61/11.59	* CEs [50,52,54,55,56,58,59,60,64,65,66] --> Loop 38 
38.61/11.59	
38.61/11.59	### Ranking functions of CR start(V1,V,V14) 
38.61/11.59	
38.61/11.59	#### Partial ranking functions of CR start(V1,V,V14) 
38.61/11.59	
38.61/11.59	
38.61/11.59	Computing Bounds
38.61/11.59	=====================================
38.61/11.59	
38.61/11.59	#### Cost of chains of minus(V1,V,Out):
38.61/11.59	* Chain [[14],16]: 1*it(14)+1
38.61/11.59	  Such that:it(14) =< V
38.61/11.59	
38.61/11.59	  with precondition: [V1=Out+V,V>=1,V1>=V] 
38.61/11.59	
38.61/11.59	* Chain [[14],15]: 1*it(14)+0
38.61/11.59	  Such that:it(14) =< V
38.61/11.59	
38.61/11.59	  with precondition: [Out=0,V1>=1,V>=1] 
38.61/11.59	
38.61/11.59	* Chain [16]: 1
38.61/11.59	  with precondition: [V=0,V1=Out,V1>=0] 
38.61/11.59	
38.61/11.59	* Chain [15]: 0
38.61/11.59	  with precondition: [Out=0,V1>=0,V>=0] 
38.61/11.59	
38.61/11.59	
38.61/11.59	#### Cost of chains of le(V1,V,Out):
38.61/11.59	* Chain [[17],20]: 1*it(17)+1
38.61/11.59	  Such that:it(17) =< V1
38.61/11.59	
38.61/11.59	  with precondition: [Out=2,V1>=1,V>=V1] 
38.61/11.59	
38.61/11.59	* Chain [[17],19]: 1*it(17)+1
38.61/11.59	  Such that:it(17) =< V
38.61/11.59	
38.61/11.59	  with precondition: [Out=1,V>=1,V1>=V+1] 
38.61/11.59	
38.61/11.59	* Chain [[17],18]: 1*it(17)+0
38.61/11.59	  Such that:it(17) =< V
38.61/11.59	
38.61/11.59	  with precondition: [Out=0,V1>=1,V>=1] 
38.61/11.59	
38.61/11.59	* Chain [20]: 1
38.61/11.59	  with precondition: [V1=0,Out=2,V>=0] 
38.61/11.59	
38.61/11.59	* Chain [19]: 1
38.61/11.59	  with precondition: [V=0,Out=1,V1>=1] 
38.61/11.59	
38.61/11.59	* Chain [18]: 0
38.61/11.59	  with precondition: [Out=0,V1>=0,V>=0] 
38.61/11.59	
38.61/11.59	
38.61/11.59	#### Cost of chains of mod(V1,V,Out):
38.61/11.59	* Chain [[23],30]: 7*it(23)+1*s(5)+2
38.61/11.59	  Such that:s(5) =< 1
38.61/11.59	aux(5) =< V1
38.61/11.59	it(23) =< aux(5)
38.61/11.59	
38.61/11.59	  with precondition: [V=1,Out=0,V1>=1] 
38.61/11.59	
38.61/11.59	* Chain [[23],26]: 5*it(23)+2
38.61/11.59	  Such that:aux(6) =< V1
38.61/11.59	it(23) =< aux(6)
38.61/11.59	
38.61/11.59	  with precondition: [V=1,Out=0,V1>=2] 
38.61/11.59	
38.61/11.59	* Chain [[23],24,30]: 5*it(23)+2*s(5)+5
38.61/11.59	  Such that:aux(7) =< 1
38.61/11.59	aux(8) =< V1
38.61/11.59	s(5) =< aux(7)
38.61/11.59	it(23) =< aux(8)
38.61/11.59	
38.61/11.59	  with precondition: [V=1,Out=0,V1>=2] 
38.61/11.59	
38.61/11.59	* Chain [[21],30]: 8*it(21)+1*s(5)+2
38.61/11.59	  Such that:s(5) =< V
38.61/11.59	aux(12) =< V1
38.61/11.59	it(21) =< aux(12)
38.61/11.59	
38.61/11.59	  with precondition: [Out=0,V>=2,V1>=V] 
38.61/11.59	
38.61/11.59	* Chain [[21],29]: 4*it(21)+2*s(14)+2
38.61/11.59	  Such that:it(21) =< V1-V+1
38.61/11.59	aux(13) =< V1
38.61/11.59	it(21) =< aux(13)
38.61/11.59	s(14) =< aux(13)
38.61/11.59	
38.61/11.59	  with precondition: [Out=0,V>=2,V1>=V+1] 
38.61/11.59	
38.61/11.59	* Chain [[21],28]: 4*it(21)+2*s(14)+3
38.61/11.59	  Such that:it(21) =< V1-V+1
38.61/11.59	aux(14) =< V1
38.61/11.59	it(21) =< aux(14)
38.61/11.59	s(14) =< aux(14)
38.61/11.59	
38.61/11.59	  with precondition: [Out=1,V>=2,V1>=V+1] 
38.61/11.59	
38.61/11.59	* Chain [[21],25]: 4*it(21)+2*s(14)+1*s(16)+3
38.61/11.59	  Such that:aux(10) =< V1
38.61/11.59	it(21) =< V1-V+1
38.61/11.59	aux(11) =< V1-Out
38.61/11.59	s(16) =< Out
38.61/11.59	it(21) =< aux(10)
38.61/11.59	s(15) =< aux(10)
38.61/11.59	it(21) =< aux(11)
38.61/11.59	s(15) =< aux(11)
38.61/11.59	s(14) =< s(15)
38.61/11.59	
38.61/11.59	  with precondition: [Out>=2,V>=Out+1,V1>=Out+V] 
38.61/11.59	
38.61/11.59	* Chain [[21],22,30]: 4*it(21)+3*s(5)+2*s(14)+5
38.61/11.59	  Such that:aux(10) =< V1
38.61/11.59	aux(16) =< V
38.61/11.59	aux(17) =< V1-V
38.61/11.59	it(21) =< aux(17)
38.61/11.59	s(5) =< aux(16)
38.61/11.59	it(21) =< aux(10)
38.61/11.59	s(15) =< aux(10)
38.61/11.59	s(15) =< aux(17)
38.61/11.59	s(14) =< s(15)
38.61/11.59	
38.61/11.59	  with precondition: [Out=0,V>=2,V1>=2*V] 
38.61/11.59	
38.61/11.59	* Chain [30]: 2*s(3)+1*s(5)+2
38.61/11.59	  Such that:s(5) =< V
38.61/11.59	aux(1) =< V1
38.61/11.59	s(3) =< aux(1)
38.61/11.59	
38.61/11.59	  with precondition: [Out=0,V1>=0,V>=0] 
38.61/11.59	
38.61/11.59	* Chain [29]: 2
38.61/11.59	  with precondition: [V1=1,Out=0,V>=2] 
38.61/11.59	
38.61/11.59	* Chain [28]: 3
38.61/11.59	  with precondition: [V1=1,Out=1,V>=2] 
38.61/11.59	
38.61/11.59	* Chain [27]: 1
38.61/11.59	  with precondition: [V=0,Out=0,V1>=1] 
38.61/11.59	
38.61/11.59	* Chain [26]: 2
38.61/11.59	  with precondition: [V=1,Out=0,V1>=1] 
38.61/11.59	
38.61/11.59	* Chain [25]: 1*s(16)+3
38.61/11.59	  Such that:s(16) =< V1
38.61/11.59	
38.61/11.59	  with precondition: [V1=Out,V1>=2,V>=V1+1] 
38.61/11.59	
38.61/11.59	* Chain [24,30]: 2*s(5)+5
38.61/11.59	  Such that:aux(7) =< 1
38.61/11.59	s(5) =< aux(7)
38.61/11.59	
38.61/11.59	  with precondition: [V=1,Out=0,V1>=1] 
38.61/11.59	
38.61/11.59	* Chain [22,30]: 3*s(5)+5
38.61/11.59	  Such that:aux(16) =< V
38.61/11.59	s(5) =< aux(16)
38.61/11.59	
38.61/11.59	  with precondition: [Out=0,V>=2,V1>=V] 
38.61/11.59	
38.61/11.59	
38.61/11.59	#### Cost of chains of start(V1,V,V14):
38.61/11.59	* Chain [38]: 12*s(48)+19*s(50)+12*s(54)+4*s(58)+2*s(60)+5
38.61/11.59	  Such that:s(53) =< V1-V
38.61/11.59	aux(23) =< V1
38.61/11.59	aux(24) =< V1-V+1
38.61/11.59	aux(25) =< V
38.61/11.59	s(50) =< aux(23)
38.61/11.59	s(54) =< aux(24)
38.61/11.59	s(48) =< aux(25)
38.61/11.59	s(58) =< s(53)
38.61/11.59	s(58) =< aux(23)
38.61/11.59	s(59) =< aux(23)
38.61/11.59	s(59) =< s(53)
38.61/11.59	s(60) =< s(59)
38.61/11.59	s(54) =< aux(23)
38.61/11.59	
38.61/11.59	  with precondition: [V1>=0,V>=0] 
38.61/11.59	
38.61/11.59	* Chain [37]: 1
38.61/11.59	  with precondition: [V1=1,V>=1,V14>=1] 
38.61/11.59	
38.61/11.59	* Chain [36]: 3
38.61/11.59	  with precondition: [V1=1,V>=2] 
38.61/11.59	
38.61/11.59	* Chain [35]: 4*s(73)+18*s(77)+21*s(81)+12*s(93)+4*s(97)+2*s(99)+18*s(100)+7
38.61/11.59	  Such that:aux(26) =< V
38.61/11.59	s(73) =< V+1
38.61/11.59	s(92) =< V-2*V14
38.61/11.59	aux(30) =< V-2*V14+1
38.61/11.59	aux(31) =< V-V14
38.61/11.59	aux(32) =< V14
38.61/11.59	s(93) =< aux(30)
38.61/11.59	s(100) =< aux(31)
38.61/11.59	s(81) =< aux(32)
38.61/11.59	s(77) =< aux(26)
38.61/11.59	s(73) =< aux(26)
38.61/11.59	s(97) =< s(92)
38.61/11.59	s(97) =< aux(31)
38.61/11.59	s(98) =< aux(31)
38.61/11.59	s(98) =< s(92)
38.61/11.59	s(99) =< s(98)
38.61/11.59	s(93) =< aux(31)
38.61/11.59	
38.61/11.59	  with precondition: [V1=2,V>=0,V14>=0] 
38.61/11.59	
38.61/11.59	* Chain [34]: 6*s(114)+17*s(118)+7
38.61/11.59	  Such that:s(116) =< V
38.61/11.59	aux(33) =< 1
38.61/11.59	s(114) =< aux(33)
38.61/11.59	s(118) =< s(116)
38.61/11.59	
38.61/11.59	  with precondition: [V1=2,V14=1,V>=2] 
38.61/11.59	
38.61/11.59	* Chain [33]: 1*s(119)+5
38.61/11.59	  Such that:s(119) =< V14
38.61/11.59	
38.61/11.59	  with precondition: [V1=2,V=V14+1,V>=3] 
38.61/11.59	
38.61/11.59	* Chain [32]: 1
38.61/11.59	  with precondition: [V=0,V1>=0] 
38.61/11.59	
38.61/11.59	* Chain [31]: 5*s(122)+17*s(123)+5
38.61/11.59	  Such that:s(120) =< 1
38.61/11.59	s(121) =< V1
38.61/11.59	s(122) =< s(120)
38.61/11.59	s(123) =< s(121)
38.61/11.59	
38.61/11.59	  with precondition: [V=1,V1>=1] 
38.61/11.59	
38.61/11.59	
38.61/11.59	Closed-form bounds of start(V1,V,V14): 
38.61/11.59	-------------------------------------
38.61/11.59	* Chain [38] with precondition: [V1>=0,V>=0] 
38.61/11.59	    - Upper bound: 21*V1+12*V+5+nat(V1-V+1)*12+nat(V1-V)*4 
38.61/11.59	    - Complexity: n 
38.61/11.59	* Chain [37] with precondition: [V1=1,V>=1,V14>=1] 
38.61/11.59	    - Upper bound: 1 
38.61/11.59	    - Complexity: constant 
38.61/11.59	* Chain [36] with precondition: [V1=1,V>=2] 
38.61/11.59	    - Upper bound: 3 
38.61/11.59	    - Complexity: constant 
38.61/11.59	* Chain [35] with precondition: [V1=2,V>=0,V14>=0] 
38.61/11.59	    - Upper bound: 22*V+21*V14+11+nat(V-2*V14+1)*12+nat(V-V14)*20+nat(V-2*V14)*4 
38.61/11.59	    - Complexity: n 
38.61/11.59	* Chain [34] with precondition: [V1=2,V14=1,V>=2] 
38.61/11.59	    - Upper bound: 17*V+13 
38.61/11.59	    - Complexity: n 
38.61/11.59	* Chain [33] with precondition: [V1=2,V=V14+1,V>=3] 
38.61/11.59	    - Upper bound: V14+5 
38.61/11.59	    - Complexity: n 
38.61/11.59	* Chain [32] with precondition: [V=0,V1>=0] 
38.61/11.59	    - Upper bound: 1 
38.61/11.59	    - Complexity: constant 
38.61/11.59	* Chain [31] with precondition: [V=1,V1>=1] 
38.61/11.59	    - Upper bound: 17*V1+10 
38.61/11.59	    - Complexity: n 
38.61/11.59	
38.61/11.59	### Maximum cost of start(V1,V,V14): max([max([17*V1+9,nat(V14)+4]),12*V+4+max([5*V+2+max([6,nat(V14)*21+V+(4*V+4)+nat(V-2*V14+1)*12+nat(V-V14)*20+nat(V-2*V14)*4]),nat(V1-V+1)*12+21*V1+nat(V1-V)*4])])+1 
38.61/11.59	Asymptotic class: n 
38.61/11.59	* Total analysis performed in 413 ms.
38.61/11.59	
38.61/11.59	
38.61/11.59	----------------------------------------
38.61/11.59	
38.61/11.59	(10)
38.61/11.59	BOUNDS(1, n^1)
38.61/11.59	
38.61/11.59	----------------------------------------
38.61/11.59	
38.61/11.59	(11) RenamingProof (BOTH BOUNDS(ID, ID))
38.61/11.59	Renamed function symbols to avoid clashes with predefined symbol.
38.61/11.59	----------------------------------------
38.61/11.59	
38.61/11.59	(12)
38.61/11.59	Obligation:
38.61/11.59	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
38.61/11.59	
38.61/11.59	
38.61/11.59	The TRS R consists of the following rules:
38.61/11.59	
38.61/11.59	   le(0', y) -> true
38.61/11.59	   le(s(x), 0') -> false
38.61/11.59	   le(s(x), s(y)) -> le(x, y)
38.61/11.59	   minus(x, 0') -> x
38.61/11.59	   minus(s(x), s(y)) -> minus(x, y)
38.61/11.59	   mod(0', y) -> 0'
38.61/11.59	   mod(s(x), 0') -> 0'
38.61/11.59	   mod(s(x), s(y)) -> if_mod(le(y, x), s(x), s(y))
38.61/11.59	   if_mod(true, x, y) -> mod(minus(x, y), y)
38.61/11.59	   if_mod(false, s(x), s(y)) -> s(x)
38.61/11.59	
38.61/11.59	S is empty.
38.61/11.59	Rewrite Strategy: INNERMOST
38.61/11.59	----------------------------------------
38.61/11.59	
38.61/11.59	(13) TypeInferenceProof (BOTH BOUNDS(ID, ID))
38.61/11.59	Infered types.
38.61/11.59	----------------------------------------
38.61/11.59	
38.61/11.59	(14)
38.61/11.59	Obligation:
38.61/11.59	Innermost TRS:
38.61/11.59	Rules:
38.61/11.59	le(0', y) -> true
38.61/11.59	le(s(x), 0') -> false
38.61/11.59	le(s(x), s(y)) -> le(x, y)
38.61/11.59	minus(x, 0') -> x
38.61/11.59	minus(s(x), s(y)) -> minus(x, y)
38.61/11.59	mod(0', y) -> 0'
38.61/11.59	mod(s(x), 0') -> 0'
38.61/11.59	mod(s(x), s(y)) -> if_mod(le(y, x), s(x), s(y))
38.61/11.59	if_mod(true, x, y) -> mod(minus(x, y), y)
38.61/11.59	if_mod(false, s(x), s(y)) -> s(x)
38.61/11.59	
38.61/11.59	Types:
38.61/11.59	le :: 0':s -> 0':s -> true:false
38.61/11.59	0' :: 0':s
38.61/11.59	true :: true:false
38.61/11.59	s :: 0':s -> 0':s
38.61/11.59	false :: true:false
38.61/11.59	minus :: 0':s -> 0':s -> 0':s
38.61/11.59	mod :: 0':s -> 0':s -> 0':s
38.61/11.59	if_mod :: true:false -> 0':s -> 0':s -> 0':s
38.61/11.59	hole_true:false1_0 :: true:false
38.61/11.59	hole_0':s2_0 :: 0':s
38.61/11.59	gen_0':s3_0 :: Nat -> 0':s
38.61/11.59	
38.61/11.59	----------------------------------------
38.61/11.59	
38.61/11.59	(15) OrderProof (LOWER BOUND(ID))
38.61/11.59	Heuristically decided to analyse the following defined symbols:
38.61/11.59	le, minus, mod
38.61/11.59	
38.61/11.59	They will be analysed ascendingly in the following order:
38.61/11.59	le < mod
38.61/11.59	minus < mod
38.61/11.59	
38.61/11.59	----------------------------------------
38.61/11.59	
38.61/11.59	(16)
38.61/11.59	Obligation:
38.61/11.59	Innermost TRS:
38.61/11.59	Rules:
38.61/11.59	le(0', y) -> true
38.61/11.59	le(s(x), 0') -> false
38.61/11.59	le(s(x), s(y)) -> le(x, y)
38.61/11.59	minus(x, 0') -> x
38.61/11.59	minus(s(x), s(y)) -> minus(x, y)
38.61/11.59	mod(0', y) -> 0'
38.61/11.59	mod(s(x), 0') -> 0'
38.61/11.59	mod(s(x), s(y)) -> if_mod(le(y, x), s(x), s(y))
38.61/11.59	if_mod(true, x, y) -> mod(minus(x, y), y)
38.61/11.59	if_mod(false, s(x), s(y)) -> s(x)
38.61/11.59	
38.61/11.59	Types:
38.61/11.59	le :: 0':s -> 0':s -> true:false
38.61/11.59	0' :: 0':s
38.61/11.59	true :: true:false
38.61/11.59	s :: 0':s -> 0':s
38.61/11.59	false :: true:false
38.61/11.59	minus :: 0':s -> 0':s -> 0':s
38.61/11.59	mod :: 0':s -> 0':s -> 0':s
38.61/11.59	if_mod :: true:false -> 0':s -> 0':s -> 0':s
38.61/11.59	hole_true:false1_0 :: true:false
38.61/11.59	hole_0':s2_0 :: 0':s
38.61/11.59	gen_0':s3_0 :: Nat -> 0':s
38.61/11.59	
38.61/11.59	
38.61/11.59	Generator Equations:
38.61/11.59	gen_0':s3_0(0) <=> 0'
38.61/11.59	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
38.61/11.59	
38.61/11.59	
38.61/11.59	The following defined symbols remain to be analysed:
38.61/11.59	le, minus, mod
38.61/11.59	
38.61/11.59	They will be analysed ascendingly in the following order:
38.61/11.59	le < mod
38.61/11.59	minus < mod
38.61/11.59	
38.61/11.59	----------------------------------------
38.61/11.59	
38.61/11.59	(17) RewriteLemmaProof (LOWER BOUND(ID))
38.61/11.59	Proved the following rewrite lemma:
38.61/11.59	le(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> true, rt in Omega(1 + n5_0)
38.61/11.59	
38.61/11.59	Induction Base:
38.61/11.59	le(gen_0':s3_0(0), gen_0':s3_0(0)) ->_R^Omega(1)
38.61/11.59	true
38.61/11.59	
38.61/11.59	Induction Step:
38.61/11.59	le(gen_0':s3_0(+(n5_0, 1)), gen_0':s3_0(+(n5_0, 1))) ->_R^Omega(1)
38.61/11.59	le(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) ->_IH
38.61/11.59	true
38.61/11.59	
38.61/11.59	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
38.61/11.59	----------------------------------------
38.61/11.59	
38.61/11.59	(18)
38.61/11.59	Complex Obligation (BEST)
38.61/11.59	
38.61/11.59	----------------------------------------
38.61/11.59	
38.61/11.59	(19)
38.61/11.59	Obligation:
38.61/11.59	Proved the lower bound n^1 for the following obligation:
38.61/11.59	
38.61/11.59	Innermost TRS:
38.61/11.59	Rules:
38.61/11.59	le(0', y) -> true
38.61/11.59	le(s(x), 0') -> false
38.61/11.59	le(s(x), s(y)) -> le(x, y)
38.61/11.59	minus(x, 0') -> x
38.61/11.59	minus(s(x), s(y)) -> minus(x, y)
38.61/11.59	mod(0', y) -> 0'
38.61/11.59	mod(s(x), 0') -> 0'
38.61/11.59	mod(s(x), s(y)) -> if_mod(le(y, x), s(x), s(y))
38.61/11.59	if_mod(true, x, y) -> mod(minus(x, y), y)
38.61/11.59	if_mod(false, s(x), s(y)) -> s(x)
38.61/11.59	
38.61/11.59	Types:
38.61/11.59	le :: 0':s -> 0':s -> true:false
38.61/11.59	0' :: 0':s
38.61/11.59	true :: true:false
38.61/11.59	s :: 0':s -> 0':s
38.61/11.59	false :: true:false
38.61/11.59	minus :: 0':s -> 0':s -> 0':s
38.61/11.59	mod :: 0':s -> 0':s -> 0':s
38.61/11.59	if_mod :: true:false -> 0':s -> 0':s -> 0':s
38.61/11.59	hole_true:false1_0 :: true:false
38.61/11.59	hole_0':s2_0 :: 0':s
38.61/11.59	gen_0':s3_0 :: Nat -> 0':s
38.61/11.59	
38.61/11.59	
38.61/11.59	Generator Equations:
38.61/11.59	gen_0':s3_0(0) <=> 0'
38.61/11.59	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
38.61/11.59	
38.61/11.59	
38.61/11.59	The following defined symbols remain to be analysed:
38.61/11.59	le, minus, mod
38.61/11.59	
38.61/11.59	They will be analysed ascendingly in the following order:
38.61/11.59	le < mod
38.61/11.59	minus < mod
38.61/11.59	
38.61/11.59	----------------------------------------
38.61/11.59	
38.61/11.59	(20) LowerBoundPropagationProof (FINISHED)
38.61/11.59	Propagated lower bound.
38.61/11.59	----------------------------------------
38.61/11.59	
38.61/11.59	(21)
38.61/11.59	BOUNDS(n^1, INF)
38.61/11.59	
38.61/11.59	----------------------------------------
38.61/11.59	
38.61/11.59	(22)
38.61/11.59	Obligation:
38.61/11.59	Innermost TRS:
38.61/11.59	Rules:
38.61/11.59	le(0', y) -> true
38.61/11.59	le(s(x), 0') -> false
38.61/11.59	le(s(x), s(y)) -> le(x, y)
38.61/11.59	minus(x, 0') -> x
38.61/11.59	minus(s(x), s(y)) -> minus(x, y)
38.61/11.59	mod(0', y) -> 0'
38.61/11.59	mod(s(x), 0') -> 0'
38.61/11.59	mod(s(x), s(y)) -> if_mod(le(y, x), s(x), s(y))
38.61/11.59	if_mod(true, x, y) -> mod(minus(x, y), y)
38.61/11.59	if_mod(false, s(x), s(y)) -> s(x)
38.61/11.59	
38.61/11.59	Types:
38.61/11.59	le :: 0':s -> 0':s -> true:false
38.61/11.59	0' :: 0':s
38.61/11.59	true :: true:false
38.61/11.59	s :: 0':s -> 0':s
38.61/11.59	false :: true:false
38.61/11.59	minus :: 0':s -> 0':s -> 0':s
38.61/11.59	mod :: 0':s -> 0':s -> 0':s
38.61/11.59	if_mod :: true:false -> 0':s -> 0':s -> 0':s
38.61/11.59	hole_true:false1_0 :: true:false
38.61/11.59	hole_0':s2_0 :: 0':s
38.61/11.59	gen_0':s3_0 :: Nat -> 0':s
38.61/11.59	
38.61/11.59	
38.61/11.59	Lemmas:
38.61/11.59	le(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> true, rt in Omega(1 + n5_0)
38.61/11.59	
38.61/11.59	
38.61/11.59	Generator Equations:
38.61/11.59	gen_0':s3_0(0) <=> 0'
38.61/11.59	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
38.61/11.59	
38.61/11.59	
38.61/11.59	The following defined symbols remain to be analysed:
38.61/11.59	minus, mod
38.61/11.59	
38.61/11.59	They will be analysed ascendingly in the following order:
38.61/11.59	minus < mod
38.61/11.59	
38.61/11.59	----------------------------------------
38.61/11.59	
38.61/11.59	(23) RewriteLemmaProof (LOWER BOUND(ID))
38.61/11.59	Proved the following rewrite lemma:
38.61/11.59	minus(gen_0':s3_0(n294_0), gen_0':s3_0(n294_0)) -> gen_0':s3_0(0), rt in Omega(1 + n294_0)
38.61/11.59	
38.61/11.59	Induction Base:
38.61/11.59	minus(gen_0':s3_0(0), gen_0':s3_0(0)) ->_R^Omega(1)
38.61/11.59	gen_0':s3_0(0)
38.61/11.59	
38.61/11.59	Induction Step:
38.61/11.59	minus(gen_0':s3_0(+(n294_0, 1)), gen_0':s3_0(+(n294_0, 1))) ->_R^Omega(1)
38.61/11.59	minus(gen_0':s3_0(n294_0), gen_0':s3_0(n294_0)) ->_IH
38.61/11.59	gen_0':s3_0(0)
38.61/11.59	
38.61/11.59	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
38.61/11.59	----------------------------------------
38.61/11.59	
38.61/11.59	(24)
38.61/11.59	Obligation:
38.61/11.59	Innermost TRS:
38.61/11.59	Rules:
38.61/11.59	le(0', y) -> true
38.61/11.59	le(s(x), 0') -> false
38.61/11.59	le(s(x), s(y)) -> le(x, y)
38.61/11.59	minus(x, 0') -> x
38.61/11.59	minus(s(x), s(y)) -> minus(x, y)
38.61/11.59	mod(0', y) -> 0'
38.61/11.59	mod(s(x), 0') -> 0'
38.61/11.59	mod(s(x), s(y)) -> if_mod(le(y, x), s(x), s(y))
38.61/11.59	if_mod(true, x, y) -> mod(minus(x, y), y)
38.61/11.59	if_mod(false, s(x), s(y)) -> s(x)
38.61/11.59	
38.61/11.59	Types:
38.61/11.59	le :: 0':s -> 0':s -> true:false
38.61/11.59	0' :: 0':s
38.61/11.59	true :: true:false
38.61/11.59	s :: 0':s -> 0':s
38.61/11.59	false :: true:false
38.61/11.59	minus :: 0':s -> 0':s -> 0':s
38.61/11.59	mod :: 0':s -> 0':s -> 0':s
38.61/11.59	if_mod :: true:false -> 0':s -> 0':s -> 0':s
38.61/11.59	hole_true:false1_0 :: true:false
38.61/11.59	hole_0':s2_0 :: 0':s
38.61/11.59	gen_0':s3_0 :: Nat -> 0':s
38.61/11.59	
38.61/11.59	
38.61/11.59	Lemmas:
38.61/11.59	le(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> true, rt in Omega(1 + n5_0)
38.61/11.59	minus(gen_0':s3_0(n294_0), gen_0':s3_0(n294_0)) -> gen_0':s3_0(0), rt in Omega(1 + n294_0)
38.61/11.59	
38.61/11.59	
38.61/11.59	Generator Equations:
38.61/11.59	gen_0':s3_0(0) <=> 0'
38.61/11.59	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
38.61/11.59	
38.61/11.59	
38.61/11.59	The following defined symbols remain to be analysed:
38.61/11.59	mod
38.61/11.65	EOF