16.81/5.36	WORST_CASE(Omega(n^1), O(n^1))
16.81/5.38	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
16.81/5.38	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
16.81/5.38	
16.81/5.38	
16.81/5.38	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1).
16.81/5.38	
16.81/5.38	(0) CpxRelTRS
16.81/5.38	(1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 195 ms]
16.81/5.38	(2) CpxRelTRS
16.81/5.38	(3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
16.81/5.38	(4) CpxWeightedTrs
16.81/5.38	    (5) CpxWeightedTrsRenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
16.81/5.38	    (6) CpxWeightedTrs
16.81/5.38	    (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
16.81/5.38	    (8) CpxTypedWeightedTrs
16.81/5.38	    (9) CompletionProof [UPPER BOUND(ID), 0 ms]
16.81/5.38	    (10) CpxTypedWeightedCompleteTrs
16.81/5.38	    (11) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 6 ms]
16.81/5.38	    (12) CpxRNTS
16.81/5.38	    (13) CompleteCoflocoProof [FINISHED, 384 ms]
16.81/5.38	    (14) BOUNDS(1, n^1)
16.81/5.38	(15) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
16.81/5.38	(16) TRS for Loop Detection
16.81/5.38	    (17) DecreasingLoopProof [LOWER BOUND(ID), 38 ms]
16.81/5.38	    (18) BEST
16.81/5.38	        (19) proven lower bound
16.81/5.38	            (20) LowerBoundPropagationProof [FINISHED, 0 ms]
16.81/5.38	            (21) BOUNDS(n^1, INF)
16.81/5.38	        (22) TRS for Loop Detection
16.81/5.38	
16.81/5.38	
16.81/5.38	----------------------------------------
16.81/5.38	
16.81/5.38	(0)
16.81/5.38	Obligation:
16.81/5.38	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1).
16.81/5.38	
16.81/5.38	
16.81/5.38	The TRS R consists of the following rules:
16.81/5.38	
16.81/5.38	   merge(Cons(x, xs), Nil) -> Cons(x, xs)
16.81/5.38	   merge(Cons(x', xs'), Cons(x, xs)) -> merge[Ite](<=(x', x), Cons(x', xs'), Cons(x, xs))
16.81/5.38	   merge(Nil, ys) -> ys
16.81/5.38	   goal(xs, ys) -> merge(xs, ys)
16.81/5.38	
16.81/5.38	The (relative) TRS S consists of the following rules:
16.81/5.38	
16.81/5.38	   <=(S(x), S(y)) -> <=(x, y)
16.81/5.38	   <=(0, y) -> True
16.81/5.38	   <=(S(x), 0) -> False
16.81/5.38	   merge[Ite](False, xs', Cons(x, xs)) -> Cons(x, merge(xs', xs))
16.81/5.38	   merge[Ite](True, Cons(x, xs), ys) -> Cons(x, merge(xs, ys))
16.81/5.38	
16.81/5.38	Rewrite Strategy: INNERMOST
16.81/5.38	----------------------------------------
16.81/5.38	
16.81/5.38	(1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID))
16.81/5.38	proved termination of relative rules
16.81/5.38	----------------------------------------
16.81/5.38	
16.81/5.38	(2)
16.81/5.38	Obligation:
16.81/5.38	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1).
16.81/5.38	
16.81/5.38	
16.81/5.38	The TRS R consists of the following rules:
16.81/5.38	
16.81/5.38	   merge(Cons(x, xs), Nil) -> Cons(x, xs)
16.81/5.38	   merge(Cons(x', xs'), Cons(x, xs)) -> merge[Ite](<=(x', x), Cons(x', xs'), Cons(x, xs))
16.81/5.38	   merge(Nil, ys) -> ys
16.81/5.38	   goal(xs, ys) -> merge(xs, ys)
16.81/5.38	
16.81/5.38	The (relative) TRS S consists of the following rules:
16.81/5.38	
16.81/5.38	   <=(S(x), S(y)) -> <=(x, y)
16.81/5.38	   <=(0, y) -> True
16.81/5.38	   <=(S(x), 0) -> False
16.81/5.38	   merge[Ite](False, xs', Cons(x, xs)) -> Cons(x, merge(xs', xs))
16.81/5.38	   merge[Ite](True, Cons(x, xs), ys) -> Cons(x, merge(xs, ys))
16.81/5.38	
16.81/5.38	Rewrite Strategy: INNERMOST
16.81/5.38	----------------------------------------
16.81/5.38	
16.81/5.38	(3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
16.81/5.38	Transformed relative TRS to weighted TRS
16.81/5.38	----------------------------------------
16.81/5.38	
16.81/5.38	(4)
16.81/5.38	Obligation:
16.81/5.38	The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1).
16.81/5.38	
16.81/5.38	
16.81/5.38	The TRS R consists of the following rules:
16.81/5.38	
16.81/5.38	   merge(Cons(x, xs), Nil) -> Cons(x, xs) [1]
16.81/5.38	   merge(Cons(x', xs'), Cons(x, xs)) -> merge[Ite](<=(x', x), Cons(x', xs'), Cons(x, xs)) [1]
16.81/5.38	   merge(Nil, ys) -> ys [1]
16.81/5.38	   goal(xs, ys) -> merge(xs, ys) [1]
16.81/5.38	   <=(S(x), S(y)) -> <=(x, y) [0]
16.81/5.38	   <=(0, y) -> True [0]
16.81/5.38	   <=(S(x), 0) -> False [0]
16.81/5.38	   merge[Ite](False, xs', Cons(x, xs)) -> Cons(x, merge(xs', xs)) [0]
16.81/5.38	   merge[Ite](True, Cons(x, xs), ys) -> Cons(x, merge(xs, ys)) [0]
16.81/5.38	
16.81/5.38	Rewrite Strategy: INNERMOST
16.81/5.38	----------------------------------------
16.81/5.38	
16.81/5.38	(5) CpxWeightedTrsRenamingProof (BOTH BOUNDS(ID, ID))
16.81/5.38	Renamed defined symbols to avoid conflicts with arithmetic symbols:
16.81/5.38	
16.81/5.38	<= => lteq
16.81/5.38	
16.81/5.38	----------------------------------------
16.81/5.38	
16.81/5.38	(6)
16.81/5.38	Obligation:
16.81/5.38	The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1).
16.81/5.38	
16.81/5.38	
16.81/5.38	The TRS R consists of the following rules:
16.81/5.38	
16.81/5.38	   merge(Cons(x, xs), Nil) -> Cons(x, xs) [1]
16.81/5.38	   merge(Cons(x', xs'), Cons(x, xs)) -> merge[Ite](lteq(x', x), Cons(x', xs'), Cons(x, xs)) [1]
16.81/5.38	   merge(Nil, ys) -> ys [1]
16.81/5.38	   goal(xs, ys) -> merge(xs, ys) [1]
16.81/5.38	   lteq(S(x), S(y)) -> lteq(x, y) [0]
16.81/5.38	   lteq(0, y) -> True [0]
16.81/5.38	   lteq(S(x), 0) -> False [0]
16.81/5.38	   merge[Ite](False, xs', Cons(x, xs)) -> Cons(x, merge(xs', xs)) [0]
16.81/5.38	   merge[Ite](True, Cons(x, xs), ys) -> Cons(x, merge(xs, ys)) [0]
16.81/5.38	
16.81/5.38	Rewrite Strategy: INNERMOST
16.81/5.38	----------------------------------------
16.81/5.38	
16.81/5.38	(7) TypeInferenceProof (BOTH BOUNDS(ID, ID))
16.81/5.38	Infered types.
16.81/5.38	----------------------------------------
16.81/5.38	
16.81/5.38	(8)
16.81/5.38	Obligation:
16.81/5.38	Runtime Complexity Weighted TRS with Types.
16.81/5.38	The TRS R consists of the following rules:
16.81/5.38	
16.81/5.38	   merge(Cons(x, xs), Nil) -> Cons(x, xs) [1]
16.81/5.38	   merge(Cons(x', xs'), Cons(x, xs)) -> merge[Ite](lteq(x', x), Cons(x', xs'), Cons(x, xs)) [1]
16.81/5.38	   merge(Nil, ys) -> ys [1]
16.81/5.38	   goal(xs, ys) -> merge(xs, ys) [1]
16.81/5.38	   lteq(S(x), S(y)) -> lteq(x, y) [0]
16.81/5.38	   lteq(0, y) -> True [0]
16.81/5.38	   lteq(S(x), 0) -> False [0]
16.81/5.38	   merge[Ite](False, xs', Cons(x, xs)) -> Cons(x, merge(xs', xs)) [0]
16.81/5.38	   merge[Ite](True, Cons(x, xs), ys) -> Cons(x, merge(xs, ys)) [0]
16.81/5.38	
16.81/5.38	The TRS has the following type information:
16.81/5.38	merge :: Cons:Nil -> Cons:Nil -> Cons:Nil
16.81/5.38	Cons :: S:0 -> Cons:Nil -> Cons:Nil
16.81/5.38	Nil :: Cons:Nil
16.81/5.38	merge[Ite] :: True:False -> Cons:Nil -> Cons:Nil -> Cons:Nil
16.81/5.38	lteq :: S:0 -> S:0 -> True:False
16.81/5.38	goal :: Cons:Nil -> Cons:Nil -> Cons:Nil
16.81/5.38	S :: S:0 -> S:0
16.81/5.38	0 :: S:0
16.81/5.38	True :: True:False
16.81/5.38	False :: True:False
16.81/5.38	
16.81/5.38	Rewrite Strategy: INNERMOST
16.81/5.38	----------------------------------------
16.81/5.38	
16.81/5.38	(9) CompletionProof (UPPER BOUND(ID))
16.81/5.38	The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added:
16.81/5.38	
16.81/5.38	   lteq(v0, v1) -> null_lteq [0]
16.81/5.38	   merge[Ite](v0, v1, v2) -> null_merge[Ite] [0]
16.81/5.38	   merge(v0, v1) -> null_merge [0]
16.81/5.38	
16.81/5.38	And the following fresh constants:    null_lteq, null_merge[Ite], null_merge
16.81/5.38	
16.81/5.38	----------------------------------------
16.81/5.38	
16.81/5.38	(10)
16.81/5.38	Obligation:
16.81/5.38	Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is:
16.81/5.38	
16.81/5.38	Runtime Complexity Weighted TRS with Types.
16.81/5.38	The TRS R consists of the following rules:
16.81/5.38	
16.81/5.38	   merge(Cons(x, xs), Nil) -> Cons(x, xs) [1]
16.81/5.38	   merge(Cons(x', xs'), Cons(x, xs)) -> merge[Ite](lteq(x', x), Cons(x', xs'), Cons(x, xs)) [1]
16.81/5.38	   merge(Nil, ys) -> ys [1]
16.81/5.38	   goal(xs, ys) -> merge(xs, ys) [1]
16.81/5.38	   lteq(S(x), S(y)) -> lteq(x, y) [0]
16.81/5.38	   lteq(0, y) -> True [0]
16.81/5.38	   lteq(S(x), 0) -> False [0]
16.81/5.38	   merge[Ite](False, xs', Cons(x, xs)) -> Cons(x, merge(xs', xs)) [0]
16.81/5.38	   merge[Ite](True, Cons(x, xs), ys) -> Cons(x, merge(xs, ys)) [0]
16.81/5.38	   lteq(v0, v1) -> null_lteq [0]
16.81/5.38	   merge[Ite](v0, v1, v2) -> null_merge[Ite] [0]
16.81/5.38	   merge(v0, v1) -> null_merge [0]
16.81/5.38	
16.81/5.38	The TRS has the following type information:
16.81/5.38	merge :: Cons:Nil:null_merge[Ite]:null_merge -> Cons:Nil:null_merge[Ite]:null_merge -> Cons:Nil:null_merge[Ite]:null_merge
16.81/5.38	Cons :: S:0 -> Cons:Nil:null_merge[Ite]:null_merge -> Cons:Nil:null_merge[Ite]:null_merge
16.81/5.38	Nil :: Cons:Nil:null_merge[Ite]:null_merge
16.81/5.38	merge[Ite] :: True:False:null_lteq -> Cons:Nil:null_merge[Ite]:null_merge -> Cons:Nil:null_merge[Ite]:null_merge -> Cons:Nil:null_merge[Ite]:null_merge
16.81/5.38	lteq :: S:0 -> S:0 -> True:False:null_lteq
16.81/5.38	goal :: Cons:Nil:null_merge[Ite]:null_merge -> Cons:Nil:null_merge[Ite]:null_merge -> Cons:Nil:null_merge[Ite]:null_merge
16.81/5.38	S :: S:0 -> S:0
16.81/5.38	0 :: S:0
16.81/5.38	True :: True:False:null_lteq
16.81/5.38	False :: True:False:null_lteq
16.81/5.38	null_lteq :: True:False:null_lteq
16.81/5.38	null_merge[Ite] :: Cons:Nil:null_merge[Ite]:null_merge
16.81/5.38	null_merge :: Cons:Nil:null_merge[Ite]:null_merge
16.81/5.38	
16.81/5.38	Rewrite Strategy: INNERMOST
16.81/5.38	----------------------------------------
16.81/5.38	
16.81/5.38	(11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
16.81/5.38	Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
16.81/5.38	The constant constructors are abstracted as follows:
16.81/5.38	
16.81/5.38	   Nil => 0
16.81/5.38	   0 => 0
16.81/5.38	   True => 2
16.81/5.38	   False => 1
16.81/5.38	   null_lteq => 0
16.81/5.38	   null_merge[Ite] => 0
16.81/5.38	   null_merge => 0
16.81/5.38	
16.81/5.38	----------------------------------------
16.81/5.38	
16.81/5.38	(12)
16.81/5.38	Obligation:
16.81/5.38	Complexity RNTS consisting of the following rules:
16.81/5.38	
16.81/5.38	   goal(z, z') -{ 1 }-> merge(xs, ys) :|: xs >= 0, z = xs, z' = ys, ys >= 0
16.81/5.38	   lteq(z, z') -{ 0 }-> lteq(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x
16.81/5.38	   lteq(z, z') -{ 0 }-> 2 :|: y >= 0, z = 0, z' = y
16.81/5.38	   lteq(z, z') -{ 0 }-> 1 :|: x >= 0, z = 1 + x, z' = 0
16.81/5.38	   lteq(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
16.81/5.38	   merge(z, z') -{ 1 }-> ys :|: z' = ys, ys >= 0, z = 0
16.81/5.38	   merge(z, z') -{ 1 }-> merge[Ite](lteq(x', x), 1 + x' + xs', 1 + x + xs) :|: xs >= 0, z' = 1 + x + xs, x' >= 0, xs' >= 0, x >= 0, z = 1 + x' + xs'
16.81/5.38	   merge(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
16.81/5.38	   merge(z, z') -{ 1 }-> 1 + x + xs :|: z = 1 + x + xs, xs >= 0, x >= 0, z' = 0
16.81/5.38	   merge[Ite](z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0
16.81/5.38	   merge[Ite](z, z', z'') -{ 0 }-> 1 + x + merge(xs, ys) :|: z = 2, xs >= 0, z' = 1 + x + xs, ys >= 0, x >= 0, z'' = ys
16.81/5.38	   merge[Ite](z, z', z'') -{ 0 }-> 1 + x + merge(xs', xs) :|: xs >= 0, z = 1, xs' >= 0, x >= 0, z' = xs', z'' = 1 + x + xs
16.81/5.38	
16.81/5.38	Only complete derivations are relevant for the runtime complexity.
16.81/5.38	
16.81/5.38	----------------------------------------
16.81/5.38	
16.81/5.38	(13) CompleteCoflocoProof (FINISHED)
16.81/5.38	Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo:
16.81/5.38	
16.81/5.38	eq(start(V1, V, V16),0,[merge(V1, V, Out)],[V1 >= 0,V >= 0]).
16.81/5.38	eq(start(V1, V, V16),0,[goal(V1, V, Out)],[V1 >= 0,V >= 0]).
16.81/5.38	eq(start(V1, V, V16),0,[lteq(V1, V, Out)],[V1 >= 0,V >= 0]).
16.81/5.38	eq(start(V1, V, V16),0,[fun(V1, V, V16, Out)],[V1 >= 0,V >= 0,V16 >= 0]).
16.81/5.38	eq(merge(V1, V, Out),1,[],[Out = 1 + V2 + V3,V1 = 1 + V2 + V3,V2 >= 0,V3 >= 0,V = 0]).
16.81/5.38	eq(merge(V1, V, Out),1,[lteq(V7, V5, Ret0),fun(Ret0, 1 + V7 + V4, 1 + V5 + V6, Ret)],[Out = Ret,V6 >= 0,V = 1 + V5 + V6,V7 >= 0,V4 >= 0,V5 >= 0,V1 = 1 + V4 + V7]).
16.81/5.38	eq(merge(V1, V, Out),1,[],[Out = V8,V = V8,V8 >= 0,V1 = 0]).
16.81/5.38	eq(goal(V1, V, Out),1,[merge(V9, V10, Ret1)],[Out = Ret1,V9 >= 0,V1 = V9,V = V10,V10 >= 0]).
16.81/5.38	eq(lteq(V1, V, Out),0,[lteq(V11, V12, Ret2)],[Out = Ret2,V = 1 + V12,V11 >= 0,V12 >= 0,V1 = 1 + V11]).
16.81/5.38	eq(lteq(V1, V, Out),0,[],[Out = 2,V13 >= 0,V1 = 0,V = V13]).
16.81/5.38	eq(lteq(V1, V, Out),0,[],[Out = 1,V14 >= 0,V1 = 1 + V14,V = 0]).
16.81/5.38	eq(fun(V1, V, V16, Out),0,[merge(V17, V18, Ret11)],[Out = 1 + Ret11 + V15,V18 >= 0,V1 = 1,V17 >= 0,V15 >= 0,V = V17,V16 = 1 + V15 + V18]).
16.81/5.38	eq(fun(V1, V, V16, Out),0,[merge(V19, V21, Ret12)],[Out = 1 + Ret12 + V20,V1 = 2,V19 >= 0,V = 1 + V19 + V20,V21 >= 0,V20 >= 0,V16 = V21]).
16.81/5.38	eq(lteq(V1, V, Out),0,[],[Out = 0,V23 >= 0,V22 >= 0,V1 = V23,V = V22]).
16.81/5.38	eq(fun(V1, V, V16, Out),0,[],[Out = 0,V25 >= 0,V16 = V26,V24 >= 0,V1 = V25,V = V24,V26 >= 0]).
16.81/5.38	eq(merge(V1, V, Out),0,[],[Out = 0,V28 >= 0,V27 >= 0,V1 = V28,V = V27]).
16.81/5.38	input_output_vars(merge(V1,V,Out),[V1,V],[Out]).
16.81/5.38	input_output_vars(goal(V1,V,Out),[V1,V],[Out]).
16.81/5.38	input_output_vars(lteq(V1,V,Out),[V1,V],[Out]).
16.81/5.38	input_output_vars(fun(V1,V,V16,Out),[V1,V,V16],[Out]).
16.81/5.38	
16.81/5.38	
16.81/5.38	CoFloCo proof output:
16.81/5.38	Preprocessing Cost Relations
16.81/5.38	=====================================
16.81/5.38	
16.81/5.38	#### Computed strongly connected components 
16.81/5.38	0. recursive  : [lteq/3]
16.81/5.38	1. recursive  : [fun/4,merge/3]
16.81/5.38	2. non_recursive  : [goal/3]
16.81/5.38	3. non_recursive  : [start/3]
16.81/5.38	
16.81/5.38	#### Obtained direct recursion through partial evaluation 
16.81/5.38	0. SCC is partially evaluated into lteq/3
16.81/5.38	1. SCC is partially evaluated into merge/3
16.81/5.38	2. SCC is completely evaluated into other SCCs
16.81/5.38	3. SCC is partially evaluated into start/3
16.81/5.38	
16.81/5.38	Control-Flow Refinement of Cost Relations
16.81/5.38	=====================================
16.81/5.38	
16.81/5.38	### Specialization of cost equations lteq/3 
16.81/5.38	* CE 16 is refined into CE [17] 
16.81/5.38	* CE 15 is refined into CE [18] 
16.81/5.38	* CE 14 is refined into CE [19] 
16.81/5.38	* CE 13 is refined into CE [20] 
16.81/5.38	
16.81/5.38	
16.81/5.38	### Cost equations --> "Loop" of lteq/3 
16.81/5.38	* CEs [20] --> Loop 12 
16.81/5.38	* CEs [17] --> Loop 13 
16.81/5.38	* CEs [18] --> Loop 14 
16.81/5.38	* CEs [19] --> Loop 15 
16.81/5.38	
16.81/5.38	### Ranking functions of CR lteq(V1,V,Out) 
16.81/5.38	* RF of phase [12]: [V,V1]
16.81/5.38	
16.81/5.38	#### Partial ranking functions of CR lteq(V1,V,Out) 
16.81/5.38	* Partial RF of phase [12]:
16.81/5.38	  - RF of loop [12:1]:
16.81/5.38	    V
16.81/5.38	    V1
16.81/5.38	
16.81/5.38	
16.81/5.38	### Specialization of cost equations merge/3 
16.81/5.38	* CE 7 is refined into CE [21,22,23,24,25] 
16.81/5.38	* CE 12 is refined into CE [26] 
16.81/5.38	* CE 10 is refined into CE [27] 
16.81/5.38	* CE 11 is refined into CE [28] 
16.81/5.38	* CE 8 is refined into CE [29,30] 
16.81/5.38	* CE 9 is refined into CE [31,32] 
16.81/5.38	
16.81/5.38	
16.81/5.38	### Cost equations --> "Loop" of merge/3 
16.81/5.38	* CEs [29,30] --> Loop 16 
16.81/5.38	* CEs [31,32] --> Loop 17 
16.81/5.38	* CEs [21,22,23,24,25,26] --> Loop 18 
16.81/5.38	* CEs [27] --> Loop 19 
16.81/5.38	* CEs [28] --> Loop 20 
16.81/5.38	
16.81/5.38	### Ranking functions of CR merge(V1,V,Out) 
16.81/5.38	* RF of phase [16,17]: [V1+V-1,V1+2*V-2]
16.81/5.38	
16.81/5.38	#### Partial ranking functions of CR merge(V1,V,Out) 
16.81/5.38	* Partial RF of phase [16,17]:
16.81/5.38	  - RF of loop [16:1]:
16.81/5.38	    V1
16.81/5.38	  - RF of loop [17:1]:
16.81/5.38	    V
16.81/5.38	
16.81/5.38	
16.81/5.38	### Specialization of cost equations start/3 
16.81/5.38	* CE 2 is refined into CE [33,34,35,36,37] 
16.81/5.38	* CE 1 is refined into CE [38] 
16.81/5.38	* CE 3 is refined into CE [39,40,41,42,43] 
16.81/5.38	* CE 4 is refined into CE [44,45,46,47,48] 
16.81/5.38	* CE 5 is refined into CE [49,50,51,52,53] 
16.81/5.38	* CE 6 is refined into CE [54,55,56,57,58] 
16.81/5.38	
16.81/5.38	
16.81/5.38	### Cost equations --> "Loop" of start/3 
16.81/5.38	* CEs [45,50,55] --> Loop 21 
16.81/5.38	* CEs [33,34,35,36,37] --> Loop 22 
16.81/5.38	* CEs [39,40,41,42,43] --> Loop 23 
16.81/5.38	* CEs [38,44,46,47,48,49,51,52,53,54,56,57,58] --> Loop 24 
16.81/5.38	
16.81/5.38	### Ranking functions of CR start(V1,V,V16) 
16.81/5.38	
16.81/5.38	#### Partial ranking functions of CR start(V1,V,V16) 
16.81/5.38	
16.81/5.38	
16.81/5.38	Computing Bounds
16.81/5.38	=====================================
16.81/5.38	
16.81/5.38	#### Cost of chains of lteq(V1,V,Out):
16.81/5.38	* Chain [[12],15]: 0
16.81/5.38	  with precondition: [Out=2,V1>=1,V>=V1] 
16.81/5.38	
16.81/5.38	* Chain [[12],14]: 0
16.81/5.38	  with precondition: [Out=1,V>=1,V1>=V+1] 
16.81/5.38	
16.81/5.38	* Chain [[12],13]: 0
16.81/5.38	  with precondition: [Out=0,V1>=1,V>=1] 
16.81/5.38	
16.81/5.38	* Chain [15]: 0
16.81/5.38	  with precondition: [V1=0,Out=2,V>=0] 
16.81/5.38	
16.81/5.38	* Chain [14]: 0
16.81/5.38	  with precondition: [V=0,Out=1,V1>=1] 
16.81/5.38	
16.81/5.38	* Chain [13]: 0
16.81/5.38	  with precondition: [Out=0,V1>=0,V>=0] 
16.81/5.38	
16.81/5.38	
16.81/5.38	#### Cost of chains of merge(V1,V,Out):
16.81/5.38	* Chain [[16,17],20]: 1*it(16)+1*it(17)+1
16.81/5.38	  Such that:it(17) =< -V1+Out
16.81/5.38	it(16) =< V1
16.81/5.38	aux(5) =< -V1+2*Out
16.81/5.38	aux(6) =< Out
16.81/5.38	it(16) =< aux(6)
16.81/5.38	it(17) =< aux(6)
16.81/5.38	it(16) =< aux(5)
16.81/5.38	it(17) =< aux(5)
16.81/5.38	
16.81/5.38	  with precondition: [V+V1=Out,V1>=1,V>=1] 
16.81/5.38	
16.81/5.38	* Chain [[16,17],19]: 1*it(16)+1*it(17)+1
16.81/5.38	  Such that:it(17) =< -V1+Out
16.81/5.38	it(16) =< V1
16.81/5.38	aux(7) =< -V1+2*Out
16.81/5.38	aux(8) =< Out
16.81/5.38	it(16) =< aux(8)
16.81/5.38	it(17) =< aux(8)
16.81/5.38	it(16) =< aux(7)
16.81/5.38	it(17) =< aux(7)
16.81/5.38	
16.81/5.38	  with precondition: [V+V1=Out,V1>=2,V>=1] 
16.81/5.38	
16.81/5.38	* Chain [[16,17],18]: 2*it(16)+1
16.81/5.38	  Such that:aux(1) =< V1+V
16.81/5.38	aux(3) =< V1+2*V
16.81/5.38	aux(9) =< Out
16.81/5.38	aux(10) =< 2*Out
16.81/5.38	it(16) =< aux(9)
16.81/5.38	it(16) =< aux(10)
16.81/5.38	it(16) =< aux(1)
16.81/5.38	it(16) =< aux(3)
16.81/5.38	
16.81/5.38	  with precondition: [V1>=1,V>=1,Out>=1,V+V1>=Out+1] 
16.81/5.38	
16.81/5.38	* Chain [20]: 1
16.81/5.38	  with precondition: [V1=0,V=Out,V>=0] 
16.81/5.38	
16.81/5.38	* Chain [19]: 1
16.81/5.38	  with precondition: [V=0,V1=Out,V1>=1] 
16.81/5.38	
16.81/5.38	* Chain [18]: 1
16.81/5.38	  with precondition: [Out=0,V1>=0,V>=0] 
16.81/5.38	
16.81/5.38	
16.81/5.38	#### Cost of chains of start(V1,V,V16):
16.81/5.38	* Chain [24]: 4*s(13)+4*s(14)+4*s(19)+2
16.81/5.38	  Such that:aux(17) =< V1
16.81/5.38	aux(18) =< V1+V
16.81/5.38	aux(19) =< V1+2*V
16.81/5.38	aux(20) =< 2*V1+2*V
16.81/5.38	aux(21) =< V
16.81/5.38	s(13) =< aux(21)
16.81/5.38	s(14) =< aux(17)
16.81/5.38	s(14) =< aux(18)
16.81/5.38	s(13) =< aux(18)
16.81/5.38	s(14) =< aux(19)
16.81/5.38	s(13) =< aux(19)
16.81/5.38	s(19) =< aux(18)
16.81/5.38	s(19) =< aux(20)
16.81/5.38	s(19) =< aux(19)
16.81/5.38	
16.81/5.38	  with precondition: [V1>=0,V>=0] 
16.81/5.38	
16.81/5.38	* Chain [23]: 2*s(35)+2*s(36)+2*s(41)+1
16.81/5.38	  Such that:s(33) =< V
16.81/5.38	s(40) =< 2*V+2*V16
16.81/5.38	s(31) =< V16
16.81/5.38	aux(23) =< V+V16
16.81/5.38	aux(24) =< V+2*V16
16.81/5.38	s(35) =< s(31)
16.81/5.38	s(36) =< s(33)
16.81/5.38	s(36) =< aux(23)
16.81/5.38	s(35) =< aux(23)
16.81/5.38	s(36) =< aux(24)
16.81/5.38	s(35) =< aux(24)
16.81/5.38	s(41) =< aux(23)
16.81/5.38	s(41) =< s(40)
16.81/5.38	s(41) =< aux(24)
16.81/5.38	
16.81/5.38	  with precondition: [V1=1,V>=0,V16>=1] 
16.81/5.38	
16.81/5.38	* Chain [22]: 2*s(46)+2*s(47)+2*s(52)+1
16.81/5.38	  Such that:s(44) =< V
16.81/5.38	s(51) =< 2*V+2*V16
16.81/5.38	s(42) =< V16
16.81/5.38	aux(26) =< V+V16
16.81/5.38	aux(27) =< V+2*V16
16.81/5.38	s(46) =< s(42)
16.81/5.38	s(47) =< s(44)
16.81/5.38	s(47) =< aux(26)
16.81/5.38	s(46) =< aux(26)
16.81/5.38	s(47) =< aux(27)
16.81/5.38	s(46) =< aux(27)
16.81/5.38	s(52) =< aux(26)
16.81/5.38	s(52) =< s(51)
16.81/5.38	s(52) =< aux(27)
16.81/5.38	
16.81/5.38	  with precondition: [V1=2,V>=1,V16>=0] 
16.81/5.38	
16.81/5.38	* Chain [21]: 2
16.81/5.38	  with precondition: [V=0,V1>=1] 
16.81/5.38	
16.81/5.38	
16.81/5.38	Closed-form bounds of start(V1,V,V16): 
16.81/5.38	-------------------------------------
16.81/5.38	* Chain [24] with precondition: [V1>=0,V>=0] 
16.81/5.38	    - Upper bound: 8*V1+8*V+2 
16.81/5.38	    - Complexity: n 
16.81/5.38	* Chain [23] with precondition: [V1=1,V>=0,V16>=1] 
16.81/5.38	    - Upper bound: 4*V+4*V16+1 
16.81/5.38	    - Complexity: n 
16.81/5.38	* Chain [22] with precondition: [V1=2,V>=1,V16>=0] 
16.81/5.38	    - Upper bound: 4*V+4*V16+1 
16.81/5.38	    - Complexity: n 
16.81/5.38	* Chain [21] with precondition: [V=0,V1>=1] 
16.81/5.38	    - Upper bound: 2 
16.81/5.38	    - Complexity: constant 
16.81/5.38	
16.81/5.38	### Maximum cost of start(V1,V,V16): max([1,2*V+max([8*V1+6*V+1,nat(V+V16)*2+nat(V16)*2])])+1 
16.81/5.38	Asymptotic class: n 
16.81/5.38	* Total analysis performed in 317 ms.
16.81/5.38	
16.81/5.38	
16.81/5.38	----------------------------------------
16.81/5.38	
16.81/5.38	(14)
16.81/5.38	BOUNDS(1, n^1)
16.81/5.38	
16.81/5.38	----------------------------------------
16.81/5.38	
16.81/5.38	(15) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
16.81/5.38	Transformed a relative TRS into a decreasing-loop problem.
16.81/5.38	----------------------------------------
16.81/5.38	
16.81/5.38	(16)
16.81/5.38	Obligation:
16.81/5.38	Analyzing the following TRS for decreasing loops:
16.81/5.38	
16.81/5.38	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1).
16.81/5.38	
16.81/5.38	
16.81/5.38	The TRS R consists of the following rules:
16.81/5.38	
16.81/5.38	   merge(Cons(x, xs), Nil) -> Cons(x, xs)
16.81/5.38	   merge(Cons(x', xs'), Cons(x, xs)) -> merge[Ite](<=(x', x), Cons(x', xs'), Cons(x, xs))
16.81/5.38	   merge(Nil, ys) -> ys
16.81/5.38	   goal(xs, ys) -> merge(xs, ys)
16.81/5.38	
16.81/5.38	The (relative) TRS S consists of the following rules:
16.81/5.38	
16.81/5.38	   <=(S(x), S(y)) -> <=(x, y)
16.81/5.38	   <=(0, y) -> True
16.81/5.38	   <=(S(x), 0) -> False
16.81/5.38	   merge[Ite](False, xs', Cons(x, xs)) -> Cons(x, merge(xs', xs))
16.81/5.38	   merge[Ite](True, Cons(x, xs), ys) -> Cons(x, merge(xs, ys))
16.81/5.38	
16.81/5.38	Rewrite Strategy: INNERMOST
16.81/5.38	----------------------------------------
16.81/5.38	
16.81/5.38	(17) DecreasingLoopProof (LOWER BOUND(ID))
16.81/5.38	The following loop(s) give(s) rise to the lower bound Omega(n^1):
16.81/5.38	
16.81/5.38	The rewrite sequence
16.81/5.38	
16.81/5.38	merge(Cons(0, xs'), Cons(x, xs)) ->^+ Cons(0, merge(xs', Cons(x, xs)))
16.81/5.38	
16.81/5.38	gives rise to a decreasing loop by considering the right hand sides subterm at position [1].
16.81/5.38	
16.81/5.38	The pumping substitution is [xs' / Cons(0, xs')].
16.81/5.38	
16.81/5.38	The result substitution is [ ].
16.81/5.38	
16.81/5.38	
16.81/5.38	
16.81/5.38	
16.81/5.38	----------------------------------------
16.81/5.38	
16.81/5.38	(18)
16.81/5.38	Complex Obligation (BEST)
16.81/5.38	
16.81/5.38	----------------------------------------
16.81/5.38	
16.81/5.38	(19)
16.81/5.38	Obligation:
16.81/5.38	Proved the lower bound n^1 for the following obligation:
16.81/5.38	
16.81/5.38	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1).
16.81/5.38	
16.81/5.38	
16.81/5.38	The TRS R consists of the following rules:
16.81/5.38	
16.81/5.38	   merge(Cons(x, xs), Nil) -> Cons(x, xs)
16.81/5.38	   merge(Cons(x', xs'), Cons(x, xs)) -> merge[Ite](<=(x', x), Cons(x', xs'), Cons(x, xs))
16.81/5.38	   merge(Nil, ys) -> ys
16.81/5.38	   goal(xs, ys) -> merge(xs, ys)
16.81/5.38	
16.81/5.38	The (relative) TRS S consists of the following rules:
16.81/5.38	
16.81/5.38	   <=(S(x), S(y)) -> <=(x, y)
16.81/5.38	   <=(0, y) -> True
16.81/5.38	   <=(S(x), 0) -> False
16.81/5.38	   merge[Ite](False, xs', Cons(x, xs)) -> Cons(x, merge(xs', xs))
16.81/5.38	   merge[Ite](True, Cons(x, xs), ys) -> Cons(x, merge(xs, ys))
16.81/5.38	
16.81/5.38	Rewrite Strategy: INNERMOST
16.81/5.38	----------------------------------------
16.81/5.38	
16.81/5.38	(20) LowerBoundPropagationProof (FINISHED)
16.81/5.38	Propagated lower bound.
16.81/5.38	----------------------------------------
16.81/5.38	
16.81/5.38	(21)
16.81/5.38	BOUNDS(n^1, INF)
16.81/5.38	
16.81/5.38	----------------------------------------
16.81/5.38	
16.81/5.38	(22)
16.81/5.38	Obligation:
16.81/5.38	Analyzing the following TRS for decreasing loops:
16.81/5.38	
16.81/5.38	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1).
16.81/5.38	
16.81/5.38	
16.81/5.38	The TRS R consists of the following rules:
16.81/5.38	
16.81/5.38	   merge(Cons(x, xs), Nil) -> Cons(x, xs)
16.81/5.38	   merge(Cons(x', xs'), Cons(x, xs)) -> merge[Ite](<=(x', x), Cons(x', xs'), Cons(x, xs))
16.81/5.38	   merge(Nil, ys) -> ys
16.81/5.38	   goal(xs, ys) -> merge(xs, ys)
16.81/5.38	
16.81/5.38	The (relative) TRS S consists of the following rules:
16.81/5.38	
16.81/5.38	   <=(S(x), S(y)) -> <=(x, y)
16.81/5.38	   <=(0, y) -> True
16.81/5.38	   <=(S(x), 0) -> False
16.81/5.38	   merge[Ite](False, xs', Cons(x, xs)) -> Cons(x, merge(xs', xs))
16.81/5.38	   merge[Ite](True, Cons(x, xs), ys) -> Cons(x, merge(xs, ys))
16.81/5.38	
16.81/5.38	Rewrite Strategy: INNERMOST
17.23/5.43	EOF