19.23/5.72	WORST_CASE(Omega(n^1), O(n^1))
19.23/5.73	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
19.23/5.73	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
19.23/5.73	
19.23/5.73	
19.23/5.73	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1).
19.23/5.73	
19.23/5.73	(0) CpxRelTRS
19.23/5.73	(1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 175 ms]
19.23/5.73	(2) CpxRelTRS
19.23/5.73	(3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
19.23/5.73	(4) CpxWeightedTrs
19.23/5.73	    (5) CpxWeightedTrsRenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
19.23/5.73	    (6) CpxWeightedTrs
19.23/5.73	    (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
19.23/5.73	    (8) CpxTypedWeightedTrs
19.23/5.73	    (9) CompletionProof [UPPER BOUND(ID), 0 ms]
19.23/5.73	    (10) CpxTypedWeightedCompleteTrs
19.23/5.73	    (11) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 6 ms]
19.23/5.73	    (12) CpxRNTS
19.23/5.73	    (13) CompleteCoflocoProof [FINISHED, 214 ms]
19.23/5.73	    (14) BOUNDS(1, n^1)
19.23/5.73	(15) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
19.23/5.73	(16) CpxRelTRS
19.23/5.73	    (17) SlicingProof [LOWER BOUND(ID), 0 ms]
19.23/5.73	    (18) CpxRelTRS
19.23/5.73	    (19) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
19.23/5.73	    (20) typed CpxTrs
19.23/5.73	    (21) OrderProof [LOWER BOUND(ID), 6 ms]
19.23/5.73	    (22) typed CpxTrs
19.23/5.73	    (23) RewriteLemmaProof [LOWER BOUND(ID), 224 ms]
19.23/5.73	    (24) BEST
19.23/5.73	        (25) proven lower bound
19.23/5.73	            (26) LowerBoundPropagationProof [FINISHED, 0 ms]
19.23/5.73	            (27) BOUNDS(n^1, INF)
19.23/5.73	        (28) typed CpxTrs
19.23/5.73	            (29) RewriteLemmaProof [LOWER BOUND(ID), 1798 ms]
19.23/5.73	            (30) typed CpxTrs
19.23/5.73	            (31) RewriteLemmaProof [LOWER BOUND(ID), 50 ms]
19.23/5.73	            (32) BOUNDS(1, INF)
19.23/5.73	
19.23/5.73	
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(0)
19.23/5.73	Obligation:
19.23/5.73	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1).
19.23/5.73	
19.23/5.73	
19.23/5.73	The TRS R consists of the following rules:
19.23/5.73	
19.23/5.73	   map(Cons(x, xs)) -> Cons(f(x), map(xs))
19.23/5.73	   map(Nil) -> Nil
19.23/5.73	   goal(xs) -> map(xs)
19.23/5.73	   f(x) -> *(x, x)
19.23/5.73	   +Full(S(x), y) -> +Full(x, S(y))
19.23/5.73	   +Full(0, y) -> y
19.23/5.73	
19.23/5.73	The (relative) TRS S consists of the following rules:
19.23/5.73	
19.23/5.73	   *(x, S(S(y))) -> +(x, *(x, S(y)))
19.23/5.73	   *(x, S(0)) -> x
19.23/5.73	   *(x, 0) -> 0
19.23/5.73	   *(0, y) -> 0
19.23/5.73	
19.23/5.73	Rewrite Strategy: INNERMOST
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID))
19.23/5.73	proved termination of relative rules
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(2)
19.23/5.73	Obligation:
19.23/5.73	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1).
19.23/5.73	
19.23/5.73	
19.23/5.73	The TRS R consists of the following rules:
19.23/5.73	
19.23/5.73	   map(Cons(x, xs)) -> Cons(f(x), map(xs))
19.23/5.73	   map(Nil) -> Nil
19.23/5.73	   goal(xs) -> map(xs)
19.23/5.73	   f(x) -> *(x, x)
19.23/5.73	   +Full(S(x), y) -> +Full(x, S(y))
19.23/5.73	   +Full(0, y) -> y
19.23/5.73	
19.23/5.73	The (relative) TRS S consists of the following rules:
19.23/5.73	
19.23/5.73	   *(x, S(S(y))) -> +(x, *(x, S(y)))
19.23/5.73	   *(x, S(0)) -> x
19.23/5.73	   *(x, 0) -> 0
19.23/5.73	   *(0, y) -> 0
19.23/5.73	
19.23/5.73	Rewrite Strategy: INNERMOST
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
19.23/5.73	Transformed relative TRS to weighted TRS
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(4)
19.23/5.73	Obligation:
19.23/5.73	The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1).
19.23/5.73	
19.23/5.73	
19.23/5.73	The TRS R consists of the following rules:
19.23/5.73	
19.23/5.73	   map(Cons(x, xs)) -> Cons(f(x), map(xs)) [1]
19.23/5.73	   map(Nil) -> Nil [1]
19.23/5.73	   goal(xs) -> map(xs) [1]
19.23/5.73	   f(x) -> *(x, x) [1]
19.23/5.73	   +Full(S(x), y) -> +Full(x, S(y)) [1]
19.23/5.73	   +Full(0, y) -> y [1]
19.23/5.73	   *(x, S(S(y))) -> +(x, *(x, S(y))) [0]
19.23/5.73	   *(x, S(0)) -> x [0]
19.23/5.73	   *(x, 0) -> 0 [0]
19.23/5.73	   *(0, y) -> 0 [0]
19.23/5.73	
19.23/5.73	Rewrite Strategy: INNERMOST
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(5) CpxWeightedTrsRenamingProof (BOTH BOUNDS(ID, ID))
19.23/5.73	Renamed defined symbols to avoid conflicts with arithmetic symbols:
19.23/5.73	
19.23/5.73	* => times
19.23/5.73	
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(6)
19.23/5.73	Obligation:
19.23/5.73	The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1).
19.23/5.73	
19.23/5.73	
19.23/5.73	The TRS R consists of the following rules:
19.23/5.73	
19.23/5.73	   map(Cons(x, xs)) -> Cons(f(x), map(xs)) [1]
19.23/5.73	   map(Nil) -> Nil [1]
19.23/5.73	   goal(xs) -> map(xs) [1]
19.23/5.73	   f(x) -> times(x, x) [1]
19.23/5.73	   +Full(S(x), y) -> +Full(x, S(y)) [1]
19.23/5.73	   +Full(0, y) -> y [1]
19.23/5.73	   times(x, S(S(y))) -> +(x, times(x, S(y))) [0]
19.23/5.73	   times(x, S(0)) -> x [0]
19.23/5.73	   times(x, 0) -> 0 [0]
19.23/5.73	   times(0, y) -> 0 [0]
19.23/5.73	
19.23/5.73	Rewrite Strategy: INNERMOST
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(7) TypeInferenceProof (BOTH BOUNDS(ID, ID))
19.23/5.73	Infered types.
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(8)
19.23/5.73	Obligation:
19.23/5.73	Runtime Complexity Weighted TRS with Types.
19.23/5.73	The TRS R consists of the following rules:
19.23/5.73	
19.23/5.73	   map(Cons(x, xs)) -> Cons(f(x), map(xs)) [1]
19.23/5.73	   map(Nil) -> Nil [1]
19.23/5.73	   goal(xs) -> map(xs) [1]
19.23/5.73	   f(x) -> times(x, x) [1]
19.23/5.73	   +Full(S(x), y) -> +Full(x, S(y)) [1]
19.23/5.73	   +Full(0, y) -> y [1]
19.23/5.73	   times(x, S(S(y))) -> +(x, times(x, S(y))) [0]
19.23/5.73	   times(x, S(0)) -> x [0]
19.23/5.73	   times(x, 0) -> 0 [0]
19.23/5.73	   times(0, y) -> 0 [0]
19.23/5.73	
19.23/5.73	The TRS has the following type information:
19.23/5.73	map :: Cons:Nil -> Cons:Nil
19.23/5.73	Cons :: S:0:+ -> Cons:Nil -> Cons:Nil
19.23/5.73	f :: S:0:+ -> S:0:+
19.23/5.73	Nil :: Cons:Nil
19.23/5.73	goal :: Cons:Nil -> Cons:Nil
19.23/5.73	times :: S:0:+ -> S:0:+ -> S:0:+
19.23/5.73	+Full :: S:0:+ -> S:0:+ -> S:0:+
19.23/5.73	S :: S:0:+ -> S:0:+
19.23/5.73	0 :: S:0:+
19.23/5.73	+ :: S:0:+ -> S:0:+ -> S:0:+
19.23/5.73	
19.23/5.73	Rewrite Strategy: INNERMOST
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(9) CompletionProof (UPPER BOUND(ID))
19.23/5.73	The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added:
19.23/5.73	
19.23/5.73	   times(v0, v1) -> null_times [0]
19.23/5.73	   +Full(v0, v1) -> null_+Full [0]
19.23/5.73	
19.23/5.73	And the following fresh constants:    null_times, null_+Full
19.23/5.73	
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(10)
19.23/5.73	Obligation:
19.23/5.73	Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is:
19.23/5.73	
19.23/5.73	Runtime Complexity Weighted TRS with Types.
19.23/5.73	The TRS R consists of the following rules:
19.23/5.73	
19.23/5.73	   map(Cons(x, xs)) -> Cons(f(x), map(xs)) [1]
19.23/5.73	   map(Nil) -> Nil [1]
19.23/5.73	   goal(xs) -> map(xs) [1]
19.23/5.73	   f(x) -> times(x, x) [1]
19.23/5.73	   +Full(S(x), y) -> +Full(x, S(y)) [1]
19.23/5.73	   +Full(0, y) -> y [1]
19.23/5.73	   times(x, S(S(y))) -> +(x, times(x, S(y))) [0]
19.23/5.73	   times(x, S(0)) -> x [0]
19.23/5.73	   times(x, 0) -> 0 [0]
19.23/5.73	   times(0, y) -> 0 [0]
19.23/5.73	   times(v0, v1) -> null_times [0]
19.23/5.73	   +Full(v0, v1) -> null_+Full [0]
19.23/5.73	
19.23/5.73	The TRS has the following type information:
19.23/5.73	map :: Cons:Nil -> Cons:Nil
19.23/5.73	Cons :: S:0:+:null_times:null_+Full -> Cons:Nil -> Cons:Nil
19.23/5.73	f :: S:0:+:null_times:null_+Full -> S:0:+:null_times:null_+Full
19.23/5.73	Nil :: Cons:Nil
19.23/5.73	goal :: Cons:Nil -> Cons:Nil
19.23/5.73	times :: S:0:+:null_times:null_+Full -> S:0:+:null_times:null_+Full -> S:0:+:null_times:null_+Full
19.23/5.73	+Full :: S:0:+:null_times:null_+Full -> S:0:+:null_times:null_+Full -> S:0:+:null_times:null_+Full
19.23/5.73	S :: S:0:+:null_times:null_+Full -> S:0:+:null_times:null_+Full
19.23/5.73	0 :: S:0:+:null_times:null_+Full
19.23/5.73	+ :: S:0:+:null_times:null_+Full -> S:0:+:null_times:null_+Full -> S:0:+:null_times:null_+Full
19.23/5.73	null_times :: S:0:+:null_times:null_+Full
19.23/5.73	null_+Full :: S:0:+:null_times:null_+Full
19.23/5.73	
19.23/5.73	Rewrite Strategy: INNERMOST
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
19.23/5.73	Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
19.23/5.73	The constant constructors are abstracted as follows:
19.23/5.73	
19.23/5.73	   Nil => 0
19.23/5.73	   0 => 0
19.23/5.73	   null_times => 0
19.23/5.73	   null_+Full => 0
19.23/5.73	
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(12)
19.23/5.73	Obligation:
19.23/5.73	Complexity RNTS consisting of the following rules:
19.23/5.73	
19.23/5.73	   +Full(z, z') -{ 1 }-> y :|: y >= 0, z = 0, z' = y
19.23/5.73	   +Full(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
19.23/5.73	   +Full(z, z') -{ 1 }-> +Full(x, 1 + y) :|: x >= 0, y >= 0, z = 1 + x, z' = y
19.23/5.73	   f(z) -{ 1 }-> times(x, x) :|: x >= 0, z = x
19.23/5.73	   goal(z) -{ 1 }-> map(xs) :|: xs >= 0, z = xs
19.23/5.73	   map(z) -{ 1 }-> 0 :|: z = 0
19.23/5.73	   map(z) -{ 1 }-> 1 + f(x) + map(xs) :|: z = 1 + x + xs, xs >= 0, x >= 0
19.23/5.73	   times(z, z') -{ 0 }-> x :|: x >= 0, z' = 1 + 0, z = x
19.23/5.73	   times(z, z') -{ 0 }-> 0 :|: x >= 0, z = x, z' = 0
19.23/5.73	   times(z, z') -{ 0 }-> 0 :|: y >= 0, z = 0, z' = y
19.23/5.73	   times(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
19.23/5.73	   times(z, z') -{ 0 }-> 1 + x + times(x, 1 + y) :|: z' = 1 + (1 + y), x >= 0, y >= 0, z = x
19.23/5.73	
19.23/5.73	Only complete derivations are relevant for the runtime complexity.
19.23/5.73	
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(13) CompleteCoflocoProof (FINISHED)
19.23/5.73	Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo:
19.23/5.73	
19.23/5.73	eq(start(V, V5),0,[map(V, Out)],[V >= 0]).
19.23/5.73	eq(start(V, V5),0,[goal(V, Out)],[V >= 0]).
19.23/5.73	eq(start(V, V5),0,[f(V, Out)],[V >= 0]).
19.23/5.73	eq(start(V, V5),0,[fun(V, V5, Out)],[V >= 0,V5 >= 0]).
19.23/5.73	eq(start(V, V5),0,[times(V, V5, Out)],[V >= 0,V5 >= 0]).
19.23/5.73	eq(map(V, Out),1,[f(V2, Ret01),map(V1, Ret1)],[Out = 1 + Ret01 + Ret1,V = 1 + V1 + V2,V1 >= 0,V2 >= 0]).
19.23/5.73	eq(map(V, Out),1,[],[Out = 0,V = 0]).
19.23/5.73	eq(goal(V, Out),1,[map(V3, Ret)],[Out = Ret,V3 >= 0,V = V3]).
19.23/5.73	eq(f(V, Out),1,[times(V4, V4, Ret2)],[Out = Ret2,V4 >= 0,V = V4]).
19.23/5.73	eq(fun(V, V5, Out),1,[fun(V6, 1 + V7, Ret3)],[Out = Ret3,V6 >= 0,V7 >= 0,V = 1 + V6,V5 = V7]).
19.23/5.73	eq(fun(V, V5, Out),1,[],[Out = V8,V8 >= 0,V = 0,V5 = V8]).
19.23/5.73	eq(times(V, V5, Out),0,[times(V9, 1 + V10, Ret11)],[Out = 1 + Ret11 + V9,V5 = 2 + V10,V9 >= 0,V10 >= 0,V = V9]).
19.23/5.73	eq(times(V, V5, Out),0,[],[Out = V11,V11 >= 0,V5 = 1,V = V11]).
19.23/5.73	eq(times(V, V5, Out),0,[],[Out = 0,V12 >= 0,V = V12,V5 = 0]).
19.23/5.73	eq(times(V, V5, Out),0,[],[Out = 0,V13 >= 0,V = 0,V5 = V13]).
19.23/5.73	eq(times(V, V5, Out),0,[],[Out = 0,V15 >= 0,V14 >= 0,V = V15,V5 = V14]).
19.23/5.73	eq(fun(V, V5, Out),0,[],[Out = 0,V17 >= 0,V16 >= 0,V = V17,V5 = V16]).
19.23/5.73	input_output_vars(map(V,Out),[V],[Out]).
19.23/5.73	input_output_vars(goal(V,Out),[V],[Out]).
19.23/5.73	input_output_vars(f(V,Out),[V],[Out]).
19.23/5.73	input_output_vars(fun(V,V5,Out),[V,V5],[Out]).
19.23/5.73	input_output_vars(times(V,V5,Out),[V,V5],[Out]).
19.23/5.73	
19.23/5.73	
19.23/5.73	CoFloCo proof output:
19.23/5.73	Preprocessing Cost Relations
19.23/5.73	=====================================
19.23/5.73	
19.23/5.73	#### Computed strongly connected components 
19.23/5.73	0. recursive  : [times/3]
19.23/5.73	1. non_recursive  : [f/2]
19.23/5.73	2. recursive  : [fun/3]
19.23/5.73	3. recursive  : [map/2]
19.23/5.73	4. non_recursive  : [goal/2]
19.23/5.73	5. non_recursive  : [start/2]
19.23/5.73	
19.23/5.73	#### Obtained direct recursion through partial evaluation 
19.23/5.73	0. SCC is partially evaluated into times/3
19.23/5.73	1. SCC is completely evaluated into other SCCs
19.23/5.73	2. SCC is partially evaluated into fun/3
19.23/5.73	3. SCC is partially evaluated into map/2
19.23/5.73	4. SCC is completely evaluated into other SCCs
19.23/5.73	5. SCC is partially evaluated into start/2
19.23/5.73	
19.23/5.73	Control-Flow Refinement of Cost Relations
19.23/5.73	=====================================
19.23/5.73	
19.23/5.73	### Specialization of cost equations times/3 
19.23/5.73	* CE 9 is refined into CE [15] 
19.23/5.73	* CE 10 is refined into CE [16] 
19.23/5.73	* CE 11 is refined into CE [17] 
19.23/5.73	* CE 8 is refined into CE [18] 
19.23/5.73	
19.23/5.73	
19.23/5.73	### Cost equations --> "Loop" of times/3 
19.23/5.73	* CEs [18] --> Loop 10 
19.23/5.73	* CEs [15] --> Loop 11 
19.23/5.73	* CEs [16,17] --> Loop 12 
19.23/5.73	
19.23/5.73	### Ranking functions of CR times(V,V5,Out) 
19.23/5.73	* RF of phase [10]: [V5-1]
19.23/5.73	
19.23/5.73	#### Partial ranking functions of CR times(V,V5,Out) 
19.23/5.73	* Partial RF of phase [10]:
19.23/5.73	  - RF of loop [10:1]:
19.23/5.73	    V5-1
19.23/5.73	
19.23/5.73	
19.23/5.73	### Specialization of cost equations fun/3 
19.23/5.73	* CE 14 is refined into CE [19] 
19.23/5.73	* CE 13 is refined into CE [20] 
19.23/5.73	* CE 12 is refined into CE [21] 
19.23/5.73	
19.23/5.73	
19.23/5.73	### Cost equations --> "Loop" of fun/3 
19.23/5.73	* CEs [21] --> Loop 13 
19.23/5.73	* CEs [19] --> Loop 14 
19.23/5.73	* CEs [20] --> Loop 15 
19.23/5.73	
19.23/5.73	### Ranking functions of CR fun(V,V5,Out) 
19.23/5.73	* RF of phase [13]: [V]
19.23/5.73	
19.23/5.73	#### Partial ranking functions of CR fun(V,V5,Out) 
19.23/5.73	* Partial RF of phase [13]:
19.23/5.73	  - RF of loop [13:1]:
19.23/5.73	    V
19.23/5.73	
19.23/5.73	
19.23/5.73	### Specialization of cost equations map/2 
19.23/5.73	* CE 7 is refined into CE [22] 
19.23/5.73	* CE 6 is refined into CE [23,24,25] 
19.23/5.73	
19.23/5.73	
19.23/5.73	### Cost equations --> "Loop" of map/2 
19.23/5.73	* CEs [25] --> Loop 16 
19.23/5.73	* CEs [24] --> Loop 17 
19.23/5.73	* CEs [23] --> Loop 18 
19.23/5.73	* CEs [22] --> Loop 19 
19.23/5.73	
19.23/5.73	### Ranking functions of CR map(V,Out) 
19.23/5.73	* RF of phase [16,17,18]: [V]
19.23/5.73	
19.23/5.73	#### Partial ranking functions of CR map(V,Out) 
19.23/5.73	* Partial RF of phase [16,17,18]:
19.23/5.73	  - RF of loop [16:1]:
19.23/5.73	    V-2
19.23/5.73	  - RF of loop [17:1]:
19.23/5.73	    V
19.23/5.73	  - RF of loop [18:1]:
19.23/5.73	    V-1
19.23/5.73	
19.23/5.73	
19.23/5.73	### Specialization of cost equations start/2 
19.23/5.73	* CE 1 is refined into CE [26,27] 
19.23/5.73	* CE 2 is refined into CE [28,29] 
19.23/5.73	* CE 3 is refined into CE [30,31,32] 
19.23/5.73	* CE 4 is refined into CE [33,34,35] 
19.23/5.73	* CE 5 is refined into CE [36,37,38] 
19.23/5.73	
19.23/5.73	
19.23/5.73	### Cost equations --> "Loop" of start/2 
19.23/5.73	* CEs [36] --> Loop 20 
19.23/5.73	* CEs [30] --> Loop 21 
19.23/5.73	* CEs [26,27,28,29,31,32,33,34,35,37,38] --> Loop 22 
19.23/5.73	
19.23/5.73	### Ranking functions of CR start(V,V5) 
19.23/5.73	
19.23/5.73	#### Partial ranking functions of CR start(V,V5) 
19.23/5.73	
19.23/5.73	
19.23/5.73	Computing Bounds
19.23/5.73	=====================================
19.23/5.73	
19.23/5.73	#### Cost of chains of times(V,V5,Out):
19.23/5.73	* Chain [[10],12]: 0
19.23/5.73	  with precondition: [V>=0,V5>=2,Out>=V+1] 
19.23/5.73	
19.23/5.73	* Chain [[10],11]: 0
19.23/5.73	  with precondition: [V>=0,V5>=2,Out+1>=2*V+V5] 
19.23/5.73	
19.23/5.73	* Chain [12]: 0
19.23/5.73	  with precondition: [Out=0,V>=0,V5>=0] 
19.23/5.73	
19.23/5.73	* Chain [11]: 0
19.23/5.73	  with precondition: [V5=1,V=Out,V>=0] 
19.23/5.73	
19.23/5.73	
19.23/5.73	#### Cost of chains of fun(V,V5,Out):
19.23/5.73	* Chain [[13],15]: 1*it(13)+1
19.23/5.73	  Such that:it(13) =< -V5+Out
19.23/5.73	
19.23/5.73	  with precondition: [V+V5=Out,V>=1,V5>=0] 
19.23/5.73	
19.23/5.73	* Chain [[13],14]: 1*it(13)+0
19.23/5.73	  Such that:it(13) =< V
19.23/5.73	
19.23/5.73	  with precondition: [Out=0,V>=1,V5>=0] 
19.23/5.73	
19.23/5.73	* Chain [15]: 1
19.23/5.73	  with precondition: [V=0,V5=Out,V5>=0] 
19.23/5.73	
19.23/5.73	* Chain [14]: 0
19.23/5.73	  with precondition: [Out=0,V>=0,V5>=0] 
19.23/5.73	
19.23/5.73	
19.23/5.73	#### Cost of chains of map(V,Out):
19.23/5.73	* Chain [[16,17,18],19]: 6*it(16)+1
19.23/5.73	  Such that:aux(3) =< V
19.23/5.73	it(16) =< aux(3)
19.23/5.73	
19.23/5.73	  with precondition: [V>=1,Out>=1] 
19.23/5.73	
19.23/5.73	* Chain [19]: 1
19.23/5.73	  with precondition: [V=0,Out=0] 
19.23/5.73	
19.23/5.73	
19.23/5.73	#### Cost of chains of start(V,V5):
19.23/5.73	* Chain [22]: 14*s(3)+2
19.23/5.73	  Such that:aux(4) =< V
19.23/5.73	s(3) =< aux(4)
19.23/5.73	
19.23/5.73	  with precondition: [V>=0] 
19.23/5.73	
19.23/5.73	* Chain [21]: 1
19.23/5.73	  with precondition: [V=1] 
19.23/5.73	
19.23/5.73	* Chain [20]: 0
19.23/5.73	  with precondition: [V5=1,V>=0] 
19.23/5.73	
19.23/5.73	
19.23/5.73	Closed-form bounds of start(V,V5): 
19.23/5.73	-------------------------------------
19.23/5.73	* Chain [22] with precondition: [V>=0] 
19.23/5.73	    - Upper bound: 14*V+2 
19.23/5.73	    - Complexity: n 
19.23/5.73	* Chain [21] with precondition: [V=1] 
19.23/5.73	    - Upper bound: 1 
19.23/5.73	    - Complexity: constant 
19.23/5.73	* Chain [20] with precondition: [V5=1,V>=0] 
19.23/5.73	    - Upper bound: 0 
19.23/5.73	    - Complexity: constant 
19.23/5.73	
19.23/5.73	### Maximum cost of start(V,V5): 14*V+2 
19.23/5.73	Asymptotic class: n 
19.23/5.73	* Total analysis performed in 164 ms.
19.23/5.73	
19.23/5.73	
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(14)
19.23/5.73	BOUNDS(1, n^1)
19.23/5.73	
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(15) RenamingProof (BOTH BOUNDS(ID, ID))
19.23/5.73	Renamed function symbols to avoid clashes with predefined symbol.
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(16)
19.23/5.73	Obligation:
19.23/5.73	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).
19.23/5.73	
19.23/5.73	
19.23/5.73	The TRS R consists of the following rules:
19.23/5.73	
19.23/5.73	   map(Cons(x, xs)) -> Cons(f(x), map(xs))
19.23/5.73	   map(Nil) -> Nil
19.23/5.73	   goal(xs) -> map(xs)
19.23/5.73	   f(x) -> *'(x, x)
19.23/5.73	   +Full(S(x), y) -> +Full(x, S(y))
19.23/5.73	   +Full(0', y) -> y
19.23/5.73	
19.23/5.73	The (relative) TRS S consists of the following rules:
19.23/5.73	
19.23/5.73	   *'(x, S(S(y))) -> +'(x, *'(x, S(y)))
19.23/5.73	   *'(x, S(0')) -> x
19.23/5.73	   *'(x, 0') -> 0'
19.23/5.73	   *'(0', y) -> 0'
19.23/5.73	
19.23/5.73	Rewrite Strategy: INNERMOST
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(17) SlicingProof (LOWER BOUND(ID))
19.23/5.73	Sliced the following arguments:
19.23/5.73	+'/0
19.23/5.73	
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(18)
19.23/5.73	Obligation:
19.23/5.73	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).
19.23/5.73	
19.23/5.73	
19.23/5.73	The TRS R consists of the following rules:
19.23/5.73	
19.23/5.73	   map(Cons(x, xs)) -> Cons(f(x), map(xs))
19.23/5.73	   map(Nil) -> Nil
19.23/5.73	   goal(xs) -> map(xs)
19.23/5.73	   f(x) -> *'(x, x)
19.23/5.73	   +Full(S(x), y) -> +Full(x, S(y))
19.23/5.73	   +Full(0', y) -> y
19.23/5.73	
19.23/5.73	The (relative) TRS S consists of the following rules:
19.23/5.73	
19.23/5.73	   *'(x, S(S(y))) -> +'(*'(x, S(y)))
19.23/5.73	   *'(x, S(0')) -> x
19.23/5.73	   *'(x, 0') -> 0'
19.23/5.73	   *'(0', y) -> 0'
19.23/5.73	
19.23/5.73	Rewrite Strategy: INNERMOST
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(19) TypeInferenceProof (BOTH BOUNDS(ID, ID))
19.23/5.73	Infered types.
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(20)
19.23/5.73	Obligation:
19.23/5.73	Innermost TRS:
19.23/5.73	Rules:
19.23/5.73	map(Cons(x, xs)) -> Cons(f(x), map(xs))
19.23/5.73	map(Nil) -> Nil
19.23/5.73	goal(xs) -> map(xs)
19.23/5.73	f(x) -> *'(x, x)
19.23/5.73	+Full(S(x), y) -> +Full(x, S(y))
19.23/5.73	+Full(0', y) -> y
19.23/5.73	*'(x, S(S(y))) -> +'(*'(x, S(y)))
19.23/5.73	*'(x, S(0')) -> x
19.23/5.73	*'(x, 0') -> 0'
19.23/5.73	*'(0', y) -> 0'
19.23/5.73	
19.23/5.73	Types:
19.23/5.73	map :: Cons:Nil -> Cons:Nil
19.23/5.73	Cons :: S:0':+' -> Cons:Nil -> Cons:Nil
19.23/5.73	f :: S:0':+' -> S:0':+'
19.23/5.73	Nil :: Cons:Nil
19.23/5.73	goal :: Cons:Nil -> Cons:Nil
19.23/5.73	*' :: S:0':+' -> S:0':+' -> S:0':+'
19.23/5.73	+Full :: S:0':+' -> S:0':+' -> S:0':+'
19.23/5.73	S :: S:0':+' -> S:0':+'
19.23/5.73	0' :: S:0':+'
19.23/5.73	+' :: S:0':+' -> S:0':+'
19.23/5.73	hole_Cons:Nil1_0 :: Cons:Nil
19.23/5.73	hole_S:0':+'2_0 :: S:0':+'
19.23/5.73	gen_Cons:Nil3_0 :: Nat -> Cons:Nil
19.23/5.73	gen_S:0':+'4_0 :: Nat -> S:0':+'
19.23/5.73	
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(21) OrderProof (LOWER BOUND(ID))
19.23/5.73	Heuristically decided to analyse the following defined symbols:
19.23/5.73	map, *', +Full
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(22)
19.23/5.73	Obligation:
19.23/5.73	Innermost TRS:
19.23/5.73	Rules:
19.23/5.73	map(Cons(x, xs)) -> Cons(f(x), map(xs))
19.23/5.73	map(Nil) -> Nil
19.23/5.73	goal(xs) -> map(xs)
19.23/5.73	f(x) -> *'(x, x)
19.23/5.73	+Full(S(x), y) -> +Full(x, S(y))
19.23/5.73	+Full(0', y) -> y
19.23/5.73	*'(x, S(S(y))) -> +'(*'(x, S(y)))
19.23/5.73	*'(x, S(0')) -> x
19.23/5.73	*'(x, 0') -> 0'
19.23/5.73	*'(0', y) -> 0'
19.23/5.73	
19.23/5.73	Types:
19.23/5.73	map :: Cons:Nil -> Cons:Nil
19.23/5.73	Cons :: S:0':+' -> Cons:Nil -> Cons:Nil
19.23/5.73	f :: S:0':+' -> S:0':+'
19.23/5.73	Nil :: Cons:Nil
19.23/5.73	goal :: Cons:Nil -> Cons:Nil
19.23/5.73	*' :: S:0':+' -> S:0':+' -> S:0':+'
19.23/5.73	+Full :: S:0':+' -> S:0':+' -> S:0':+'
19.23/5.73	S :: S:0':+' -> S:0':+'
19.23/5.73	0' :: S:0':+'
19.23/5.73	+' :: S:0':+' -> S:0':+'
19.23/5.73	hole_Cons:Nil1_0 :: Cons:Nil
19.23/5.73	hole_S:0':+'2_0 :: S:0':+'
19.23/5.73	gen_Cons:Nil3_0 :: Nat -> Cons:Nil
19.23/5.73	gen_S:0':+'4_0 :: Nat -> S:0':+'
19.23/5.73	
19.23/5.73	
19.23/5.73	Generator Equations:
19.23/5.73	gen_Cons:Nil3_0(0) <=> Nil
19.23/5.73	gen_Cons:Nil3_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil3_0(x))
19.23/5.73	gen_S:0':+'4_0(0) <=> 0'
19.23/5.73	gen_S:0':+'4_0(+(x, 1)) <=> S(gen_S:0':+'4_0(x))
19.23/5.73	
19.23/5.73	
19.23/5.73	The following defined symbols remain to be analysed:
19.23/5.73	map, *', +Full
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(23) RewriteLemmaProof (LOWER BOUND(ID))
19.23/5.73	Proved the following rewrite lemma:
19.23/5.73	map(gen_Cons:Nil3_0(n6_0)) -> gen_Cons:Nil3_0(n6_0), rt in Omega(1 + n6_0)
19.23/5.73	
19.23/5.73	Induction Base:
19.23/5.73	map(gen_Cons:Nil3_0(0)) ->_R^Omega(1)
19.23/5.73	Nil
19.23/5.73	
19.23/5.73	Induction Step:
19.23/5.73	map(gen_Cons:Nil3_0(+(n6_0, 1))) ->_R^Omega(1)
19.23/5.73	Cons(f(0'), map(gen_Cons:Nil3_0(n6_0))) ->_R^Omega(1)
19.23/5.73	Cons(*'(0', 0'), map(gen_Cons:Nil3_0(n6_0))) ->_R^Omega(0)
19.23/5.73	Cons(0', map(gen_Cons:Nil3_0(n6_0))) ->_IH
19.23/5.73	Cons(0', gen_Cons:Nil3_0(c7_0))
19.23/5.73	
19.23/5.73	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(24)
19.23/5.73	Complex Obligation (BEST)
19.23/5.73	
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(25)
19.23/5.73	Obligation:
19.23/5.73	Proved the lower bound n^1 for the following obligation:
19.23/5.73	
19.23/5.73	Innermost TRS:
19.23/5.73	Rules:
19.23/5.73	map(Cons(x, xs)) -> Cons(f(x), map(xs))
19.23/5.73	map(Nil) -> Nil
19.23/5.73	goal(xs) -> map(xs)
19.23/5.73	f(x) -> *'(x, x)
19.23/5.73	+Full(S(x), y) -> +Full(x, S(y))
19.23/5.73	+Full(0', y) -> y
19.23/5.73	*'(x, S(S(y))) -> +'(*'(x, S(y)))
19.23/5.73	*'(x, S(0')) -> x
19.23/5.73	*'(x, 0') -> 0'
19.23/5.73	*'(0', y) -> 0'
19.23/5.73	
19.23/5.73	Types:
19.23/5.73	map :: Cons:Nil -> Cons:Nil
19.23/5.73	Cons :: S:0':+' -> Cons:Nil -> Cons:Nil
19.23/5.73	f :: S:0':+' -> S:0':+'
19.23/5.73	Nil :: Cons:Nil
19.23/5.73	goal :: Cons:Nil -> Cons:Nil
19.23/5.73	*' :: S:0':+' -> S:0':+' -> S:0':+'
19.23/5.73	+Full :: S:0':+' -> S:0':+' -> S:0':+'
19.23/5.73	S :: S:0':+' -> S:0':+'
19.23/5.73	0' :: S:0':+'
19.23/5.73	+' :: S:0':+' -> S:0':+'
19.23/5.73	hole_Cons:Nil1_0 :: Cons:Nil
19.23/5.73	hole_S:0':+'2_0 :: S:0':+'
19.23/5.73	gen_Cons:Nil3_0 :: Nat -> Cons:Nil
19.23/5.73	gen_S:0':+'4_0 :: Nat -> S:0':+'
19.23/5.73	
19.23/5.73	
19.23/5.73	Generator Equations:
19.23/5.73	gen_Cons:Nil3_0(0) <=> Nil
19.23/5.73	gen_Cons:Nil3_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil3_0(x))
19.23/5.73	gen_S:0':+'4_0(0) <=> 0'
19.23/5.73	gen_S:0':+'4_0(+(x, 1)) <=> S(gen_S:0':+'4_0(x))
19.23/5.73	
19.23/5.73	
19.23/5.73	The following defined symbols remain to be analysed:
19.23/5.73	map, *', +Full
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(26) LowerBoundPropagationProof (FINISHED)
19.23/5.73	Propagated lower bound.
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(27)
19.23/5.73	BOUNDS(n^1, INF)
19.23/5.73	
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(28)
19.23/5.73	Obligation:
19.23/5.73	Innermost TRS:
19.23/5.73	Rules:
19.23/5.73	map(Cons(x, xs)) -> Cons(f(x), map(xs))
19.23/5.73	map(Nil) -> Nil
19.23/5.73	goal(xs) -> map(xs)
19.23/5.73	f(x) -> *'(x, x)
19.23/5.73	+Full(S(x), y) -> +Full(x, S(y))
19.23/5.73	+Full(0', y) -> y
19.23/5.73	*'(x, S(S(y))) -> +'(*'(x, S(y)))
19.23/5.73	*'(x, S(0')) -> x
19.23/5.73	*'(x, 0') -> 0'
19.23/5.73	*'(0', y) -> 0'
19.23/5.73	
19.23/5.73	Types:
19.23/5.73	map :: Cons:Nil -> Cons:Nil
19.23/5.73	Cons :: S:0':+' -> Cons:Nil -> Cons:Nil
19.23/5.73	f :: S:0':+' -> S:0':+'
19.23/5.73	Nil :: Cons:Nil
19.23/5.73	goal :: Cons:Nil -> Cons:Nil
19.23/5.73	*' :: S:0':+' -> S:0':+' -> S:0':+'
19.23/5.73	+Full :: S:0':+' -> S:0':+' -> S:0':+'
19.23/5.73	S :: S:0':+' -> S:0':+'
19.23/5.73	0' :: S:0':+'
19.23/5.73	+' :: S:0':+' -> S:0':+'
19.23/5.73	hole_Cons:Nil1_0 :: Cons:Nil
19.23/5.73	hole_S:0':+'2_0 :: S:0':+'
19.23/5.73	gen_Cons:Nil3_0 :: Nat -> Cons:Nil
19.23/5.73	gen_S:0':+'4_0 :: Nat -> S:0':+'
19.23/5.73	
19.23/5.73	
19.23/5.73	Lemmas:
19.23/5.73	map(gen_Cons:Nil3_0(n6_0)) -> gen_Cons:Nil3_0(n6_0), rt in Omega(1 + n6_0)
19.23/5.73	
19.23/5.73	
19.23/5.73	Generator Equations:
19.23/5.73	gen_Cons:Nil3_0(0) <=> Nil
19.23/5.73	gen_Cons:Nil3_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil3_0(x))
19.23/5.73	gen_S:0':+'4_0(0) <=> 0'
19.23/5.73	gen_S:0':+'4_0(+(x, 1)) <=> S(gen_S:0':+'4_0(x))
19.23/5.73	
19.23/5.73	
19.23/5.73	The following defined symbols remain to be analysed:
19.23/5.73	*', +Full
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(29) RewriteLemmaProof (LOWER BOUND(ID))
19.23/5.73	Proved the following rewrite lemma:
19.23/5.73	*'(gen_S:0':+'4_0(a), gen_S:0':+'4_0(+(2, n274_0))) -> *5_0, rt in Omega(0)
19.23/5.73	
19.23/5.73	Induction Base:
19.23/5.73	*'(gen_S:0':+'4_0(a), gen_S:0':+'4_0(+(2, 0)))
19.23/5.73	
19.23/5.73	Induction Step:
19.23/5.73	*'(gen_S:0':+'4_0(a), gen_S:0':+'4_0(+(2, +(n274_0, 1)))) ->_R^Omega(0)
19.23/5.73	+'(*'(gen_S:0':+'4_0(a), S(gen_S:0':+'4_0(+(1, n274_0))))) ->_IH
19.23/5.73	+'(*5_0)
19.23/5.73	
19.23/5.73	We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0).
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(30)
19.23/5.73	Obligation:
19.23/5.73	Innermost TRS:
19.23/5.73	Rules:
19.23/5.73	map(Cons(x, xs)) -> Cons(f(x), map(xs))
19.23/5.73	map(Nil) -> Nil
19.23/5.73	goal(xs) -> map(xs)
19.23/5.73	f(x) -> *'(x, x)
19.23/5.73	+Full(S(x), y) -> +Full(x, S(y))
19.23/5.73	+Full(0', y) -> y
19.23/5.73	*'(x, S(S(y))) -> +'(*'(x, S(y)))
19.23/5.73	*'(x, S(0')) -> x
19.23/5.73	*'(x, 0') -> 0'
19.23/5.73	*'(0', y) -> 0'
19.23/5.73	
19.23/5.73	Types:
19.23/5.73	map :: Cons:Nil -> Cons:Nil
19.23/5.73	Cons :: S:0':+' -> Cons:Nil -> Cons:Nil
19.23/5.73	f :: S:0':+' -> S:0':+'
19.23/5.73	Nil :: Cons:Nil
19.23/5.73	goal :: Cons:Nil -> Cons:Nil
19.23/5.73	*' :: S:0':+' -> S:0':+' -> S:0':+'
19.23/5.73	+Full :: S:0':+' -> S:0':+' -> S:0':+'
19.23/5.73	S :: S:0':+' -> S:0':+'
19.23/5.73	0' :: S:0':+'
19.23/5.73	+' :: S:0':+' -> S:0':+'
19.23/5.73	hole_Cons:Nil1_0 :: Cons:Nil
19.23/5.73	hole_S:0':+'2_0 :: S:0':+'
19.23/5.73	gen_Cons:Nil3_0 :: Nat -> Cons:Nil
19.23/5.73	gen_S:0':+'4_0 :: Nat -> S:0':+'
19.23/5.73	
19.23/5.73	
19.23/5.73	Lemmas:
19.23/5.73	map(gen_Cons:Nil3_0(n6_0)) -> gen_Cons:Nil3_0(n6_0), rt in Omega(1 + n6_0)
19.23/5.73	*'(gen_S:0':+'4_0(a), gen_S:0':+'4_0(+(2, n274_0))) -> *5_0, rt in Omega(0)
19.23/5.73	
19.23/5.73	
19.23/5.73	Generator Equations:
19.23/5.73	gen_Cons:Nil3_0(0) <=> Nil
19.23/5.73	gen_Cons:Nil3_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil3_0(x))
19.23/5.73	gen_S:0':+'4_0(0) <=> 0'
19.23/5.73	gen_S:0':+'4_0(+(x, 1)) <=> S(gen_S:0':+'4_0(x))
19.23/5.73	
19.23/5.73	
19.23/5.73	The following defined symbols remain to be analysed:
19.23/5.73	+Full
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(31) RewriteLemmaProof (LOWER BOUND(ID))
19.23/5.73	Proved the following rewrite lemma:
19.23/5.73	+Full(gen_S:0':+'4_0(n26080_0), gen_S:0':+'4_0(b)) -> gen_S:0':+'4_0(+(n26080_0, b)), rt in Omega(1 + n26080_0)
19.23/5.73	
19.23/5.73	Induction Base:
19.23/5.73	+Full(gen_S:0':+'4_0(0), gen_S:0':+'4_0(b)) ->_R^Omega(1)
19.23/5.73	gen_S:0':+'4_0(b)
19.23/5.73	
19.23/5.73	Induction Step:
19.23/5.73	+Full(gen_S:0':+'4_0(+(n26080_0, 1)), gen_S:0':+'4_0(b)) ->_R^Omega(1)
19.23/5.73	+Full(gen_S:0':+'4_0(n26080_0), S(gen_S:0':+'4_0(b))) ->_IH
19.23/5.73	gen_S:0':+'4_0(+(+(b, 1), c26081_0))
19.23/5.73	
19.23/5.73	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
19.23/5.73	----------------------------------------
19.23/5.73	
19.23/5.73	(32)
19.23/5.73	BOUNDS(1, INF)
19.52/5.80	EOF