1111.19/291.65 WORST_CASE(Omega(n^1), O(n^2)) 1111.29/291.68 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1111.29/291.68 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1111.29/291.68 1111.29/291.68 1111.29/291.68 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1111.29/291.68 1111.29/291.68 (0) CpxTRS 1111.29/291.68 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 1111.29/291.68 (2) CpxWeightedTrs 1111.29/291.68 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1111.29/291.68 (4) CpxTypedWeightedTrs 1111.29/291.68 (5) CompletionProof [UPPER BOUND(ID), 0 ms] 1111.29/291.68 (6) CpxTypedWeightedCompleteTrs 1111.29/291.68 (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 1111.29/291.68 (8) CpxRNTS 1111.29/291.68 (9) CompleteCoflocoProof [FINISHED, 1208 ms] 1111.29/291.68 (10) BOUNDS(1, n^2) 1111.29/291.68 (11) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1111.29/291.68 (12) CpxTRS 1111.29/291.68 (13) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1111.29/291.68 (14) typed CpxTrs 1111.29/291.68 (15) OrderProof [LOWER BOUND(ID), 0 ms] 1111.29/291.68 (16) typed CpxTrs 1111.29/291.68 (17) RewriteLemmaProof [LOWER BOUND(ID), 274 ms] 1111.29/291.68 (18) BEST 1111.29/291.68 (19) proven lower bound 1111.29/291.68 (20) LowerBoundPropagationProof [FINISHED, 0 ms] 1111.29/291.68 (21) BOUNDS(n^1, INF) 1111.29/291.68 (22) typed CpxTrs 1111.29/291.68 (23) RewriteLemmaProof [LOWER BOUND(ID), 10 ms] 1111.29/291.68 (24) typed CpxTrs 1111.29/291.68 (25) RewriteLemmaProof [LOWER BOUND(ID), 0 ms] 1111.29/291.68 (26) typed CpxTrs 1111.29/291.68 (27) RewriteLemmaProof [LOWER BOUND(ID), 0 ms] 1111.29/291.68 (28) typed CpxTrs 1111.29/291.68 1111.29/291.68 1111.29/291.68 ---------------------------------------- 1111.29/291.68 1111.29/291.68 (0) 1111.29/291.68 Obligation: 1111.29/291.68 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1111.29/291.68 1111.29/291.68 1111.29/291.68 The TRS R consists of the following rules: 1111.29/291.68 1111.29/291.68 app(x, y) -> helpa(0, plus(length(x), length(y)), x, y) 1111.29/291.68 plus(x, 0) -> x 1111.29/291.68 plus(x, s(y)) -> s(plus(x, y)) 1111.29/291.68 length(nil) -> 0 1111.29/291.68 length(cons(x, y)) -> s(length(y)) 1111.29/291.68 helpa(c, l, ys, zs) -> if(ge(c, l), c, l, ys, zs) 1111.29/291.68 ge(x, 0) -> true 1111.29/291.68 ge(0, s(x)) -> false 1111.29/291.68 ge(s(x), s(y)) -> ge(x, y) 1111.29/291.68 if(true, c, l, ys, zs) -> nil 1111.29/291.68 if(false, c, l, ys, zs) -> helpb(c, l, ys, zs) 1111.29/291.68 take(0, cons(x, xs), ys) -> x 1111.29/291.68 take(0, nil, cons(y, ys)) -> y 1111.29/291.68 take(s(c), cons(x, xs), ys) -> take(c, xs, ys) 1111.29/291.68 take(s(c), nil, cons(y, ys)) -> take(c, nil, ys) 1111.29/291.68 helpb(c, l, ys, zs) -> cons(take(c, ys, zs), helpa(s(c), l, ys, zs)) 1111.29/291.68 1111.29/291.68 S is empty. 1111.29/291.68 Rewrite Strategy: INNERMOST 1111.29/291.68 ---------------------------------------- 1111.29/291.68 1111.29/291.68 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 1111.29/291.68 Transformed relative TRS to weighted TRS 1111.29/291.68 ---------------------------------------- 1111.29/291.68 1111.29/291.68 (2) 1111.29/291.68 Obligation: 1111.29/291.68 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). 1111.29/291.68 1111.29/291.68 1111.29/291.68 The TRS R consists of the following rules: 1111.29/291.68 1111.29/291.68 app(x, y) -> helpa(0, plus(length(x), length(y)), x, y) [1] 1111.29/291.68 plus(x, 0) -> x [1] 1111.29/291.68 plus(x, s(y)) -> s(plus(x, y)) [1] 1111.29/291.68 length(nil) -> 0 [1] 1111.29/291.68 length(cons(x, y)) -> s(length(y)) [1] 1111.29/291.68 helpa(c, l, ys, zs) -> if(ge(c, l), c, l, ys, zs) [1] 1111.29/291.68 ge(x, 0) -> true [1] 1111.29/291.68 ge(0, s(x)) -> false [1] 1111.29/291.68 ge(s(x), s(y)) -> ge(x, y) [1] 1111.29/291.68 if(true, c, l, ys, zs) -> nil [1] 1111.29/291.68 if(false, c, l, ys, zs) -> helpb(c, l, ys, zs) [1] 1111.29/291.68 take(0, cons(x, xs), ys) -> x [1] 1111.29/291.68 take(0, nil, cons(y, ys)) -> y [1] 1111.29/291.68 take(s(c), cons(x, xs), ys) -> take(c, xs, ys) [1] 1111.29/291.68 take(s(c), nil, cons(y, ys)) -> take(c, nil, ys) [1] 1111.29/291.68 helpb(c, l, ys, zs) -> cons(take(c, ys, zs), helpa(s(c), l, ys, zs)) [1] 1111.29/291.68 1111.29/291.68 Rewrite Strategy: INNERMOST 1111.29/291.68 ---------------------------------------- 1111.29/291.68 1111.29/291.68 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1111.29/291.68 Infered types. 1111.29/291.68 ---------------------------------------- 1111.29/291.68 1111.29/291.68 (4) 1111.29/291.68 Obligation: 1111.29/291.68 Runtime Complexity Weighted TRS with Types. 1111.29/291.68 The TRS R consists of the following rules: 1111.29/291.68 1111.29/291.68 app(x, y) -> helpa(0, plus(length(x), length(y)), x, y) [1] 1111.29/291.68 plus(x, 0) -> x [1] 1111.29/291.68 plus(x, s(y)) -> s(plus(x, y)) [1] 1111.29/291.68 length(nil) -> 0 [1] 1111.29/291.68 length(cons(x, y)) -> s(length(y)) [1] 1111.29/291.68 helpa(c, l, ys, zs) -> if(ge(c, l), c, l, ys, zs) [1] 1111.29/291.68 ge(x, 0) -> true [1] 1111.29/291.68 ge(0, s(x)) -> false [1] 1111.29/291.68 ge(s(x), s(y)) -> ge(x, y) [1] 1111.29/291.68 if(true, c, l, ys, zs) -> nil [1] 1111.29/291.68 if(false, c, l, ys, zs) -> helpb(c, l, ys, zs) [1] 1111.29/291.68 take(0, cons(x, xs), ys) -> x [1] 1111.29/291.68 take(0, nil, cons(y, ys)) -> y [1] 1111.29/291.68 take(s(c), cons(x, xs), ys) -> take(c, xs, ys) [1] 1111.29/291.68 take(s(c), nil, cons(y, ys)) -> take(c, nil, ys) [1] 1111.29/291.68 helpb(c, l, ys, zs) -> cons(take(c, ys, zs), helpa(s(c), l, ys, zs)) [1] 1111.29/291.68 1111.29/291.68 The TRS has the following type information: 1111.29/291.68 app :: nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.68 helpa :: 0:s -> 0:s -> nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.68 0 :: 0:s 1111.29/291.68 plus :: 0:s -> 0:s -> 0:s 1111.29/291.68 length :: nil:cons:xs -> 0:s 1111.29/291.68 s :: 0:s -> 0:s 1111.29/291.68 nil :: nil:cons:xs 1111.29/291.68 cons :: take -> nil:cons:xs -> nil:cons:xs 1111.29/291.68 if :: true:false -> 0:s -> 0:s -> nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.68 ge :: 0:s -> 0:s -> true:false 1111.29/291.68 true :: true:false 1111.29/291.68 false :: true:false 1111.29/291.68 helpb :: 0:s -> 0:s -> nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.68 take :: 0:s -> nil:cons:xs -> nil:cons:xs -> take 1111.29/291.68 xs :: nil:cons:xs 1111.29/291.68 1111.29/291.68 Rewrite Strategy: INNERMOST 1111.29/291.68 ---------------------------------------- 1111.29/291.68 1111.29/291.68 (5) CompletionProof (UPPER BOUND(ID)) 1111.29/291.68 The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: 1111.29/291.68 1111.29/291.68 length(v0) -> null_length [0] 1111.29/291.68 take(v0, v1, v2) -> null_take [0] 1111.29/291.68 plus(v0, v1) -> null_plus [0] 1111.29/291.68 ge(v0, v1) -> null_ge [0] 1111.29/291.68 if(v0, v1, v2, v3, v4) -> null_if [0] 1111.29/291.68 1111.29/291.68 And the following fresh constants: null_length, null_take, null_plus, null_ge, null_if 1111.29/291.68 1111.29/291.68 ---------------------------------------- 1111.29/291.68 1111.29/291.68 (6) 1111.29/291.68 Obligation: 1111.29/291.68 Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: 1111.29/291.68 1111.29/291.68 Runtime Complexity Weighted TRS with Types. 1111.29/291.68 The TRS R consists of the following rules: 1111.29/291.68 1111.29/291.68 app(x, y) -> helpa(0, plus(length(x), length(y)), x, y) [1] 1111.29/291.68 plus(x, 0) -> x [1] 1111.29/291.68 plus(x, s(y)) -> s(plus(x, y)) [1] 1111.29/291.68 length(nil) -> 0 [1] 1111.29/291.68 length(cons(x, y)) -> s(length(y)) [1] 1111.29/291.68 helpa(c, l, ys, zs) -> if(ge(c, l), c, l, ys, zs) [1] 1111.29/291.68 ge(x, 0) -> true [1] 1111.29/291.68 ge(0, s(x)) -> false [1] 1111.29/291.68 ge(s(x), s(y)) -> ge(x, y) [1] 1111.29/291.68 if(true, c, l, ys, zs) -> nil [1] 1111.29/291.68 if(false, c, l, ys, zs) -> helpb(c, l, ys, zs) [1] 1111.29/291.68 take(0, cons(x, xs), ys) -> x [1] 1111.29/291.68 take(0, nil, cons(y, ys)) -> y [1] 1111.29/291.68 take(s(c), cons(x, xs), ys) -> take(c, xs, ys) [1] 1111.29/291.68 take(s(c), nil, cons(y, ys)) -> take(c, nil, ys) [1] 1111.29/291.68 helpb(c, l, ys, zs) -> cons(take(c, ys, zs), helpa(s(c), l, ys, zs)) [1] 1111.29/291.68 length(v0) -> null_length [0] 1111.29/291.68 take(v0, v1, v2) -> null_take [0] 1111.29/291.68 plus(v0, v1) -> null_plus [0] 1111.29/291.68 ge(v0, v1) -> null_ge [0] 1111.29/291.68 if(v0, v1, v2, v3, v4) -> null_if [0] 1111.29/291.68 1111.29/291.68 The TRS has the following type information: 1111.29/291.68 app :: nil:cons:xs:null_if -> nil:cons:xs:null_if -> nil:cons:xs:null_if 1111.29/291.68 helpa :: 0:s:null_length:null_plus -> 0:s:null_length:null_plus -> nil:cons:xs:null_if -> nil:cons:xs:null_if -> nil:cons:xs:null_if 1111.29/291.68 0 :: 0:s:null_length:null_plus 1111.29/291.68 plus :: 0:s:null_length:null_plus -> 0:s:null_length:null_plus -> 0:s:null_length:null_plus 1111.29/291.68 length :: nil:cons:xs:null_if -> 0:s:null_length:null_plus 1111.29/291.68 s :: 0:s:null_length:null_plus -> 0:s:null_length:null_plus 1111.29/291.68 nil :: nil:cons:xs:null_if 1111.29/291.68 cons :: null_take -> nil:cons:xs:null_if -> nil:cons:xs:null_if 1111.29/291.68 if :: true:false:null_ge -> 0:s:null_length:null_plus -> 0:s:null_length:null_plus -> nil:cons:xs:null_if -> nil:cons:xs:null_if -> nil:cons:xs:null_if 1111.29/291.68 ge :: 0:s:null_length:null_plus -> 0:s:null_length:null_plus -> true:false:null_ge 1111.29/291.68 true :: true:false:null_ge 1111.29/291.68 false :: true:false:null_ge 1111.29/291.68 helpb :: 0:s:null_length:null_plus -> 0:s:null_length:null_plus -> nil:cons:xs:null_if -> nil:cons:xs:null_if -> nil:cons:xs:null_if 1111.29/291.68 take :: 0:s:null_length:null_plus -> nil:cons:xs:null_if -> nil:cons:xs:null_if -> null_take 1111.29/291.68 xs :: nil:cons:xs:null_if 1111.29/291.68 null_length :: 0:s:null_length:null_plus 1111.29/291.68 null_take :: null_take 1111.29/291.68 null_plus :: 0:s:null_length:null_plus 1111.29/291.68 null_ge :: true:false:null_ge 1111.29/291.68 null_if :: nil:cons:xs:null_if 1111.29/291.68 1111.29/291.68 Rewrite Strategy: INNERMOST 1111.29/291.68 ---------------------------------------- 1111.29/291.68 1111.29/291.68 (7) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 1111.29/291.68 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 1111.29/291.68 The constant constructors are abstracted as follows: 1111.29/291.68 1111.29/291.68 0 => 0 1111.29/291.68 nil => 0 1111.29/291.68 true => 2 1111.29/291.68 false => 1 1111.29/291.68 xs => 1 1111.29/291.68 null_length => 0 1111.29/291.68 null_take => 0 1111.29/291.68 null_plus => 0 1111.29/291.68 null_ge => 0 1111.29/291.68 null_if => 0 1111.29/291.68 1111.29/291.68 ---------------------------------------- 1111.29/291.68 1111.29/291.68 (8) 1111.29/291.68 Obligation: 1111.29/291.68 Complexity RNTS consisting of the following rules: 1111.29/291.68 1111.29/291.68 app(z, z') -{ 1 }-> helpa(0, plus(length(x), length(y)), x, y) :|: x >= 0, y >= 0, z = x, z' = y 1111.29/291.68 ge(z, z') -{ 1 }-> ge(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 1111.29/291.68 ge(z, z') -{ 1 }-> 2 :|: x >= 0, z = x, z' = 0 1111.29/291.68 ge(z, z') -{ 1 }-> 1 :|: z' = 1 + x, x >= 0, z = 0 1111.29/291.68 ge(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 1111.29/291.68 helpa(z, z', z'', z1) -{ 1 }-> if(ge(c, l), c, l, ys, zs) :|: z' = l, c >= 0, ys >= 0, zs >= 0, z'' = ys, z = c, l >= 0, z1 = zs 1111.29/291.68 helpb(z, z', z'', z1) -{ 1 }-> 1 + take(c, ys, zs) + helpa(1 + c, l, ys, zs) :|: z' = l, c >= 0, ys >= 0, zs >= 0, z'' = ys, z = c, l >= 0, z1 = zs 1111.29/291.68 if(z, z', z'', z1, z2) -{ 1 }-> helpb(c, l, ys, zs) :|: z2 = zs, c >= 0, z = 1, ys >= 0, zs >= 0, l >= 0, z' = c, z'' = l, z1 = ys 1111.29/291.68 if(z, z', z'', z1, z2) -{ 1 }-> 0 :|: z = 2, z2 = zs, c >= 0, ys >= 0, zs >= 0, l >= 0, z' = c, z'' = l, z1 = ys 1111.29/291.68 if(z, z', z'', z1, z2) -{ 0 }-> 0 :|: z1 = v3, v0 >= 0, v4 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, z2 = v4, v2 >= 0, v3 >= 0 1111.29/291.68 length(z) -{ 1 }-> 0 :|: z = 0 1111.29/291.68 length(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 1111.29/291.68 length(z) -{ 1 }-> 1 + length(y) :|: z = 1 + x + y, x >= 0, y >= 0 1111.29/291.68 plus(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0 1111.29/291.68 plus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 1111.29/291.68 plus(z, z') -{ 1 }-> 1 + plus(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = x 1111.29/291.68 take(z, z', z'') -{ 1 }-> x :|: ys >= 0, x >= 0, z'' = ys, z = 0, z' = 1 + x + 1 1111.29/291.68 take(z, z', z'') -{ 1 }-> y :|: z'' = 1 + y + ys, ys >= 0, y >= 0, z = 0, z' = 0 1111.29/291.68 take(z, z', z'') -{ 1 }-> take(c, 1, ys) :|: c >= 0, ys >= 0, x >= 0, z'' = ys, z = 1 + c, z' = 1 + x + 1 1111.29/291.68 take(z, z', z'') -{ 1 }-> take(c, 0, ys) :|: z'' = 1 + y + ys, c >= 0, ys >= 0, y >= 0, z = 1 + c, z' = 0 1111.29/291.68 take(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 1111.29/291.68 1111.29/291.68 Only complete derivations are relevant for the runtime complexity. 1111.29/291.68 1111.29/291.68 ---------------------------------------- 1111.29/291.68 1111.29/291.68 (9) CompleteCoflocoProof (FINISHED) 1111.29/291.68 Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: 1111.29/291.68 1111.29/291.68 eq(start(V1, V, V9, V14, V22),0,[app(V1, V, Out)],[V1 >= 0,V >= 0]). 1111.29/291.68 eq(start(V1, V, V9, V14, V22),0,[plus(V1, V, Out)],[V1 >= 0,V >= 0]). 1111.29/291.68 eq(start(V1, V, V9, V14, V22),0,[length(V1, Out)],[V1 >= 0]). 1111.29/291.68 eq(start(V1, V, V9, V14, V22),0,[helpa(V1, V, V9, V14, Out)],[V1 >= 0,V >= 0,V9 >= 0,V14 >= 0]). 1111.29/291.68 eq(start(V1, V, V9, V14, V22),0,[ge(V1, V, Out)],[V1 >= 0,V >= 0]). 1111.29/291.68 eq(start(V1, V, V9, V14, V22),0,[if(V1, V, V9, V14, V22, Out)],[V1 >= 0,V >= 0,V9 >= 0,V14 >= 0,V22 >= 0]). 1111.29/291.68 eq(start(V1, V, V9, V14, V22),0,[take(V1, V, V9, Out)],[V1 >= 0,V >= 0,V9 >= 0]). 1111.29/291.68 eq(start(V1, V, V9, V14, V22),0,[helpb(V1, V, V9, V14, Out)],[V1 >= 0,V >= 0,V9 >= 0,V14 >= 0]). 1111.29/291.68 eq(app(V1, V, Out),1,[length(V3, Ret10),length(V2, Ret11),plus(Ret10, Ret11, Ret1),helpa(0, Ret1, V3, V2, Ret)],[Out = Ret,V3 >= 0,V2 >= 0,V1 = V3,V = V2]). 1111.29/291.68 eq(plus(V1, V, Out),1,[],[Out = V4,V4 >= 0,V1 = V4,V = 0]). 1111.29/291.68 eq(plus(V1, V, Out),1,[plus(V5, V6, Ret12)],[Out = 1 + Ret12,V = 1 + V6,V5 >= 0,V6 >= 0,V1 = V5]). 1111.29/291.68 eq(length(V1, Out),1,[],[Out = 0,V1 = 0]). 1111.29/291.68 eq(length(V1, Out),1,[length(V8, Ret13)],[Out = 1 + Ret13,V1 = 1 + V7 + V8,V7 >= 0,V8 >= 0]). 1111.29/291.68 eq(helpa(V1, V, V9, V14, Out),1,[ge(V10, V11, Ret0),if(Ret0, V10, V11, V12, V13, Ret2)],[Out = Ret2,V = V11,V10 >= 0,V12 >= 0,V13 >= 0,V9 = V12,V1 = V10,V11 >= 0,V14 = V13]). 1111.29/291.68 eq(ge(V1, V, Out),1,[],[Out = 2,V15 >= 0,V1 = V15,V = 0]). 1111.29/291.68 eq(ge(V1, V, Out),1,[],[Out = 1,V = 1 + V16,V16 >= 0,V1 = 0]). 1111.29/291.68 eq(ge(V1, V, Out),1,[ge(V18, V17, Ret3)],[Out = Ret3,V = 1 + V17,V18 >= 0,V17 >= 0,V1 = 1 + V18]). 1111.29/291.68 eq(if(V1, V, V9, V14, V22, Out),1,[],[Out = 0,V1 = 2,V22 = V21,V19 >= 0,V20 >= 0,V21 >= 0,V23 >= 0,V = V19,V9 = V23,V14 = V20]). 1111.29/291.68 eq(if(V1, V, V9, V14, V22, Out),1,[helpb(V24, V27, V26, V25, Ret4)],[Out = Ret4,V22 = V25,V24 >= 0,V1 = 1,V26 >= 0,V25 >= 0,V27 >= 0,V = V24,V9 = V27,V14 = V26]). 1111.29/291.68 eq(take(V1, V, V9, Out),1,[],[Out = V28,V29 >= 0,V28 >= 0,V9 = V29,V1 = 0,V = 2 + V28]). 1111.29/291.68 eq(take(V1, V, V9, Out),1,[],[Out = V30,V9 = 1 + V30 + V31,V31 >= 0,V30 >= 0,V1 = 0,V = 0]). 1111.29/291.68 eq(take(V1, V, V9, Out),1,[take(V32, 1, V34, Ret5)],[Out = Ret5,V32 >= 0,V34 >= 0,V33 >= 0,V9 = V34,V1 = 1 + V32,V = 2 + V33]). 1111.29/291.68 eq(take(V1, V, V9, Out),1,[take(V37, 0, V36, Ret6)],[Out = Ret6,V9 = 1 + V35 + V36,V37 >= 0,V36 >= 0,V35 >= 0,V1 = 1 + V37,V = 0]). 1111.29/291.68 eq(helpb(V1, V, V9, V14, Out),1,[take(V40, V38, V39, Ret01),helpa(1 + V40, V41, V38, V39, Ret14)],[Out = 1 + Ret01 + Ret14,V = V41,V40 >= 0,V38 >= 0,V39 >= 0,V9 = V38,V1 = V40,V41 >= 0,V14 = V39]). 1111.29/291.68 eq(length(V1, Out),0,[],[Out = 0,V42 >= 0,V1 = V42]). 1111.29/291.68 eq(take(V1, V, V9, Out),0,[],[Out = 0,V44 >= 0,V9 = V45,V43 >= 0,V1 = V44,V = V43,V45 >= 0]). 1111.29/291.68 eq(plus(V1, V, Out),0,[],[Out = 0,V47 >= 0,V46 >= 0,V1 = V47,V = V46]). 1111.29/291.68 eq(ge(V1, V, Out),0,[],[Out = 0,V48 >= 0,V49 >= 0,V1 = V48,V = V49]). 1111.29/291.68 eq(if(V1, V, V9, V14, V22, Out),0,[],[Out = 0,V14 = V54,V50 >= 0,V53 >= 0,V9 = V51,V52 >= 0,V1 = V50,V = V52,V22 = V53,V51 >= 0,V54 >= 0]). 1111.29/291.68 input_output_vars(app(V1,V,Out),[V1,V],[Out]). 1111.29/291.68 input_output_vars(plus(V1,V,Out),[V1,V],[Out]). 1111.29/291.68 input_output_vars(length(V1,Out),[V1],[Out]). 1111.29/291.68 input_output_vars(helpa(V1,V,V9,V14,Out),[V1,V,V9,V14],[Out]). 1111.29/291.68 input_output_vars(ge(V1,V,Out),[V1,V],[Out]). 1111.29/291.68 input_output_vars(if(V1,V,V9,V14,V22,Out),[V1,V,V9,V14,V22],[Out]). 1111.29/291.68 input_output_vars(take(V1,V,V9,Out),[V1,V,V9],[Out]). 1111.29/291.68 input_output_vars(helpb(V1,V,V9,V14,Out),[V1,V,V9,V14],[Out]). 1111.29/291.68 1111.29/291.68 1111.29/291.68 CoFloCo proof output: 1111.29/291.68 Preprocessing Cost Relations 1111.29/291.68 ===================================== 1111.29/291.68 1111.29/291.68 #### Computed strongly connected components 1111.29/291.68 0. recursive : [ge/3] 1111.29/291.68 1. recursive : [take/4] 1111.29/291.68 2. recursive : [helpa/5,helpb/5,if/6] 1111.29/291.68 3. recursive : [length/2] 1111.29/291.68 4. recursive : [plus/3] 1111.29/291.68 5. non_recursive : [app/3] 1111.29/291.68 6. non_recursive : [start/5] 1111.29/291.68 1111.29/291.68 #### Obtained direct recursion through partial evaluation 1111.29/291.68 0. SCC is partially evaluated into ge/3 1111.29/291.68 1. SCC is partially evaluated into take/4 1111.29/291.68 2. SCC is partially evaluated into helpa/5 1111.29/291.68 3. SCC is partially evaluated into length/2 1111.29/291.68 4. SCC is partially evaluated into plus/3 1111.29/291.68 5. SCC is partially evaluated into app/3 1111.29/291.68 6. SCC is partially evaluated into start/5 1111.29/291.68 1111.29/291.68 Control-Flow Refinement of Cost Relations 1111.29/291.68 ===================================== 1111.29/291.68 1111.29/291.68 ### Specialization of cost equations ge/3 1111.29/291.68 * CE 29 is refined into CE [30] 1111.29/291.68 * CE 26 is refined into CE [31] 1111.29/291.68 * CE 27 is refined into CE [32] 1111.29/291.68 * CE 28 is refined into CE [33] 1111.29/291.68 1111.29/291.68 1111.29/291.68 ### Cost equations --> "Loop" of ge/3 1111.29/291.68 * CEs [33] --> Loop 20 1111.29/291.68 * CEs [30] --> Loop 21 1111.29/291.68 * CEs [31] --> Loop 22 1111.29/291.68 * CEs [32] --> Loop 23 1111.29/291.68 1111.29/291.68 ### Ranking functions of CR ge(V1,V,Out) 1111.29/291.68 * RF of phase [20]: [V,V1] 1111.29/291.68 1111.29/291.68 #### Partial ranking functions of CR ge(V1,V,Out) 1111.29/291.68 * Partial RF of phase [20]: 1111.29/291.68 - RF of loop [20:1]: 1111.29/291.68 V 1111.29/291.68 V1 1111.29/291.68 1111.29/291.68 1111.29/291.68 ### Specialization of cost equations take/4 1111.29/291.68 * CE 15 is refined into CE [34] 1111.29/291.68 * CE 11 is refined into CE [35] 1111.29/291.68 * CE 12 is refined into CE [36] 1111.29/291.68 * CE 13 is refined into CE [37] 1111.29/291.68 * CE 14 is refined into CE [38] 1111.29/291.68 1111.29/291.68 1111.29/291.68 ### Cost equations --> "Loop" of take/4 1111.29/291.68 * CEs [37] --> Loop 24 1111.29/291.68 * CEs [38] --> Loop 25 1111.29/291.68 * CEs [34] --> Loop 26 1111.29/291.68 * CEs [35] --> Loop 27 1111.29/291.68 * CEs [36] --> Loop 28 1111.29/291.68 1111.29/291.68 ### Ranking functions of CR take(V1,V,V9,Out) 1111.29/291.68 * RF of phase [25]: [V1,V9] 1111.29/291.68 1111.29/291.68 #### Partial ranking functions of CR take(V1,V,V9,Out) 1111.29/291.68 * Partial RF of phase [25]: 1111.29/291.68 - RF of loop [25:1]: 1111.29/291.68 V1 1111.29/291.68 V9 1111.29/291.68 1111.29/291.68 1111.29/291.68 ### Specialization of cost equations helpa/5 1111.29/291.68 * CE 18 is refined into CE [39,40,41,42,43] 1111.29/291.68 * CE 16 is refined into CE [44,45,46,47,48] 1111.29/291.68 * CE 17 is refined into CE [49,50] 1111.29/291.68 1111.29/291.68 1111.29/291.68 ### Cost equations --> "Loop" of helpa/5 1111.29/291.68 * CEs [45,49] --> Loop 29 1111.29/291.68 * CEs [44,46,47,48,50] --> Loop 30 1111.29/291.68 * CEs [42] --> Loop 31 1111.29/291.68 * CEs [43] --> Loop 32 1111.29/291.68 * CEs [40] --> Loop 33 1111.29/291.68 * CEs [41] --> Loop 34 1111.29/291.68 * CEs [39] --> Loop 35 1111.29/291.68 1111.29/291.68 ### Ranking functions of CR helpa(V1,V,V9,V14,Out) 1111.29/291.68 * RF of phase [31,32]: [-V1+V] 1111.29/291.68 1111.29/291.68 #### Partial ranking functions of CR helpa(V1,V,V9,V14,Out) 1111.29/291.68 * Partial RF of phase [31,32]: 1111.29/291.68 - RF of loop [31:1,32:1]: 1111.29/291.68 -V1+V 1111.29/291.68 - RF of loop [32:1]: 1111.29/291.68 -V1+V14 1111.29/291.68 1111.29/291.68 1111.29/291.68 ### Specialization of cost equations length/2 1111.29/291.68 * CE 23 is refined into CE [51] 1111.29/291.68 * CE 25 is refined into CE [52] 1111.29/291.68 * CE 24 is refined into CE [53] 1111.29/291.68 1111.29/291.68 1111.29/291.68 ### Cost equations --> "Loop" of length/2 1111.29/291.68 * CEs [53] --> Loop 36 1111.29/291.68 * CEs [51,52] --> Loop 37 1111.29/291.68 1111.29/291.68 ### Ranking functions of CR length(V1,Out) 1111.29/291.68 * RF of phase [36]: [V1] 1111.29/291.68 1111.29/291.68 #### Partial ranking functions of CR length(V1,Out) 1111.29/291.68 * Partial RF of phase [36]: 1111.29/291.68 - RF of loop [36:1]: 1111.29/291.68 V1 1111.29/291.68 1111.29/291.68 1111.29/291.68 ### Specialization of cost equations plus/3 1111.29/291.68 * CE 22 is refined into CE [54] 1111.29/291.68 * CE 20 is refined into CE [55] 1111.29/291.68 * CE 21 is refined into CE [56] 1111.29/291.68 1111.29/291.68 1111.29/291.68 ### Cost equations --> "Loop" of plus/3 1111.29/291.68 * CEs [56] --> Loop 38 1111.29/291.68 * CEs [54] --> Loop 39 1111.29/291.68 * CEs [55] --> Loop 40 1111.29/291.68 1111.29/291.68 ### Ranking functions of CR plus(V1,V,Out) 1111.29/291.68 * RF of phase [38]: [V] 1111.29/291.68 1111.29/291.68 #### Partial ranking functions of CR plus(V1,V,Out) 1111.29/291.68 * Partial RF of phase [38]: 1111.29/291.68 - RF of loop [38:1]: 1111.29/291.68 V 1111.29/291.68 1111.29/291.68 1111.29/291.68 ### Specialization of cost equations app/3 1111.29/291.68 * CE 19 is refined into CE [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] 1111.29/291.68 1111.29/291.68 1111.29/291.68 ### Cost equations --> "Loop" of app/3 1111.29/291.68 * CEs [70] --> Loop 41 1111.29/291.68 * CEs [76] --> Loop 42 1111.29/291.68 * CEs [61,66,80] --> Loop 43 1111.29/291.68 * CEs [63,68,72,78,82] --> Loop 44 1111.29/291.68 * CEs [71] --> Loop 45 1111.29/291.68 * CEs [62,67,77,81] --> Loop 46 1111.29/291.68 * CEs [57,58,59,64,69,73,74,75,79,83] --> Loop 47 1111.29/291.68 * CEs [60,65] --> Loop 48 1111.29/291.68 1111.29/291.68 ### Ranking functions of CR app(V1,V,Out) 1111.29/291.69 1111.29/291.69 #### Partial ranking functions of CR app(V1,V,Out) 1111.29/291.69 1111.29/291.69 1111.29/291.69 ### Specialization of cost equations start/5 1111.29/291.69 * CE 2 is refined into CE [84] 1111.29/291.69 * CE 1 is refined into CE [85] 1111.29/291.69 * CE 3 is refined into CE [86,87,88,89,90,91,92,93] 1111.29/291.69 * CE 4 is refined into CE [94,95,96,97,98,99,100,101] 1111.29/291.69 * CE 5 is refined into CE [102,103,104,105,106,107,108,109] 1111.29/291.69 * CE 6 is refined into CE [110,111,112,113] 1111.29/291.69 * CE 7 is refined into CE [114,115] 1111.29/291.69 * CE 8 is refined into CE [116,117,118,119,120,121] 1111.29/291.69 * CE 9 is refined into CE [122,123,124,125,126] 1111.29/291.69 * CE 10 is refined into CE [127,128,129,130] 1111.29/291.69 1111.29/291.69 1111.29/291.69 ### Cost equations --> "Loop" of start/5 1111.29/291.69 * CEs [100,101] --> Loop 49 1111.29/291.69 * CEs [84] --> Loop 50 1111.29/291.69 * CEs [92,93] --> Loop 51 1111.29/291.69 * CEs [88,89] --> Loop 52 1111.29/291.69 * CEs [86,87,90,91] --> Loop 53 1111.29/291.69 * CEs [102,117,118,122,128] --> Loop 54 1111.29/291.69 * CEs [96,97,119] --> Loop 55 1111.29/291.69 * CEs [94,95,116] --> Loop 56 1111.29/291.69 * CEs [85,98,99,103,104,105,106,107,108,109,110,111,112,113,114,115,120,121,123,124,125,126,127,129,130] --> Loop 57 1111.29/291.69 1111.29/291.69 ### Ranking functions of CR start(V1,V,V9,V14,V22) 1111.29/291.69 1111.29/291.69 #### Partial ranking functions of CR start(V1,V,V9,V14,V22) 1111.29/291.69 1111.29/291.69 1111.29/291.69 Computing Bounds 1111.29/291.69 ===================================== 1111.29/291.69 1111.29/291.69 #### Cost of chains of ge(V1,V,Out): 1111.29/291.69 * Chain [[20],23]: 1*it(20)+1 1111.29/291.69 Such that:it(20) =< V1 1111.29/291.69 1111.29/291.69 with precondition: [Out=1,V1>=1,V>=V1+1] 1111.29/291.69 1111.29/291.69 * Chain [[20],22]: 1*it(20)+1 1111.29/291.69 Such that:it(20) =< V 1111.29/291.69 1111.29/291.69 with precondition: [Out=2,V>=1,V1>=V] 1111.29/291.69 1111.29/291.69 * Chain [[20],21]: 1*it(20)+0 1111.29/291.69 Such that:it(20) =< V 1111.29/291.69 1111.29/291.69 with precondition: [Out=0,V1>=1,V>=1] 1111.29/291.69 1111.29/291.69 * Chain [23]: 1 1111.29/291.69 with precondition: [V1=0,Out=1,V>=1] 1111.29/291.69 1111.29/291.69 * Chain [22]: 1 1111.29/291.69 with precondition: [V=0,Out=2,V1>=0] 1111.29/291.69 1111.29/291.69 * Chain [21]: 0 1111.29/291.69 with precondition: [Out=0,V1>=0,V>=0] 1111.29/291.69 1111.29/291.69 1111.29/291.69 #### Cost of chains of take(V1,V,V9,Out): 1111.29/291.69 * Chain [[25],28]: 1*it(25)+1 1111.29/291.69 Such that:it(25) =< V1 1111.29/291.69 1111.29/291.69 with precondition: [V=0,V1>=1,Out>=0,V9>=Out+V1+1] 1111.29/291.69 1111.29/291.69 * Chain [[25],26]: 1*it(25)+0 1111.29/291.69 Such that:it(25) =< V9 1111.29/291.69 1111.29/291.69 with precondition: [V=0,Out=0,V1>=1,V9>=1] 1111.29/291.69 1111.29/291.69 * Chain [28]: 1 1111.29/291.69 with precondition: [V1=0,V=0,Out>=0,V9>=Out+1] 1111.29/291.69 1111.29/291.69 * Chain [27]: 1 1111.29/291.69 with precondition: [V1=0,V=Out+2,V>=2,V9>=0] 1111.29/291.69 1111.29/291.69 * Chain [26]: 0 1111.29/291.69 with precondition: [Out=0,V1>=0,V>=0,V9>=0] 1111.29/291.69 1111.29/291.69 * Chain [24,26]: 1 1111.29/291.69 with precondition: [Out=0,V1>=1,V>=2,V9>=0] 1111.29/291.69 1111.29/291.69 1111.29/291.69 #### Cost of chains of helpa(V1,V,V9,V14,Out): 1111.29/291.69 * Chain [[31,32],30]: 5*it(31)+5*it(32)+4*s(3)+1*s(15)+1*s(16)+2*s(17)+3 1111.29/291.69 Such that:it(32) =< -V1+V14 1111.29/291.69 aux(4) =< V14 1111.29/291.69 aux(8) =< -V1+V 1111.29/291.69 aux(9) =< V 1111.29/291.69 it(32) =< aux(8) 1111.29/291.69 s(3) =< aux(9) 1111.29/291.69 it(31) =< aux(8) 1111.29/291.69 aux(5) =< aux(9) 1111.29/291.69 s(16) =< it(31)*aux(4) 1111.29/291.69 s(15) =< it(31)*aux(9) 1111.29/291.69 s(18) =< it(32)*aux(5) 1111.29/291.69 s(17) =< s(18) 1111.29/291.69 1111.29/291.69 with precondition: [V1>=1,V9>=0,V14>=0,Out>=1,V>=V1+1] 1111.29/291.69 1111.29/291.69 * Chain [35,[31,32],30]: 9*it(31)+5*it(32)+1*s(15)+1*s(16)+2*s(17)+8 1111.29/291.69 Such that:aux(10) =< V 1111.29/291.69 aux(11) =< V14 1111.29/291.69 it(32) =< aux(11) 1111.29/291.69 it(32) =< aux(10) 1111.29/291.69 it(31) =< aux(10) 1111.29/291.69 aux(5) =< aux(10) 1111.29/291.69 s(16) =< it(31)*aux(11) 1111.29/291.69 s(15) =< it(31)*aux(10) 1111.29/291.69 s(18) =< it(32)*aux(5) 1111.29/291.69 s(17) =< s(18) 1111.29/291.69 1111.29/291.69 with precondition: [V1=0,V9=0,V>=2,V14>=1,Out>=2] 1111.29/291.69 1111.29/291.69 * Chain [35,30]: 3*s(3)+1*s(4)+8 1111.29/291.69 Such that:s(4) =< 1 1111.29/291.69 aux(1) =< V 1111.29/291.69 s(3) =< aux(1) 1111.29/291.69 1111.29/291.69 with precondition: [V1=0,V9=0,V>=1,Out>=1,V14>=Out] 1111.29/291.69 1111.29/291.69 * Chain [34,[31,32],30]: 9*it(31)+5*it(32)+1*s(15)+1*s(16)+2*s(17)+1*s(19)+8 1111.29/291.69 Such that:aux(12) =< V 1111.29/291.69 aux(13) =< V14 1111.29/291.69 it(32) =< aux(13) 1111.29/291.69 s(19) =< aux(13) 1111.29/291.69 it(32) =< aux(12) 1111.29/291.69 it(31) =< aux(12) 1111.29/291.69 aux(5) =< aux(12) 1111.29/291.69 s(16) =< it(31)*aux(13) 1111.29/291.69 s(15) =< it(31)*aux(12) 1111.29/291.69 s(18) =< it(32)*aux(5) 1111.29/291.69 s(17) =< s(18) 1111.29/291.69 1111.29/291.69 with precondition: [V1=0,V>=2,V9>=0,V14>=0,Out>=2] 1111.29/291.69 1111.29/291.69 * Chain [34,30]: 3*s(3)+1*s(4)+1*s(19)+8 1111.29/291.69 Such that:s(4) =< 1 1111.29/291.69 aux(1) =< V 1111.29/291.69 s(19) =< V14 1111.29/291.69 s(3) =< aux(1) 1111.29/291.69 1111.29/291.69 with precondition: [V1=0,Out=1,V>=1,V9>=0,V14>=0] 1111.29/291.69 1111.29/291.69 * Chain [33,[31,32],30]: 9*it(31)+5*it(32)+1*s(15)+1*s(16)+2*s(17)+8 1111.29/291.69 Such that:aux(14) =< V 1111.29/291.69 aux(15) =< V14 1111.29/291.69 it(32) =< aux(15) 1111.29/291.69 it(32) =< aux(14) 1111.29/291.69 it(31) =< aux(14) 1111.29/291.69 aux(5) =< aux(14) 1111.29/291.69 s(16) =< it(31)*aux(15) 1111.29/291.69 s(15) =< it(31)*aux(14) 1111.29/291.69 s(18) =< it(32)*aux(5) 1111.29/291.69 s(17) =< s(18) 1111.29/291.69 1111.29/291.69 with precondition: [V1=0,V>=2,V9>=2,V14>=0,Out>=V9] 1111.29/291.69 1111.29/291.69 * Chain [33,30]: 3*s(3)+1*s(4)+8 1111.29/291.69 Such that:s(4) =< 1 1111.29/291.69 aux(1) =< V 1111.29/291.69 s(3) =< aux(1) 1111.29/291.69 1111.29/291.69 with precondition: [V1=0,V9=Out+1,V>=1,V9>=2,V14>=0] 1111.29/291.69 1111.29/291.69 * Chain [30]: 3*s(3)+1*s(4)+3 1111.29/291.69 Such that:s(4) =< V1 1111.29/291.69 aux(1) =< V 1111.29/291.69 s(3) =< aux(1) 1111.29/291.69 1111.29/291.69 with precondition: [Out=0,V1>=0,V>=0,V9>=0,V14>=0] 1111.29/291.69 1111.29/291.69 * Chain [29]: 3 1111.29/291.69 with precondition: [V=0,Out=0,V1>=0,V9>=0,V14>=0] 1111.29/291.69 1111.29/291.69 1111.29/291.69 #### Cost of chains of length(V1,Out): 1111.29/291.69 * Chain [[36],37]: 1*it(36)+1 1111.29/291.69 Such that:it(36) =< V1 1111.29/291.69 1111.29/291.69 with precondition: [Out>=1,V1>=Out] 1111.29/291.69 1111.29/291.69 * Chain [37]: 1 1111.29/291.69 with precondition: [Out=0,V1>=0] 1111.29/291.69 1111.29/291.69 1111.29/291.69 #### Cost of chains of plus(V1,V,Out): 1111.29/291.69 * Chain [[38],40]: 1*it(38)+1 1111.29/291.69 Such that:it(38) =< V 1111.29/291.69 1111.29/291.69 with precondition: [V+V1=Out,V1>=0,V>=1] 1111.29/291.69 1111.29/291.69 * Chain [[38],39]: 1*it(38)+0 1111.29/291.69 Such that:it(38) =< Out 1111.29/291.69 1111.29/291.69 with precondition: [V1>=0,Out>=1,V>=Out] 1111.29/291.69 1111.29/291.69 * Chain [40]: 1 1111.29/291.69 with precondition: [V=0,V1=Out,V1>=0] 1111.29/291.69 1111.29/291.69 * Chain [39]: 0 1111.29/291.69 with precondition: [Out=0,V1>=0,V>=0] 1111.29/291.69 1111.29/291.69 1111.29/291.69 #### Cost of chains of app(V1,V,Out): 1111.29/291.69 * Chain [48]: 10*s(51)+2*s(53)+12 1111.29/291.69 Such that:aux(20) =< 1 1111.29/291.69 aux(21) =< V 1111.29/291.69 s(53) =< aux(20) 1111.29/291.69 s(51) =< aux(21) 1111.29/291.69 1111.29/291.69 with precondition: [V1=0,Out>=1,V>=Out] 1111.29/291.69 1111.29/291.69 * Chain [47]: 19*s(67)+8*s(81)+3*s(99)+7 1111.29/291.69 Such that:s(98) =< V1+V 1111.29/291.69 aux(32) =< V1 1111.29/291.69 aux(33) =< V 1111.29/291.69 s(81) =< aux(32) 1111.29/291.69 s(67) =< aux(33) 1111.29/291.69 s(99) =< s(98) 1111.29/291.69 1111.29/291.69 with precondition: [Out=0,V1>=0,V>=0] 1111.29/291.69 1111.29/291.69 * Chain [46]: 21*s(106)+4*s(108)+2*s(118)+3*s(124)+12 1111.29/291.69 Such that:s(122) =< V1+V 1111.29/291.69 aux(38) =< 1 1111.29/291.69 aux(39) =< V1 1111.29/291.69 aux(40) =< V 1111.29/291.69 s(108) =< aux(38) 1111.29/291.69 s(118) =< aux(39) 1111.29/291.69 s(106) =< aux(40) 1111.29/291.69 s(124) =< s(122) 1111.29/291.69 1111.29/291.69 with precondition: [Out=1,V1>=0,V>=1] 1111.29/291.69 1111.29/291.69 * Chain [45]: 4*s(132)+1*s(133)+1*s(135)+12 1111.29/291.69 Such that:s(133) =< 1 1111.29/291.69 s(135) =< V 1111.29/291.69 aux(41) =< V1 1111.29/291.69 s(132) =< aux(41) 1111.29/291.69 1111.29/291.69 with precondition: [Out=1,V1>=1,V>=0] 1111.29/291.69 1111.29/291.69 * Chain [44]: 17*s(137)+5*s(139)+6*s(147)+3*s(156)+12 1111.29/291.69 Such that:s(155) =< V1+V 1111.29/291.69 aux(47) =< 1 1111.29/291.69 aux(48) =< V1 1111.29/291.69 aux(49) =< V 1111.29/291.69 s(139) =< aux(47) 1111.29/291.69 s(147) =< aux(48) 1111.29/291.69 s(137) =< aux(49) 1111.29/291.69 s(156) =< s(155) 1111.29/291.69 1111.29/291.69 with precondition: [V1=Out+1,V1>=2,V>=0] 1111.29/291.69 1111.29/291.69 * Chain [43]: 135*s(163)+18*s(170)+18*s(173)+1*s(187)+12 1111.29/291.69 Such that:s(187) =< V1 1111.29/291.69 aux(53) =< V 1111.29/291.69 s(163) =< aux(53) 1111.29/291.69 s(169) =< aux(53) 1111.29/291.69 s(170) =< s(163)*aux(53) 1111.29/291.69 s(172) =< s(163)*s(169) 1111.29/291.69 s(173) =< s(172) 1111.29/291.69 1111.29/291.69 with precondition: [V1>=0,V>=2,Out>=2] 1111.29/291.69 1111.29/291.69 * Chain [42]: 1*s(200)+3*s(201)+15*s(205)+27*s(206)+3*s(208)+3*s(209)+6*s(211)+12 1111.29/291.69 Such that:s(200) =< V1 1111.29/291.69 s(203) =< V1+V 1111.29/291.69 aux(54) =< V 1111.29/291.69 s(201) =< aux(54) 1111.29/291.69 s(205) =< aux(54) 1111.29/291.69 s(205) =< s(203) 1111.29/291.69 s(206) =< s(203) 1111.29/291.69 s(207) =< s(203) 1111.29/291.69 s(208) =< s(206)*aux(54) 1111.29/291.69 s(209) =< s(206)*s(203) 1111.29/291.69 s(210) =< s(205)*s(207) 1111.29/291.69 s(211) =< s(210) 1111.29/291.69 1111.29/291.69 with precondition: [V1>=1,V>=1,Out>=2] 1111.29/291.69 1111.29/291.69 * Chain [41]: 28*s(213)+15*s(216)+3*s(219)+3*s(220)+6*s(222)+1*s(223)+12 1111.29/291.69 Such that:s(215) =< V 1111.29/291.69 aux(55) =< V1 1111.29/291.69 s(213) =< aux(55) 1111.29/291.69 s(216) =< s(215) 1111.29/291.69 s(216) =< aux(55) 1111.29/291.69 s(218) =< aux(55) 1111.29/291.69 s(219) =< s(213)*s(215) 1111.29/291.69 s(220) =< s(213)*aux(55) 1111.29/291.69 s(221) =< s(216)*s(218) 1111.29/291.69 s(222) =< s(221) 1111.29/291.69 s(223) =< s(215) 1111.29/291.69 1111.29/291.69 with precondition: [V1>=2,V>=0,Out>=2] 1111.29/291.69 1111.29/291.69 1111.29/291.69 #### Cost of chains of start(V1,V,V9,V14,V22): 1111.29/291.69 * Chain [57]: 2*s(224)+1*s(225)+215*s(227)+10*s(229)+10*s(234)+2*s(236)+2*s(237)+4*s(239)+54*s(243)+36*s(245)+10*s(250)+18*s(270)+18*s(272)+15*s(277)+3*s(280)+3*s(281)+6*s(283)+15*s(287)+3*s(289)+3*s(290)+6*s(292)+1*s(314)+12 1111.29/291.69 Such that:s(225) =< V1+1 1111.29/291.69 s(314) =< V9 1111.29/291.69 aux(57) =< 1 1111.29/291.69 aux(58) =< -V1+V 1111.29/291.69 aux(59) =< -V1+V14 1111.29/291.69 aux(60) =< V1 1111.29/291.69 aux(61) =< V1+V 1111.29/291.69 aux(62) =< V 1111.29/291.69 aux(63) =< V14 1111.29/291.69 s(250) =< aux(57) 1111.29/291.69 s(229) =< aux(59) 1111.29/291.69 s(243) =< aux(60) 1111.29/291.69 s(227) =< aux(62) 1111.29/291.69 s(224) =< aux(63) 1111.29/291.69 s(245) =< aux(61) 1111.29/291.69 s(229) =< aux(58) 1111.29/291.69 s(234) =< aux(58) 1111.29/291.69 s(235) =< aux(62) 1111.29/291.69 s(236) =< s(234)*aux(63) 1111.29/291.69 s(237) =< s(234)*aux(62) 1111.29/291.69 s(238) =< s(229)*s(235) 1111.29/291.69 s(239) =< s(238) 1111.29/291.69 s(270) =< s(227)*aux(62) 1111.29/291.69 s(271) =< s(227)*s(235) 1111.29/291.69 s(272) =< s(271) 1111.29/291.69 s(277) =< aux(62) 1111.29/291.69 s(277) =< aux(61) 1111.29/291.69 s(279) =< aux(61) 1111.29/291.69 s(280) =< s(245)*aux(62) 1111.29/291.69 s(281) =< s(245)*aux(61) 1111.29/291.69 s(282) =< s(277)*s(279) 1111.29/291.69 s(283) =< s(282) 1111.29/291.69 s(287) =< aux(62) 1111.29/291.69 s(287) =< aux(60) 1111.29/291.69 s(288) =< aux(60) 1111.29/291.69 s(289) =< s(243)*aux(62) 1111.29/291.69 s(290) =< s(243)*aux(60) 1111.29/291.69 s(291) =< s(287)*s(288) 1111.29/291.69 s(292) =< s(291) 1111.29/291.69 1111.29/291.69 with precondition: [V1>=0] 1111.29/291.69 1111.29/291.69 * Chain [56]: 2*s(316)+15*s(318)+5*s(319)+1*s(326)+1*s(327)+2*s(329)+8 1111.29/291.69 Such that:aux(65) =< V14 1111.29/291.69 aux(66) =< 1 1111.29/291.69 aux(67) =< V 1111.29/291.69 s(316) =< aux(66) 1111.29/291.69 s(318) =< aux(67) 1111.29/291.69 s(319) =< aux(65) 1111.29/291.69 s(319) =< aux(67) 1111.29/291.69 s(325) =< aux(67) 1111.29/291.69 s(326) =< s(318)*aux(65) 1111.29/291.69 s(327) =< s(318)*aux(67) 1111.29/291.69 s(328) =< s(319)*s(325) 1111.29/291.69 s(329) =< s(328) 1111.29/291.69 1111.29/291.69 with precondition: [V1=0,V9=0,V>=0,V14>=1] 1111.29/291.69 1111.29/291.69 * Chain [55]: 2*s(333)+15*s(335)+5*s(336)+1*s(343)+1*s(344)+2*s(346)+8 1111.29/291.69 Such that:aux(69) =< V14 1111.29/291.69 aux(70) =< 1 1111.29/291.69 aux(71) =< V 1111.29/291.69 s(333) =< aux(70) 1111.29/291.69 s(335) =< aux(71) 1111.29/291.69 s(336) =< aux(69) 1111.29/291.69 s(336) =< aux(71) 1111.29/291.69 s(342) =< aux(71) 1111.29/291.69 s(343) =< s(335)*aux(69) 1111.29/291.69 s(344) =< s(335)*aux(71) 1111.29/291.69 s(345) =< s(336)*s(342) 1111.29/291.69 s(346) =< s(345) 1111.29/291.69 1111.29/291.69 with precondition: [V1=0,V>=0,V9>=2,V14>=0] 1111.29/291.69 1111.29/291.69 * Chain [54]: 3*s(352)+40*s(353)+15*s(356)+3*s(359)+3*s(360)+6*s(362)+2*s(363)+12 1111.29/291.69 Such that:aux(72) =< 1 1111.29/291.69 aux(73) =< V 1111.29/291.69 aux(74) =< V14 1111.29/291.69 s(352) =< aux(72) 1111.29/291.69 s(363) =< aux(74) 1111.29/291.69 s(353) =< aux(73) 1111.29/291.69 s(356) =< aux(74) 1111.29/291.69 s(356) =< aux(73) 1111.29/291.69 s(358) =< aux(73) 1111.29/291.69 s(359) =< s(353)*aux(74) 1111.29/291.69 s(360) =< s(353)*aux(73) 1111.29/291.69 s(361) =< s(356)*s(358) 1111.29/291.69 s(362) =< s(361) 1111.29/291.69 1111.29/291.69 with precondition: [V1=0,V>=1] 1111.29/291.69 1111.29/291.69 * Chain [53]: 1*s(368)+19*s(370)+5*s(371)+1*s(378)+1*s(379)+2*s(381)+2*s(382)+1*s(383)+5*s(387)+5*s(392)+1*s(394)+1*s(395)+2*s(397)+6 1111.29/291.69 Such that:s(368) =< 1 1111.29/291.69 s(389) =< -V+V9 1111.29/291.69 s(387) =< -V+V22 1111.29/291.69 s(383) =< V+1 1111.29/291.69 aux(78) =< V9 1111.29/291.69 aux(79) =< V22 1111.29/291.69 s(382) =< aux(79) 1111.29/291.69 s(370) =< aux(78) 1111.29/291.69 s(387) =< s(389) 1111.29/291.69 s(392) =< s(389) 1111.29/291.69 s(377) =< aux(78) 1111.29/291.69 s(394) =< s(392)*aux(79) 1111.29/291.69 s(395) =< s(392)*aux(78) 1111.29/291.69 s(396) =< s(387)*s(377) 1111.29/291.69 s(397) =< s(396) 1111.29/291.69 s(371) =< aux(79) 1111.29/291.69 s(371) =< aux(78) 1111.29/291.69 s(378) =< s(370)*aux(79) 1111.29/291.69 s(379) =< s(370)*aux(78) 1111.29/291.69 s(380) =< s(371)*s(377) 1111.29/291.69 s(381) =< s(380) 1111.29/291.69 1111.29/291.69 with precondition: [V1=1,V>=0,V9>=0,V14>=0,V22>=0] 1111.29/291.69 1111.29/291.69 * Chain [52]: 1*s(398)+12*s(400)+5*s(401)+1*s(408)+1*s(409)+2*s(411)+6 1111.29/291.69 Such that:s(398) =< 1 1111.29/291.69 aux(81) =< V22 1111.29/291.69 aux(82) =< V9 1111.29/291.69 s(400) =< aux(82) 1111.29/291.69 s(401) =< aux(81) 1111.29/291.69 s(401) =< aux(82) 1111.29/291.69 s(407) =< aux(82) 1111.29/291.69 s(408) =< s(400)*aux(81) 1111.29/291.69 s(409) =< s(400)*aux(82) 1111.29/291.69 s(410) =< s(401)*s(407) 1111.29/291.69 s(411) =< s(410) 1111.29/291.69 1111.29/291.69 with precondition: [V1=1,V=0,V9>=0,V14>=2,V22>=0] 1111.29/291.69 1111.29/291.69 * Chain [51]: 2*s(412)+1*s(413)+7*s(415)+5*s(417)+5*s(422)+1*s(424)+1*s(425)+2*s(427)+6 1111.29/291.69 Such that:s(419) =< -V+V9 1111.29/291.69 s(417) =< -V+V22 1111.29/291.69 s(413) =< V+1 1111.29/291.69 s(418) =< V22 1111.29/291.69 aux(83) =< V 1111.29/291.69 aux(84) =< V9 1111.29/291.69 s(412) =< aux(83) 1111.29/291.69 s(417) =< s(419) 1111.29/291.69 s(415) =< aux(84) 1111.29/291.69 s(422) =< s(419) 1111.29/291.69 s(423) =< aux(84) 1111.29/291.69 s(424) =< s(422)*s(418) 1111.29/291.69 s(425) =< s(422)*aux(84) 1111.29/291.69 s(426) =< s(417)*s(423) 1111.29/291.69 s(427) =< s(426) 1111.29/291.69 1111.29/291.69 with precondition: [V1=1,V14=0,V>=1,V9>=0,V22>=V+1] 1111.29/291.69 1111.29/291.69 * Chain [50]: 1 1111.29/291.69 with precondition: [V1=2,V>=0,V9>=0,V14>=0,V22>=0] 1111.29/291.69 1111.29/291.69 * Chain [49]: 2*s(428)+1*s(429)+7*s(431)+5*s(433)+5*s(438)+1*s(440)+1*s(441)+2*s(443)+5 1111.29/291.69 Such that:s(435) =< -V1+V 1111.29/291.69 s(433) =< -V1+V14 1111.29/291.69 s(429) =< V1+1 1111.29/291.69 s(434) =< V14 1111.29/291.69 aux(85) =< V1 1111.29/291.69 aux(86) =< V 1111.29/291.69 s(428) =< aux(85) 1111.29/291.69 s(433) =< s(435) 1111.29/291.69 s(431) =< aux(86) 1111.29/291.69 s(438) =< s(435) 1111.29/291.69 s(439) =< aux(86) 1111.29/291.69 s(440) =< s(438)*s(434) 1111.29/291.69 s(441) =< s(438)*aux(86) 1111.29/291.69 s(442) =< s(433)*s(439) 1111.29/291.69 s(443) =< s(442) 1111.29/291.69 1111.29/291.69 with precondition: [V9=0,V1>=1,V>=0,V14>=V1+1] 1111.29/291.69 1111.29/291.69 1111.29/291.69 Closed-form bounds of start(V1,V,V9,V14,V22): 1111.29/291.69 ------------------------------------- 1111.29/291.69 * Chain [57] with precondition: [V1>=0] 1111.29/291.69 - Upper bound: 54*V1+22+3*V1*V1+9*V1*nat(V)+nat(V)*245+nat(V)*36*nat(V)+nat(V)*9*nat(V1+V)+nat(V)*2*nat(-V1+V)+nat(V)*4*nat(-V1+V14)+nat(V9)+nat(V14)*2+nat(V14)*2*nat(-V1+V)+nat(V1+V)*36+nat(V1+V)*3*nat(V1+V)+(V1+1)+nat(-V1+V)*10+nat(-V1+V14)*10 1111.29/291.69 - Complexity: n^2 1111.29/291.69 * Chain [56] with precondition: [V1=0,V9=0,V>=0,V14>=1] 1111.29/291.69 - Upper bound: 15*V+10+V*V+3*V*V14+5*V14 1111.29/291.69 - Complexity: n^2 1111.29/291.69 * Chain [55] with precondition: [V1=0,V>=0,V9>=2,V14>=0] 1111.29/291.69 - Upper bound: 15*V+10+V*V+3*V*V14+5*V14 1111.29/291.69 - Complexity: n^2 1111.29/291.69 * Chain [54] with precondition: [V1=0,V>=1] 1111.29/291.69 - Upper bound: 40*V+15+3*V*V+9*V*nat(V14)+nat(V14)*17 1111.29/291.69 - Complexity: n^2 1111.29/291.69 * Chain [53] with precondition: [V1=1,V>=0,V9>=0,V14>=0,V22>=0] 1111.29/291.69 - Upper bound: 19*V9+7+V9*V9+3*V9*V22+nat(-V+V9)*V9+2*V9*nat(-V+V22)+7*V22+nat(-V+V9)*V22+(V+1)+nat(-V+V9)*5+nat(-V+V22)*5 1111.29/291.69 - Complexity: n^2 1111.29/291.69 * Chain [52] with precondition: [V1=1,V=0,V9>=0,V14>=2,V22>=0] 1111.29/291.69 - Upper bound: 12*V9+7+V9*V9+3*V9*V22+5*V22 1111.29/291.69 - Complexity: n^2 1111.29/291.69 * Chain [51] with precondition: [V1=1,V14=0,V>=1,V9>=0,V22>=V+1] 1111.29/291.69 - Upper bound: 2*V+7*V9+6+nat(-V+V9)*V9+(-V+V22)*(2*V9)+nat(-V+V9)*V22+(V+1)+nat(-V+V9)*5+(-5*V+5*V22) 1111.29/291.69 - Complexity: n^2 1111.29/291.69 * Chain [50] with precondition: [V1=2,V>=0,V9>=0,V14>=0,V22>=0] 1111.29/291.69 - Upper bound: 1 1111.29/291.69 - Complexity: constant 1111.29/291.69 * Chain [49] with precondition: [V9=0,V1>=1,V>=0,V14>=V1+1] 1111.29/291.69 - Upper bound: 2*V1+7*V+5+nat(-V1+V)*V+(-V1+V14)*(2*V)+nat(-V1+V)*V14+(V1+1)+nat(-V1+V)*5+(-5*V1+5*V14) 1111.29/291.69 - Complexity: n^2 1111.29/291.69 1111.29/291.69 ### Maximum cost of start(V1,V,V9,V14,V22): max([nat(V)*2+4+max([nat(V)*5+max([nat(V)*8+5+nat(V)*nat(V)+nat(V14)*2+max([nat(V)*3*nat(V14)+nat(V14)*3,nat(V)*25+5+nat(V)*2*nat(V)+max([nat(V)*9*nat(V14)+nat(V14)*15,54*V1+7+3*V1*V1+9*V1*nat(V)+nat(V)*205+nat(V)*33*nat(V)+nat(V)*9*nat(V1+V)+nat(V)*2*nat(-V1+V)+nat(V)*4*nat(-V1+V14)+nat(V9)+nat(V14)*2*nat(-V1+V)+nat(V1+V)*36+nat(V1+V)*3*nat(V1+V)+(V1+1)+nat(-V1+V)*10+nat(-V1+V14)*10])]),nat(-V1+V)*nat(V)+2*V1+nat(V)*2*nat(-V1+V14)+nat(-V1+V)*nat(V14)+(V1+1)+nat(-V1+V)*5+nat(-V1+V14)*5]),nat(V9)*7+1+nat(-V+V9)*nat(V9)+nat(V9)*2*nat(-V+V22)+nat(-V+V9)*nat(V22)+nat(V+1)+nat(-V+V9)*5+nat(-V+V22)*5]),nat(-V+V9)*nat(V9)+nat(V9)*7+nat(V9)*2*nat(-V+V22)+nat(V22)*2+nat(-V+V9)*nat(V22)+nat(V+1)+nat(-V+V9)*5+nat(-V+V22)*5+(nat(V9)*12+6+nat(V9)*nat(V9)+nat(V9)*3*nat(V22)+nat(V22)*5)])+1 1111.29/291.69 Asymptotic class: n^2 1111.29/291.69 * Total analysis performed in 1062 ms. 1111.29/291.69 1111.29/291.69 1111.29/291.69 ---------------------------------------- 1111.29/291.69 1111.29/291.69 (10) 1111.29/291.69 BOUNDS(1, n^2) 1111.29/291.69 1111.29/291.69 ---------------------------------------- 1111.29/291.69 1111.29/291.69 (11) RenamingProof (BOTH BOUNDS(ID, ID)) 1111.29/291.69 Renamed function symbols to avoid clashes with predefined symbol. 1111.29/291.69 ---------------------------------------- 1111.29/291.69 1111.29/291.69 (12) 1111.29/291.69 Obligation: 1111.29/291.69 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1111.29/291.69 1111.29/291.69 1111.29/291.69 The TRS R consists of the following rules: 1111.29/291.69 1111.29/291.69 app(x, y) -> helpa(0', plus(length(x), length(y)), x, y) 1111.29/291.69 plus(x, 0') -> x 1111.29/291.69 plus(x, s(y)) -> s(plus(x, y)) 1111.29/291.69 length(nil) -> 0' 1111.29/291.69 length(cons(x, y)) -> s(length(y)) 1111.29/291.69 helpa(c, l, ys, zs) -> if(ge(c, l), c, l, ys, zs) 1111.29/291.69 ge(x, 0') -> true 1111.29/291.69 ge(0', s(x)) -> false 1111.29/291.69 ge(s(x), s(y)) -> ge(x, y) 1111.29/291.69 if(true, c, l, ys, zs) -> nil 1111.29/291.69 if(false, c, l, ys, zs) -> helpb(c, l, ys, zs) 1111.29/291.69 take(0', cons(x, xs), ys) -> x 1111.29/291.69 take(0', nil, cons(y, ys)) -> y 1111.29/291.69 take(s(c), cons(x, xs), ys) -> take(c, xs, ys) 1111.29/291.69 take(s(c), nil, cons(y, ys)) -> take(c, nil, ys) 1111.29/291.69 helpb(c, l, ys, zs) -> cons(take(c, ys, zs), helpa(s(c), l, ys, zs)) 1111.29/291.69 1111.29/291.69 S is empty. 1111.29/291.69 Rewrite Strategy: INNERMOST 1111.29/291.69 ---------------------------------------- 1111.29/291.69 1111.29/291.69 (13) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1111.29/291.69 Infered types. 1111.29/291.69 ---------------------------------------- 1111.29/291.69 1111.29/291.69 (14) 1111.29/291.69 Obligation: 1111.29/291.69 Innermost TRS: 1111.29/291.69 Rules: 1111.29/291.69 app(x, y) -> helpa(0', plus(length(x), length(y)), x, y) 1111.29/291.69 plus(x, 0') -> x 1111.29/291.69 plus(x, s(y)) -> s(plus(x, y)) 1111.29/291.69 length(nil) -> 0' 1111.29/291.69 length(cons(x, y)) -> s(length(y)) 1111.29/291.69 helpa(c, l, ys, zs) -> if(ge(c, l), c, l, ys, zs) 1111.29/291.69 ge(x, 0') -> true 1111.29/291.69 ge(0', s(x)) -> false 1111.29/291.69 ge(s(x), s(y)) -> ge(x, y) 1111.29/291.69 if(true, c, l, ys, zs) -> nil 1111.29/291.69 if(false, c, l, ys, zs) -> helpb(c, l, ys, zs) 1111.29/291.69 take(0', cons(x, xs), ys) -> x 1111.29/291.69 take(0', nil, cons(y, ys)) -> y 1111.29/291.69 take(s(c), cons(x, xs), ys) -> take(c, xs, ys) 1111.29/291.69 take(s(c), nil, cons(y, ys)) -> take(c, nil, ys) 1111.29/291.69 helpb(c, l, ys, zs) -> cons(take(c, ys, zs), helpa(s(c), l, ys, zs)) 1111.29/291.69 1111.29/291.69 Types: 1111.29/291.69 app :: nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 helpa :: 0':s -> 0':s -> nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 0' :: 0':s 1111.29/291.69 plus :: 0':s -> 0':s -> 0':s 1111.29/291.69 length :: nil:cons:xs -> 0':s 1111.29/291.69 s :: 0':s -> 0':s 1111.29/291.69 nil :: nil:cons:xs 1111.29/291.69 cons :: take -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 if :: true:false -> 0':s -> 0':s -> nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 ge :: 0':s -> 0':s -> true:false 1111.29/291.69 true :: true:false 1111.29/291.69 false :: true:false 1111.29/291.69 helpb :: 0':s -> 0':s -> nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 take :: 0':s -> nil:cons:xs -> nil:cons:xs -> take 1111.29/291.69 xs :: nil:cons:xs 1111.29/291.69 hole_nil:cons:xs1_0 :: nil:cons:xs 1111.29/291.69 hole_0':s2_0 :: 0':s 1111.29/291.69 hole_take3_0 :: take 1111.29/291.69 hole_true:false4_0 :: true:false 1111.29/291.69 gen_nil:cons:xs5_0 :: Nat -> nil:cons:xs 1111.29/291.69 gen_0':s6_0 :: Nat -> 0':s 1111.29/291.69 1111.29/291.69 ---------------------------------------- 1111.29/291.69 1111.29/291.69 (15) OrderProof (LOWER BOUND(ID)) 1111.29/291.69 Heuristically decided to analyse the following defined symbols: 1111.29/291.69 helpa, plus, length, ge, helpb, take 1111.29/291.69 1111.29/291.69 They will be analysed ascendingly in the following order: 1111.29/291.69 ge < helpa 1111.29/291.69 helpa = helpb 1111.29/291.69 take < helpb 1111.29/291.69 1111.29/291.69 ---------------------------------------- 1111.29/291.69 1111.29/291.69 (16) 1111.29/291.69 Obligation: 1111.29/291.69 Innermost TRS: 1111.29/291.69 Rules: 1111.29/291.69 app(x, y) -> helpa(0', plus(length(x), length(y)), x, y) 1111.29/291.69 plus(x, 0') -> x 1111.29/291.69 plus(x, s(y)) -> s(plus(x, y)) 1111.29/291.69 length(nil) -> 0' 1111.29/291.69 length(cons(x, y)) -> s(length(y)) 1111.29/291.69 helpa(c, l, ys, zs) -> if(ge(c, l), c, l, ys, zs) 1111.29/291.69 ge(x, 0') -> true 1111.29/291.69 ge(0', s(x)) -> false 1111.29/291.69 ge(s(x), s(y)) -> ge(x, y) 1111.29/291.69 if(true, c, l, ys, zs) -> nil 1111.29/291.69 if(false, c, l, ys, zs) -> helpb(c, l, ys, zs) 1111.29/291.69 take(0', cons(x, xs), ys) -> x 1111.29/291.69 take(0', nil, cons(y, ys)) -> y 1111.29/291.69 take(s(c), cons(x, xs), ys) -> take(c, xs, ys) 1111.29/291.69 take(s(c), nil, cons(y, ys)) -> take(c, nil, ys) 1111.29/291.69 helpb(c, l, ys, zs) -> cons(take(c, ys, zs), helpa(s(c), l, ys, zs)) 1111.29/291.69 1111.29/291.69 Types: 1111.29/291.69 app :: nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 helpa :: 0':s -> 0':s -> nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 0' :: 0':s 1111.29/291.69 plus :: 0':s -> 0':s -> 0':s 1111.29/291.69 length :: nil:cons:xs -> 0':s 1111.29/291.69 s :: 0':s -> 0':s 1111.29/291.69 nil :: nil:cons:xs 1111.29/291.69 cons :: take -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 if :: true:false -> 0':s -> 0':s -> nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 ge :: 0':s -> 0':s -> true:false 1111.29/291.69 true :: true:false 1111.29/291.69 false :: true:false 1111.29/291.69 helpb :: 0':s -> 0':s -> nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 take :: 0':s -> nil:cons:xs -> nil:cons:xs -> take 1111.29/291.69 xs :: nil:cons:xs 1111.29/291.69 hole_nil:cons:xs1_0 :: nil:cons:xs 1111.29/291.69 hole_0':s2_0 :: 0':s 1111.29/291.69 hole_take3_0 :: take 1111.29/291.69 hole_true:false4_0 :: true:false 1111.29/291.69 gen_nil:cons:xs5_0 :: Nat -> nil:cons:xs 1111.29/291.69 gen_0':s6_0 :: Nat -> 0':s 1111.29/291.69 1111.29/291.69 1111.29/291.69 Generator Equations: 1111.29/291.69 gen_nil:cons:xs5_0(0) <=> nil 1111.29/291.69 gen_nil:cons:xs5_0(+(x, 1)) <=> cons(hole_take3_0, gen_nil:cons:xs5_0(x)) 1111.29/291.69 gen_0':s6_0(0) <=> 0' 1111.29/291.69 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 1111.29/291.69 1111.29/291.69 1111.29/291.69 The following defined symbols remain to be analysed: 1111.29/291.69 plus, helpa, length, ge, helpb, take 1111.29/291.69 1111.29/291.69 They will be analysed ascendingly in the following order: 1111.29/291.69 ge < helpa 1111.29/291.69 helpa = helpb 1111.29/291.69 take < helpb 1111.29/291.69 1111.29/291.69 ---------------------------------------- 1111.29/291.69 1111.29/291.69 (17) RewriteLemmaProof (LOWER BOUND(ID)) 1111.29/291.69 Proved the following rewrite lemma: 1111.29/291.69 plus(gen_0':s6_0(a), gen_0':s6_0(n8_0)) -> gen_0':s6_0(+(n8_0, a)), rt in Omega(1 + n8_0) 1111.29/291.69 1111.29/291.69 Induction Base: 1111.29/291.69 plus(gen_0':s6_0(a), gen_0':s6_0(0)) ->_R^Omega(1) 1111.29/291.69 gen_0':s6_0(a) 1111.29/291.69 1111.29/291.69 Induction Step: 1111.29/291.69 plus(gen_0':s6_0(a), gen_0':s6_0(+(n8_0, 1))) ->_R^Omega(1) 1111.29/291.69 s(plus(gen_0':s6_0(a), gen_0':s6_0(n8_0))) ->_IH 1111.29/291.69 s(gen_0':s6_0(+(a, c9_0))) 1111.29/291.69 1111.29/291.69 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1111.29/291.69 ---------------------------------------- 1111.29/291.69 1111.29/291.69 (18) 1111.29/291.69 Complex Obligation (BEST) 1111.29/291.69 1111.29/291.69 ---------------------------------------- 1111.29/291.69 1111.29/291.69 (19) 1111.29/291.69 Obligation: 1111.29/291.69 Proved the lower bound n^1 for the following obligation: 1111.29/291.69 1111.29/291.69 Innermost TRS: 1111.29/291.69 Rules: 1111.29/291.69 app(x, y) -> helpa(0', plus(length(x), length(y)), x, y) 1111.29/291.69 plus(x, 0') -> x 1111.29/291.69 plus(x, s(y)) -> s(plus(x, y)) 1111.29/291.69 length(nil) -> 0' 1111.29/291.69 length(cons(x, y)) -> s(length(y)) 1111.29/291.69 helpa(c, l, ys, zs) -> if(ge(c, l), c, l, ys, zs) 1111.29/291.69 ge(x, 0') -> true 1111.29/291.69 ge(0', s(x)) -> false 1111.29/291.69 ge(s(x), s(y)) -> ge(x, y) 1111.29/291.69 if(true, c, l, ys, zs) -> nil 1111.29/291.69 if(false, c, l, ys, zs) -> helpb(c, l, ys, zs) 1111.29/291.69 take(0', cons(x, xs), ys) -> x 1111.29/291.69 take(0', nil, cons(y, ys)) -> y 1111.29/291.69 take(s(c), cons(x, xs), ys) -> take(c, xs, ys) 1111.29/291.69 take(s(c), nil, cons(y, ys)) -> take(c, nil, ys) 1111.29/291.69 helpb(c, l, ys, zs) -> cons(take(c, ys, zs), helpa(s(c), l, ys, zs)) 1111.29/291.69 1111.29/291.69 Types: 1111.29/291.69 app :: nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 helpa :: 0':s -> 0':s -> nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 0' :: 0':s 1111.29/291.69 plus :: 0':s -> 0':s -> 0':s 1111.29/291.69 length :: nil:cons:xs -> 0':s 1111.29/291.69 s :: 0':s -> 0':s 1111.29/291.69 nil :: nil:cons:xs 1111.29/291.69 cons :: take -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 if :: true:false -> 0':s -> 0':s -> nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 ge :: 0':s -> 0':s -> true:false 1111.29/291.69 true :: true:false 1111.29/291.69 false :: true:false 1111.29/291.69 helpb :: 0':s -> 0':s -> nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 take :: 0':s -> nil:cons:xs -> nil:cons:xs -> take 1111.29/291.69 xs :: nil:cons:xs 1111.29/291.69 hole_nil:cons:xs1_0 :: nil:cons:xs 1111.29/291.69 hole_0':s2_0 :: 0':s 1111.29/291.69 hole_take3_0 :: take 1111.29/291.69 hole_true:false4_0 :: true:false 1111.29/291.69 gen_nil:cons:xs5_0 :: Nat -> nil:cons:xs 1111.29/291.69 gen_0':s6_0 :: Nat -> 0':s 1111.29/291.69 1111.29/291.69 1111.29/291.69 Generator Equations: 1111.29/291.69 gen_nil:cons:xs5_0(0) <=> nil 1111.29/291.69 gen_nil:cons:xs5_0(+(x, 1)) <=> cons(hole_take3_0, gen_nil:cons:xs5_0(x)) 1111.29/291.69 gen_0':s6_0(0) <=> 0' 1111.29/291.69 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 1111.29/291.69 1111.29/291.69 1111.29/291.69 The following defined symbols remain to be analysed: 1111.29/291.69 plus, helpa, length, ge, helpb, take 1111.29/291.69 1111.29/291.69 They will be analysed ascendingly in the following order: 1111.29/291.69 ge < helpa 1111.29/291.69 helpa = helpb 1111.29/291.69 take < helpb 1111.29/291.69 1111.29/291.69 ---------------------------------------- 1111.29/291.69 1111.29/291.69 (20) LowerBoundPropagationProof (FINISHED) 1111.29/291.69 Propagated lower bound. 1111.29/291.69 ---------------------------------------- 1111.29/291.69 1111.29/291.69 (21) 1111.29/291.69 BOUNDS(n^1, INF) 1111.29/291.69 1111.29/291.69 ---------------------------------------- 1111.29/291.69 1111.29/291.69 (22) 1111.29/291.69 Obligation: 1111.29/291.69 Innermost TRS: 1111.29/291.69 Rules: 1111.29/291.69 app(x, y) -> helpa(0', plus(length(x), length(y)), x, y) 1111.29/291.69 plus(x, 0') -> x 1111.29/291.69 plus(x, s(y)) -> s(plus(x, y)) 1111.29/291.69 length(nil) -> 0' 1111.29/291.69 length(cons(x, y)) -> s(length(y)) 1111.29/291.69 helpa(c, l, ys, zs) -> if(ge(c, l), c, l, ys, zs) 1111.29/291.69 ge(x, 0') -> true 1111.29/291.69 ge(0', s(x)) -> false 1111.29/291.69 ge(s(x), s(y)) -> ge(x, y) 1111.29/291.69 if(true, c, l, ys, zs) -> nil 1111.29/291.69 if(false, c, l, ys, zs) -> helpb(c, l, ys, zs) 1111.29/291.69 take(0', cons(x, xs), ys) -> x 1111.29/291.69 take(0', nil, cons(y, ys)) -> y 1111.29/291.69 take(s(c), cons(x, xs), ys) -> take(c, xs, ys) 1111.29/291.69 take(s(c), nil, cons(y, ys)) -> take(c, nil, ys) 1111.29/291.69 helpb(c, l, ys, zs) -> cons(take(c, ys, zs), helpa(s(c), l, ys, zs)) 1111.29/291.69 1111.29/291.69 Types: 1111.29/291.69 app :: nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 helpa :: 0':s -> 0':s -> nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 0' :: 0':s 1111.29/291.69 plus :: 0':s -> 0':s -> 0':s 1111.29/291.69 length :: nil:cons:xs -> 0':s 1111.29/291.69 s :: 0':s -> 0':s 1111.29/291.69 nil :: nil:cons:xs 1111.29/291.69 cons :: take -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 if :: true:false -> 0':s -> 0':s -> nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 ge :: 0':s -> 0':s -> true:false 1111.29/291.69 true :: true:false 1111.29/291.69 false :: true:false 1111.29/291.69 helpb :: 0':s -> 0':s -> nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 take :: 0':s -> nil:cons:xs -> nil:cons:xs -> take 1111.29/291.69 xs :: nil:cons:xs 1111.29/291.69 hole_nil:cons:xs1_0 :: nil:cons:xs 1111.29/291.69 hole_0':s2_0 :: 0':s 1111.29/291.69 hole_take3_0 :: take 1111.29/291.69 hole_true:false4_0 :: true:false 1111.29/291.69 gen_nil:cons:xs5_0 :: Nat -> nil:cons:xs 1111.29/291.69 gen_0':s6_0 :: Nat -> 0':s 1111.29/291.69 1111.29/291.69 1111.29/291.69 Lemmas: 1111.29/291.69 plus(gen_0':s6_0(a), gen_0':s6_0(n8_0)) -> gen_0':s6_0(+(n8_0, a)), rt in Omega(1 + n8_0) 1111.29/291.69 1111.29/291.69 1111.29/291.69 Generator Equations: 1111.29/291.69 gen_nil:cons:xs5_0(0) <=> nil 1111.29/291.69 gen_nil:cons:xs5_0(+(x, 1)) <=> cons(hole_take3_0, gen_nil:cons:xs5_0(x)) 1111.29/291.69 gen_0':s6_0(0) <=> 0' 1111.29/291.69 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 1111.29/291.69 1111.29/291.69 1111.29/291.69 The following defined symbols remain to be analysed: 1111.29/291.69 length, helpa, ge, helpb, take 1111.29/291.69 1111.29/291.69 They will be analysed ascendingly in the following order: 1111.29/291.69 ge < helpa 1111.29/291.69 helpa = helpb 1111.29/291.69 take < helpb 1111.29/291.69 1111.29/291.69 ---------------------------------------- 1111.29/291.69 1111.29/291.69 (23) RewriteLemmaProof (LOWER BOUND(ID)) 1111.29/291.69 Proved the following rewrite lemma: 1111.29/291.69 length(gen_nil:cons:xs5_0(n857_0)) -> gen_0':s6_0(n857_0), rt in Omega(1 + n857_0) 1111.29/291.69 1111.29/291.69 Induction Base: 1111.29/291.69 length(gen_nil:cons:xs5_0(0)) ->_R^Omega(1) 1111.29/291.69 0' 1111.29/291.69 1111.29/291.69 Induction Step: 1111.29/291.69 length(gen_nil:cons:xs5_0(+(n857_0, 1))) ->_R^Omega(1) 1111.29/291.69 s(length(gen_nil:cons:xs5_0(n857_0))) ->_IH 1111.29/291.69 s(gen_0':s6_0(c858_0)) 1111.29/291.69 1111.29/291.69 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1111.29/291.69 ---------------------------------------- 1111.29/291.69 1111.29/291.69 (24) 1111.29/291.69 Obligation: 1111.29/291.69 Innermost TRS: 1111.29/291.69 Rules: 1111.29/291.69 app(x, y) -> helpa(0', plus(length(x), length(y)), x, y) 1111.29/291.69 plus(x, 0') -> x 1111.29/291.69 plus(x, s(y)) -> s(plus(x, y)) 1111.29/291.69 length(nil) -> 0' 1111.29/291.69 length(cons(x, y)) -> s(length(y)) 1111.29/291.69 helpa(c, l, ys, zs) -> if(ge(c, l), c, l, ys, zs) 1111.29/291.69 ge(x, 0') -> true 1111.29/291.69 ge(0', s(x)) -> false 1111.29/291.69 ge(s(x), s(y)) -> ge(x, y) 1111.29/291.69 if(true, c, l, ys, zs) -> nil 1111.29/291.69 if(false, c, l, ys, zs) -> helpb(c, l, ys, zs) 1111.29/291.69 take(0', cons(x, xs), ys) -> x 1111.29/291.69 take(0', nil, cons(y, ys)) -> y 1111.29/291.69 take(s(c), cons(x, xs), ys) -> take(c, xs, ys) 1111.29/291.69 take(s(c), nil, cons(y, ys)) -> take(c, nil, ys) 1111.29/291.69 helpb(c, l, ys, zs) -> cons(take(c, ys, zs), helpa(s(c), l, ys, zs)) 1111.29/291.69 1111.29/291.69 Types: 1111.29/291.69 app :: nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 helpa :: 0':s -> 0':s -> nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 0' :: 0':s 1111.29/291.69 plus :: 0':s -> 0':s -> 0':s 1111.29/291.69 length :: nil:cons:xs -> 0':s 1111.29/291.69 s :: 0':s -> 0':s 1111.29/291.69 nil :: nil:cons:xs 1111.29/291.69 cons :: take -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 if :: true:false -> 0':s -> 0':s -> nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 ge :: 0':s -> 0':s -> true:false 1111.29/291.69 true :: true:false 1111.29/291.69 false :: true:false 1111.29/291.69 helpb :: 0':s -> 0':s -> nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 take :: 0':s -> nil:cons:xs -> nil:cons:xs -> take 1111.29/291.69 xs :: nil:cons:xs 1111.29/291.69 hole_nil:cons:xs1_0 :: nil:cons:xs 1111.29/291.69 hole_0':s2_0 :: 0':s 1111.29/291.69 hole_take3_0 :: take 1111.29/291.69 hole_true:false4_0 :: true:false 1111.29/291.69 gen_nil:cons:xs5_0 :: Nat -> nil:cons:xs 1111.29/291.69 gen_0':s6_0 :: Nat -> 0':s 1111.29/291.69 1111.29/291.69 1111.29/291.69 Lemmas: 1111.29/291.69 plus(gen_0':s6_0(a), gen_0':s6_0(n8_0)) -> gen_0':s6_0(+(n8_0, a)), rt in Omega(1 + n8_0) 1111.29/291.69 length(gen_nil:cons:xs5_0(n857_0)) -> gen_0':s6_0(n857_0), rt in Omega(1 + n857_0) 1111.29/291.69 1111.29/291.69 1111.29/291.69 Generator Equations: 1111.29/291.69 gen_nil:cons:xs5_0(0) <=> nil 1111.29/291.69 gen_nil:cons:xs5_0(+(x, 1)) <=> cons(hole_take3_0, gen_nil:cons:xs5_0(x)) 1111.29/291.69 gen_0':s6_0(0) <=> 0' 1111.29/291.69 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 1111.29/291.69 1111.29/291.69 1111.29/291.69 The following defined symbols remain to be analysed: 1111.29/291.69 ge, helpa, helpb, take 1111.29/291.69 1111.29/291.69 They will be analysed ascendingly in the following order: 1111.29/291.69 ge < helpa 1111.29/291.69 helpa = helpb 1111.29/291.69 take < helpb 1111.29/291.69 1111.29/291.69 ---------------------------------------- 1111.29/291.69 1111.29/291.69 (25) RewriteLemmaProof (LOWER BOUND(ID)) 1111.29/291.69 Proved the following rewrite lemma: 1111.29/291.69 ge(gen_0':s6_0(n1150_0), gen_0':s6_0(n1150_0)) -> true, rt in Omega(1 + n1150_0) 1111.29/291.69 1111.29/291.69 Induction Base: 1111.29/291.69 ge(gen_0':s6_0(0), gen_0':s6_0(0)) ->_R^Omega(1) 1111.29/291.69 true 1111.29/291.69 1111.29/291.69 Induction Step: 1111.29/291.69 ge(gen_0':s6_0(+(n1150_0, 1)), gen_0':s6_0(+(n1150_0, 1))) ->_R^Omega(1) 1111.29/291.69 ge(gen_0':s6_0(n1150_0), gen_0':s6_0(n1150_0)) ->_IH 1111.29/291.69 true 1111.29/291.69 1111.29/291.69 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1111.29/291.69 ---------------------------------------- 1111.29/291.69 1111.29/291.69 (26) 1111.29/291.69 Obligation: 1111.29/291.69 Innermost TRS: 1111.29/291.69 Rules: 1111.29/291.69 app(x, y) -> helpa(0', plus(length(x), length(y)), x, y) 1111.29/291.69 plus(x, 0') -> x 1111.29/291.69 plus(x, s(y)) -> s(plus(x, y)) 1111.29/291.69 length(nil) -> 0' 1111.29/291.69 length(cons(x, y)) -> s(length(y)) 1111.29/291.69 helpa(c, l, ys, zs) -> if(ge(c, l), c, l, ys, zs) 1111.29/291.69 ge(x, 0') -> true 1111.29/291.69 ge(0', s(x)) -> false 1111.29/291.69 ge(s(x), s(y)) -> ge(x, y) 1111.29/291.69 if(true, c, l, ys, zs) -> nil 1111.29/291.69 if(false, c, l, ys, zs) -> helpb(c, l, ys, zs) 1111.29/291.69 take(0', cons(x, xs), ys) -> x 1111.29/291.69 take(0', nil, cons(y, ys)) -> y 1111.29/291.69 take(s(c), cons(x, xs), ys) -> take(c, xs, ys) 1111.29/291.69 take(s(c), nil, cons(y, ys)) -> take(c, nil, ys) 1111.29/291.69 helpb(c, l, ys, zs) -> cons(take(c, ys, zs), helpa(s(c), l, ys, zs)) 1111.29/291.69 1111.29/291.69 Types: 1111.29/291.69 app :: nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 helpa :: 0':s -> 0':s -> nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 0' :: 0':s 1111.29/291.69 plus :: 0':s -> 0':s -> 0':s 1111.29/291.69 length :: nil:cons:xs -> 0':s 1111.29/291.69 s :: 0':s -> 0':s 1111.29/291.69 nil :: nil:cons:xs 1111.29/291.69 cons :: take -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 if :: true:false -> 0':s -> 0':s -> nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 ge :: 0':s -> 0':s -> true:false 1111.29/291.69 true :: true:false 1111.29/291.69 false :: true:false 1111.29/291.69 helpb :: 0':s -> 0':s -> nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 take :: 0':s -> nil:cons:xs -> nil:cons:xs -> take 1111.29/291.69 xs :: nil:cons:xs 1111.29/291.69 hole_nil:cons:xs1_0 :: nil:cons:xs 1111.29/291.69 hole_0':s2_0 :: 0':s 1111.29/291.69 hole_take3_0 :: take 1111.29/291.69 hole_true:false4_0 :: true:false 1111.29/291.69 gen_nil:cons:xs5_0 :: Nat -> nil:cons:xs 1111.29/291.69 gen_0':s6_0 :: Nat -> 0':s 1111.29/291.69 1111.29/291.69 1111.29/291.69 Lemmas: 1111.29/291.69 plus(gen_0':s6_0(a), gen_0':s6_0(n8_0)) -> gen_0':s6_0(+(n8_0, a)), rt in Omega(1 + n8_0) 1111.29/291.69 length(gen_nil:cons:xs5_0(n857_0)) -> gen_0':s6_0(n857_0), rt in Omega(1 + n857_0) 1111.29/291.69 ge(gen_0':s6_0(n1150_0), gen_0':s6_0(n1150_0)) -> true, rt in Omega(1 + n1150_0) 1111.29/291.69 1111.29/291.69 1111.29/291.69 Generator Equations: 1111.29/291.69 gen_nil:cons:xs5_0(0) <=> nil 1111.29/291.69 gen_nil:cons:xs5_0(+(x, 1)) <=> cons(hole_take3_0, gen_nil:cons:xs5_0(x)) 1111.29/291.69 gen_0':s6_0(0) <=> 0' 1111.29/291.69 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 1111.29/291.69 1111.29/291.69 1111.29/291.69 The following defined symbols remain to be analysed: 1111.29/291.69 take, helpa, helpb 1111.29/291.69 1111.29/291.69 They will be analysed ascendingly in the following order: 1111.29/291.69 helpa = helpb 1111.29/291.69 take < helpb 1111.29/291.69 1111.29/291.69 ---------------------------------------- 1111.29/291.69 1111.29/291.69 (27) RewriteLemmaProof (LOWER BOUND(ID)) 1111.29/291.69 Proved the following rewrite lemma: 1111.29/291.69 take(gen_0':s6_0(n1472_0), gen_nil:cons:xs5_0(0), gen_nil:cons:xs5_0(+(1, n1472_0))) -> hole_take3_0, rt in Omega(1 + n1472_0) 1111.29/291.69 1111.29/291.69 Induction Base: 1111.29/291.69 take(gen_0':s6_0(0), gen_nil:cons:xs5_0(0), gen_nil:cons:xs5_0(+(1, 0))) ->_R^Omega(1) 1111.29/291.69 hole_take3_0 1111.29/291.69 1111.29/291.69 Induction Step: 1111.29/291.69 take(gen_0':s6_0(+(n1472_0, 1)), gen_nil:cons:xs5_0(0), gen_nil:cons:xs5_0(+(1, +(n1472_0, 1)))) ->_R^Omega(1) 1111.29/291.69 take(gen_0':s6_0(n1472_0), nil, gen_nil:cons:xs5_0(+(1, n1472_0))) ->_IH 1111.29/291.69 hole_take3_0 1111.29/291.69 1111.29/291.69 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1111.29/291.69 ---------------------------------------- 1111.29/291.69 1111.29/291.69 (28) 1111.29/291.69 Obligation: 1111.29/291.69 Innermost TRS: 1111.29/291.69 Rules: 1111.29/291.69 app(x, y) -> helpa(0', plus(length(x), length(y)), x, y) 1111.29/291.69 plus(x, 0') -> x 1111.29/291.69 plus(x, s(y)) -> s(plus(x, y)) 1111.29/291.69 length(nil) -> 0' 1111.29/291.69 length(cons(x, y)) -> s(length(y)) 1111.29/291.69 helpa(c, l, ys, zs) -> if(ge(c, l), c, l, ys, zs) 1111.29/291.69 ge(x, 0') -> true 1111.29/291.69 ge(0', s(x)) -> false 1111.29/291.69 ge(s(x), s(y)) -> ge(x, y) 1111.29/291.69 if(true, c, l, ys, zs) -> nil 1111.29/291.69 if(false, c, l, ys, zs) -> helpb(c, l, ys, zs) 1111.29/291.69 take(0', cons(x, xs), ys) -> x 1111.29/291.69 take(0', nil, cons(y, ys)) -> y 1111.29/291.69 take(s(c), cons(x, xs), ys) -> take(c, xs, ys) 1111.29/291.69 take(s(c), nil, cons(y, ys)) -> take(c, nil, ys) 1111.29/291.69 helpb(c, l, ys, zs) -> cons(take(c, ys, zs), helpa(s(c), l, ys, zs)) 1111.29/291.69 1111.29/291.69 Types: 1111.29/291.69 app :: nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 helpa :: 0':s -> 0':s -> nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 0' :: 0':s 1111.29/291.69 plus :: 0':s -> 0':s -> 0':s 1111.29/291.69 length :: nil:cons:xs -> 0':s 1111.29/291.69 s :: 0':s -> 0':s 1111.29/291.69 nil :: nil:cons:xs 1111.29/291.69 cons :: take -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 if :: true:false -> 0':s -> 0':s -> nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 ge :: 0':s -> 0':s -> true:false 1111.29/291.69 true :: true:false 1111.29/291.69 false :: true:false 1111.29/291.69 helpb :: 0':s -> 0':s -> nil:cons:xs -> nil:cons:xs -> nil:cons:xs 1111.29/291.69 take :: 0':s -> nil:cons:xs -> nil:cons:xs -> take 1111.29/291.69 xs :: nil:cons:xs 1111.29/291.69 hole_nil:cons:xs1_0 :: nil:cons:xs 1111.29/291.69 hole_0':s2_0 :: 0':s 1111.29/291.69 hole_take3_0 :: take 1111.29/291.69 hole_true:false4_0 :: true:false 1111.29/291.69 gen_nil:cons:xs5_0 :: Nat -> nil:cons:xs 1111.29/291.69 gen_0':s6_0 :: Nat -> 0':s 1111.29/291.69 1111.29/291.69 1111.29/291.69 Lemmas: 1111.29/291.69 plus(gen_0':s6_0(a), gen_0':s6_0(n8_0)) -> gen_0':s6_0(+(n8_0, a)), rt in Omega(1 + n8_0) 1111.29/291.69 length(gen_nil:cons:xs5_0(n857_0)) -> gen_0':s6_0(n857_0), rt in Omega(1 + n857_0) 1111.29/291.69 ge(gen_0':s6_0(n1150_0), gen_0':s6_0(n1150_0)) -> true, rt in Omega(1 + n1150_0) 1111.29/291.69 take(gen_0':s6_0(n1472_0), gen_nil:cons:xs5_0(0), gen_nil:cons:xs5_0(+(1, n1472_0))) -> hole_take3_0, rt in Omega(1 + n1472_0) 1111.29/291.69 1111.29/291.69 1111.29/291.69 Generator Equations: 1111.29/291.69 gen_nil:cons:xs5_0(0) <=> nil 1111.29/291.69 gen_nil:cons:xs5_0(+(x, 1)) <=> cons(hole_take3_0, gen_nil:cons:xs5_0(x)) 1111.29/291.69 gen_0':s6_0(0) <=> 0' 1111.29/291.69 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 1111.29/291.69 1111.29/291.69 1111.29/291.69 The following defined symbols remain to be analysed: 1111.29/291.69 helpb, helpa 1111.29/291.69 1111.29/291.69 They will be analysed ascendingly in the following order: 1111.29/291.69 helpa = helpb 1111.42/291.75 EOF