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