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