245.92/63.50 WORST_CASE(Omega(n^1), O(n^1)) 245.92/63.51 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 245.92/63.51 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 245.92/63.51 245.92/63.51 245.92/63.51 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 245.92/63.51 245.92/63.51 (0) CpxTRS 245.92/63.51 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 245.92/63.51 (2) CpxWeightedTrs 245.92/63.51 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 2 ms] 245.92/63.51 (4) CpxTypedWeightedTrs 245.92/63.51 (5) CompletionProof [UPPER BOUND(ID), 0 ms] 245.92/63.51 (6) CpxTypedWeightedCompleteTrs 245.92/63.51 (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 2 ms] 245.92/63.51 (8) CpxRNTS 245.92/63.51 (9) CompleteCoflocoProof [FINISHED, 4097 ms] 245.92/63.51 (10) BOUNDS(1, n^1) 245.92/63.51 (11) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 245.92/63.51 (12) TRS for Loop Detection 245.92/63.51 (13) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 245.92/63.51 (14) BEST 245.92/63.51 (15) proven lower bound 245.92/63.51 (16) LowerBoundPropagationProof [FINISHED, 0 ms] 245.92/63.51 (17) BOUNDS(n^1, INF) 245.92/63.51 (18) TRS for Loop Detection 245.92/63.51 245.92/63.51 245.92/63.51 ---------------------------------------- 245.92/63.51 245.92/63.51 (0) 245.92/63.51 Obligation: 245.92/63.51 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 245.92/63.51 245.92/63.51 245.92/63.51 The TRS R consists of the following rules: 245.92/63.51 245.92/63.51 min(0, y) -> 0 245.92/63.51 min(s(x), 0) -> 0 245.92/63.51 min(s(x), s(y)) -> min(x, y) 245.92/63.51 len(nil) -> 0 245.92/63.51 len(cons(x, xs)) -> s(len(xs)) 245.92/63.51 sum(x, 0) -> x 245.92/63.51 sum(x, s(y)) -> s(sum(x, y)) 245.92/63.51 le(0, x) -> true 245.92/63.51 le(s(x), 0) -> false 245.92/63.51 le(s(x), s(y)) -> le(x, y) 245.92/63.51 take(0, cons(y, ys)) -> y 245.92/63.51 take(s(x), cons(y, ys)) -> take(x, ys) 245.92/63.51 addList(x, y) -> if(le(0, min(len(x), len(y))), 0, x, y, nil) 245.92/63.51 if(false, c, x, y, z) -> z 245.92/63.51 if(true, c, xs, ys, z) -> if(le(s(c), min(len(xs), len(ys))), s(c), xs, ys, cons(sum(take(c, xs), take(c, ys)), z)) 245.92/63.51 245.92/63.51 S is empty. 245.92/63.51 Rewrite Strategy: INNERMOST 245.92/63.51 ---------------------------------------- 245.92/63.51 245.92/63.51 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 245.92/63.51 Transformed relative TRS to weighted TRS 245.92/63.51 ---------------------------------------- 245.92/63.51 245.92/63.51 (2) 245.92/63.51 Obligation: 245.92/63.51 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). 245.92/63.51 245.92/63.51 245.92/63.51 The TRS R consists of the following rules: 245.92/63.51 245.92/63.51 min(0, y) -> 0 [1] 245.92/63.51 min(s(x), 0) -> 0 [1] 245.92/63.51 min(s(x), s(y)) -> min(x, y) [1] 245.92/63.51 len(nil) -> 0 [1] 245.92/63.51 len(cons(x, xs)) -> s(len(xs)) [1] 245.92/63.51 sum(x, 0) -> x [1] 245.92/63.51 sum(x, s(y)) -> s(sum(x, y)) [1] 245.92/63.51 le(0, x) -> true [1] 245.92/63.51 le(s(x), 0) -> false [1] 245.92/63.51 le(s(x), s(y)) -> le(x, y) [1] 245.92/63.51 take(0, cons(y, ys)) -> y [1] 245.92/63.51 take(s(x), cons(y, ys)) -> take(x, ys) [1] 245.92/63.51 addList(x, y) -> if(le(0, min(len(x), len(y))), 0, x, y, nil) [1] 245.92/63.51 if(false, c, x, y, z) -> z [1] 245.92/63.51 if(true, c, xs, ys, z) -> if(le(s(c), min(len(xs), len(ys))), s(c), xs, ys, cons(sum(take(c, xs), take(c, ys)), z)) [1] 245.92/63.51 245.92/63.51 Rewrite Strategy: INNERMOST 245.92/63.51 ---------------------------------------- 245.92/63.51 245.92/63.51 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 245.92/63.51 Infered types. 245.92/63.51 ---------------------------------------- 245.92/63.51 245.92/63.51 (4) 245.92/63.51 Obligation: 245.92/63.51 Runtime Complexity Weighted TRS with Types. 245.92/63.51 The TRS R consists of the following rules: 245.92/63.51 245.92/63.51 min(0, y) -> 0 [1] 245.92/63.51 min(s(x), 0) -> 0 [1] 245.92/63.51 min(s(x), s(y)) -> min(x, y) [1] 245.92/63.51 len(nil) -> 0 [1] 245.92/63.51 len(cons(x, xs)) -> s(len(xs)) [1] 245.92/63.51 sum(x, 0) -> x [1] 245.92/63.51 sum(x, s(y)) -> s(sum(x, y)) [1] 245.92/63.51 le(0, x) -> true [1] 245.92/63.51 le(s(x), 0) -> false [1] 245.92/63.51 le(s(x), s(y)) -> le(x, y) [1] 245.92/63.51 take(0, cons(y, ys)) -> y [1] 245.92/63.51 take(s(x), cons(y, ys)) -> take(x, ys) [1] 245.92/63.51 addList(x, y) -> if(le(0, min(len(x), len(y))), 0, x, y, nil) [1] 245.92/63.51 if(false, c, x, y, z) -> z [1] 245.92/63.51 if(true, c, xs, ys, z) -> if(le(s(c), min(len(xs), len(ys))), s(c), xs, ys, cons(sum(take(c, xs), take(c, ys)), z)) [1] 245.92/63.51 245.92/63.51 The TRS has the following type information: 245.92/63.51 min :: 0:s -> 0:s -> 0:s 245.92/63.51 0 :: 0:s 245.92/63.51 s :: 0:s -> 0:s 245.92/63.51 len :: nil:cons -> 0:s 245.92/63.51 nil :: nil:cons 245.92/63.51 cons :: 0:s -> nil:cons -> nil:cons 245.92/63.51 sum :: 0:s -> 0:s -> 0:s 245.92/63.51 le :: 0:s -> 0:s -> true:false 245.92/63.51 true :: true:false 245.92/63.51 false :: true:false 245.92/63.51 take :: 0:s -> nil:cons -> 0:s 245.92/63.51 addList :: nil:cons -> nil:cons -> nil:cons 245.92/63.51 if :: true:false -> 0:s -> nil:cons -> nil:cons -> nil:cons -> nil:cons 245.92/63.51 245.92/63.51 Rewrite Strategy: INNERMOST 245.92/63.51 ---------------------------------------- 245.92/63.51 245.92/63.51 (5) CompletionProof (UPPER BOUND(ID)) 245.92/63.51 The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: 245.92/63.51 245.92/63.51 take(v0, v1) -> null_take [0] 245.92/63.51 min(v0, v1) -> null_min [0] 245.92/63.51 sum(v0, v1) -> null_sum [0] 245.92/63.51 le(v0, v1) -> null_le [0] 245.92/63.51 if(v0, v1, v2, v3, v4) -> null_if [0] 245.92/63.51 len(v0) -> null_len [0] 245.92/63.51 245.92/63.51 And the following fresh constants: null_take, null_min, null_sum, null_le, null_if, null_len 245.92/63.51 245.92/63.51 ---------------------------------------- 245.92/63.51 245.92/63.51 (6) 245.92/63.51 Obligation: 245.92/63.51 Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: 245.92/63.51 245.92/63.51 Runtime Complexity Weighted TRS with Types. 245.92/63.51 The TRS R consists of the following rules: 245.92/63.51 245.92/63.51 min(0, y) -> 0 [1] 245.92/63.51 min(s(x), 0) -> 0 [1] 245.92/63.51 min(s(x), s(y)) -> min(x, y) [1] 245.92/63.51 len(nil) -> 0 [1] 245.92/63.51 len(cons(x, xs)) -> s(len(xs)) [1] 245.92/63.51 sum(x, 0) -> x [1] 245.92/63.51 sum(x, s(y)) -> s(sum(x, y)) [1] 245.92/63.51 le(0, x) -> true [1] 245.92/63.51 le(s(x), 0) -> false [1] 245.92/63.51 le(s(x), s(y)) -> le(x, y) [1] 245.92/63.51 take(0, cons(y, ys)) -> y [1] 245.92/63.51 take(s(x), cons(y, ys)) -> take(x, ys) [1] 245.92/63.51 addList(x, y) -> if(le(0, min(len(x), len(y))), 0, x, y, nil) [1] 245.92/63.51 if(false, c, x, y, z) -> z [1] 245.92/63.51 if(true, c, xs, ys, z) -> if(le(s(c), min(len(xs), len(ys))), s(c), xs, ys, cons(sum(take(c, xs), take(c, ys)), z)) [1] 245.92/63.51 take(v0, v1) -> null_take [0] 245.92/63.51 min(v0, v1) -> null_min [0] 245.92/63.51 sum(v0, v1) -> null_sum [0] 245.92/63.51 le(v0, v1) -> null_le [0] 245.92/63.51 if(v0, v1, v2, v3, v4) -> null_if [0] 245.92/63.51 len(v0) -> null_len [0] 245.92/63.51 245.92/63.51 The TRS has the following type information: 245.92/63.51 min :: 0:s:null_take:null_min:null_sum:null_len -> 0:s:null_take:null_min:null_sum:null_len -> 0:s:null_take:null_min:null_sum:null_len 245.92/63.51 0 :: 0:s:null_take:null_min:null_sum:null_len 245.92/63.51 s :: 0:s:null_take:null_min:null_sum:null_len -> 0:s:null_take:null_min:null_sum:null_len 245.92/63.51 len :: nil:cons:null_if -> 0:s:null_take:null_min:null_sum:null_len 245.92/63.51 nil :: nil:cons:null_if 245.92/63.51 cons :: 0:s:null_take:null_min:null_sum:null_len -> nil:cons:null_if -> nil:cons:null_if 245.92/63.51 sum :: 0:s:null_take:null_min:null_sum:null_len -> 0:s:null_take:null_min:null_sum:null_len -> 0:s:null_take:null_min:null_sum:null_len 245.92/63.51 le :: 0:s:null_take:null_min:null_sum:null_len -> 0:s:null_take:null_min:null_sum:null_len -> true:false:null_le 245.92/63.51 true :: true:false:null_le 245.92/63.51 false :: true:false:null_le 245.92/63.51 take :: 0:s:null_take:null_min:null_sum:null_len -> nil:cons:null_if -> 0:s:null_take:null_min:null_sum:null_len 245.92/63.51 addList :: nil:cons:null_if -> nil:cons:null_if -> nil:cons:null_if 245.92/63.51 if :: true:false:null_le -> 0:s:null_take:null_min:null_sum:null_len -> nil:cons:null_if -> nil:cons:null_if -> nil:cons:null_if -> nil:cons:null_if 245.92/63.51 null_take :: 0:s:null_take:null_min:null_sum:null_len 245.92/63.51 null_min :: 0:s:null_take:null_min:null_sum:null_len 245.92/63.51 null_sum :: 0:s:null_take:null_min:null_sum:null_len 245.92/63.51 null_le :: true:false:null_le 245.92/63.51 null_if :: nil:cons:null_if 245.92/63.51 null_len :: 0:s:null_take:null_min:null_sum:null_len 245.92/63.51 245.92/63.51 Rewrite Strategy: INNERMOST 245.92/63.51 ---------------------------------------- 245.92/63.51 245.92/63.51 (7) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 245.92/63.51 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 245.92/63.51 The constant constructors are abstracted as follows: 245.92/63.51 245.92/63.51 0 => 0 245.92/63.51 nil => 0 245.92/63.51 true => 2 245.92/63.51 false => 1 245.92/63.51 null_take => 0 245.92/63.51 null_min => 0 245.92/63.51 null_sum => 0 245.92/63.51 null_le => 0 245.92/63.51 null_if => 0 245.92/63.51 null_len => 0 245.92/63.51 245.92/63.51 ---------------------------------------- 245.92/63.51 245.92/63.51 (8) 245.92/63.51 Obligation: 245.92/63.51 Complexity RNTS consisting of the following rules: 245.92/63.51 245.92/63.51 addList(z', z'') -{ 1 }-> if(le(0, min(len(x), len(y))), 0, x, y, 0) :|: z' = x, z'' = y, x >= 0, y >= 0 245.92/63.51 if(z', z'', z1, z2, z3) -{ 1 }-> z :|: z2 = y, z >= 0, c >= 0, z3 = z, x >= 0, y >= 0, z' = 1, z'' = c, z1 = x 245.92/63.51 if(z', z'', z1, z2, z3) -{ 1 }-> if(le(1 + c, min(len(xs), len(ys))), 1 + c, xs, ys, 1 + sum(take(c, xs), take(c, ys)) + z) :|: z2 = ys, xs >= 0, z >= 0, z' = 2, c >= 0, ys >= 0, z3 = z, z'' = c, z1 = xs 245.92/63.51 if(z', z'', z1, z2, z3) -{ 0 }-> 0 :|: z2 = v3, v0 >= 0, v4 >= 0, z1 = v2, v1 >= 0, z'' = v1, z3 = v4, v2 >= 0, v3 >= 0, z' = v0 245.92/63.51 le(z', z'') -{ 1 }-> le(x, y) :|: z' = 1 + x, x >= 0, y >= 0, z'' = 1 + y 245.92/63.51 le(z', z'') -{ 1 }-> 2 :|: x >= 0, z'' = x, z' = 0 245.92/63.51 le(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 1 + x, x >= 0 245.92/63.51 le(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0 245.92/63.51 len(z') -{ 1 }-> 0 :|: z' = 0 245.92/63.51 len(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0 245.92/63.51 len(z') -{ 1 }-> 1 + len(xs) :|: xs >= 0, z' = 1 + x + xs, x >= 0 245.92/63.51 min(z', z'') -{ 1 }-> min(x, y) :|: z' = 1 + x, x >= 0, y >= 0, z'' = 1 + y 245.92/63.51 min(z', z'') -{ 1 }-> 0 :|: z'' = y, y >= 0, z' = 0 245.92/63.51 min(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = 1 + x, x >= 0 245.92/63.51 min(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0 245.92/63.51 sum(z', z'') -{ 1 }-> x :|: z'' = 0, z' = x, x >= 0 245.92/63.51 sum(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0 245.92/63.51 sum(z', z'') -{ 1 }-> 1 + sum(x, y) :|: z' = x, x >= 0, y >= 0, z'' = 1 + y 245.92/63.51 take(z', z'') -{ 1 }-> y :|: z'' = 1 + y + ys, ys >= 0, y >= 0, z' = 0 245.92/63.51 take(z', z'') -{ 1 }-> take(x, ys) :|: z' = 1 + x, z'' = 1 + y + ys, ys >= 0, x >= 0, y >= 0 245.92/63.51 take(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0 245.92/63.51 245.92/63.51 Only complete derivations are relevant for the runtime complexity. 245.92/63.51 245.92/63.51 ---------------------------------------- 245.92/63.51 245.92/63.51 (9) CompleteCoflocoProof (FINISHED) 245.92/63.51 Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: 245.92/63.51 245.92/63.51 eq(start(V, V1, V28, V26, V27),0,[min(V, V1, Out)],[V >= 0,V1 >= 0]). 245.92/63.51 eq(start(V, V1, V28, V26, V27),0,[len(V, Out)],[V >= 0]). 245.92/63.51 eq(start(V, V1, V28, V26, V27),0,[sum(V, V1, Out)],[V >= 0,V1 >= 0]). 245.92/63.51 eq(start(V, V1, V28, V26, V27),0,[le(V, V1, Out)],[V >= 0,V1 >= 0]). 245.92/63.51 eq(start(V, V1, V28, V26, V27),0,[take(V, V1, Out)],[V >= 0,V1 >= 0]). 245.92/63.51 eq(start(V, V1, V28, V26, V27),0,[addList(V, V1, Out)],[V >= 0,V1 >= 0]). 245.92/63.51 eq(start(V, V1, V28, V26, V27),0,[if(V, V1, V28, V26, V27, Out)],[V >= 0,V1 >= 0,V28 >= 0,V26 >= 0,V27 >= 0]). 245.92/63.51 eq(min(V, V1, Out),1,[],[Out = 0,V1 = V2,V2 >= 0,V = 0]). 245.92/63.51 eq(min(V, V1, Out),1,[],[Out = 0,V1 = 0,V = 1 + V3,V3 >= 0]). 245.92/63.51 eq(min(V, V1, Out),1,[min(V4, V5, Ret)],[Out = Ret,V = 1 + V4,V4 >= 0,V5 >= 0,V1 = 1 + V5]). 245.92/63.51 eq(len(V, Out),1,[],[Out = 0,V = 0]). 245.92/63.51 eq(len(V, Out),1,[len(V7, Ret1)],[Out = 1 + Ret1,V7 >= 0,V = 1 + V6 + V7,V6 >= 0]). 245.92/63.51 eq(sum(V, V1, Out),1,[],[Out = V8,V1 = 0,V = V8,V8 >= 0]). 245.92/63.51 eq(sum(V, V1, Out),1,[sum(V9, V10, Ret11)],[Out = 1 + Ret11,V = V9,V9 >= 0,V10 >= 0,V1 = 1 + V10]). 245.92/63.51 eq(le(V, V1, Out),1,[],[Out = 2,V11 >= 0,V1 = V11,V = 0]). 245.92/63.51 eq(le(V, V1, Out),1,[],[Out = 1,V1 = 0,V = 1 + V12,V12 >= 0]). 245.92/63.51 eq(le(V, V1, Out),1,[le(V14, V13, Ret2)],[Out = Ret2,V = 1 + V14,V14 >= 0,V13 >= 0,V1 = 1 + V13]). 245.92/63.51 eq(take(V, V1, Out),1,[],[Out = V15,V1 = 1 + V15 + V16,V16 >= 0,V15 >= 0,V = 0]). 245.92/63.51 eq(take(V, V1, Out),1,[take(V18, V19, Ret3)],[Out = Ret3,V = 1 + V18,V1 = 1 + V17 + V19,V19 >= 0,V18 >= 0,V17 >= 0]). 245.92/63.51 eq(addList(V, V1, Out),1,[len(V21, Ret010),len(V20, Ret011),min(Ret010, Ret011, Ret01),le(0, Ret01, Ret0),if(Ret0, 0, V21, V20, 0, Ret4)],[Out = Ret4,V = V21,V1 = V20,V21 >= 0,V20 >= 0]). 245.92/63.51 eq(if(V, V1, V28, V26, V27, Out),1,[],[Out = V22,V26 = V24,V22 >= 0,V23 >= 0,V27 = V22,V25 >= 0,V24 >= 0,V = 1,V1 = V23,V28 = V25]). 245.92/63.51 eq(if(V, V1, V28, V26, V27, Out),1,[len(V31, Ret0101),len(V32, Ret0111),min(Ret0101, Ret0111, Ret012),le(1 + V30, Ret012, Ret02),take(V30, V31, Ret4010),take(V30, V32, Ret4011),sum(Ret4010, Ret4011, Ret401),if(Ret02, 1 + V30, V31, V32, 1 + Ret401 + V29, Ret5)],[Out = Ret5,V26 = V32,V31 >= 0,V29 >= 0,V = 2,V30 >= 0,V32 >= 0,V27 = V29,V1 = V30,V28 = V31]). 245.92/63.51 eq(take(V, V1, Out),0,[],[Out = 0,V34 >= 0,V33 >= 0,V1 = V33,V = V34]). 245.92/63.51 eq(min(V, V1, Out),0,[],[Out = 0,V36 >= 0,V35 >= 0,V1 = V35,V = V36]). 245.92/63.51 eq(sum(V, V1, Out),0,[],[Out = 0,V38 >= 0,V37 >= 0,V1 = V37,V = V38]). 245.92/63.51 eq(le(V, V1, Out),0,[],[Out = 0,V39 >= 0,V40 >= 0,V1 = V40,V = V39]). 245.92/63.51 eq(if(V, V1, V28, V26, V27, Out),0,[],[Out = 0,V26 = V44,V42 >= 0,V43 >= 0,V28 = V45,V41 >= 0,V1 = V41,V27 = V43,V45 >= 0,V44 >= 0,V = V42]). 245.92/63.51 eq(len(V, Out),0,[],[Out = 0,V46 >= 0,V = V46]). 245.92/63.51 input_output_vars(min(V,V1,Out),[V,V1],[Out]). 245.92/63.51 input_output_vars(len(V,Out),[V],[Out]). 245.92/63.51 input_output_vars(sum(V,V1,Out),[V,V1],[Out]). 245.92/63.51 input_output_vars(le(V,V1,Out),[V,V1],[Out]). 245.92/63.51 input_output_vars(take(V,V1,Out),[V,V1],[Out]). 245.92/63.51 input_output_vars(addList(V,V1,Out),[V,V1],[Out]). 245.92/63.51 input_output_vars(if(V,V1,V28,V26,V27,Out),[V,V1,V28,V26,V27],[Out]). 245.92/63.51 245.92/63.51 245.92/63.51 CoFloCo proof output: 245.92/63.51 Preprocessing Cost Relations 245.92/63.51 ===================================== 245.92/63.51 245.92/63.51 #### Computed strongly connected components 245.92/63.51 0. recursive : [le/3] 245.92/63.51 1. recursive : [len/2] 245.92/63.51 2. recursive : [min/3] 245.92/63.51 3. recursive : [sum/3] 245.92/63.51 4. recursive : [take/3] 245.92/63.51 5. recursive : [if/6] 245.92/63.51 6. non_recursive : [addList/3] 245.92/63.51 7. non_recursive : [start/5] 245.92/63.51 245.92/63.51 #### Obtained direct recursion through partial evaluation 245.92/63.51 0. SCC is partially evaluated into le/3 245.92/63.51 1. SCC is partially evaluated into len/2 245.92/63.51 2. SCC is partially evaluated into min/3 245.92/63.51 3. SCC is partially evaluated into sum/3 245.92/63.51 4. SCC is partially evaluated into take/3 245.92/63.51 5. SCC is partially evaluated into if/6 245.92/63.51 6. SCC is partially evaluated into addList/3 245.92/63.51 7. SCC is partially evaluated into start/5 245.92/63.51 245.92/63.51 Control-Flow Refinement of Cost Relations 245.92/63.51 ===================================== 245.92/63.51 245.92/63.51 ### Specialization of cost equations le/3 245.92/63.51 * CE 21 is refined into CE [29] 245.92/63.51 * CE 19 is refined into CE [30] 245.92/63.51 * CE 18 is refined into CE [31] 245.92/63.51 * CE 20 is refined into CE [32] 245.92/63.51 245.92/63.51 245.92/63.51 ### Cost equations --> "Loop" of le/3 245.92/63.52 * CEs [32] --> Loop 21 245.92/63.52 * CEs [29] --> Loop 22 245.92/63.52 * CEs [30] --> Loop 23 245.92/63.52 * CEs [31] --> Loop 24 245.92/63.52 245.92/63.52 ### Ranking functions of CR le(V,V1,Out) 245.92/63.52 * RF of phase [21]: [V,V1] 245.92/63.52 245.92/63.52 #### Partial ranking functions of CR le(V,V1,Out) 245.92/63.52 * Partial RF of phase [21]: 245.92/63.52 - RF of loop [21:1]: 245.92/63.52 V 245.92/63.52 V1 245.92/63.52 245.92/63.52 245.92/63.52 ### Specialization of cost equations len/2 245.92/63.52 * CE 12 is refined into CE [33] 245.92/63.52 * CE 14 is refined into CE [34] 245.92/63.52 * CE 13 is refined into CE [35] 245.92/63.52 245.92/63.52 245.92/63.52 ### Cost equations --> "Loop" of len/2 245.92/63.52 * CEs [35] --> Loop 25 245.92/63.52 * CEs [33,34] --> Loop 26 245.92/63.52 245.92/63.52 ### Ranking functions of CR len(V,Out) 245.92/63.52 * RF of phase [25]: [V] 245.92/63.52 245.92/63.52 #### Partial ranking functions of CR len(V,Out) 245.92/63.52 * Partial RF of phase [25]: 245.92/63.52 - RF of loop [25:1]: 245.92/63.52 V 245.92/63.52 245.92/63.52 245.92/63.52 ### Specialization of cost equations min/3 245.92/63.52 * CE 9 is refined into CE [36] 245.92/63.52 * CE 8 is refined into CE [37] 245.92/63.52 * CE 11 is refined into CE [38] 245.92/63.52 * CE 10 is refined into CE [39] 245.92/63.52 245.92/63.52 245.92/63.52 ### Cost equations --> "Loop" of min/3 245.92/63.52 * CEs [39] --> Loop 27 245.92/63.52 * CEs [36] --> Loop 28 245.92/63.52 * CEs [37,38] --> Loop 29 245.92/63.52 245.92/63.52 ### Ranking functions of CR min(V,V1,Out) 245.92/63.52 * RF of phase [27]: [V,V1] 245.92/63.52 245.92/63.52 #### Partial ranking functions of CR min(V,V1,Out) 245.92/63.52 * Partial RF of phase [27]: 245.92/63.52 - RF of loop [27:1]: 245.92/63.52 V 245.92/63.52 V1 245.92/63.52 245.92/63.52 245.92/63.52 ### Specialization of cost equations sum/3 245.92/63.52 * CE 17 is refined into CE [40] 245.92/63.52 * CE 15 is refined into CE [41] 245.92/63.52 * CE 16 is refined into CE [42] 245.92/63.52 245.92/63.52 245.92/63.52 ### Cost equations --> "Loop" of sum/3 245.92/63.52 * CEs [42] --> Loop 30 245.92/63.52 * CEs [40] --> Loop 31 245.92/63.52 * CEs [41] --> Loop 32 245.92/63.52 245.92/63.52 ### Ranking functions of CR sum(V,V1,Out) 245.92/63.52 * RF of phase [30]: [V1] 245.92/63.52 245.92/63.52 #### Partial ranking functions of CR sum(V,V1,Out) 245.92/63.52 * Partial RF of phase [30]: 245.92/63.52 - RF of loop [30:1]: 245.92/63.52 V1 245.92/63.52 245.92/63.52 245.92/63.52 ### Specialization of cost equations take/3 245.92/63.52 * CE 24 is refined into CE [43] 245.92/63.52 * CE 22 is refined into CE [44] 245.92/63.52 * CE 23 is refined into CE [45] 245.92/63.52 245.92/63.52 245.92/63.52 ### Cost equations --> "Loop" of take/3 245.92/63.52 * CEs [45] --> Loop 33 245.92/63.52 * CEs [43] --> Loop 34 245.92/63.52 * CEs [44] --> Loop 35 245.92/63.52 245.92/63.52 ### Ranking functions of CR take(V,V1,Out) 245.92/63.52 * RF of phase [33]: [V,V1] 245.92/63.52 245.92/63.52 #### Partial ranking functions of CR take(V,V1,Out) 245.92/63.52 * Partial RF of phase [33]: 245.92/63.52 - RF of loop [33:1]: 245.92/63.52 V 245.92/63.52 V1 245.92/63.52 245.92/63.52 245.92/63.52 ### Specialization of cost equations if/6 245.92/63.52 * CE 28 is refined into CE [46] 245.92/63.52 * CE 26 is refined into CE [47] 245.92/63.52 * CE 27 is refined into CE [48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223] 245.92/63.52 245.92/63.52 245.92/63.52 ### Cost equations --> "Loop" of if/6 245.92/63.52 * CEs [68,112,156,200] --> Loop 36 245.92/63.52 * CEs [64,66,108,110,152,154,196,198] --> Loop 37 245.92/63.52 * CEs [62,63,69,106,107,113,150,151,157,194,195,201] --> Loop 38 245.92/63.52 * CEs [90,134,178,222] --> Loop 39 245.92/63.52 * CEs [86,88,130,132,174,176,218,220] --> Loop 40 245.92/63.52 * CEs [84,85,91,128,129,135,172,173,179,216,217,223] --> Loop 41 245.92/63.52 * CEs [50,94,138,182] --> Loop 42 245.92/63.52 * CEs [51,56,57,95,100,101,139,144,145,183,188,189] --> Loop 43 245.92/63.52 * CEs [48,52,53,92,96,136,140,141,180,184] --> Loop 44 245.92/63.52 * CEs [49,54,55,58,59,60,61,65,67,93,97,98,99,102,103,104,105,109,111,137,142,143,146,147,148,149,153,155,181,185,186,187,190,191,192,193,197,199] --> Loop 45 245.92/63.52 * CEs [72,116,160,204] --> Loop 46 245.92/63.52 * CEs [73,78,79,117,122,123,161,166,167,205,210,211] --> Loop 47 245.92/63.52 * CEs [70,74,75,114,118,158,162,163,202,206] --> Loop 48 245.92/63.52 * CEs [71,76,77,80,81,82,83,87,89,115,119,120,121,124,125,126,127,131,133,159,164,165,168,169,170,171,175,177,203,207,208,209,212,213,214,215,219,221] --> Loop 49 245.92/63.52 * CEs [46] --> Loop 50 245.92/63.52 * CEs [47] --> Loop 51 245.92/63.52 245.92/63.52 ### Ranking functions of CR if(V,V1,V28,V26,V27,Out) 245.92/63.52 245.92/63.52 #### Partial ranking functions of CR if(V,V1,V28,V26,V27,Out) 245.92/63.52 245.92/63.52 245.92/63.52 ### Specialization of cost equations addList/3 245.92/63.52 * CE 25 is refined into CE [224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251] 245.92/63.52 245.92/63.52 245.92/63.52 ### Cost equations --> "Loop" of addList/3 245.92/63.52 * CEs [228,235,242,249] --> Loop 52 245.92/63.52 * CEs [227,234,241,248] --> Loop 53 245.92/63.52 * CEs [226,233,240,247] --> Loop 54 245.92/63.52 * CEs [229,236,243,250] --> Loop 55 245.92/63.52 * CEs [224,225,230,231,232,237,238,239,244,245,246,251] --> Loop 56 245.92/63.52 245.92/63.52 ### Ranking functions of CR addList(V,V1,Out) 245.92/63.52 245.92/63.52 #### Partial ranking functions of CR addList(V,V1,Out) 245.92/63.52 245.92/63.52 245.92/63.52 ### Specialization of cost equations start/5 245.92/63.52 * CE 1 is refined into CE [252] 245.92/63.52 * CE 2 is refined into CE [253,254] 245.92/63.52 * CE 3 is refined into CE [255,256,257,258] 245.92/63.52 * CE 4 is refined into CE [259,260,261,262,263] 245.92/63.52 * CE 5 is refined into CE [264,265,266] 245.92/63.52 * CE 6 is refined into CE [267,268,269,270,271] 245.92/63.52 * CE 7 is refined into CE [272,273,274,275,276,277,278,279,280,281] 245.92/63.52 245.92/63.52 245.92/63.52 ### Cost equations --> "Loop" of start/5 245.92/63.52 * CEs [255,260,274,277] --> Loop 57 245.92/63.52 * CEs [275,276,278,279,280,281] --> Loop 58 245.92/63.52 * CEs [272] --> Loop 59 245.92/63.52 * CEs [252,253,254,256,257,258,259,261,262,263,264,265,266,267,268,269,270,271,273] --> Loop 60 245.92/63.52 245.92/63.52 ### Ranking functions of CR start(V,V1,V28,V26,V27) 245.92/63.52 245.92/63.52 #### Partial ranking functions of CR start(V,V1,V28,V26,V27) 245.92/63.52 245.92/63.52 245.92/63.52 Computing Bounds 245.92/63.52 ===================================== 245.92/63.52 245.92/63.52 #### Cost of chains of le(V,V1,Out): 245.92/63.52 * Chain [[21],24]: 1*it(21)+1 245.92/63.52 Such that:it(21) =< V 245.92/63.52 245.92/63.52 with precondition: [Out=2,V>=1,V1>=V] 245.92/63.52 245.92/63.52 * Chain [[21],23]: 1*it(21)+1 245.92/63.52 Such that:it(21) =< V1 245.92/63.52 245.92/63.52 with precondition: [Out=1,V1>=1,V>=V1+1] 245.92/63.52 245.92/63.52 * Chain [[21],22]: 1*it(21)+0 245.92/63.52 Such that:it(21) =< V1 245.92/63.52 245.92/63.52 with precondition: [Out=0,V>=1,V1>=1] 245.92/63.52 245.92/63.52 * Chain [24]: 1 245.92/63.52 with precondition: [V=0,Out=2,V1>=0] 245.92/63.52 245.92/63.52 * Chain [23]: 1 245.92/63.52 with precondition: [V1=0,Out=1,V>=1] 245.92/63.52 245.92/63.52 * Chain [22]: 0 245.92/63.52 with precondition: [Out=0,V>=0,V1>=0] 245.92/63.52 245.92/63.52 245.92/63.52 #### Cost of chains of len(V,Out): 245.92/63.52 * Chain [[25],26]: 1*it(25)+1 245.92/63.52 Such that:it(25) =< V 245.92/63.52 245.92/63.52 with precondition: [Out>=1,V>=Out] 245.92/63.52 245.92/63.52 * Chain [26]: 1 245.92/63.52 with precondition: [Out=0,V>=0] 245.92/63.52 245.92/63.52 245.92/63.52 #### Cost of chains of min(V,V1,Out): 245.92/63.52 * Chain [[27],29]: 1*it(27)+1 245.92/63.52 Such that:it(27) =< V1 245.92/63.52 245.92/63.52 with precondition: [Out=0,V>=1,V1>=1] 245.92/63.52 245.92/63.52 * Chain [[27],28]: 1*it(27)+1 245.92/63.52 Such that:it(27) =< V1 245.92/63.52 245.92/63.52 with precondition: [Out=0,V1>=1,V>=V1+1] 245.92/63.52 245.92/63.52 * Chain [29]: 1 245.92/63.52 with precondition: [Out=0,V>=0,V1>=0] 245.92/63.52 245.92/63.52 * Chain [28]: 1 245.92/63.52 with precondition: [V1=0,Out=0,V>=1] 245.92/63.52 245.92/63.52 245.92/63.52 #### Cost of chains of sum(V,V1,Out): 245.92/63.52 * Chain [[30],32]: 1*it(30)+1 245.92/63.52 Such that:it(30) =< V1 245.92/63.52 245.92/63.52 with precondition: [V+V1=Out,V>=0,V1>=1] 245.92/63.52 245.92/63.52 * Chain [[30],31]: 1*it(30)+0 245.92/63.52 Such that:it(30) =< Out 245.92/63.52 245.92/63.52 with precondition: [V>=0,Out>=1,V1>=Out] 245.92/63.52 245.92/63.52 * Chain [32]: 1 245.92/63.52 with precondition: [V1=0,V=Out,V>=0] 245.92/63.52 245.92/63.52 * Chain [31]: 0 245.92/63.52 with precondition: [Out=0,V>=0,V1>=0] 245.92/63.52 245.92/63.52 245.92/63.52 #### Cost of chains of take(V,V1,Out): 245.92/63.52 * Chain [[33],35]: 1*it(33)+1 245.92/63.52 Such that:it(33) =< V 245.92/63.52 245.92/63.52 with precondition: [V>=1,Out>=0,V1>=Out+V+1] 245.92/63.52 245.92/63.52 * Chain [[33],34]: 1*it(33)+0 245.92/63.52 Such that:it(33) =< V1 245.92/63.52 245.92/63.52 with precondition: [Out=0,V>=1,V1>=1] 245.92/63.52 245.92/63.52 * Chain [35]: 1 245.92/63.52 with precondition: [V=0,Out>=0,V1>=Out+1] 245.92/63.52 245.92/63.52 * Chain [34]: 0 245.92/63.52 with precondition: [Out=0,V>=0,V1>=0] 245.92/63.52 245.92/63.52 245.92/63.52 #### Cost of chains of if(V,V1,V28,V26,V27,Out): 245.92/63.52 * Chain [51]: 1 245.92/63.52 with precondition: [V=1,V27=Out,V1>=0,V28>=0,V26>=0,V27>=0] 245.92/63.52 245.92/63.52 * Chain [50]: 0 245.92/63.52 with precondition: [Out=0,V>=0,V1>=0,V28>=0,V26>=0,V27>=0] 245.92/63.52 245.92/63.52 * Chain [49,50]: 43*s(11)+74*s(20)+17*s(30)+3*s(207)+6 245.92/63.52 Such that:aux(56) =< V1 245.92/63.52 aux(59) =< V1+1 245.92/63.52 aux(62) =< V28 245.92/63.52 aux(63) =< V26 245.92/63.52 s(207) =< aux(56) 245.92/63.52 s(11) =< aux(62) 245.92/63.52 s(20) =< aux(63) 245.92/63.52 s(30) =< aux(59) 245.92/63.52 245.92/63.52 with precondition: [V=2,Out=0,V1>=0,V28>=0,V26>=0,V27>=0] 245.92/63.52 245.92/63.52 * Chain [48,50]: 18*s(222)+5*s(236)+7 245.92/63.52 Such that:aux(74) =< V28 245.92/63.52 aux(76) =< V26 245.92/63.52 s(222) =< aux(76) 245.92/63.52 s(236) =< aux(74) 245.92/63.52 245.92/63.52 with precondition: [V=2,V1=0,Out=0,V28>=1,V26>=0,V27>=0] 245.92/63.52 245.92/63.52 * Chain [47,50]: 30*s(264)+14*s(268)+6 245.92/63.52 Such that:aux(98) =< V28 245.92/63.52 aux(99) =< V26 245.92/63.52 s(268) =< aux(98) 245.92/63.52 s(264) =< aux(99) 245.92/63.52 245.92/63.52 with precondition: [V=2,V1=0,Out=0,V28>=0,V26>=2,V27>=0] 245.92/63.52 245.92/63.52 * Chain [46,50]: 4*s(332)+6*s(333)+2*s(338)+7 245.92/63.52 Such that:aux(104) =< V28+V26 245.92/63.52 aux(105) =< V26 245.92/63.52 aux(106) =< V28 245.92/63.52 s(338) =< aux(106) 245.92/63.52 s(332) =< aux(104) 245.92/63.52 s(333) =< aux(105) 245.92/63.52 245.92/63.52 with precondition: [V=2,V1=0,Out=0,V28>=1,V26>=2,V27>=0] 245.92/63.52 245.92/63.52 * Chain [45,51]: 43*s(353)+74*s(360)+20*s(368)+8 245.92/63.52 Such that:aux(144) =< V1+1 245.92/63.52 aux(146) =< V26 245.92/63.52 aux(147) =< V28 245.92/63.52 s(368) =< aux(144) 245.92/63.52 s(353) =< aux(147) 245.92/63.52 s(360) =< aux(146) 245.92/63.52 245.92/63.52 with precondition: [V=2,Out=V27+1,V1>=0,V28>=0,V26>=0,Out>=1] 245.92/63.52 245.92/63.52 * Chain [45,50]: 43*s(353)+74*s(360)+20*s(368)+7 245.92/63.52 Such that:aux(144) =< V1+1 245.92/63.52 aux(146) =< V26 245.92/63.52 aux(148) =< V28 245.92/63.52 s(368) =< aux(144) 245.92/63.52 s(353) =< aux(148) 245.92/63.52 s(360) =< aux(146) 245.92/63.52 245.92/63.52 with precondition: [V=2,Out=0,V1>=0,V28>=0,V26>=0,V27>=0] 245.92/63.52 245.92/63.52 * Chain [44,51]: 18*s(526)+5*s(537)+9 245.92/63.52 Such that:aux(153) =< V28 245.92/63.52 aux(154) =< V26 245.92/63.52 s(537) =< aux(153) 245.92/63.52 s(526) =< aux(154) 245.92/63.52 245.92/63.52 with precondition: [V=2,V1=0,V26>=0,V27>=0,Out>=V27+1,V27+V28>=Out] 245.92/63.52 245.92/63.52 * Chain [44,50]: 18*s(526)+5*s(537)+8 245.92/63.52 Such that:aux(153) =< V28 245.92/63.52 aux(154) =< V26 245.92/63.52 s(537) =< aux(153) 245.92/63.52 s(526) =< aux(154) 245.92/63.52 245.92/63.52 with precondition: [V=2,V1=0,Out=0,V28>=1,V26>=0,V27>=0] 245.92/63.52 245.92/63.52 * Chain [43,51]: 12*s(559)+14*s(562)+18*s(568)+8 245.92/63.52 Such that:aux(168) =< V26 245.92/63.52 aux(166) =< -V27+Out 245.92/63.52 aux(169) =< V28 245.92/63.52 s(559) =< aux(166) 245.92/63.52 s(562) =< aux(169) 245.92/63.52 s(568) =< aux(168) 245.92/63.52 245.92/63.52 with precondition: [V=2,V1=0,V28>=0,V27>=0,Out>=V27+2,V26+V27>=Out] 245.92/63.52 245.92/63.52 * Chain [43,50]: 30*s(559)+14*s(562)+7 245.92/63.52 Such that:aux(170) =< V28 245.92/63.52 aux(171) =< V26 245.92/63.52 s(559) =< aux(171) 245.92/63.52 s(562) =< aux(170) 245.92/63.52 245.92/63.52 with precondition: [V=2,V1=0,Out=0,V28>=0,V26>=2,V27>=0] 245.92/63.52 245.92/63.52 * Chain [42,51]: 4*s(615)+6*s(616)+2*s(620)+9 245.92/63.52 Such that:aux(175) =< V28 245.92/63.52 aux(176) =< V26 245.92/63.52 aux(174) =< -V27+Out 245.92/63.52 s(615) =< aux(174) 245.92/63.52 s(620) =< aux(175) 245.92/63.52 s(616) =< aux(176) 245.92/63.52 245.92/63.52 with precondition: [V=2,V1=0,V28>=1,V26>=2,V27>=0,Out>=V27+2,V26+V27+V28>=Out+1] 245.92/63.52 245.92/63.52 * Chain [42,50]: 4*s(615)+6*s(616)+2*s(620)+8 245.92/63.52 Such that:aux(175) =< V28 245.92/63.52 aux(174) =< V28+V26 245.92/63.52 aux(176) =< V26 245.92/63.52 s(615) =< aux(174) 245.92/63.52 s(620) =< aux(175) 245.92/63.52 s(616) =< aux(176) 245.92/63.52 245.92/63.52 with precondition: [V=2,V1=0,Out=0,V28>=1,V26>=2,V27>=0] 245.92/63.52 245.92/63.52 * Chain [41,50]: 14*s(632)+6*s(633)+12*s(634)+10*s(644)+18*s(647)+6 245.92/63.52 Such that:aux(200) =< -V1+V26 245.92/63.52 aux(197) =< V1 245.92/63.52 aux(201) =< V1+1 245.92/63.52 aux(204) =< V28 245.92/63.52 aux(205) =< V26 245.92/63.52 s(644) =< aux(197) 245.92/63.52 s(632) =< aux(204) 245.92/63.52 s(634) =< aux(200) 245.92/63.52 s(633) =< aux(201) 245.92/63.52 s(647) =< aux(205) 245.92/63.52 245.92/63.52 with precondition: [V=2,Out=0,V1>=1,V28>=0,V27>=0,V26>=V1+2] 245.92/63.52 245.92/63.52 * Chain [40,50]: 4*s(716)+16*s(717)+8*s(733)+4*s(735)+7 245.92/63.52 Such that:aux(218) =< V1 245.92/63.52 aux(221) =< V1+1 245.92/63.52 aux(224) =< V28 245.92/63.52 aux(225) =< V26 245.92/63.52 s(733) =< aux(218) 245.92/63.52 s(735) =< aux(224) 245.92/63.52 s(716) =< aux(221) 245.92/63.52 s(717) =< aux(225) 245.92/63.52 245.92/63.52 with precondition: [V=2,Out=0,V1>=1,V26>=0,V27>=0,V28>=V1+1] 245.92/63.52 245.92/63.52 * Chain [39,50]: 4*s(764)+2*s(766)+6*s(767)+4*s(771)+2*s(773)+2*s(774)+7 245.92/63.52 Such that:aux(237) =< -2*V1+V28+V26 245.92/63.52 aux(234) =< -V1+V26 245.92/63.52 aux(235) =< V1 245.92/63.52 aux(238) =< V1+1 245.92/63.52 aux(236) =< V28 245.92/63.52 aux(239) =< V26 245.92/63.52 s(766) =< aux(234) 245.92/63.52 s(774) =< aux(236) 245.92/63.52 s(773) =< aux(237) 245.92/63.52 s(764) =< aux(235) 245.92/63.52 s(767) =< aux(239) 245.92/63.52 s(771) =< aux(238) 245.92/63.52 245.92/63.52 with precondition: [V=2,Out=0,V1>=1,V27>=0,V28>=V1+1,V26>=V1+2] 245.92/63.52 245.92/63.52 * Chain [38,51]: 14*s(791)+10*s(792)+12*s(793)+18*s(804)+6*s(808)+8 245.92/63.52 Such that:aux(254) =< V1 245.92/63.52 aux(258) =< V1+1 245.92/63.52 aux(257) =< -V27+Out 245.92/63.52 aux(261) =< V28 245.92/63.52 aux(262) =< V26 245.92/63.52 s(808) =< aux(254) 245.92/63.52 s(791) =< aux(261) 245.92/63.52 s(793) =< aux(257) 245.92/63.52 s(792) =< aux(258) 245.92/63.52 s(804) =< aux(262) 245.92/63.52 245.92/63.52 with precondition: [V=2,V1>=1,V28>=0,V27>=0,Out>=V27+2,V26+V27>=Out+V1] 245.92/63.52 245.92/63.52 * Chain [38,50]: 14*s(791)+10*s(792)+12*s(793)+18*s(804)+6*s(808)+7 245.92/63.52 Such that:aux(257) =< -V1+V26 245.92/63.52 aux(254) =< V1 245.92/63.52 aux(258) =< V1+1 245.92/63.52 aux(263) =< V28 245.92/63.52 aux(264) =< V26 245.92/63.52 s(808) =< aux(254) 245.92/63.52 s(791) =< aux(263) 245.92/63.52 s(793) =< aux(257) 245.92/63.52 s(792) =< aux(258) 245.92/63.52 s(804) =< aux(264) 245.92/63.52 245.92/63.52 with precondition: [V=2,Out=0,V1>=1,V28>=0,V27>=0,V26>=V1+2] 245.92/63.52 245.92/63.52 * Chain [37,51]: 9*s(863)+16*s(864)+4*s(879)+3*s(893)+9 245.92/63.52 Such that:aux(273) =< V1 245.92/63.52 aux(274) =< V1+1 245.92/63.52 aux(275) =< V28 245.92/63.52 aux(276) =< V26 245.92/63.52 s(893) =< aux(273) 245.92/63.52 s(863) =< aux(274) 245.92/63.52 s(879) =< aux(275) 245.92/63.52 s(864) =< aux(276) 245.92/63.52 245.92/63.52 with precondition: [V=2,V1>=1,V26>=0,V27>=0,Out>=V27+1,V27+V28>=Out+V1] 245.92/63.52 245.92/63.52 * Chain [37,50]: 9*s(863)+16*s(864)+4*s(879)+3*s(893)+8 245.92/63.52 Such that:aux(273) =< V1 245.92/63.52 aux(274) =< V1+1 245.92/63.52 aux(275) =< V28 245.92/63.52 aux(276) =< V26 245.92/63.52 s(893) =< aux(273) 245.92/63.52 s(863) =< aux(274) 245.92/63.52 s(879) =< aux(275) 245.92/63.52 s(864) =< aux(276) 245.92/63.52 245.92/63.52 with precondition: [V=2,Out=0,V1>=1,V26>=0,V27>=0,V28>=V1+1] 245.92/63.52 245.92/63.52 * Chain [36,51]: 4*s(903)+4*s(905)+6*s(906)+4*s(909)+2*s(912)+9 245.92/63.52 Such that:aux(283) =< V1 245.92/63.52 aux(286) =< V1+1 245.92/63.52 aux(284) =< V28 245.92/63.52 aux(285) =< -V27+Out 245.92/63.52 aux(287) =< V26 245.92/63.52 s(912) =< aux(284) 245.92/63.52 s(905) =< aux(285) 245.92/63.52 s(909) =< aux(283) 245.92/63.52 s(906) =< aux(287) 245.92/63.52 s(903) =< aux(286) 245.92/63.52 245.92/63.52 with precondition: [V=2,V1>=1,V27>=0,V28>=V1+1,V26>=V1+2,Out>=V27+2,V26+V27+V28>=2*V1+Out+1] 245.92/63.52 245.92/63.52 * Chain [36,50]: 4*s(903)+4*s(905)+6*s(906)+4*s(909)+2*s(912)+8 245.92/63.52 Such that:aux(285) =< -2*V1+V28+V26 245.92/63.52 aux(283) =< V1 245.92/63.52 aux(286) =< V1+1 245.92/63.52 aux(284) =< V28 245.92/63.52 aux(288) =< V26 245.92/63.52 s(912) =< aux(284) 245.92/63.52 s(905) =< aux(285) 245.92/63.52 s(909) =< aux(283) 245.92/63.52 s(906) =< aux(288) 245.92/63.52 s(903) =< aux(286) 245.92/63.52 245.92/63.52 with precondition: [V=2,Out=0,V1>=1,V27>=0,V28>=V1+1,V26>=V1+2] 245.92/63.52 245.92/63.52 245.92/63.52 #### Cost of chains of addList(V,V1,Out): 245.92/63.52 * Chain [56]: 1310*s(1034)+112*s(1035)+2770*s(1037)+592*s(1038)+13 245.92/63.52 Such that:aux(328) =< 1 245.92/63.52 aux(329) =< V 245.92/63.52 aux(330) =< V+V1 245.92/63.52 aux(331) =< V1 245.92/63.52 s(1034) =< aux(329) 245.92/63.52 s(1035) =< aux(330) 245.92/63.52 s(1037) =< aux(331) 245.92/63.52 s(1038) =< aux(328) 245.92/63.52 245.92/63.52 with precondition: [Out=0,V>=0,V1>=0] 245.92/63.52 245.92/63.52 * Chain [55]: 80*s(1198)+174*s(1199)+302*s(1200)+13 245.92/63.52 Such that:aux(336) =< 1 245.92/63.52 aux(337) =< V 245.92/63.52 aux(338) =< V1 245.92/63.52 s(1198) =< aux(336) 245.92/63.52 s(1199) =< aux(337) 245.92/63.52 s(1200) =< aux(338) 245.92/63.52 245.92/63.52 with precondition: [Out=1,V>=0,V1>=0] 245.92/63.52 245.92/63.52 * Chain [54]: 126*s(1234)+58*s(1235)+13 245.92/63.52 Such that:aux(345) =< V 245.92/63.52 aux(346) =< V1 245.92/63.52 s(1235) =< aux(345) 245.92/63.52 s(1234) =< aux(346) 245.92/63.52 245.92/63.52 with precondition: [V>=0,Out>=2,V1>=Out] 245.92/63.52 245.92/63.52 * Chain [53]: 16*s(1270)+10*s(1271)+30*s(1272)+14 245.92/63.52 Such that:aux(351) =< V 245.92/63.52 aux(352) =< V+V1 245.92/63.52 aux(353) =< V1 245.92/63.52 s(1270) =< aux(352) 245.92/63.52 s(1271) =< aux(351) 245.92/63.52 s(1272) =< aux(353) 245.92/63.52 245.92/63.52 with precondition: [V>=1,V1>=2,Out>=2,V+V1>=Out+1] 245.92/63.52 245.92/63.52 * Chain [52]: 22*s(1305)+78*s(1306)+14 245.92/63.52 Such that:aux(358) =< V 245.92/63.52 aux(359) =< V1 245.92/63.52 s(1305) =< aux(358) 245.92/63.52 s(1306) =< aux(359) 245.92/63.52 245.92/63.52 with precondition: [V1>=0,Out>=1,V>=Out] 245.92/63.52 245.92/63.52 245.92/63.52 #### Cost of chains of start(V,V1,V28,V26,V27): 245.92/63.52 * Chain [60]: 3351*s(1330)+1577*s(1331)+128*s(1344)+672*s(1346)+158*s(1374)+6*s(1375)+300*s(1377)+74*s(1378)+26*s(1379)+8*s(1380)+14 245.92/63.52 Such that:s(1367) =< -2*V1+V28+V26 245.92/63.52 s(1368) =< -V1+V26 245.92/63.52 s(1370) =< V1+1 245.92/63.52 s(1371) =< V28 245.92/63.52 s(1372) =< V28+V26 245.92/63.52 s(1373) =< V26 245.92/63.52 aux(360) =< 1 245.92/63.52 aux(361) =< V 245.92/63.52 aux(362) =< V+V1 245.92/63.52 aux(363) =< V1 245.92/63.52 s(1331) =< aux(361) 245.92/63.52 s(1330) =< aux(363) 245.92/63.52 s(1344) =< aux(362) 245.92/63.52 s(1346) =< aux(360) 245.92/63.52 s(1374) =< s(1371) 245.92/63.52 s(1375) =< s(1367) 245.92/63.52 s(1377) =< s(1373) 245.92/63.52 s(1378) =< s(1370) 245.92/63.52 s(1379) =< s(1368) 245.92/63.52 s(1380) =< s(1372) 245.92/63.52 245.92/63.52 with precondition: [V>=0] 245.92/63.52 245.92/63.52 * Chain [59]: 1 245.92/63.52 with precondition: [V=1,V1>=0,V28>=0,V26>=0,V27>=0] 245.92/63.52 245.92/63.52 * Chain [58]: 150*s(1384)+79*s(1385)+4*s(1390)+43*s(1396)+13*s(1404)+12*s(1406)+4*s(1423)+9 245.92/63.52 Such that:s(1420) =< -2*V1+V28+V26 245.92/63.52 s(1401) =< -V1+V26 245.92/63.52 s(1389) =< V28+V26 245.92/63.52 aux(365) =< V1 245.92/63.52 aux(366) =< V1+1 245.92/63.52 aux(367) =< V28 245.92/63.52 aux(368) =< V26 245.92/63.52 s(1385) =< aux(367) 245.92/63.52 s(1423) =< s(1420) 245.92/63.52 s(1404) =< aux(365) 245.92/63.52 s(1384) =< aux(368) 245.92/63.52 s(1396) =< aux(366) 245.92/63.52 s(1406) =< s(1401) 245.92/63.52 s(1390) =< s(1389) 245.92/63.52 245.92/63.52 with precondition: [V=2,V1>=0,V28>=0,V26>=0,V27>=0] 245.92/63.52 245.92/63.52 * Chain [57]: 15*s(1429)+54*s(1430)+9 245.92/63.52 Such that:aux(369) =< V28 245.92/63.52 aux(370) =< V26 245.92/63.52 s(1429) =< aux(369) 245.92/63.52 s(1430) =< aux(370) 245.92/63.52 245.92/63.52 with precondition: [V1=0,V>=0] 245.92/63.52 245.92/63.52 245.92/63.52 Closed-form bounds of start(V,V1,V28,V26,V27): 245.92/63.52 ------------------------------------- 245.92/63.52 * Chain [60] with precondition: [V>=0] 245.92/63.52 - Upper bound: 1577*V+686+nat(V1)*3351+nat(V28)*158+nat(V26)*300+nat(V+V1)*128+nat(V1+1)*74+nat(V28+V26)*8+nat(-V1+V26)*26+nat(-2*V1+V28+V26)*6 245.92/63.52 - Complexity: n 245.92/63.52 * Chain [59] with precondition: [V=1,V1>=0,V28>=0,V26>=0,V27>=0] 245.92/63.52 - Upper bound: 1 245.92/63.52 - Complexity: constant 245.92/63.52 * Chain [58] with precondition: [V=2,V1>=0,V28>=0,V26>=0,V27>=0] 245.92/63.52 - Upper bound: 56*V1+83*V28+154*V26+52+nat(-V1+V26)*12+nat(-2*V1+V28+V26)*4 245.92/63.52 - Complexity: n 245.92/63.52 * Chain [57] with precondition: [V1=0,V>=0] 245.92/63.52 - Upper bound: nat(V28)*15+9+nat(V26)*54 245.92/63.52 - Complexity: n 245.92/63.52 245.92/63.52 ### Maximum cost of start(V,V1,V28,V26,V27): 1577*V+677+nat(V1)*3338+nat(V28)*79+nat(V26)*150+nat(V+V1)*128+nat(V1+1)*31+nat(V28+V26)*4+nat(-V1+V26)*14+nat(-2*V1+V28+V26)*2+(nat(V28)*64+nat(V1)*13+nat(V26)*96+nat(V1+1)*43+nat(V28+V26)*4+nat(-V1+V26)*12+nat(-2*V1+V28+V26)*4)+(nat(V28)*15+8+nat(V26)*54)+1 245.92/63.52 Asymptotic class: n 245.92/63.52 * Total analysis performed in 3828 ms. 245.92/63.52 245.92/63.52 245.92/63.52 ---------------------------------------- 245.92/63.52 245.92/63.52 (10) 245.92/63.52 BOUNDS(1, n^1) 245.92/63.52 245.92/63.52 ---------------------------------------- 245.92/63.52 245.92/63.52 (11) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 245.92/63.52 Transformed a relative TRS into a decreasing-loop problem. 245.92/63.52 ---------------------------------------- 245.92/63.52 245.92/63.52 (12) 245.92/63.52 Obligation: 245.92/63.52 Analyzing the following TRS for decreasing loops: 245.92/63.52 245.92/63.52 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 245.92/63.52 245.92/63.52 245.92/63.52 The TRS R consists of the following rules: 245.92/63.52 245.92/63.52 min(0, y) -> 0 245.92/63.52 min(s(x), 0) -> 0 245.92/63.52 min(s(x), s(y)) -> min(x, y) 245.92/63.52 len(nil) -> 0 245.92/63.52 len(cons(x, xs)) -> s(len(xs)) 245.92/63.52 sum(x, 0) -> x 245.92/63.52 sum(x, s(y)) -> s(sum(x, y)) 245.92/63.52 le(0, x) -> true 245.92/63.52 le(s(x), 0) -> false 245.92/63.52 le(s(x), s(y)) -> le(x, y) 245.92/63.52 take(0, cons(y, ys)) -> y 245.92/63.52 take(s(x), cons(y, ys)) -> take(x, ys) 245.92/63.52 addList(x, y) -> if(le(0, min(len(x), len(y))), 0, x, y, nil) 245.92/63.52 if(false, c, x, y, z) -> z 245.92/63.52 if(true, c, xs, ys, z) -> if(le(s(c), min(len(xs), len(ys))), s(c), xs, ys, cons(sum(take(c, xs), take(c, ys)), z)) 245.92/63.52 245.92/63.52 S is empty. 245.92/63.52 Rewrite Strategy: INNERMOST 245.92/63.52 ---------------------------------------- 245.92/63.52 245.92/63.52 (13) DecreasingLoopProof (LOWER BOUND(ID)) 245.92/63.52 The following loop(s) give(s) rise to the lower bound Omega(n^1): 245.92/63.52 245.92/63.52 The rewrite sequence 245.92/63.52 245.92/63.52 min(s(x), s(y)) ->^+ min(x, y) 245.92/63.52 245.92/63.52 gives rise to a decreasing loop by considering the right hand sides subterm at position []. 245.92/63.52 245.92/63.52 The pumping substitution is [x / s(x), y / s(y)]. 245.92/63.52 245.92/63.52 The result substitution is [ ]. 245.92/63.52 245.92/63.52 245.92/63.52 245.92/63.52 245.92/63.52 ---------------------------------------- 245.92/63.52 245.92/63.52 (14) 245.92/63.52 Complex Obligation (BEST) 245.92/63.52 245.92/63.52 ---------------------------------------- 245.92/63.52 245.92/63.52 (15) 245.92/63.52 Obligation: 245.92/63.52 Proved the lower bound n^1 for the following obligation: 245.92/63.52 245.92/63.52 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 245.92/63.52 245.92/63.52 245.92/63.52 The TRS R consists of the following rules: 245.92/63.52 245.92/63.52 min(0, y) -> 0 245.92/63.52 min(s(x), 0) -> 0 245.92/63.52 min(s(x), s(y)) -> min(x, y) 245.92/63.52 len(nil) -> 0 245.92/63.52 len(cons(x, xs)) -> s(len(xs)) 245.92/63.52 sum(x, 0) -> x 245.92/63.52 sum(x, s(y)) -> s(sum(x, y)) 245.92/63.52 le(0, x) -> true 245.92/63.52 le(s(x), 0) -> false 245.92/63.52 le(s(x), s(y)) -> le(x, y) 245.92/63.52 take(0, cons(y, ys)) -> y 245.92/63.52 take(s(x), cons(y, ys)) -> take(x, ys) 245.92/63.52 addList(x, y) -> if(le(0, min(len(x), len(y))), 0, x, y, nil) 245.92/63.52 if(false, c, x, y, z) -> z 245.92/63.52 if(true, c, xs, ys, z) -> if(le(s(c), min(len(xs), len(ys))), s(c), xs, ys, cons(sum(take(c, xs), take(c, ys)), z)) 245.92/63.52 245.92/63.52 S is empty. 245.92/63.52 Rewrite Strategy: INNERMOST 245.92/63.52 ---------------------------------------- 245.92/63.52 245.92/63.52 (16) LowerBoundPropagationProof (FINISHED) 245.92/63.52 Propagated lower bound. 245.92/63.52 ---------------------------------------- 245.92/63.52 245.92/63.52 (17) 245.92/63.52 BOUNDS(n^1, INF) 245.92/63.52 245.92/63.52 ---------------------------------------- 245.92/63.52 245.92/63.52 (18) 245.92/63.52 Obligation: 245.92/63.52 Analyzing the following TRS for decreasing loops: 245.92/63.52 245.92/63.52 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 245.92/63.52 245.92/63.52 245.92/63.52 The TRS R consists of the following rules: 245.92/63.52 245.92/63.52 min(0, y) -> 0 245.92/63.52 min(s(x), 0) -> 0 245.92/63.52 min(s(x), s(y)) -> min(x, y) 245.92/63.52 len(nil) -> 0 245.92/63.52 len(cons(x, xs)) -> s(len(xs)) 245.92/63.52 sum(x, 0) -> x 245.92/63.52 sum(x, s(y)) -> s(sum(x, y)) 245.92/63.52 le(0, x) -> true 245.92/63.52 le(s(x), 0) -> false 245.92/63.52 le(s(x), s(y)) -> le(x, y) 245.92/63.52 take(0, cons(y, ys)) -> y 245.92/63.52 take(s(x), cons(y, ys)) -> take(x, ys) 245.92/63.52 addList(x, y) -> if(le(0, min(len(x), len(y))), 0, x, y, nil) 245.92/63.52 if(false, c, x, y, z) -> z 245.92/63.52 if(true, c, xs, ys, z) -> if(le(s(c), min(len(xs), len(ys))), s(c), xs, ys, cons(sum(take(c, xs), take(c, ys)), z)) 245.92/63.52 245.92/63.52 S is empty. 245.92/63.52 Rewrite Strategy: INNERMOST 246.26/63.58 EOF