22.70/8.02	WORST_CASE(Omega(n^1), O(n^1))
22.91/8.03	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
22.91/8.03	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
22.91/8.03	
22.91/8.03	
22.91/8.03	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
22.91/8.03	
22.91/8.03	(0) CpxTRS
22.91/8.03	(1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms]
22.91/8.03	(2) CpxTRS
22.91/8.03	    (3) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
22.91/8.03	    (4) CpxTRS
22.91/8.03	    (5) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
22.91/8.03	    (6) CpxWeightedTrs
22.91/8.03	    (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
22.91/8.03	    (8) CpxTypedWeightedTrs
22.91/8.03	    (9) CompletionProof [UPPER BOUND(ID), 0 ms]
22.91/8.03	    (10) CpxTypedWeightedCompleteTrs
22.91/8.03	    (11) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
22.91/8.03	    (12) CpxRNTS
22.91/8.03	    (13) CompleteCoflocoProof [FINISHED, 290 ms]
22.91/8.03	    (14) BOUNDS(1, n^1)
22.91/8.03	(15) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
22.91/8.03	(16) CpxTRS
22.91/8.03	    (17) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
22.91/8.03	    (18) typed CpxTrs
22.91/8.03	    (19) OrderProof [LOWER BOUND(ID), 0 ms]
22.91/8.03	    (20) typed CpxTrs
22.91/8.03	    (21) RewriteLemmaProof [LOWER BOUND(ID), 263 ms]
22.91/8.03	    (22) BEST
22.91/8.03	        (23) proven lower bound
22.91/8.03	            (24) LowerBoundPropagationProof [FINISHED, 0 ms]
22.91/8.03	            (25) BOUNDS(n^1, INF)
22.91/8.03	        (26) typed CpxTrs
22.91/8.03	            (27) RewriteLemmaProof [LOWER BOUND(ID), 61 ms]
22.91/8.03	            (28) BOUNDS(1, INF)
22.91/8.03	
22.91/8.03	
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(0)
22.91/8.03	Obligation:
22.91/8.03	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
22.91/8.03	
22.91/8.03	
22.91/8.03	The TRS R consists of the following rules:
22.91/8.03	
22.91/8.03	   minus(x, 0) -> x
22.91/8.03	   minus(s(x), s(y)) -> minus(x, y)
22.91/8.03	   quot(0, s(y)) -> 0
22.91/8.03	   quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
22.91/8.03	   plus(0, y) -> y
22.91/8.03	   plus(s(x), y) -> s(plus(x, y))
22.91/8.03	   plus(minus(x, s(0)), minus(y, s(s(z)))) -> plus(minus(y, s(s(z))), minus(x, s(0)))
22.91/8.03	
22.91/8.03	S is empty.
22.91/8.03	Rewrite Strategy: FULL
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(1) NestedDefinedSymbolProof (UPPER BOUND(ID))
22.91/8.03	The following defined symbols can occur below the 0th argument of quot: minus
22.91/8.03	The following defined symbols can occur below the 0th argument of minus: minus
22.91/8.03	
22.91/8.03	Hence, the left-hand sides of the following rules are not basic-reachable and can be removed:
22.91/8.03	plus(minus(x, s(0)), minus(y, s(s(z)))) -> plus(minus(y, s(s(z))), minus(x, s(0)))
22.91/8.03	
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(2)
22.91/8.03	Obligation:
22.91/8.03	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
22.91/8.03	
22.91/8.03	
22.91/8.03	The TRS R consists of the following rules:
22.91/8.03	
22.91/8.03	   minus(x, 0) -> x
22.91/8.03	   minus(s(x), s(y)) -> minus(x, y)
22.91/8.03	   quot(0, s(y)) -> 0
22.91/8.03	   quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
22.91/8.03	   plus(0, y) -> y
22.91/8.03	   plus(s(x), y) -> s(plus(x, y))
22.91/8.03	
22.91/8.03	S is empty.
22.91/8.03	Rewrite Strategy: FULL
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(3) RcToIrcProof (BOTH BOUNDS(ID, ID))
22.91/8.03	Converted rc-obligation to irc-obligation.
22.91/8.03	
22.91/8.03	The duplicating contexts are:
22.91/8.03	quot(s(x), s([]))
22.91/8.03	
22.91/8.03	
22.91/8.03	The defined contexts are:
22.91/8.03	quot([], s(x1))
22.91/8.03	minus([], x1)
22.91/8.03	
22.91/8.03	
22.91/8.03	[] just represents basic- or constructor-terms in the following defined contexts:
22.91/8.03	quot([], s(x1))
22.91/8.03	
22.91/8.03	
22.91/8.03	As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc.
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(4)
22.91/8.03	Obligation:
22.91/8.03	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
22.91/8.03	
22.91/8.03	
22.91/8.03	The TRS R consists of the following rules:
22.91/8.03	
22.91/8.03	   minus(x, 0) -> x
22.91/8.03	   minus(s(x), s(y)) -> minus(x, y)
22.91/8.03	   quot(0, s(y)) -> 0
22.91/8.03	   quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
22.91/8.03	   plus(0, y) -> y
22.91/8.03	   plus(s(x), y) -> s(plus(x, y))
22.91/8.03	
22.91/8.03	S is empty.
22.91/8.03	Rewrite Strategy: INNERMOST
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(5) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
22.91/8.03	Transformed relative TRS to weighted TRS
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(6)
22.91/8.03	Obligation:
22.91/8.03	The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1).
22.91/8.03	
22.91/8.03	
22.91/8.03	The TRS R consists of the following rules:
22.91/8.03	
22.91/8.03	   minus(x, 0) -> x [1]
22.91/8.03	   minus(s(x), s(y)) -> minus(x, y) [1]
22.91/8.03	   quot(0, s(y)) -> 0 [1]
22.91/8.03	   quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) [1]
22.91/8.03	   plus(0, y) -> y [1]
22.91/8.03	   plus(s(x), y) -> s(plus(x, y)) [1]
22.91/8.03	
22.91/8.03	Rewrite Strategy: INNERMOST
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(7) TypeInferenceProof (BOTH BOUNDS(ID, ID))
22.91/8.03	Infered types.
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(8)
22.91/8.03	Obligation:
22.91/8.03	Runtime Complexity Weighted TRS with Types.
22.91/8.03	The TRS R consists of the following rules:
22.91/8.03	
22.91/8.03	   minus(x, 0) -> x [1]
22.91/8.03	   minus(s(x), s(y)) -> minus(x, y) [1]
22.91/8.03	   quot(0, s(y)) -> 0 [1]
22.91/8.03	   quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) [1]
22.91/8.03	   plus(0, y) -> y [1]
22.91/8.03	   plus(s(x), y) -> s(plus(x, y)) [1]
22.91/8.03	
22.91/8.03	The TRS has the following type information:
22.91/8.03	minus :: 0:s -> 0:s -> 0:s
22.91/8.03	0 :: 0:s
22.91/8.03	s :: 0:s -> 0:s
22.91/8.03	quot :: 0:s -> 0:s -> 0:s
22.91/8.03	plus :: 0:s -> 0:s -> 0:s
22.91/8.03	
22.91/8.03	Rewrite Strategy: INNERMOST
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(9) CompletionProof (UPPER BOUND(ID))
22.91/8.03	The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added:
22.91/8.03	
22.91/8.03	   minus(v0, v1) -> null_minus [0]
22.91/8.03	   quot(v0, v1) -> null_quot [0]
22.91/8.03	   plus(v0, v1) -> null_plus [0]
22.91/8.03	
22.91/8.03	And the following fresh constants:    null_minus, null_quot, null_plus
22.91/8.03	
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(10)
22.91/8.03	Obligation:
22.91/8.03	Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is:
22.91/8.03	
22.91/8.03	Runtime Complexity Weighted TRS with Types.
22.91/8.03	The TRS R consists of the following rules:
22.91/8.03	
22.91/8.03	   minus(x, 0) -> x [1]
22.91/8.03	   minus(s(x), s(y)) -> minus(x, y) [1]
22.91/8.03	   quot(0, s(y)) -> 0 [1]
22.91/8.03	   quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) [1]
22.91/8.03	   plus(0, y) -> y [1]
22.91/8.03	   plus(s(x), y) -> s(plus(x, y)) [1]
22.91/8.03	   minus(v0, v1) -> null_minus [0]
22.91/8.03	   quot(v0, v1) -> null_quot [0]
22.91/8.03	   plus(v0, v1) -> null_plus [0]
22.91/8.03	
22.91/8.03	The TRS has the following type information:
22.91/8.03	minus :: 0:s:null_minus:null_quot:null_plus -> 0:s:null_minus:null_quot:null_plus -> 0:s:null_minus:null_quot:null_plus
22.91/8.03	0 :: 0:s:null_minus:null_quot:null_plus
22.91/8.03	s :: 0:s:null_minus:null_quot:null_plus -> 0:s:null_minus:null_quot:null_plus
22.91/8.03	quot :: 0:s:null_minus:null_quot:null_plus -> 0:s:null_minus:null_quot:null_plus -> 0:s:null_minus:null_quot:null_plus
22.91/8.03	plus :: 0:s:null_minus:null_quot:null_plus -> 0:s:null_minus:null_quot:null_plus -> 0:s:null_minus:null_quot:null_plus
22.91/8.03	null_minus :: 0:s:null_minus:null_quot:null_plus
22.91/8.03	null_quot :: 0:s:null_minus:null_quot:null_plus
22.91/8.03	null_plus :: 0:s:null_minus:null_quot:null_plus
22.91/8.03	
22.91/8.03	Rewrite Strategy: INNERMOST
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
22.91/8.03	Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
22.91/8.03	The constant constructors are abstracted as follows:
22.91/8.03	
22.91/8.03	   0 => 0
22.91/8.03	   null_minus => 0
22.91/8.03	   null_quot => 0
22.91/8.03	   null_plus => 0
22.91/8.03	
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(12)
22.91/8.03	Obligation:
22.91/8.03	Complexity RNTS consisting of the following rules:
22.91/8.03	
22.91/8.03	   minus(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0
22.91/8.03	   minus(z, z') -{ 1 }-> minus(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x
22.91/8.03	   minus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
22.91/8.03	   plus(z, z') -{ 1 }-> y :|: y >= 0, z = 0, z' = y
22.91/8.03	   plus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
22.91/8.03	   plus(z, z') -{ 1 }-> 1 + plus(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y
22.91/8.03	   quot(z, z') -{ 1 }-> 0 :|: z' = 1 + y, y >= 0, z = 0
22.91/8.03	   quot(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
22.91/8.03	   quot(z, z') -{ 1 }-> 1 + quot(minus(x, y), 1 + y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x
22.91/8.03	
22.91/8.03	Only complete derivations are relevant for the runtime complexity.
22.91/8.03	
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(13) CompleteCoflocoProof (FINISHED)
22.91/8.03	Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo:
22.91/8.03	
22.91/8.03	eq(start(V1, V),0,[minus(V1, V, Out)],[V1 >= 0,V >= 0]).
22.91/8.03	eq(start(V1, V),0,[quot(V1, V, Out)],[V1 >= 0,V >= 0]).
22.91/8.03	eq(start(V1, V),0,[plus(V1, V, Out)],[V1 >= 0,V >= 0]).
22.91/8.03	eq(minus(V1, V, Out),1,[],[Out = V2,V2 >= 0,V1 = V2,V = 0]).
22.91/8.03	eq(minus(V1, V, Out),1,[minus(V3, V4, Ret)],[Out = Ret,V = 1 + V4,V3 >= 0,V4 >= 0,V1 = 1 + V3]).
22.91/8.03	eq(quot(V1, V, Out),1,[],[Out = 0,V = 1 + V5,V5 >= 0,V1 = 0]).
22.91/8.03	eq(quot(V1, V, Out),1,[minus(V7, V6, Ret10),quot(Ret10, 1 + V6, Ret1)],[Out = 1 + Ret1,V = 1 + V6,V7 >= 0,V6 >= 0,V1 = 1 + V7]).
22.91/8.03	eq(plus(V1, V, Out),1,[],[Out = V8,V8 >= 0,V1 = 0,V = V8]).
22.91/8.03	eq(plus(V1, V, Out),1,[plus(V9, V10, Ret11)],[Out = 1 + Ret11,V9 >= 0,V10 >= 0,V1 = 1 + V9,V = V10]).
22.91/8.03	eq(minus(V1, V, Out),0,[],[Out = 0,V12 >= 0,V11 >= 0,V1 = V12,V = V11]).
22.91/8.03	eq(quot(V1, V, Out),0,[],[Out = 0,V14 >= 0,V13 >= 0,V1 = V14,V = V13]).
22.91/8.03	eq(plus(V1, V, Out),0,[],[Out = 0,V16 >= 0,V15 >= 0,V1 = V16,V = V15]).
22.91/8.03	input_output_vars(minus(V1,V,Out),[V1,V],[Out]).
22.91/8.03	input_output_vars(quot(V1,V,Out),[V1,V],[Out]).
22.91/8.03	input_output_vars(plus(V1,V,Out),[V1,V],[Out]).
22.91/8.03	
22.91/8.03	
22.91/8.03	CoFloCo proof output:
22.91/8.03	Preprocessing Cost Relations
22.91/8.03	=====================================
22.91/8.03	
22.91/8.03	#### Computed strongly connected components 
22.91/8.03	0. recursive  : [minus/3]
22.91/8.03	1. recursive  : [plus/3]
22.91/8.03	2. recursive  : [quot/3]
22.91/8.03	3. non_recursive  : [start/2]
22.91/8.03	
22.91/8.03	#### Obtained direct recursion through partial evaluation 
22.91/8.03	0. SCC is partially evaluated into minus/3
22.91/8.03	1. SCC is partially evaluated into plus/3
22.91/8.03	2. SCC is partially evaluated into quot/3
22.91/8.03	3. SCC is partially evaluated into start/2
22.91/8.03	
22.91/8.03	Control-Flow Refinement of Cost Relations
22.91/8.03	=====================================
22.91/8.03	
22.91/8.03	### Specialization of cost equations minus/3 
22.91/8.03	* CE 6 is refined into CE [13] 
22.91/8.03	* CE 4 is refined into CE [14] 
22.91/8.03	* CE 5 is refined into CE [15] 
22.91/8.03	
22.91/8.03	
22.91/8.03	### Cost equations --> "Loop" of minus/3 
22.91/8.03	* CEs [15] --> Loop 10 
22.91/8.03	* CEs [13] --> Loop 11 
22.91/8.03	* CEs [14] --> Loop 12 
22.91/8.03	
22.91/8.03	### Ranking functions of CR minus(V1,V,Out) 
22.91/8.03	* RF of phase [10]: [V,V1]
22.91/8.03	
22.91/8.03	#### Partial ranking functions of CR minus(V1,V,Out) 
22.91/8.03	* Partial RF of phase [10]:
22.91/8.03	  - RF of loop [10:1]:
22.91/8.03	    V
22.91/8.03	    V1
22.91/8.03	
22.91/8.03	
22.91/8.03	### Specialization of cost equations plus/3 
22.91/8.03	* CE 12 is refined into CE [16] 
22.91/8.03	* CE 10 is refined into CE [17] 
22.91/8.03	* CE 11 is refined into CE [18] 
22.91/8.03	
22.91/8.03	
22.91/8.03	### Cost equations --> "Loop" of plus/3 
22.91/8.03	* CEs [18] --> Loop 13 
22.91/8.03	* CEs [16] --> Loop 14 
22.91/8.03	* CEs [17] --> Loop 15 
22.91/8.03	
22.91/8.03	### Ranking functions of CR plus(V1,V,Out) 
22.91/8.03	* RF of phase [13]: [V1]
22.91/8.03	
22.91/8.03	#### Partial ranking functions of CR plus(V1,V,Out) 
22.91/8.03	* Partial RF of phase [13]:
22.91/8.03	  - RF of loop [13:1]:
22.91/8.03	    V1
22.91/8.03	
22.91/8.03	
22.91/8.03	### Specialization of cost equations quot/3 
22.91/8.03	* CE 7 is refined into CE [19] 
22.91/8.03	* CE 9 is refined into CE [20] 
22.91/8.03	* CE 8 is refined into CE [21,22,23] 
22.91/8.03	
22.91/8.03	
22.91/8.03	### Cost equations --> "Loop" of quot/3 
22.91/8.03	* CEs [23] --> Loop 16 
22.91/8.03	* CEs [22] --> Loop 17 
22.91/8.03	* CEs [21] --> Loop 18 
22.91/8.03	* CEs [19,20] --> Loop 19 
22.91/8.03	
22.91/8.03	### Ranking functions of CR quot(V1,V,Out) 
22.91/8.03	* RF of phase [16]: [V1-1,V1-V+1]
22.91/8.03	* RF of phase [18]: [V1]
22.91/8.03	
22.91/8.03	#### Partial ranking functions of CR quot(V1,V,Out) 
22.91/8.03	* Partial RF of phase [16]:
22.91/8.03	  - RF of loop [16:1]:
22.91/8.03	    V1-1
22.91/8.03	    V1-V+1
22.91/8.03	* Partial RF of phase [18]:
22.91/8.03	  - RF of loop [18:1]:
22.91/8.03	    V1
22.91/8.03	
22.91/8.03	
22.91/8.03	### Specialization of cost equations start/2 
22.91/8.03	* CE 1 is refined into CE [24,25,26] 
22.91/8.03	* CE 2 is refined into CE [27,28,29,30,31] 
22.91/8.03	* CE 3 is refined into CE [32,33,34,35] 
22.91/8.03	
22.91/8.03	
22.91/8.03	### Cost equations --> "Loop" of start/2 
22.91/8.03	* CEs [27] --> Loop 20 
22.91/8.03	* CEs [24] --> Loop 21 
22.91/8.03	* CEs [25,26,28,29,30,31,32,33,34,35] --> Loop 22 
22.91/8.03	
22.91/8.03	### Ranking functions of CR start(V1,V) 
22.91/8.03	
22.91/8.03	#### Partial ranking functions of CR start(V1,V) 
22.91/8.03	
22.91/8.03	
22.91/8.03	Computing Bounds
22.91/8.03	=====================================
22.91/8.03	
22.91/8.03	#### Cost of chains of minus(V1,V,Out):
22.91/8.03	* Chain [[10],12]: 1*it(10)+1
22.91/8.03	  Such that:it(10) =< V
22.91/8.03	
22.91/8.03	  with precondition: [V1=Out+V,V>=1,V1>=V] 
22.91/8.03	
22.91/8.03	* Chain [[10],11]: 1*it(10)+0
22.91/8.03	  Such that:it(10) =< V
22.91/8.03	
22.91/8.03	  with precondition: [Out=0,V1>=1,V>=1] 
22.91/8.03	
22.91/8.03	* Chain [12]: 1
22.91/8.03	  with precondition: [V=0,V1=Out,V1>=0] 
22.91/8.03	
22.91/8.03	* Chain [11]: 0
22.91/8.03	  with precondition: [Out=0,V1>=0,V>=0] 
22.91/8.03	
22.91/8.03	
22.91/8.03	#### Cost of chains of plus(V1,V,Out):
22.91/8.03	* Chain [[13],15]: 1*it(13)+1
22.91/8.03	  Such that:it(13) =< -V+Out
22.91/8.03	
22.91/8.03	  with precondition: [V+V1=Out,V1>=1,V>=0] 
22.91/8.03	
22.91/8.03	* Chain [[13],14]: 1*it(13)+0
22.91/8.03	  Such that:it(13) =< Out
22.91/8.03	
22.91/8.03	  with precondition: [V>=0,Out>=1,V1>=Out] 
22.91/8.03	
22.91/8.03	* Chain [15]: 1
22.91/8.03	  with precondition: [V1=0,V=Out,V>=0] 
22.91/8.03	
22.91/8.03	* Chain [14]: 0
22.91/8.03	  with precondition: [Out=0,V1>=0,V>=0] 
22.91/8.03	
22.91/8.03	
22.91/8.03	#### Cost of chains of quot(V1,V,Out):
22.91/8.03	* Chain [[18],19]: 2*it(18)+1
22.91/8.03	  Such that:it(18) =< Out
22.91/8.03	
22.91/8.03	  with precondition: [V=1,Out>=1,V1>=Out] 
22.91/8.03	
22.91/8.03	* Chain [[18],17,19]: 2*it(18)+1*s(2)+2
22.91/8.03	  Such that:s(2) =< 1
22.91/8.03	it(18) =< Out
22.91/8.03	
22.91/8.03	  with precondition: [V=1,Out>=2,V1>=Out] 
22.91/8.03	
22.91/8.03	* Chain [[16],19]: 2*it(16)+1*s(5)+1
22.91/8.03	  Such that:it(16) =< V1-V+1
22.91/8.03	aux(3) =< V1
22.91/8.03	it(16) =< aux(3)
22.91/8.03	s(5) =< aux(3)
22.91/8.03	
22.91/8.03	  with precondition: [V>=2,Out>=1,V1+2>=2*Out+V] 
22.91/8.03	
22.91/8.03	* Chain [[16],17,19]: 2*it(16)+1*s(2)+1*s(5)+2
22.91/8.03	  Such that:it(16) =< V1-V+1
22.91/8.03	s(2) =< V
22.91/8.03	aux(4) =< V1
22.91/8.03	it(16) =< aux(4)
22.91/8.03	s(5) =< aux(4)
22.91/8.03	
22.91/8.03	  with precondition: [V>=2,Out>=2,V1+3>=2*Out+V] 
22.91/8.03	
22.91/8.03	* Chain [19]: 1
22.91/8.03	  with precondition: [Out=0,V1>=0,V>=0] 
22.91/8.03	
22.91/8.03	* Chain [17,19]: 1*s(2)+2
22.91/8.03	  Such that:s(2) =< V
22.91/8.03	
22.91/8.03	  with precondition: [Out=1,V1>=1,V>=1] 
22.91/8.03	
22.91/8.03	
22.91/8.03	#### Cost of chains of start(V1,V):
22.91/8.03	* Chain [22]: 4*s(9)+4*s(12)+4*s(14)+2
22.91/8.03	  Such that:aux(6) =< V1
22.91/8.03	aux(7) =< V1-V+1
22.91/8.03	aux(8) =< V
22.91/8.03	s(14) =< aux(6)
22.91/8.03	s(12) =< aux(7)
22.91/8.03	s(9) =< aux(8)
22.91/8.03	s(12) =< aux(6)
22.91/8.03	
22.91/8.03	  with precondition: [V1>=0,V>=0] 
22.91/8.03	
22.91/8.03	* Chain [21]: 1
22.91/8.03	  with precondition: [V=0,V1>=0] 
22.91/8.03	
22.91/8.03	* Chain [20]: 1*s(21)+4*s(23)+2
22.91/8.03	  Such that:s(21) =< 1
22.91/8.03	s(22) =< V1
22.91/8.03	s(23) =< s(22)
22.91/8.03	
22.91/8.03	  with precondition: [V=1,V1>=1] 
22.91/8.03	
22.91/8.03	
22.91/8.03	Closed-form bounds of start(V1,V): 
22.91/8.03	-------------------------------------
22.91/8.03	* Chain [22] with precondition: [V1>=0,V>=0] 
22.91/8.03	    - Upper bound: 4*V1+4*V+2+nat(V1-V+1)*4 
22.91/8.03	    - Complexity: n 
22.91/8.03	* Chain [21] with precondition: [V=0,V1>=0] 
22.91/8.03	    - Upper bound: 1 
22.91/8.03	    - Complexity: constant 
22.91/8.03	* Chain [20] with precondition: [V=1,V1>=1] 
22.91/8.03	    - Upper bound: 4*V1+3 
22.91/8.03	    - Complexity: n 
22.91/8.03	
22.91/8.03	### Maximum cost of start(V1,V): 4*V1+1+max([1,nat(V1-V+1)*4+4*V])+1 
22.91/8.03	Asymptotic class: n 
22.91/8.03	* Total analysis performed in 218 ms.
22.91/8.03	
22.91/8.03	
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(14)
22.91/8.03	BOUNDS(1, n^1)
22.91/8.03	
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(15) RenamingProof (BOTH BOUNDS(ID, ID))
22.91/8.03	Renamed function symbols to avoid clashes with predefined symbol.
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(16)
22.91/8.03	Obligation:
22.91/8.03	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
22.91/8.03	
22.91/8.03	
22.91/8.03	The TRS R consists of the following rules:
22.91/8.03	
22.91/8.03	   minus(x, 0') -> x
22.91/8.03	   minus(s(x), s(y)) -> minus(x, y)
22.91/8.03	   quot(0', s(y)) -> 0'
22.91/8.03	   quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
22.91/8.03	   plus(0', y) -> y
22.91/8.03	   plus(s(x), y) -> s(plus(x, y))
22.91/8.03	   plus(minus(x, s(0')), minus(y, s(s(z)))) -> plus(minus(y, s(s(z))), minus(x, s(0')))
22.91/8.03	
22.91/8.03	S is empty.
22.91/8.03	Rewrite Strategy: FULL
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(17) TypeInferenceProof (BOTH BOUNDS(ID, ID))
22.91/8.03	Infered types.
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(18)
22.91/8.03	Obligation:
22.91/8.03	TRS:
22.91/8.03	Rules:
22.91/8.03	minus(x, 0') -> x
22.91/8.03	minus(s(x), s(y)) -> minus(x, y)
22.91/8.03	quot(0', s(y)) -> 0'
22.91/8.03	quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
22.91/8.03	plus(0', y) -> y
22.91/8.03	plus(s(x), y) -> s(plus(x, y))
22.91/8.03	plus(minus(x, s(0')), minus(y, s(s(z)))) -> plus(minus(y, s(s(z))), minus(x, s(0')))
22.91/8.03	
22.91/8.03	Types:
22.91/8.03	minus :: 0':s -> 0':s -> 0':s
22.91/8.03	0' :: 0':s
22.91/8.03	s :: 0':s -> 0':s
22.91/8.03	quot :: 0':s -> 0':s -> 0':s
22.91/8.03	plus :: 0':s -> 0':s -> 0':s
22.91/8.03	hole_0':s1_0 :: 0':s
22.91/8.03	gen_0':s2_0 :: Nat -> 0':s
22.91/8.03	
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(19) OrderProof (LOWER BOUND(ID))
22.91/8.03	Heuristically decided to analyse the following defined symbols:
22.91/8.03	minus, quot, plus
22.91/8.03	
22.91/8.03	They will be analysed ascendingly in the following order:
22.91/8.03	minus < quot
22.91/8.03	minus < plus
22.91/8.03	
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(20)
22.91/8.03	Obligation:
22.91/8.03	TRS:
22.91/8.03	Rules:
22.91/8.03	minus(x, 0') -> x
22.91/8.03	minus(s(x), s(y)) -> minus(x, y)
22.91/8.03	quot(0', s(y)) -> 0'
22.91/8.03	quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
22.91/8.03	plus(0', y) -> y
22.91/8.03	plus(s(x), y) -> s(plus(x, y))
22.91/8.03	plus(minus(x, s(0')), minus(y, s(s(z)))) -> plus(minus(y, s(s(z))), minus(x, s(0')))
22.91/8.03	
22.91/8.03	Types:
22.91/8.03	minus :: 0':s -> 0':s -> 0':s
22.91/8.03	0' :: 0':s
22.91/8.03	s :: 0':s -> 0':s
22.91/8.03	quot :: 0':s -> 0':s -> 0':s
22.91/8.03	plus :: 0':s -> 0':s -> 0':s
22.91/8.03	hole_0':s1_0 :: 0':s
22.91/8.03	gen_0':s2_0 :: Nat -> 0':s
22.91/8.03	
22.91/8.03	
22.91/8.03	Generator Equations:
22.91/8.03	gen_0':s2_0(0) <=> 0'
22.91/8.03	gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x))
22.91/8.03	
22.91/8.03	
22.91/8.03	The following defined symbols remain to be analysed:
22.91/8.03	minus, quot, plus
22.91/8.03	
22.91/8.03	They will be analysed ascendingly in the following order:
22.91/8.03	minus < quot
22.91/8.03	minus < plus
22.91/8.03	
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(21) RewriteLemmaProof (LOWER BOUND(ID))
22.91/8.03	Proved the following rewrite lemma:
22.91/8.03	minus(gen_0':s2_0(n4_0), gen_0':s2_0(n4_0)) -> gen_0':s2_0(0), rt in Omega(1 + n4_0)
22.91/8.03	
22.91/8.03	Induction Base:
22.91/8.03	minus(gen_0':s2_0(0), gen_0':s2_0(0)) ->_R^Omega(1)
22.91/8.03	gen_0':s2_0(0)
22.91/8.03	
22.91/8.03	Induction Step:
22.91/8.03	minus(gen_0':s2_0(+(n4_0, 1)), gen_0':s2_0(+(n4_0, 1))) ->_R^Omega(1)
22.91/8.03	minus(gen_0':s2_0(n4_0), gen_0':s2_0(n4_0)) ->_IH
22.91/8.03	gen_0':s2_0(0)
22.91/8.03	
22.91/8.03	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(22)
22.91/8.03	Complex Obligation (BEST)
22.91/8.03	
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(23)
22.91/8.03	Obligation:
22.91/8.03	Proved the lower bound n^1 for the following obligation:
22.91/8.03	
22.91/8.03	TRS:
22.91/8.03	Rules:
22.91/8.03	minus(x, 0') -> x
22.91/8.03	minus(s(x), s(y)) -> minus(x, y)
22.91/8.03	quot(0', s(y)) -> 0'
22.91/8.03	quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
22.91/8.03	plus(0', y) -> y
22.91/8.03	plus(s(x), y) -> s(plus(x, y))
22.91/8.03	plus(minus(x, s(0')), minus(y, s(s(z)))) -> plus(minus(y, s(s(z))), minus(x, s(0')))
22.91/8.03	
22.91/8.03	Types:
22.91/8.03	minus :: 0':s -> 0':s -> 0':s
22.91/8.03	0' :: 0':s
22.91/8.03	s :: 0':s -> 0':s
22.91/8.03	quot :: 0':s -> 0':s -> 0':s
22.91/8.03	plus :: 0':s -> 0':s -> 0':s
22.91/8.03	hole_0':s1_0 :: 0':s
22.91/8.03	gen_0':s2_0 :: Nat -> 0':s
22.91/8.03	
22.91/8.03	
22.91/8.03	Generator Equations:
22.91/8.03	gen_0':s2_0(0) <=> 0'
22.91/8.03	gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x))
22.91/8.03	
22.91/8.03	
22.91/8.03	The following defined symbols remain to be analysed:
22.91/8.03	minus, quot, plus
22.91/8.03	
22.91/8.03	They will be analysed ascendingly in the following order:
22.91/8.03	minus < quot
22.91/8.03	minus < plus
22.91/8.03	
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(24) LowerBoundPropagationProof (FINISHED)
22.91/8.03	Propagated lower bound.
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(25)
22.91/8.03	BOUNDS(n^1, INF)
22.91/8.03	
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(26)
22.91/8.03	Obligation:
22.91/8.03	TRS:
22.91/8.03	Rules:
22.91/8.03	minus(x, 0') -> x
22.91/8.03	minus(s(x), s(y)) -> minus(x, y)
22.91/8.03	quot(0', s(y)) -> 0'
22.91/8.03	quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
22.91/8.03	plus(0', y) -> y
22.91/8.03	plus(s(x), y) -> s(plus(x, y))
22.91/8.03	plus(minus(x, s(0')), minus(y, s(s(z)))) -> plus(minus(y, s(s(z))), minus(x, s(0')))
22.91/8.03	
22.91/8.03	Types:
22.91/8.03	minus :: 0':s -> 0':s -> 0':s
22.91/8.03	0' :: 0':s
22.91/8.03	s :: 0':s -> 0':s
22.91/8.03	quot :: 0':s -> 0':s -> 0':s
22.91/8.03	plus :: 0':s -> 0':s -> 0':s
22.91/8.03	hole_0':s1_0 :: 0':s
22.91/8.03	gen_0':s2_0 :: Nat -> 0':s
22.91/8.03	
22.91/8.03	
22.91/8.03	Lemmas:
22.91/8.03	minus(gen_0':s2_0(n4_0), gen_0':s2_0(n4_0)) -> gen_0':s2_0(0), rt in Omega(1 + n4_0)
22.91/8.03	
22.91/8.03	
22.91/8.03	Generator Equations:
22.91/8.03	gen_0':s2_0(0) <=> 0'
22.91/8.03	gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x))
22.91/8.03	
22.91/8.03	
22.91/8.03	The following defined symbols remain to be analysed:
22.91/8.03	quot, plus
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(27) RewriteLemmaProof (LOWER BOUND(ID))
22.91/8.03	Proved the following rewrite lemma:
22.91/8.03	plus(gen_0':s2_0(n296_0), gen_0':s2_0(b)) -> gen_0':s2_0(+(n296_0, b)), rt in Omega(1 + n296_0)
22.91/8.03	
22.91/8.03	Induction Base:
22.91/8.03	plus(gen_0':s2_0(0), gen_0':s2_0(b)) ->_R^Omega(1)
22.91/8.03	gen_0':s2_0(b)
22.91/8.03	
22.91/8.03	Induction Step:
22.91/8.03	plus(gen_0':s2_0(+(n296_0, 1)), gen_0':s2_0(b)) ->_R^Omega(1)
22.91/8.03	s(plus(gen_0':s2_0(n296_0), gen_0':s2_0(b))) ->_IH
22.91/8.03	s(gen_0':s2_0(+(b, c297_0)))
22.91/8.03	
22.91/8.03	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
22.91/8.03	----------------------------------------
22.91/8.03	
22.91/8.03	(28)
22.91/8.03	BOUNDS(1, INF)
22.96/10.08	EOF