1114.76/291.56	WORST_CASE(Omega(n^1), O(n^2))
1114.76/291.57	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
1114.76/291.57	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
1114.76/291.57	
1114.76/291.57	(0) CpxTRS
1114.76/291.57	(1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
1114.76/291.57	(2) CpxWeightedTrs
1114.76/291.57	    (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
1114.76/291.57	    (4) CpxTypedWeightedTrs
1114.76/291.57	    (5) CompletionProof [UPPER BOUND(ID), 0 ms]
1114.76/291.57	    (6) CpxTypedWeightedCompleteTrs
1114.76/291.57	    (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
1114.76/291.57	    (8) CpxRNTS
1114.76/291.57	    (9) CompleteCoflocoProof [FINISHED, 522 ms]
1114.76/291.57	    (10) BOUNDS(1, n^2)
1114.76/291.57	(11) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
1114.76/291.57	(12) TRS for Loop Detection
1114.76/291.57	    (13) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
1114.76/291.57	    (14) BEST
1114.76/291.57	        (15) proven lower bound
1114.76/291.57	            (16) LowerBoundPropagationProof [FINISHED, 0 ms]
1114.76/291.57	            (17) BOUNDS(n^1, INF)
1114.76/291.57	        (18) TRS for Loop Detection
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	----------------------------------------
1114.76/291.57	
1114.76/291.57	(0)
1114.76/291.57	Obligation:
1114.76/291.57	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	The TRS R consists of the following rules:
1114.76/291.57	
1114.76/291.57	   f(true, x, y) -> f(and(gt(x, y), gt(y, s(s(0)))), plus(s(0), x), double(y))
1114.76/291.57	   gt(0, v) -> false
1114.76/291.57	   gt(s(u), 0) -> true
1114.76/291.57	   gt(s(u), s(v)) -> gt(u, v)
1114.76/291.57	   and(x, true) -> x
1114.76/291.57	   and(x, false) -> false
1114.76/291.57	   plus(n, 0) -> n
1114.76/291.57	   plus(n, s(m)) -> s(plus(n, m))
1114.76/291.57	   double(0) -> 0
1114.76/291.57	   double(s(x)) -> s(s(double(x)))
1114.76/291.57	
1114.76/291.57	S is empty.
1114.76/291.57	Rewrite Strategy: INNERMOST
1114.76/291.57	----------------------------------------
1114.76/291.57	
1114.76/291.57	(1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
1114.76/291.57	Transformed relative TRS to weighted TRS
1114.76/291.57	----------------------------------------
1114.76/291.57	
1114.76/291.57	(2)
1114.76/291.57	Obligation:
1114.76/291.57	The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2).
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	The TRS R consists of the following rules:
1114.76/291.57	
1114.76/291.57	   f(true, x, y) -> f(and(gt(x, y), gt(y, s(s(0)))), plus(s(0), x), double(y)) [1]
1114.76/291.57	   gt(0, v) -> false [1]
1114.76/291.57	   gt(s(u), 0) -> true [1]
1114.76/291.57	   gt(s(u), s(v)) -> gt(u, v) [1]
1114.76/291.57	   and(x, true) -> x [1]
1114.76/291.57	   and(x, false) -> false [1]
1114.76/291.57	   plus(n, 0) -> n [1]
1114.76/291.57	   plus(n, s(m)) -> s(plus(n, m)) [1]
1114.76/291.57	   double(0) -> 0 [1]
1114.76/291.57	   double(s(x)) -> s(s(double(x))) [1]
1114.76/291.57	
1114.76/291.57	Rewrite Strategy: INNERMOST
1114.76/291.57	----------------------------------------
1114.76/291.57	
1114.76/291.57	(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
1114.76/291.57	Infered types.
1114.76/291.57	----------------------------------------
1114.76/291.57	
1114.76/291.57	(4)
1114.76/291.57	Obligation:
1114.76/291.57	Runtime Complexity Weighted TRS with Types.
1114.76/291.57	The TRS R consists of the following rules:
1114.76/291.57	
1114.76/291.57	   f(true, x, y) -> f(and(gt(x, y), gt(y, s(s(0)))), plus(s(0), x), double(y)) [1]
1114.76/291.57	   gt(0, v) -> false [1]
1114.76/291.57	   gt(s(u), 0) -> true [1]
1114.76/291.57	   gt(s(u), s(v)) -> gt(u, v) [1]
1114.76/291.57	   and(x, true) -> x [1]
1114.76/291.57	   and(x, false) -> false [1]
1114.76/291.57	   plus(n, 0) -> n [1]
1114.76/291.57	   plus(n, s(m)) -> s(plus(n, m)) [1]
1114.76/291.57	   double(0) -> 0 [1]
1114.76/291.57	   double(s(x)) -> s(s(double(x))) [1]
1114.76/291.57	
1114.76/291.57	The TRS has the following type information:
1114.76/291.57	f :: true:false -> 0:s -> 0:s -> f
1114.76/291.57	true :: true:false
1114.76/291.57	and :: true:false -> true:false -> true:false
1114.76/291.57	gt :: 0:s -> 0:s -> true:false
1114.76/291.57	s :: 0:s -> 0:s
1114.76/291.57	0 :: 0:s
1114.76/291.57	plus :: 0:s -> 0:s -> 0:s
1114.76/291.57	double :: 0:s -> 0:s
1114.76/291.57	false :: true:false
1114.76/291.57	
1114.76/291.57	Rewrite Strategy: INNERMOST
1114.76/291.57	----------------------------------------
1114.76/291.57	
1114.76/291.57	(5) CompletionProof (UPPER BOUND(ID))
1114.76/291.57	The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added:
1114.76/291.57	
1114.76/291.57	   f(v0, v1, v2) -> null_f [0]
1114.76/291.57	
1114.76/291.57	And the following fresh constants:    null_f
1114.76/291.57	
1114.76/291.57	----------------------------------------
1114.76/291.57	
1114.76/291.57	(6)
1114.76/291.57	Obligation:
1114.76/291.57	Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is:
1114.76/291.57	
1114.76/291.57	Runtime Complexity Weighted TRS with Types.
1114.76/291.57	The TRS R consists of the following rules:
1114.76/291.57	
1114.76/291.57	   f(true, x, y) -> f(and(gt(x, y), gt(y, s(s(0)))), plus(s(0), x), double(y)) [1]
1114.76/291.57	   gt(0, v) -> false [1]
1114.76/291.57	   gt(s(u), 0) -> true [1]
1114.76/291.57	   gt(s(u), s(v)) -> gt(u, v) [1]
1114.76/291.57	   and(x, true) -> x [1]
1114.76/291.57	   and(x, false) -> false [1]
1114.76/291.57	   plus(n, 0) -> n [1]
1114.76/291.57	   plus(n, s(m)) -> s(plus(n, m)) [1]
1114.76/291.57	   double(0) -> 0 [1]
1114.76/291.57	   double(s(x)) -> s(s(double(x))) [1]
1114.76/291.57	   f(v0, v1, v2) -> null_f [0]
1114.76/291.57	
1114.76/291.57	The TRS has the following type information:
1114.76/291.57	f :: true:false -> 0:s -> 0:s -> null_f
1114.76/291.57	true :: true:false
1114.76/291.57	and :: true:false -> true:false -> true:false
1114.76/291.57	gt :: 0:s -> 0:s -> true:false
1114.76/291.57	s :: 0:s -> 0:s
1114.76/291.57	0 :: 0:s
1114.76/291.57	plus :: 0:s -> 0:s -> 0:s
1114.76/291.57	double :: 0:s -> 0:s
1114.76/291.57	false :: true:false
1114.76/291.57	null_f :: null_f
1114.76/291.57	
1114.76/291.57	Rewrite Strategy: INNERMOST
1114.76/291.57	----------------------------------------
1114.76/291.57	
1114.76/291.57	(7) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
1114.76/291.57	Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
1114.76/291.57	The constant constructors are abstracted as follows:
1114.76/291.57	
1114.76/291.57	   true => 1
1114.76/291.57	   0 => 0
1114.76/291.57	   false => 0
1114.76/291.57	   null_f => 0
1114.76/291.57	
1114.76/291.57	----------------------------------------
1114.76/291.57	
1114.76/291.57	(8)
1114.76/291.57	Obligation:
1114.76/291.57	Complexity RNTS consisting of the following rules:
1114.76/291.57	
1114.76/291.57	   and(z, z') -{ 1 }-> x :|: x >= 0, z' = 1, z = x
1114.76/291.57	   and(z, z') -{ 1 }-> 0 :|: x >= 0, z = x, z' = 0
1114.76/291.57	   double(z) -{ 1 }-> 0 :|: z = 0
1114.76/291.57	   double(z) -{ 1 }-> 1 + (1 + double(x)) :|: x >= 0, z = 1 + x
1114.76/291.57	   f(z, z', z'') -{ 1 }-> f(and(gt(x, y), gt(y, 1 + (1 + 0))), plus(1 + 0, x), double(y)) :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0
1114.76/291.57	   f(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0
1114.76/291.57	   gt(z, z') -{ 1 }-> gt(u, v) :|: v >= 0, z' = 1 + v, z = 1 + u, u >= 0
1114.76/291.57	   gt(z, z') -{ 1 }-> 1 :|: z = 1 + u, z' = 0, u >= 0
1114.76/291.57	   gt(z, z') -{ 1 }-> 0 :|: v >= 0, z' = v, z = 0
1114.76/291.57	   plus(z, z') -{ 1 }-> n :|: n >= 0, z = n, z' = 0
1114.76/291.57	   plus(z, z') -{ 1 }-> 1 + plus(n, m) :|: n >= 0, z = n, z' = 1 + m, m >= 0
1114.76/291.57	
1114.76/291.57	Only complete derivations are relevant for the runtime complexity.
1114.76/291.57	
1114.76/291.57	----------------------------------------
1114.76/291.57	
1114.76/291.57	(9) CompleteCoflocoProof (FINISHED)
1114.76/291.57	Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo:
1114.76/291.57	
1114.76/291.57	eq(start(V1, V, V2),0,[f(V1, V, V2, Out)],[V1 >= 0,V >= 0,V2 >= 0]).
1114.76/291.57	eq(start(V1, V, V2),0,[gt(V1, V, Out)],[V1 >= 0,V >= 0]).
1114.76/291.57	eq(start(V1, V, V2),0,[and(V1, V, Out)],[V1 >= 0,V >= 0]).
1114.76/291.57	eq(start(V1, V, V2),0,[plus(V1, V, Out)],[V1 >= 0,V >= 0]).
1114.76/291.57	eq(start(V1, V, V2),0,[double(V1, Out)],[V1 >= 0]).
1114.76/291.57	eq(f(V1, V, V2, Out),1,[gt(V4, V3, Ret00),gt(V3, 1 + (1 + 0), Ret01),and(Ret00, Ret01, Ret0),plus(1 + 0, V4, Ret1),double(V3, Ret2),f(Ret0, Ret1, Ret2, Ret)],[Out = Ret,V = V4,V2 = V3,V1 = 1,V4 >= 0,V3 >= 0]).
1114.76/291.57	eq(gt(V1, V, Out),1,[],[Out = 0,V5 >= 0,V = V5,V1 = 0]).
1114.76/291.57	eq(gt(V1, V, Out),1,[],[Out = 1,V1 = 1 + V6,V = 0,V6 >= 0]).
1114.76/291.57	eq(gt(V1, V, Out),1,[gt(V7, V8, Ret3)],[Out = Ret3,V8 >= 0,V = 1 + V8,V1 = 1 + V7,V7 >= 0]).
1114.76/291.57	eq(and(V1, V, Out),1,[],[Out = V9,V9 >= 0,V = 1,V1 = V9]).
1114.76/291.57	eq(and(V1, V, Out),1,[],[Out = 0,V10 >= 0,V1 = V10,V = 0]).
1114.76/291.57	eq(plus(V1, V, Out),1,[],[Out = V11,V11 >= 0,V1 = V11,V = 0]).
1114.76/291.57	eq(plus(V1, V, Out),1,[plus(V12, V13, Ret11)],[Out = 1 + Ret11,V12 >= 0,V1 = V12,V = 1 + V13,V13 >= 0]).
1114.76/291.57	eq(double(V1, Out),1,[],[Out = 0,V1 = 0]).
1114.76/291.57	eq(double(V1, Out),1,[double(V14, Ret111)],[Out = 2 + Ret111,V14 >= 0,V1 = 1 + V14]).
1114.76/291.57	eq(f(V1, V, V2, Out),0,[],[Out = 0,V16 >= 0,V2 = V17,V15 >= 0,V1 = V16,V = V15,V17 >= 0]).
1114.76/291.57	input_output_vars(f(V1,V,V2,Out),[V1,V,V2],[Out]).
1114.76/291.57	input_output_vars(gt(V1,V,Out),[V1,V],[Out]).
1114.76/291.57	input_output_vars(and(V1,V,Out),[V1,V],[Out]).
1114.76/291.57	input_output_vars(plus(V1,V,Out),[V1,V],[Out]).
1114.76/291.57	input_output_vars(double(V1,Out),[V1],[Out]).
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	CoFloCo proof output:
1114.76/291.57	Preprocessing Cost Relations
1114.76/291.57	=====================================
1114.76/291.57	
1114.76/291.57	#### Computed strongly connected components 
1114.76/291.57	0. non_recursive  : [and/3]
1114.76/291.57	1. recursive  : [double/2]
1114.76/291.57	2. recursive  : [gt/3]
1114.76/291.57	3. recursive  : [plus/3]
1114.76/291.57	4. recursive  : [f/4]
1114.76/291.57	5. non_recursive  : [start/3]
1114.76/291.57	
1114.76/291.57	#### Obtained direct recursion through partial evaluation 
1114.76/291.57	0. SCC is partially evaluated into and/3
1114.76/291.57	1. SCC is partially evaluated into double/2
1114.76/291.57	2. SCC is partially evaluated into gt/3
1114.76/291.57	3. SCC is partially evaluated into plus/3
1114.76/291.57	4. SCC is partially evaluated into f/4
1114.76/291.57	5. SCC is partially evaluated into start/3
1114.76/291.57	
1114.76/291.57	Control-Flow Refinement of Cost Relations
1114.76/291.57	=====================================
1114.76/291.57	
1114.76/291.57	### Specialization of cost equations and/3 
1114.76/291.57	* CE 11 is refined into CE [17] 
1114.76/291.57	* CE 12 is refined into CE [18] 
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	### Cost equations --> "Loop" of and/3 
1114.76/291.57	* CEs [17] --> Loop 13 
1114.76/291.57	* CEs [18] --> Loop 14 
1114.76/291.57	
1114.76/291.57	### Ranking functions of CR and(V1,V,Out) 
1114.76/291.57	
1114.76/291.57	#### Partial ranking functions of CR and(V1,V,Out) 
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	### Specialization of cost equations double/2 
1114.76/291.57	* CE 16 is refined into CE [19] 
1114.76/291.57	* CE 15 is refined into CE [20] 
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	### Cost equations --> "Loop" of double/2 
1114.76/291.57	* CEs [20] --> Loop 15 
1114.76/291.57	* CEs [19] --> Loop 16 
1114.76/291.57	
1114.76/291.57	### Ranking functions of CR double(V1,Out) 
1114.76/291.57	* RF of phase [16]: [V1]
1114.76/291.57	
1114.76/291.57	#### Partial ranking functions of CR double(V1,Out) 
1114.76/291.57	* Partial RF of phase [16]:
1114.76/291.57	  - RF of loop [16:1]:
1114.76/291.57	    V1
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	### Specialization of cost equations gt/3 
1114.76/291.57	* CE 10 is refined into CE [21] 
1114.76/291.57	* CE 9 is refined into CE [22] 
1114.76/291.57	* CE 8 is refined into CE [23] 
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	### Cost equations --> "Loop" of gt/3 
1114.76/291.57	* CEs [22] --> Loop 17 
1114.76/291.57	* CEs [23] --> Loop 18 
1114.76/291.57	* CEs [21] --> Loop 19 
1114.76/291.57	
1114.76/291.57	### Ranking functions of CR gt(V1,V,Out) 
1114.76/291.57	* RF of phase [19]: [V,V1]
1114.76/291.57	
1114.76/291.57	#### Partial ranking functions of CR gt(V1,V,Out) 
1114.76/291.57	* Partial RF of phase [19]:
1114.76/291.57	  - RF of loop [19:1]:
1114.76/291.57	    V
1114.76/291.57	    V1
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	### Specialization of cost equations plus/3 
1114.76/291.57	* CE 14 is refined into CE [24] 
1114.76/291.57	* CE 13 is refined into CE [25] 
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	### Cost equations --> "Loop" of plus/3 
1114.76/291.57	* CEs [25] --> Loop 20 
1114.76/291.57	* CEs [24] --> Loop 21 
1114.76/291.57	
1114.76/291.57	### Ranking functions of CR plus(V1,V,Out) 
1114.76/291.57	* RF of phase [21]: [V]
1114.76/291.57	
1114.76/291.57	#### Partial ranking functions of CR plus(V1,V,Out) 
1114.76/291.57	* Partial RF of phase [21]:
1114.76/291.57	  - RF of loop [21:1]:
1114.76/291.57	    V
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	### Specialization of cost equations f/4 
1114.76/291.57	* CE 7 is refined into CE [26] 
1114.76/291.57	* CE 6 is refined into CE [27,28,29,30,31,32,33,34] 
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	### Cost equations --> "Loop" of f/4 
1114.76/291.57	* CEs [34] --> Loop 22 
1114.76/291.57	* CEs [32] --> Loop 23 
1114.76/291.57	* CEs [33] --> Loop 24 
1114.76/291.57	* CEs [31] --> Loop 25 
1114.76/291.57	* CEs [30] --> Loop 26 
1114.76/291.57	* CEs [29] --> Loop 27 
1114.76/291.57	* CEs [28] --> Loop 28 
1114.76/291.57	* CEs [27] --> Loop 29 
1114.76/291.57	* CEs [26] --> Loop 30 
1114.76/291.57	
1114.76/291.57	### Ranking functions of CR f(V1,V,V2,Out) 
1114.76/291.57	* RF of phase [22]: [V/2-V2/2]
1114.76/291.57	
1114.76/291.57	#### Partial ranking functions of CR f(V1,V,V2,Out) 
1114.76/291.57	* Partial RF of phase [22]:
1114.76/291.57	  - RF of loop [22:1]:
1114.76/291.57	    V/2-V2/2
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	### Specialization of cost equations start/3 
1114.76/291.57	* CE 1 is refined into CE [35,36,37,38,39,40,41,42] 
1114.76/291.57	* CE 2 is refined into CE [43,44,45,46] 
1114.76/291.57	* CE 3 is refined into CE [47,48] 
1114.76/291.57	* CE 4 is refined into CE [49,50] 
1114.76/291.57	* CE 5 is refined into CE [51,52] 
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	### Cost equations --> "Loop" of start/3 
1114.76/291.57	* CEs [48] --> Loop 31 
1114.76/291.57	* CEs [42] --> Loop 32 
1114.76/291.57	* CEs [41] --> Loop 33 
1114.76/291.57	* CEs [40] --> Loop 34 
1114.76/291.57	* CEs [39,52] --> Loop 35 
1114.76/291.57	* CEs [38,45,46,50] --> Loop 36 
1114.76/291.57	* CEs [35,37] --> Loop 37 
1114.76/291.57	* CEs [36,44,47,49] --> Loop 38 
1114.76/291.57	* CEs [43,51] --> Loop 39 
1114.76/291.57	
1114.76/291.57	### Ranking functions of CR start(V1,V,V2) 
1114.76/291.57	
1114.76/291.57	#### Partial ranking functions of CR start(V1,V,V2) 
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	Computing Bounds
1114.76/291.57	=====================================
1114.76/291.57	
1114.76/291.57	#### Cost of chains of and(V1,V,Out):
1114.76/291.57	* Chain [14]: 1
1114.76/291.57	  with precondition: [V=0,Out=0,V1>=0] 
1114.76/291.57	
1114.76/291.57	* Chain [13]: 1
1114.76/291.57	  with precondition: [V=1,V1=Out,V1>=0] 
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	#### Cost of chains of double(V1,Out):
1114.76/291.57	* Chain [[16],15]: 1*it(16)+1
1114.76/291.57	  Such that:it(16) =< Out/2
1114.76/291.57	
1114.76/291.57	  with precondition: [2*V1=Out,V1>=1] 
1114.76/291.57	
1114.76/291.57	* Chain [15]: 1
1114.76/291.57	  with precondition: [V1=0,Out=0] 
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	#### Cost of chains of gt(V1,V,Out):
1114.76/291.57	* Chain [[19],18]: 1*it(19)+1
1114.76/291.57	  Such that:it(19) =< V1
1114.76/291.57	
1114.76/291.57	  with precondition: [Out=0,V1>=1,V>=V1] 
1114.76/291.57	
1114.76/291.57	* Chain [[19],17]: 1*it(19)+1
1114.76/291.57	  Such that:it(19) =< V
1114.76/291.57	
1114.76/291.57	  with precondition: [Out=1,V>=1,V1>=V+1] 
1114.76/291.57	
1114.76/291.57	* Chain [18]: 1
1114.76/291.57	  with precondition: [V1=0,Out=0,V>=0] 
1114.76/291.57	
1114.76/291.57	* Chain [17]: 1
1114.76/291.57	  with precondition: [V=0,Out=1,V1>=1] 
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	#### Cost of chains of plus(V1,V,Out):
1114.76/291.57	* Chain [[21],20]: 1*it(21)+1
1114.76/291.57	  Such that:it(21) =< V
1114.76/291.57	
1114.76/291.57	  with precondition: [V+V1=Out,V1>=0,V>=1] 
1114.76/291.57	
1114.76/291.57	* Chain [20]: 1
1114.76/291.57	  with precondition: [V=0,V1=Out,V1>=0] 
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	#### Cost of chains of f(V1,V,V2,Out):
1114.76/291.57	* Chain [[22],30]: 6*it(22)+2*s(9)+1*s(10)+1*s(11)+0
1114.76/291.57	  Such that:aux(6) =< 2*V-3/2*V2
1114.76/291.57	aux(4) =< 3*V-2*V2
1114.76/291.57	s(12) =< 6*V-4*V2
1114.76/291.57	aux(5) =< V/2-V2/2
1114.76/291.57	s(12) =< aux(4)
1114.76/291.57	aux(2) =< aux(5)
1114.76/291.57	it(22) =< aux(5)
1114.76/291.57	aux(2) =< aux(6)
1114.76/291.57	it(22) =< aux(6)
1114.76/291.57	s(11) =< it(22)*aux(4)
1114.76/291.57	s(10) =< aux(2)*2
1114.76/291.57	s(9) =< s(12)
1114.76/291.57	
1114.76/291.57	  with precondition: [V1=1,Out=0,V2>=3,V>=V2+1] 
1114.76/291.57	
1114.76/291.57	* Chain [[22],23,30]: 6*it(22)+2*s(9)+1*s(10)+1*s(11)+2*s(13)+1*s(14)+1*s(16)+6
1114.76/291.57	  Such that:s(14) =< 2
1114.76/291.57	aux(6) =< 2*V-3/2*V2
1114.76/291.57	aux(5) =< V/2-V2/2
1114.76/291.57	aux(8) =< 3*V-2*V2
1114.76/291.57	aux(9) =< 6*V-4*V2
1114.76/291.57	s(12) =< aux(9)
1114.76/291.57	s(16) =< aux(9)
1114.76/291.57	s(13) =< aux(8)
1114.76/291.57	s(12) =< aux(8)
1114.76/291.57	aux(2) =< aux(5)
1114.76/291.57	it(22) =< aux(5)
1114.76/291.57	aux(2) =< aux(6)
1114.76/291.57	it(22) =< aux(6)
1114.76/291.57	s(11) =< it(22)*aux(8)
1114.76/291.57	s(10) =< aux(2)*2
1114.76/291.57	s(9) =< s(12)
1114.76/291.57	
1114.76/291.57	  with precondition: [V1=1,Out=0,V2>=3,V>=V2+1] 
1114.76/291.57	
1114.76/291.57	* Chain [30]: 0
1114.76/291.57	  with precondition: [Out=0,V1>=0,V>=0,V2>=0] 
1114.76/291.57	
1114.76/291.57	* Chain [29,30]: 6
1114.76/291.57	  with precondition: [V1=1,V=0,V2=0,Out=0] 
1114.76/291.57	
1114.76/291.57	* Chain [28,30]: 2*s(17)+6
1114.76/291.57	  Such that:aux(10) =< V2
1114.76/291.57	s(17) =< aux(10)
1114.76/291.57	
1114.76/291.57	  with precondition: [V1=1,V=0,Out=0,2>=V2,V2>=1] 
1114.76/291.57	
1114.76/291.57	* Chain [27,30]: 1*s(19)+1*s(20)+6
1114.76/291.57	  Such that:s(19) =< 2
1114.76/291.57	s(20) =< V2
1114.76/291.57	
1114.76/291.57	  with precondition: [V1=1,V=0,Out=0,V2>=3] 
1114.76/291.57	
1114.76/291.57	* Chain [26,30]: 1*s(21)+6
1114.76/291.57	  Such that:s(21) =< V
1114.76/291.57	
1114.76/291.57	  with precondition: [V1=1,V2=0,Out=0,V>=1] 
1114.76/291.57	
1114.76/291.57	* Chain [25,30]: 2*s(22)+2*s(23)+6
1114.76/291.57	  Such that:aux(11) =< V
1114.76/291.57	aux(12) =< V2
1114.76/291.57	s(22) =< aux(11)
1114.76/291.57	s(23) =< aux(12)
1114.76/291.57	
1114.76/291.57	  with precondition: [V1=1,Out=0,2>=V2,V>=1,V2>=V] 
1114.76/291.57	
1114.76/291.57	* Chain [24,30]: 3*s(26)+1*s(28)+6
1114.76/291.57	  Such that:s(28) =< V+1
1114.76/291.57	aux(13) =< V2
1114.76/291.57	s(26) =< aux(13)
1114.76/291.57	
1114.76/291.57	  with precondition: [V1=1,Out=0,2>=V2,V2>=1,V>=V2+1] 
1114.76/291.57	
1114.76/291.57	* Chain [23,30]: 2*s(13)+1*s(14)+1*s(16)+6
1114.76/291.57	  Such that:s(14) =< 2
1114.76/291.57	aux(7) =< V
1114.76/291.57	s(16) =< V2
1114.76/291.57	s(13) =< aux(7)
1114.76/291.57	
1114.76/291.57	  with precondition: [V1=1,Out=0,V>=1,V2>=3,V2>=V] 
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	#### Cost of chains of start(V1,V,V2):
1114.76/291.57	* Chain [39]: 1
1114.76/291.57	  with precondition: [V1=0] 
1114.76/291.57	
1114.76/291.57	* Chain [38]: 2*s(53)+6
1114.76/291.57	  Such that:s(52) =< V2
1114.76/291.57	s(53) =< s(52)
1114.76/291.57	
1114.76/291.57	  with precondition: [V=0,V1>=0] 
1114.76/291.57	
1114.76/291.57	* Chain [37]: 1*s(54)+1*s(55)+6
1114.76/291.57	  Such that:s(54) =< 2
1114.76/291.57	s(55) =< V2
1114.76/291.57	
1114.76/291.57	  with precondition: [V1>=0,V>=0,V2>=0] 
1114.76/291.57	
1114.76/291.57	* Chain [36]: 3*s(56)+1*s(57)+6
1114.76/291.57	  Such that:s(57) =< V1
1114.76/291.57	aux(18) =< V
1114.76/291.57	s(56) =< aux(18)
1114.76/291.57	
1114.76/291.57	  with precondition: [V1>=0,V>=1] 
1114.76/291.57	
1114.76/291.57	* Chain [35]: 2*s(62)+2*s(63)+1*s(64)+6
1114.76/291.57	  Such that:s(64) =< V1
1114.76/291.57	s(60) =< V
1114.76/291.57	s(61) =< V2
1114.76/291.57	s(62) =< s(60)
1114.76/291.57	s(63) =< s(61)
1114.76/291.57	
1114.76/291.57	  with precondition: [V1>=1] 
1114.76/291.57	
1114.76/291.57	* Chain [34]: 1*s(65)+3*s(67)+6
1114.76/291.57	  Such that:s(65) =< V+1
1114.76/291.57	s(66) =< V2
1114.76/291.57	s(67) =< s(66)
1114.76/291.57	
1114.76/291.57	  with precondition: [V1=1,2>=V2,V2>=1,V>=V2+1] 
1114.76/291.57	
1114.76/291.57	* Chain [33]: 1*s(68)+1*s(70)+2*s(71)+6
1114.76/291.57	  Such that:s(68) =< 2
1114.76/291.57	s(69) =< V
1114.76/291.57	s(70) =< V2
1114.76/291.57	s(71) =< s(69)
1114.76/291.57	
1114.76/291.57	  with precondition: [V1=1,V>=1,V2>=3,V2>=V] 
1114.76/291.57	
1114.76/291.57	* Chain [32]: 1*s(72)+1*s(78)+2*s(79)+12*s(81)+2*s(82)+2*s(83)+4*s(84)+6
1114.76/291.57	  Such that:s(72) =< 2
1114.76/291.57	s(73) =< 2*V-3/2*V2
1114.76/291.57	s(74) =< 3*V-2*V2
1114.76/291.57	s(75) =< 6*V-4*V2
1114.76/291.57	s(76) =< V/2-V2/2
1114.76/291.57	s(77) =< s(75)
1114.76/291.57	s(78) =< s(75)
1114.76/291.57	s(79) =< s(74)
1114.76/291.57	s(77) =< s(74)
1114.76/291.57	s(80) =< s(76)
1114.76/291.57	s(81) =< s(76)
1114.76/291.57	s(80) =< s(73)
1114.76/291.57	s(81) =< s(73)
1114.76/291.57	s(82) =< s(81)*s(74)
1114.76/291.57	s(83) =< s(80)*2
1114.76/291.57	s(84) =< s(77)
1114.76/291.57	
1114.76/291.57	  with precondition: [V1=1,V2>=3,V>=V2+1] 
1114.76/291.57	
1114.76/291.57	* Chain [31]: 1
1114.76/291.57	  with precondition: [V=1,V1>=0] 
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	Closed-form bounds of start(V1,V,V2): 
1114.76/291.57	-------------------------------------
1114.76/291.57	* Chain [39] with precondition: [V1=0] 
1114.76/291.57	    - Upper bound: 1 
1114.76/291.57	    - Complexity: constant 
1114.76/291.57	* Chain [38] with precondition: [V=0,V1>=0] 
1114.76/291.57	    - Upper bound: nat(V2)*2+6 
1114.76/291.57	    - Complexity: n 
1114.76/291.57	* Chain [37] with precondition: [V1>=0,V>=0,V2>=0] 
1114.76/291.57	    - Upper bound: V2+8 
1114.76/291.57	    - Complexity: n 
1114.76/291.57	* Chain [36] with precondition: [V1>=0,V>=1] 
1114.76/291.57	    - Upper bound: V1+3*V+6 
1114.76/291.57	    - Complexity: n 
1114.76/291.57	* Chain [35] with precondition: [V1>=1] 
1114.76/291.57	    - Upper bound: V1+6+nat(V)*2+nat(V2)*2 
1114.76/291.57	    - Complexity: n 
1114.76/291.57	* Chain [34] with precondition: [V1=1,2>=V2,V2>=1,V>=V2+1] 
1114.76/291.57	    - Upper bound: V+3*V2+7 
1114.76/291.57	    - Complexity: n 
1114.76/291.57	* Chain [33] with precondition: [V1=1,V>=1,V2>=3,V2>=V] 
1114.76/291.57	    - Upper bound: 2*V+V2+8 
1114.76/291.57	    - Complexity: n 
1114.76/291.57	* Chain [32] with precondition: [V1=1,V2>=3,V>=V2+1] 
1114.76/291.57	    - Upper bound: 8*V-8*V2+(30*V-20*V2+(6*V-4*V2+8+(V/2-V2/2)*(6*V-4*V2))) 
1114.76/291.57	    - Complexity: n^2 
1114.76/291.57	* Chain [31] with precondition: [V=1,V1>=0] 
1114.76/291.57	    - Upper bound: 1 
1114.76/291.57	    - Complexity: constant 
1114.76/291.57	
1114.76/291.57	### Maximum cost of start(V1,V,V2): max([max([V1+5+nat(V)*3,nat(3*V-2*V2)*2+7+nat(3*V-2*V2)*2*nat(V/2-V2/2)+nat(6*V-4*V2)*5+nat(V/2-V2/2)*16]),nat(V2)+5+max([nat(V2)+max([nat(V+1)+nat(V2),nat(V)*2+V1]),nat(V)*2+2])])+1 
1114.76/291.57	Asymptotic class: n^2 
1114.76/291.57	* Total analysis performed in 423 ms.
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	----------------------------------------
1114.76/291.57	
1114.76/291.57	(10)
1114.76/291.57	BOUNDS(1, n^2)
1114.76/291.57	
1114.76/291.57	----------------------------------------
1114.76/291.57	
1114.76/291.57	(11) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
1114.76/291.57	Transformed a relative TRS into a decreasing-loop problem.
1114.76/291.57	----------------------------------------
1114.76/291.57	
1114.76/291.57	(12)
1114.76/291.57	Obligation:
1114.76/291.57	Analyzing the following TRS for decreasing loops:
1114.76/291.57	
1114.76/291.57	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	The TRS R consists of the following rules:
1114.76/291.57	
1114.76/291.57	   f(true, x, y) -> f(and(gt(x, y), gt(y, s(s(0)))), plus(s(0), x), double(y))
1114.76/291.57	   gt(0, v) -> false
1114.76/291.57	   gt(s(u), 0) -> true
1114.76/291.57	   gt(s(u), s(v)) -> gt(u, v)
1114.76/291.57	   and(x, true) -> x
1114.76/291.57	   and(x, false) -> false
1114.76/291.57	   plus(n, 0) -> n
1114.76/291.57	   plus(n, s(m)) -> s(plus(n, m))
1114.76/291.57	   double(0) -> 0
1114.76/291.57	   double(s(x)) -> s(s(double(x)))
1114.76/291.57	
1114.76/291.57	S is empty.
1114.76/291.57	Rewrite Strategy: INNERMOST
1114.76/291.57	----------------------------------------
1114.76/291.57	
1114.76/291.57	(13) DecreasingLoopProof (LOWER BOUND(ID))
1114.76/291.57	The following loop(s) give(s) rise to the lower bound Omega(n^1):
1114.76/291.57	
1114.76/291.57	The rewrite sequence
1114.76/291.57	
1114.76/291.57	gt(s(u), s(v)) ->^+ gt(u, v)
1114.76/291.57	
1114.76/291.57	gives rise to a decreasing loop by considering the right hand sides subterm at position [].
1114.76/291.57	
1114.76/291.57	The pumping substitution is [u / s(u), v / s(v)].
1114.76/291.57	
1114.76/291.57	The result substitution is [ ].
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	----------------------------------------
1114.76/291.57	
1114.76/291.57	(14)
1114.76/291.57	Complex Obligation (BEST)
1114.76/291.57	
1114.76/291.57	----------------------------------------
1114.76/291.57	
1114.76/291.57	(15)
1114.76/291.57	Obligation:
1114.76/291.57	Proved the lower bound n^1 for the following obligation:
1114.76/291.57	
1114.76/291.57	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	The TRS R consists of the following rules:
1114.76/291.57	
1114.76/291.57	   f(true, x, y) -> f(and(gt(x, y), gt(y, s(s(0)))), plus(s(0), x), double(y))
1114.76/291.57	   gt(0, v) -> false
1114.76/291.57	   gt(s(u), 0) -> true
1114.76/291.57	   gt(s(u), s(v)) -> gt(u, v)
1114.76/291.57	   and(x, true) -> x
1114.76/291.57	   and(x, false) -> false
1114.76/291.57	   plus(n, 0) -> n
1114.76/291.57	   plus(n, s(m)) -> s(plus(n, m))
1114.76/291.57	   double(0) -> 0
1114.76/291.57	   double(s(x)) -> s(s(double(x)))
1114.76/291.57	
1114.76/291.57	S is empty.
1114.76/291.57	Rewrite Strategy: INNERMOST
1114.76/291.57	----------------------------------------
1114.76/291.57	
1114.76/291.57	(16) LowerBoundPropagationProof (FINISHED)
1114.76/291.57	Propagated lower bound.
1114.76/291.57	----------------------------------------
1114.76/291.57	
1114.76/291.57	(17)
1114.76/291.57	BOUNDS(n^1, INF)
1114.76/291.57	
1114.76/291.57	----------------------------------------
1114.76/291.57	
1114.76/291.57	(18)
1114.76/291.57	Obligation:
1114.76/291.57	Analyzing the following TRS for decreasing loops:
1114.76/291.57	
1114.76/291.57	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
1114.76/291.57	
1114.76/291.57	
1114.76/291.57	The TRS R consists of the following rules:
1114.76/291.57	
1114.76/291.57	   f(true, x, y) -> f(and(gt(x, y), gt(y, s(s(0)))), plus(s(0), x), double(y))
1114.76/291.57	   gt(0, v) -> false
1114.76/291.57	   gt(s(u), 0) -> true
1114.76/291.57	   gt(s(u), s(v)) -> gt(u, v)
1114.76/291.57	   and(x, true) -> x
1114.76/291.57	   and(x, false) -> false
1114.76/291.57	   plus(n, 0) -> n
1114.76/291.57	   plus(n, s(m)) -> s(plus(n, m))
1114.76/291.57	   double(0) -> 0
1114.76/291.57	   double(s(x)) -> s(s(double(x)))
1114.76/291.57	
1114.76/291.57	S is empty.
1114.76/291.57	Rewrite Strategy: INNERMOST
1114.76/291.61	EOF