914.76/294.47 WORST_CASE(Omega(n^1), O(n^3)) 914.86/294.49 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 914.86/294.49 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 914.86/294.49 914.86/294.49 914.86/294.49 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^3). 914.86/294.49 914.86/294.49 (0) CpxTRS 914.86/294.49 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 914.86/294.49 (2) CpxWeightedTrs 914.86/294.49 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 914.86/294.49 (4) CpxTypedWeightedTrs 914.86/294.49 (5) CompletionProof [UPPER BOUND(ID), 0 ms] 914.86/294.49 (6) CpxTypedWeightedCompleteTrs 914.86/294.49 (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 1 ms] 914.86/294.49 (8) CpxRNTS 914.86/294.49 (9) CompleteCoflocoProof [FINISHED, 3657 ms] 914.86/294.49 (10) BOUNDS(1, n^3) 914.86/294.49 (11) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 914.86/294.49 (12) CpxTRS 914.86/294.49 (13) SlicingProof [LOWER BOUND(ID), 0 ms] 914.86/294.49 (14) CpxTRS 914.86/294.49 (15) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 914.86/294.49 (16) typed CpxTrs 914.86/294.49 (17) OrderProof [LOWER BOUND(ID), 0 ms] 914.86/294.49 (18) typed CpxTrs 914.86/294.49 (19) RewriteLemmaProof [LOWER BOUND(ID), 288 ms] 914.86/294.49 (20) BEST 914.86/294.49 (21) proven lower bound 914.86/294.49 (22) LowerBoundPropagationProof [FINISHED, 0 ms] 914.86/294.49 (23) BOUNDS(n^1, INF) 914.86/294.49 (24) typed CpxTrs 914.86/294.49 (25) RewriteLemmaProof [LOWER BOUND(ID), 30 ms] 914.86/294.49 (26) typed CpxTrs 914.86/294.49 (27) RewriteLemmaProof [LOWER BOUND(ID), 47 ms] 914.86/294.49 (28) typed CpxTrs 914.86/294.49 914.86/294.49 914.86/294.49 ---------------------------------------- 914.86/294.49 914.86/294.49 (0) 914.86/294.49 Obligation: 914.86/294.49 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^3). 914.86/294.49 914.86/294.49 914.86/294.49 The TRS R consists of the following rules: 914.86/294.49 914.86/294.49 lessElements(l, t) -> lessE(l, t, 0) 914.86/294.49 lessE(l, t, n) -> if(le(length(l), n), le(length(toList(t)), n), l, t, n) 914.86/294.49 if(true, b, l, t, n) -> l 914.86/294.49 if(false, true, l, t, n) -> t 914.86/294.49 if(false, false, l, t, n) -> lessE(l, t, s(n)) 914.86/294.49 length(nil) -> 0 914.86/294.49 length(cons(n, l)) -> s(length(l)) 914.86/294.49 toList(leaf) -> nil 914.86/294.49 toList(node(t1, n, t2)) -> append(toList(t1), cons(n, toList(t2))) 914.86/294.49 append(nil, l2) -> l2 914.86/294.49 append(cons(n, l1), l2) -> cons(n, append(l1, l2)) 914.86/294.49 le(s(n), 0) -> false 914.86/294.49 le(0, m) -> true 914.86/294.49 le(s(n), s(m)) -> le(n, m) 914.86/294.49 a -> c 914.86/294.49 a -> d 914.86/294.49 914.86/294.49 S is empty. 914.86/294.49 Rewrite Strategy: INNERMOST 914.86/294.49 ---------------------------------------- 914.86/294.49 914.86/294.49 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 914.86/294.49 Transformed relative TRS to weighted TRS 914.86/294.49 ---------------------------------------- 914.86/294.49 914.86/294.49 (2) 914.86/294.49 Obligation: 914.86/294.49 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^3). 914.86/294.49 914.86/294.49 914.86/294.49 The TRS R consists of the following rules: 914.86/294.49 914.86/294.49 lessElements(l, t) -> lessE(l, t, 0) [1] 914.86/294.49 lessE(l, t, n) -> if(le(length(l), n), le(length(toList(t)), n), l, t, n) [1] 914.86/294.49 if(true, b, l, t, n) -> l [1] 914.86/294.49 if(false, true, l, t, n) -> t [1] 914.86/294.49 if(false, false, l, t, n) -> lessE(l, t, s(n)) [1] 914.86/294.49 length(nil) -> 0 [1] 914.86/294.49 length(cons(n, l)) -> s(length(l)) [1] 914.86/294.49 toList(leaf) -> nil [1] 914.86/294.49 toList(node(t1, n, t2)) -> append(toList(t1), cons(n, toList(t2))) [1] 914.86/294.49 append(nil, l2) -> l2 [1] 914.86/294.49 append(cons(n, l1), l2) -> cons(n, append(l1, l2)) [1] 914.86/294.49 le(s(n), 0) -> false [1] 914.86/294.49 le(0, m) -> true [1] 914.86/294.49 le(s(n), s(m)) -> le(n, m) [1] 914.86/294.49 a -> c [1] 914.86/294.49 a -> d [1] 914.86/294.49 914.86/294.49 Rewrite Strategy: INNERMOST 914.86/294.49 ---------------------------------------- 914.86/294.49 914.86/294.49 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 914.86/294.49 Infered types. 914.86/294.49 ---------------------------------------- 914.86/294.49 914.86/294.49 (4) 914.86/294.49 Obligation: 914.86/294.49 Runtime Complexity Weighted TRS with Types. 914.86/294.49 The TRS R consists of the following rules: 914.86/294.49 914.86/294.49 lessElements(l, t) -> lessE(l, t, 0) [1] 914.86/294.49 lessE(l, t, n) -> if(le(length(l), n), le(length(toList(t)), n), l, t, n) [1] 914.86/294.49 if(true, b, l, t, n) -> l [1] 914.86/294.49 if(false, true, l, t, n) -> t [1] 914.86/294.49 if(false, false, l, t, n) -> lessE(l, t, s(n)) [1] 914.86/294.49 length(nil) -> 0 [1] 914.86/294.49 length(cons(n, l)) -> s(length(l)) [1] 914.86/294.49 toList(leaf) -> nil [1] 914.86/294.49 toList(node(t1, n, t2)) -> append(toList(t1), cons(n, toList(t2))) [1] 914.86/294.49 append(nil, l2) -> l2 [1] 914.86/294.49 append(cons(n, l1), l2) -> cons(n, append(l1, l2)) [1] 914.86/294.49 le(s(n), 0) -> false [1] 914.86/294.49 le(0, m) -> true [1] 914.86/294.49 le(s(n), s(m)) -> le(n, m) [1] 914.86/294.49 a -> c [1] 914.86/294.49 a -> d [1] 914.86/294.49 914.86/294.49 The TRS has the following type information: 914.86/294.49 lessElements :: nil:cons:leaf:node -> nil:cons:leaf:node -> nil:cons:leaf:node 914.86/294.49 lessE :: nil:cons:leaf:node -> nil:cons:leaf:node -> 0:s -> nil:cons:leaf:node 914.86/294.49 0 :: 0:s 914.86/294.49 if :: true:false -> true:false -> nil:cons:leaf:node -> nil:cons:leaf:node -> 0:s -> nil:cons:leaf:node 914.86/294.49 le :: 0:s -> 0:s -> true:false 914.86/294.49 length :: nil:cons:leaf:node -> 0:s 914.86/294.49 toList :: nil:cons:leaf:node -> nil:cons:leaf:node 914.86/294.49 true :: true:false 914.86/294.49 false :: true:false 914.86/294.49 s :: 0:s -> 0:s 914.86/294.49 nil :: nil:cons:leaf:node 914.86/294.49 cons :: a -> nil:cons:leaf:node -> nil:cons:leaf:node 914.86/294.49 leaf :: nil:cons:leaf:node 914.86/294.49 node :: nil:cons:leaf:node -> a -> nil:cons:leaf:node -> nil:cons:leaf:node 914.86/294.49 append :: nil:cons:leaf:node -> nil:cons:leaf:node -> nil:cons:leaf:node 914.86/294.49 a :: c:d 914.86/294.49 c :: c:d 914.86/294.49 d :: c:d 914.86/294.49 914.86/294.49 Rewrite Strategy: INNERMOST 914.86/294.49 ---------------------------------------- 914.86/294.49 914.86/294.49 (5) CompletionProof (UPPER BOUND(ID)) 914.86/294.49 The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: 914.86/294.49 914.86/294.49 length(v0) -> null_length [0] 914.86/294.49 toList(v0) -> null_toList [0] 914.86/294.49 append(v0, v1) -> null_append [0] 914.86/294.49 le(v0, v1) -> null_le [0] 914.86/294.49 if(v0, v1, v2, v3, v4) -> null_if [0] 914.86/294.49 914.86/294.49 And the following fresh constants: null_length, null_toList, null_append, null_le, null_if, const 914.86/294.49 914.86/294.49 ---------------------------------------- 914.86/294.49 914.86/294.49 (6) 914.86/294.49 Obligation: 914.86/294.49 Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: 914.86/294.49 914.86/294.49 Runtime Complexity Weighted TRS with Types. 914.86/294.49 The TRS R consists of the following rules: 914.86/294.49 914.86/294.49 lessElements(l, t) -> lessE(l, t, 0) [1] 914.86/294.49 lessE(l, t, n) -> if(le(length(l), n), le(length(toList(t)), n), l, t, n) [1] 914.86/294.49 if(true, b, l, t, n) -> l [1] 914.86/294.49 if(false, true, l, t, n) -> t [1] 914.86/294.49 if(false, false, l, t, n) -> lessE(l, t, s(n)) [1] 914.86/294.49 length(nil) -> 0 [1] 914.86/294.49 length(cons(n, l)) -> s(length(l)) [1] 914.86/294.49 toList(leaf) -> nil [1] 914.86/294.49 toList(node(t1, n, t2)) -> append(toList(t1), cons(n, toList(t2))) [1] 914.86/294.49 append(nil, l2) -> l2 [1] 914.86/294.49 append(cons(n, l1), l2) -> cons(n, append(l1, l2)) [1] 914.86/294.49 le(s(n), 0) -> false [1] 914.86/294.49 le(0, m) -> true [1] 914.86/294.49 le(s(n), s(m)) -> le(n, m) [1] 914.86/294.49 a -> c [1] 914.86/294.49 a -> d [1] 914.86/294.49 length(v0) -> null_length [0] 914.86/294.49 toList(v0) -> null_toList [0] 914.86/294.49 append(v0, v1) -> null_append [0] 914.86/294.49 le(v0, v1) -> null_le [0] 914.86/294.49 if(v0, v1, v2, v3, v4) -> null_if [0] 914.86/294.49 914.86/294.49 The TRS has the following type information: 914.86/294.49 lessElements :: nil:cons:leaf:node:null_toList:null_append:null_if -> nil:cons:leaf:node:null_toList:null_append:null_if -> nil:cons:leaf:node:null_toList:null_append:null_if 914.86/294.49 lessE :: nil:cons:leaf:node:null_toList:null_append:null_if -> nil:cons:leaf:node:null_toList:null_append:null_if -> 0:s:null_length -> nil:cons:leaf:node:null_toList:null_append:null_if 914.86/294.49 0 :: 0:s:null_length 914.86/294.49 if :: true:false:null_le -> true:false:null_le -> nil:cons:leaf:node:null_toList:null_append:null_if -> nil:cons:leaf:node:null_toList:null_append:null_if -> 0:s:null_length -> nil:cons:leaf:node:null_toList:null_append:null_if 914.86/294.49 le :: 0:s:null_length -> 0:s:null_length -> true:false:null_le 914.86/294.49 length :: nil:cons:leaf:node:null_toList:null_append:null_if -> 0:s:null_length 914.86/294.49 toList :: nil:cons:leaf:node:null_toList:null_append:null_if -> nil:cons:leaf:node:null_toList:null_append:null_if 914.86/294.49 true :: true:false:null_le 914.86/294.49 false :: true:false:null_le 914.86/294.49 s :: 0:s:null_length -> 0:s:null_length 914.86/294.49 nil :: nil:cons:leaf:node:null_toList:null_append:null_if 914.86/294.49 cons :: a -> nil:cons:leaf:node:null_toList:null_append:null_if -> nil:cons:leaf:node:null_toList:null_append:null_if 914.86/294.49 leaf :: nil:cons:leaf:node:null_toList:null_append:null_if 914.86/294.49 node :: nil:cons:leaf:node:null_toList:null_append:null_if -> a -> nil:cons:leaf:node:null_toList:null_append:null_if -> nil:cons:leaf:node:null_toList:null_append:null_if 914.86/294.49 append :: nil:cons:leaf:node:null_toList:null_append:null_if -> nil:cons:leaf:node:null_toList:null_append:null_if -> nil:cons:leaf:node:null_toList:null_append:null_if 914.86/294.49 a :: c:d 914.86/294.49 c :: c:d 914.86/294.49 d :: c:d 914.86/294.49 null_length :: 0:s:null_length 914.86/294.49 null_toList :: nil:cons:leaf:node:null_toList:null_append:null_if 914.86/294.49 null_append :: nil:cons:leaf:node:null_toList:null_append:null_if 914.86/294.49 null_le :: true:false:null_le 914.86/294.49 null_if :: nil:cons:leaf:node:null_toList:null_append:null_if 914.86/294.49 const :: a 914.86/294.49 914.86/294.49 Rewrite Strategy: INNERMOST 914.86/294.49 ---------------------------------------- 914.86/294.49 914.86/294.49 (7) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 914.86/294.49 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 914.86/294.49 The constant constructors are abstracted as follows: 914.86/294.49 914.86/294.49 0 => 0 914.86/294.49 true => 2 914.86/294.49 false => 1 914.86/294.49 nil => 1 914.86/294.49 leaf => 0 914.86/294.49 c => 0 914.86/294.49 d => 1 914.86/294.49 null_length => 0 914.86/294.49 null_toList => 0 914.86/294.49 null_append => 0 914.86/294.49 null_le => 0 914.86/294.49 null_if => 0 914.86/294.49 const => 0 914.86/294.49 914.86/294.49 ---------------------------------------- 914.86/294.49 914.86/294.49 (8) 914.86/294.49 Obligation: 914.86/294.49 Complexity RNTS consisting of the following rules: 914.86/294.49 914.86/294.49 a -{ 1 }-> 1 :|: 914.86/294.49 a -{ 1 }-> 0 :|: 914.86/294.49 append(z, z') -{ 1 }-> l2 :|: z = 1, z' = l2, l2 >= 0 914.86/294.49 append(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 914.86/294.49 append(z, z') -{ 1 }-> 1 + n + append(l1, l2) :|: n >= 0, z = 1 + n + l1, z' = l2, l1 >= 0, l2 >= 0 914.86/294.49 if(z, z', z'', z1, z2) -{ 1 }-> l :|: z = 2, b >= 0, n >= 0, z1 = t, z' = b, l >= 0, t >= 0, z2 = n, z'' = l 914.86/294.49 if(z, z', z'', z1, z2) -{ 1 }-> t :|: n >= 0, z' = 2, z = 1, z1 = t, l >= 0, t >= 0, z2 = n, z'' = l 914.86/294.49 if(z, z', z'', z1, z2) -{ 1 }-> lessE(l, t, 1 + n) :|: n >= 0, z = 1, z1 = t, l >= 0, t >= 0, z' = 1, z2 = n, z'' = l 914.86/294.49 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 914.86/294.49 le(z, z') -{ 1 }-> le(n, m) :|: n >= 0, z' = 1 + m, z = 1 + n, m >= 0 914.86/294.49 le(z, z') -{ 1 }-> 2 :|: z' = m, z = 0, m >= 0 914.86/294.49 le(z, z') -{ 1 }-> 1 :|: n >= 0, z = 1 + n, z' = 0 914.86/294.49 le(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 914.86/294.49 length(z) -{ 1 }-> 0 :|: z = 1 914.86/294.49 length(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 914.86/294.49 length(z) -{ 1 }-> 1 + length(l) :|: z = 1 + n + l, n >= 0, l >= 0 914.86/294.49 lessE(z, z', z'') -{ 1 }-> if(le(length(l), n), le(length(toList(t)), n), l, t, n) :|: n >= 0, z' = t, z'' = n, z = l, l >= 0, t >= 0 914.86/294.49 lessElements(z, z') -{ 1 }-> lessE(l, t, 0) :|: z' = t, z = l, l >= 0, t >= 0 914.86/294.49 toList(z) -{ 1 }-> append(toList(t1), 1 + n + toList(t2)) :|: n >= 0, t1 >= 0, z = 1 + t1 + n + t2, t2 >= 0 914.86/294.49 toList(z) -{ 1 }-> 1 :|: z = 0 914.86/294.49 toList(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 914.86/294.49 914.86/294.49 Only complete derivations are relevant for the runtime complexity. 914.86/294.49 914.86/294.49 ---------------------------------------- 914.86/294.49 914.86/294.49 (9) CompleteCoflocoProof (FINISHED) 914.86/294.49 Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: 914.86/294.49 914.86/294.49 eq(start(V1, V, V4, V13, V11),0,[lessElements(V1, V, Out)],[V1 >= 0,V >= 0]). 914.86/294.49 eq(start(V1, V, V4, V13, V11),0,[lessE(V1, V, V4, Out)],[V1 >= 0,V >= 0,V4 >= 0]). 914.86/294.49 eq(start(V1, V, V4, V13, V11),0,[if(V1, V, V4, V13, V11, Out)],[V1 >= 0,V >= 0,V4 >= 0,V13 >= 0,V11 >= 0]). 914.86/294.49 eq(start(V1, V, V4, V13, V11),0,[length(V1, Out)],[V1 >= 0]). 914.86/294.49 eq(start(V1, V, V4, V13, V11),0,[toList(V1, Out)],[V1 >= 0]). 914.86/294.49 eq(start(V1, V, V4, V13, V11),0,[append(V1, V, Out)],[V1 >= 0,V >= 0]). 914.86/294.49 eq(start(V1, V, V4, V13, V11),0,[le(V1, V, Out)],[V1 >= 0,V >= 0]). 914.86/294.49 eq(start(V1, V, V4, V13, V11),0,[a(Out)],[]). 914.86/294.49 eq(lessElements(V1, V, Out),1,[lessE(V3, V2, 0, Ret)],[Out = Ret,V = V2,V1 = V3,V3 >= 0,V2 >= 0]). 914.86/294.49 eq(lessE(V1, V, V4, Out),1,[length(V7, Ret00),le(Ret00, V6, Ret0),toList(V5, Ret100),length(Ret100, Ret10),le(Ret10, V6, Ret1),if(Ret0, Ret1, V7, V5, V6, Ret2)],[Out = Ret2,V6 >= 0,V = V5,V4 = V6,V1 = V7,V7 >= 0,V5 >= 0]). 914.86/294.49 eq(if(V1, V, V4, V13, V11, Out),1,[],[Out = V12,V1 = 2,V9 >= 0,V10 >= 0,V13 = V8,V = V9,V12 >= 0,V8 >= 0,V11 = V10,V4 = V12]). 914.86/294.49 eq(if(V1, V, V4, V13, V11, Out),1,[],[Out = V16,V15 >= 0,V = 2,V1 = 1,V13 = V16,V14 >= 0,V16 >= 0,V11 = V15,V4 = V14]). 914.86/294.49 eq(if(V1, V, V4, V13, V11, Out),1,[lessE(V17, V18, 1 + V19, Ret3)],[Out = Ret3,V19 >= 0,V1 = 1,V13 = V18,V17 >= 0,V18 >= 0,V = 1,V11 = V19,V4 = V17]). 914.86/294.49 eq(length(V1, Out),1,[],[Out = 0,V1 = 1]). 914.86/294.49 eq(length(V1, Out),1,[length(V20, Ret11)],[Out = 1 + Ret11,V1 = 1 + V20 + V21,V21 >= 0,V20 >= 0]). 914.86/294.49 eq(toList(V1, Out),1,[],[Out = 1,V1 = 0]). 914.86/294.49 eq(toList(V1, Out),1,[toList(V24, Ret01),toList(V23, Ret111),append(Ret01, 1 + V22 + Ret111, Ret4)],[Out = Ret4,V22 >= 0,V24 >= 0,V1 = 1 + V22 + V23 + V24,V23 >= 0]). 914.86/294.49 eq(append(V1, V, Out),1,[],[Out = V25,V1 = 1,V = V25,V25 >= 0]). 914.86/294.49 eq(append(V1, V, Out),1,[append(V26, V27, Ret12)],[Out = 1 + Ret12 + V28,V28 >= 0,V1 = 1 + V26 + V28,V = V27,V26 >= 0,V27 >= 0]). 914.86/294.49 eq(le(V1, V, Out),1,[],[Out = 1,V29 >= 0,V1 = 1 + V29,V = 0]). 914.86/294.49 eq(le(V1, V, Out),1,[],[Out = 2,V = V30,V1 = 0,V30 >= 0]). 914.86/294.49 eq(le(V1, V, Out),1,[le(V31, V32, Ret5)],[Out = Ret5,V31 >= 0,V = 1 + V32,V1 = 1 + V31,V32 >= 0]). 914.86/294.49 eq(a(Out),1,[],[Out = 0]). 914.86/294.49 eq(a(Out),1,[],[Out = 1]). 914.86/294.49 eq(length(V1, Out),0,[],[Out = 0,V33 >= 0,V1 = V33]). 914.86/294.49 eq(toList(V1, Out),0,[],[Out = 0,V34 >= 0,V1 = V34]). 914.86/294.49 eq(append(V1, V, Out),0,[],[Out = 0,V36 >= 0,V35 >= 0,V1 = V36,V = V35]). 914.86/294.49 eq(le(V1, V, Out),0,[],[Out = 0,V37 >= 0,V38 >= 0,V1 = V37,V = V38]). 914.86/294.49 eq(if(V1, V, V4, V13, V11, Out),0,[],[Out = 0,V13 = V42,V39 >= 0,V41 >= 0,V4 = V43,V40 >= 0,V1 = V39,V = V40,V11 = V41,V43 >= 0,V42 >= 0]). 914.86/294.49 input_output_vars(lessElements(V1,V,Out),[V1,V],[Out]). 914.86/294.49 input_output_vars(lessE(V1,V,V4,Out),[V1,V,V4],[Out]). 914.86/294.49 input_output_vars(if(V1,V,V4,V13,V11,Out),[V1,V,V4,V13,V11],[Out]). 914.86/294.49 input_output_vars(length(V1,Out),[V1],[Out]). 914.86/294.49 input_output_vars(toList(V1,Out),[V1],[Out]). 914.86/294.49 input_output_vars(append(V1,V,Out),[V1,V],[Out]). 914.86/294.49 input_output_vars(le(V1,V,Out),[V1,V],[Out]). 914.86/294.49 input_output_vars(a(Out),[],[Out]). 914.86/294.49 914.86/294.49 914.86/294.49 CoFloCo proof output: 914.86/294.49 Preprocessing Cost Relations 914.86/294.49 ===================================== 914.86/294.49 914.86/294.49 #### Computed strongly connected components 914.86/294.49 0. non_recursive : [a/1] 914.86/294.49 1. recursive : [append/3] 914.86/294.49 2. recursive : [le/3] 914.86/294.49 3. recursive : [length/2] 914.86/294.49 4. recursive [non_tail,multiple] : [toList/2] 914.86/294.49 5. recursive : [if/6,lessE/4] 914.86/294.49 6. non_recursive : [lessElements/3] 914.86/294.49 7. non_recursive : [start/5] 914.86/294.49 914.86/294.49 #### Obtained direct recursion through partial evaluation 914.86/294.49 0. SCC is partially evaluated into a/1 914.86/294.49 1. SCC is partially evaluated into append/3 914.86/294.49 2. SCC is partially evaluated into le/3 914.86/294.49 3. SCC is partially evaluated into length/2 914.86/294.49 4. SCC is partially evaluated into toList/2 914.86/294.49 5. SCC is partially evaluated into lessE/4 914.86/294.49 6. SCC is completely evaluated into other SCCs 914.86/294.49 7. SCC is partially evaluated into start/5 914.86/294.49 914.86/294.49 Control-Flow Refinement of Cost Relations 914.86/294.49 ===================================== 914.86/294.49 914.86/294.49 ### Specialization of cost equations a/1 914.86/294.49 * CE 30 is refined into CE [31] 914.86/294.49 * CE 29 is refined into CE [32] 914.86/294.49 914.86/294.49 914.86/294.49 ### Cost equations --> "Loop" of a/1 914.86/294.49 * CEs [31] --> Loop 20 914.86/294.49 * CEs [32] --> Loop 21 914.86/294.49 914.86/294.49 ### Ranking functions of CR a(Out) 914.86/294.49 914.86/294.49 #### Partial ranking functions of CR a(Out) 914.86/294.49 914.86/294.49 914.86/294.49 ### Specialization of cost equations append/3 914.86/294.49 * CE 24 is refined into CE [33] 914.86/294.49 * CE 22 is refined into CE [34] 914.86/294.49 * CE 23 is refined into CE [35] 914.86/294.49 914.86/294.49 914.86/294.49 ### Cost equations --> "Loop" of append/3 914.86/294.49 * CEs [35] --> Loop 22 914.86/294.49 * CEs [33] --> Loop 23 914.86/294.49 * CEs [34] --> Loop 24 914.86/294.49 914.86/294.49 ### Ranking functions of CR append(V1,V,Out) 914.86/294.49 * RF of phase [22]: [V1] 914.86/294.49 914.86/294.49 #### Partial ranking functions of CR append(V1,V,Out) 914.86/294.49 * Partial RF of phase [22]: 914.86/294.49 - RF of loop [22:1]: 914.86/294.49 V1 914.86/294.49 914.86/294.49 914.86/294.49 ### Specialization of cost equations le/3 914.86/294.49 * CE 28 is refined into CE [36] 914.86/294.49 * CE 25 is refined into CE [37] 914.86/294.49 * CE 26 is refined into CE [38] 914.86/294.49 * CE 27 is refined into CE [39] 914.86/294.49 914.86/294.49 914.86/294.49 ### Cost equations --> "Loop" of le/3 914.86/294.49 * CEs [39] --> Loop 25 914.86/294.49 * CEs [36] --> Loop 26 914.86/294.49 * CEs [37] --> Loop 27 914.86/294.49 * CEs [38] --> Loop 28 914.86/294.49 914.86/294.49 ### Ranking functions of CR le(V1,V,Out) 914.86/294.49 * RF of phase [25]: [V,V1] 914.86/294.49 914.86/294.49 #### Partial ranking functions of CR le(V1,V,Out) 914.86/294.49 * Partial RF of phase [25]: 914.86/294.49 - RF of loop [25:1]: 914.86/294.49 V 914.86/294.49 V1 914.86/294.49 914.86/294.49 914.86/294.49 ### Specialization of cost equations length/2 914.86/294.49 * CE 16 is refined into CE [40] 914.86/294.49 * CE 18 is refined into CE [41] 914.86/294.49 * CE 17 is refined into CE [42] 914.86/294.49 914.86/294.49 914.86/294.49 ### Cost equations --> "Loop" of length/2 914.86/294.49 * CEs [42] --> Loop 29 914.86/294.49 * CEs [40,41] --> Loop 30 914.86/294.49 914.86/294.49 ### Ranking functions of CR length(V1,Out) 914.86/294.49 * RF of phase [29]: [V1] 914.86/294.49 914.86/294.49 #### Partial ranking functions of CR length(V1,Out) 914.86/294.49 * Partial RF of phase [29]: 914.86/294.49 - RF of loop [29:1]: 914.86/294.49 V1 914.86/294.49 914.86/294.49 914.86/294.49 ### Specialization of cost equations toList/2 914.86/294.49 * CE 21 is refined into CE [43] 914.86/294.49 * CE 19 is refined into CE [44] 914.86/294.49 * CE 20 is refined into CE [45,46,47,48] 914.86/294.49 914.86/294.49 914.86/294.49 ### Cost equations --> "Loop" of toList/2 914.86/294.49 * CEs [48] --> Loop 31 914.86/294.49 * CEs [47] --> Loop 32 914.86/294.49 * CEs [45] --> Loop 33 914.86/294.49 * CEs [46] --> Loop 34 914.86/294.49 * CEs [43] --> Loop 35 914.86/294.49 * CEs [44] --> Loop 36 914.86/294.49 914.86/294.49 ### Ranking functions of CR toList(V1,Out) 914.86/294.49 * RF of phase [31,32,33,34]: [V1] 914.86/294.49 914.86/294.49 #### Partial ranking functions of CR toList(V1,Out) 914.86/294.49 * Partial RF of phase [31,32,33,34]: 914.86/294.49 - RF of loop [31:1,31:2,32:1,32:2,33:1,33:2,34:1,34:2]: 914.86/294.49 V1 914.86/294.49 914.86/294.49 914.86/294.49 ### Specialization of cost equations lessE/4 914.86/294.49 * CE 14 is refined into CE [49,50,51,52,53,54,55,56] 914.86/294.49 * CE 15 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] 914.86/294.49 * CE 12 is refined into CE [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] 914.86/294.49 * CE 13 is refined into CE [152,153,154] 914.86/294.49 914.86/294.49 914.86/294.49 ### Cost equations --> "Loop" of lessE/4 914.86/294.49 * CEs [154] --> Loop 37 914.86/294.49 * CEs [153] --> Loop 38 914.86/294.49 * CEs [152] --> Loop 39 914.86/294.49 * CEs [54,55,56] --> Loop 40 914.86/294.49 * CEs [50,51] --> Loop 41 914.86/294.49 * CEs [66] --> Loop 42 914.86/294.49 * CEs [111,112] --> Loop 43 914.86/294.49 * CEs [90,103,113,114,115,116,126] --> Loop 44 914.86/294.49 * CEs [57,58,59,60,61,62,63,64,65,67,68,69,70,71,72,73,74,75,76,77,78,79,80] --> Loop 45 914.86/294.49 * CEs [49,52,53,81,82,83,84,85,86,87,88,89,91,92,93,94,95,96,97,98,99,100,101,102,104,105,106,107,108,109,110,117,118,119,120,121,122,123,124,125,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] --> Loop 46 914.86/294.49 914.86/294.49 ### Ranking functions of CR lessE(V1,V,V4,Out) 914.86/294.49 * RF of phase [37]: [V-V4+1,V1-V4] 914.86/294.49 914.86/294.49 #### Partial ranking functions of CR lessE(V1,V,V4,Out) 914.86/294.49 * Partial RF of phase [37]: 914.86/294.49 - RF of loop [37:1]: 914.86/294.49 V-V4+1 914.86/294.49 V1-V4 914.86/294.49 914.86/294.49 914.86/294.49 ### Specialization of cost equations start/5 914.86/294.49 * CE 1 is refined into CE [155] 914.86/294.49 * CE 2 is refined into CE [156,157,158] 914.86/294.49 * CE 3 is refined into CE [159] 914.86/294.49 * CE 4 is refined into CE [160] 914.86/294.49 * CE 5 is refined into CE [161,162,163,164,165] 914.86/294.49 * CE 6 is refined into CE [166,167,168,169,170,171] 914.86/294.49 * CE 7 is refined into CE [172,173] 914.86/294.49 * CE 8 is refined into CE [174,175,176] 914.86/294.49 * CE 9 is refined into CE [177,178,179,180] 914.86/294.49 * CE 10 is refined into CE [181,182,183,184,185] 914.86/294.49 * CE 11 is refined into CE [186,187] 914.86/294.49 914.86/294.49 914.86/294.49 ### Cost equations --> "Loop" of start/5 914.86/294.49 * CEs [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] --> Loop 47 914.86/294.49 914.86/294.49 ### Ranking functions of CR start(V1,V,V4,V13,V11) 914.86/294.49 914.86/294.49 #### Partial ranking functions of CR start(V1,V,V4,V13,V11) 914.86/294.49 914.86/294.49 914.86/294.49 Computing Bounds 914.86/294.49 ===================================== 914.86/294.49 914.86/294.49 #### Cost of chains of a(Out): 914.86/294.49 * Chain [21]: 1 914.86/294.49 with precondition: [Out=0] 914.86/294.49 914.86/294.49 * Chain [20]: 1 914.86/294.49 with precondition: [Out=1] 914.86/294.49 914.86/294.49 914.86/294.49 #### Cost of chains of append(V1,V,Out): 914.86/294.49 * Chain [[22],24]: 1*it(22)+1 914.86/294.49 Such that:it(22) =< -V+Out 914.86/294.49 914.86/294.49 with precondition: [V+V1=Out+1,V1>=2,V>=0] 914.86/294.49 914.86/294.49 * Chain [[22],23]: 1*it(22)+0 914.86/294.49 Such that:it(22) =< Out 914.86/294.49 914.86/294.49 with precondition: [V>=0,Out>=1,V1>=Out] 914.86/294.49 914.86/294.49 * Chain [24]: 1 914.86/294.49 with precondition: [V1=1,V=Out,V>=0] 914.86/294.49 914.86/294.49 * Chain [23]: 0 914.86/294.49 with precondition: [Out=0,V1>=0,V>=0] 914.86/294.49 914.86/294.49 914.86/294.49 #### Cost of chains of le(V1,V,Out): 914.86/294.49 * Chain [[25],28]: 1*it(25)+1 914.86/294.49 Such that:it(25) =< V1 914.86/294.49 914.86/294.49 with precondition: [Out=2,V1>=1,V>=V1] 914.86/294.49 914.86/294.49 * Chain [[25],27]: 1*it(25)+1 914.86/294.49 Such that:it(25) =< V 914.86/294.49 914.86/294.49 with precondition: [Out=1,V>=1,V1>=V+1] 914.86/294.49 914.86/294.49 * Chain [[25],26]: 1*it(25)+0 914.86/294.49 Such that:it(25) =< V 914.86/294.49 914.86/294.49 with precondition: [Out=0,V1>=1,V>=1] 914.86/294.49 914.86/294.49 * Chain [28]: 1 914.86/294.49 with precondition: [V1=0,Out=2,V>=0] 914.86/294.49 914.86/294.49 * Chain [27]: 1 914.86/294.49 with precondition: [V=0,Out=1,V1>=1] 914.86/294.49 914.86/294.49 * Chain [26]: 0 914.86/294.49 with precondition: [Out=0,V1>=0,V>=0] 914.86/294.49 914.86/294.49 914.86/294.49 #### Cost of chains of length(V1,Out): 914.86/294.49 * Chain [[29],30]: 1*it(29)+1 914.86/294.49 Such that:it(29) =< V1 914.86/294.49 914.86/294.49 with precondition: [Out>=1,V1>=Out] 914.86/294.49 914.86/294.49 * Chain [30]: 1 914.86/294.49 with precondition: [Out=0,V1>=0] 914.86/294.49 914.86/294.49 914.86/294.49 #### Cost of chains of toList(V1,Out): 914.86/294.49 * Chain [36]: 1 914.86/294.49 with precondition: [V1=0,Out=1] 914.86/294.49 914.86/294.49 * Chain [35]: 0 914.86/294.49 with precondition: [Out=0,V1>=0] 914.86/294.49 914.86/294.49 * Chain [multiple([31,32,33,34],[[36],[35]])]: 1*it(31)+5*it(32)+1*it([36])+1*s(6)+1*s(7)+0 914.86/294.49 Such that:aux(3) =< V1 914.86/294.49 aux(4) =< V1+1 914.86/294.49 aux(5) =< 2*V1+1 914.86/294.49 it(32) =< aux(3) 914.86/294.49 it([36]) =< aux(4) 914.86/294.49 it(31) =< aux(5) 914.86/294.49 it(32) =< aux(5) 914.86/294.49 it([36]) =< aux(5) 914.86/294.49 aux(2) =< aux(3)-1 914.86/294.49 s(6) =< it(31)*aux(3) 914.86/294.49 s(7) =< it(32)*aux(2) 914.86/294.49 914.86/294.49 with precondition: [V1>=1,Out>=0,V1+1>=Out] 914.86/294.49 914.86/294.49 914.86/294.49 #### Cost of chains of lessE(V1,V,V4,Out): 914.86/294.49 * Chain [[37],46]: 6*it(37)+49*s(8)+88*s(10)+22*s(13)+125*s(25)+25*s(26)+25*s(27)+25*s(29)+25*s(30)+1*s(422)+2*s(423)+5*s(424)+1*s(425)+1*s(426)+1*s(427)+1*s(428)+1*s(429)+7 914.86/294.49 Such that:aux(58) =< 1 914.86/294.49 it(37) =< V-V4+1 914.86/294.49 aux(62) =< 2*V+1 914.86/294.49 aux(72) =< V1 914.86/294.49 aux(73) =< V 914.86/294.49 aux(74) =< V+1 914.86/294.49 s(13) =< aux(58) 914.86/294.49 s(8) =< aux(72) 914.86/294.49 s(10) =< aux(74) 914.86/294.49 s(25) =< aux(73) 914.86/294.49 s(26) =< aux(74) 914.86/294.49 s(27) =< aux(62) 914.86/294.49 s(25) =< aux(62) 914.86/294.49 s(26) =< aux(62) 914.86/294.49 s(28) =< aux(73)-1 914.86/294.49 s(29) =< s(27)*aux(73) 914.86/294.49 s(30) =< s(25)*s(28) 914.86/294.49 aux(69) =< aux(73)*2+1 914.86/294.49 aux(68) =< aux(73)+1 914.86/294.49 aux(67) =< aux(73) 914.86/294.49 s(433) =< it(37)*aux(72) 914.86/294.49 s(422) =< it(37)*aux(72) 914.86/294.49 s(430) =< it(37)*aux(69) 914.86/294.49 s(431) =< it(37)*aux(68) 914.86/294.49 s(432) =< it(37)*aux(67) 914.86/294.49 s(429) =< s(431) 914.86/294.49 s(423) =< s(433) 914.86/294.49 s(424) =< s(432) 914.86/294.49 s(425) =< s(431) 914.86/294.49 s(426) =< s(430) 914.86/294.49 s(424) =< s(430) 914.86/294.49 s(425) =< s(430) 914.86/294.49 s(427) =< s(426)*aux(73) 914.86/294.49 s(428) =< s(424)*s(28) 914.86/294.49 914.86/294.49 with precondition: [Out=0,V4>=1,V1>=V4+1,V>=V4] 914.86/294.49 914.86/294.49 * Chain [[37],45]: 6*it(37)+1*s(422)+2*s(423)+5*s(424)+1*s(425)+1*s(426)+1*s(427)+1*s(428)+1*s(429)+23*s(434)+7*s(435)+50*s(444)+10*s(445)+10*s(446)+10*s(448)+10*s(449)+19*s(493)+7 914.86/294.49 Such that:aux(93) =< 1 914.86/294.49 it(37) =< V-V4+1 914.86/294.49 aux(97) =< 2*V+1 914.86/294.49 aux(99) =< V 914.86/294.49 aux(100) =< V+1 914.86/294.49 aux(101) =< Out 914.86/294.49 s(435) =< aux(93) 914.86/294.49 s(493) =< aux(101) 914.86/294.49 s(434) =< aux(100) 914.86/294.49 s(444) =< aux(99) 914.86/294.49 s(445) =< aux(100) 914.86/294.49 s(446) =< aux(97) 914.86/294.49 s(444) =< aux(97) 914.86/294.49 s(445) =< aux(97) 914.86/294.49 s(419) =< aux(99)-1 914.86/294.49 s(448) =< s(446)*aux(99) 914.86/294.49 s(449) =< s(444)*s(419) 914.86/294.49 aux(69) =< aux(99)*2+1 914.86/294.49 aux(68) =< aux(99)+1 914.86/294.49 aux(67) =< aux(99) 914.86/294.49 s(433) =< it(37)*aux(101) 914.86/294.49 s(422) =< it(37)*aux(101) 914.86/294.49 s(430) =< it(37)*aux(69) 914.86/294.49 s(431) =< it(37)*aux(68) 914.86/294.49 s(432) =< it(37)*aux(67) 914.86/294.49 s(429) =< s(431) 914.86/294.49 s(423) =< s(433) 914.86/294.49 s(424) =< s(432) 914.86/294.49 s(425) =< s(431) 914.86/294.49 s(426) =< s(430) 914.86/294.49 s(424) =< s(430) 914.86/294.49 s(425) =< s(430) 914.86/294.49 s(427) =< s(426)*aux(99) 914.86/294.49 s(428) =< s(424)*s(419) 914.86/294.49 914.86/294.49 with precondition: [V1=Out,V4>=1,V1>=V4+1,V>=V4] 914.86/294.49 914.86/294.49 * Chain [[37],40]: 6*it(37)+1*s(422)+2*s(423)+5*s(424)+1*s(425)+1*s(426)+1*s(427)+1*s(428)+1*s(429)+7*s(573)+10*s(580)+2*s(581)+2*s(582)+2*s(584)+2*s(585)+1*s(597)+6 914.86/294.49 Such that:it(37) =< V1-V4 914.86/294.49 aux(106) =< Out+1 914.86/294.49 aux(107) =< 2*Out+1 914.86/294.49 aux(109) =< V1 914.86/294.49 aux(110) =< Out 914.86/294.49 s(573) =< aux(109) 914.86/294.49 s(580) =< aux(110) 914.86/294.49 s(581) =< aux(106) 914.86/294.49 s(582) =< aux(107) 914.86/294.49 s(580) =< aux(107) 914.86/294.49 s(581) =< aux(107) 914.86/294.49 s(419) =< aux(110)-1 914.86/294.49 s(584) =< s(582)*aux(110) 914.86/294.49 s(585) =< s(580)*s(419) 914.86/294.49 s(597) =< aux(106) 914.86/294.49 aux(69) =< aux(110)*2+1 914.86/294.49 aux(68) =< aux(110)+1 914.86/294.49 aux(67) =< aux(110) 914.86/294.49 s(433) =< it(37)*aux(109) 914.86/294.49 s(422) =< it(37)*aux(109) 914.86/294.49 s(430) =< it(37)*aux(69) 914.86/294.49 s(431) =< it(37)*aux(68) 914.86/294.49 s(432) =< it(37)*aux(67) 914.86/294.49 s(429) =< s(431) 914.86/294.49 s(423) =< s(433) 914.86/294.49 s(424) =< s(432) 914.86/294.49 s(425) =< s(431) 914.86/294.49 s(426) =< s(430) 914.86/294.49 s(424) =< s(430) 914.86/294.49 s(425) =< s(430) 914.86/294.49 s(427) =< s(426)*aux(110) 914.86/294.49 s(428) =< s(424)*s(419) 914.86/294.49 914.86/294.49 with precondition: [V=Out,V4>=1,V1>=V4+2,V>=V4] 914.86/294.49 914.86/294.49 * Chain [46]: 49*s(8)+73*s(10)+22*s(13)+125*s(25)+25*s(26)+25*s(27)+25*s(29)+25*s(30)+15*s(50)+7 914.86/294.49 Such that:aux(58) =< 1 914.86/294.49 aux(59) =< V1 914.86/294.49 aux(60) =< V 914.86/294.49 aux(61) =< V+1 914.86/294.49 aux(62) =< 2*V+1 914.86/294.49 aux(63) =< V4 914.86/294.49 s(13) =< aux(58) 914.86/294.49 s(8) =< aux(59) 914.86/294.49 s(10) =< aux(63) 914.86/294.49 s(25) =< aux(60) 914.86/294.49 s(26) =< aux(61) 914.86/294.49 s(27) =< aux(62) 914.86/294.49 s(25) =< aux(62) 914.86/294.49 s(26) =< aux(62) 914.86/294.49 s(28) =< aux(60)-1 914.86/294.49 s(29) =< s(27)*aux(60) 914.86/294.49 s(30) =< s(25)*s(28) 914.86/294.49 s(50) =< aux(61) 914.86/294.49 914.86/294.49 with precondition: [Out=0,V1>=0,V>=0,V4>=0] 914.86/294.49 914.86/294.49 * Chain [45]: 17*s(434)+7*s(435)+50*s(444)+10*s(445)+10*s(446)+10*s(448)+10*s(449)+6*s(469)+19*s(493)+7 914.86/294.49 Such that:aux(93) =< 1 914.86/294.49 aux(94) =< V1 914.86/294.49 aux(95) =< V 914.86/294.49 aux(96) =< V+1 914.86/294.49 aux(97) =< 2*V+1 914.86/294.49 aux(98) =< V4 914.86/294.49 s(435) =< aux(93) 914.86/294.49 s(493) =< aux(94) 914.86/294.49 s(434) =< aux(98) 914.86/294.49 s(444) =< aux(95) 914.86/294.49 s(445) =< aux(96) 914.86/294.49 s(446) =< aux(97) 914.86/294.49 s(444) =< aux(97) 914.86/294.49 s(445) =< aux(97) 914.86/294.49 s(447) =< aux(95)-1 914.86/294.49 s(448) =< s(446)*aux(95) 914.86/294.49 s(449) =< s(444)*s(447) 914.86/294.49 s(469) =< aux(96) 914.86/294.49 914.86/294.49 with precondition: [V1=Out,V1>=0,V>=0,V4>=0] 914.86/294.49 914.86/294.49 * Chain [44]: 35*s(602)+7*s(603)+7*s(604)+7*s(606)+7*s(607)+5*s(608)+5*s(620)+5 914.86/294.49 Such that:aux(116) =< V1 914.86/294.49 aux(117) =< V 914.86/294.49 aux(118) =< V+1 914.86/294.49 aux(119) =< 2*V+1 914.86/294.49 s(620) =< aux(116) 914.86/294.49 s(602) =< aux(117) 914.86/294.49 s(603) =< aux(118) 914.86/294.49 s(604) =< aux(119) 914.86/294.49 s(602) =< aux(119) 914.86/294.49 s(603) =< aux(119) 914.86/294.49 s(605) =< aux(117)-1 914.86/294.49 s(606) =< s(604)*aux(117) 914.86/294.49 s(607) =< s(602)*s(605) 914.86/294.49 s(608) =< aux(118) 914.86/294.49 914.86/294.49 with precondition: [V4=0,Out=0,V1>=0,V>=1] 914.86/294.49 914.86/294.49 * Chain [43]: 2*s(676)+5 914.86/294.49 Such that:aux(120) =< V1 914.86/294.49 s(676) =< aux(120) 914.86/294.49 914.86/294.49 with precondition: [V4=0,Out=0,V1>=1,V>=0] 914.86/294.49 914.86/294.49 * Chain [42]: 5*s(682)+1*s(683)+1*s(684)+1*s(686)+1*s(687)+1*s(688)+6 914.86/294.49 Such that:s(679) =< V 914.86/294.49 s(681) =< 2*V+1 914.86/294.49 aux(121) =< V+1 914.86/294.49 s(688) =< aux(121) 914.86/294.49 s(682) =< s(679) 914.86/294.49 s(683) =< aux(121) 914.86/294.49 s(684) =< s(681) 914.86/294.49 s(682) =< s(681) 914.86/294.49 s(683) =< s(681) 914.86/294.49 s(685) =< s(679)-1 914.86/294.49 s(686) =< s(684)*s(679) 914.86/294.49 s(687) =< s(682)*s(685) 914.86/294.49 914.86/294.49 with precondition: [V4=0,V1=Out,V1>=0,V>=1] 914.86/294.49 914.86/294.49 * Chain [41]: 2*s(689)+5*s(694)+1*s(695)+1*s(696)+1*s(698)+1*s(699)+6 914.86/294.49 Such that:s(691) =< V 914.86/294.49 s(692) =< V+1 914.86/294.49 s(693) =< 2*V+1 914.86/294.49 aux(122) =< V1 914.86/294.49 s(689) =< aux(122) 914.86/294.49 s(694) =< s(691) 914.86/294.49 s(695) =< s(692) 914.86/294.49 s(696) =< s(693) 914.86/294.49 s(694) =< s(693) 914.86/294.49 s(695) =< s(693) 914.86/294.49 s(697) =< s(691)-1 914.86/294.49 s(698) =< s(696)*s(691) 914.86/294.49 s(699) =< s(694)*s(697) 914.86/294.49 914.86/294.49 with precondition: [V4=0,V=Out,V1>=1,V>=0] 914.86/294.49 914.86/294.49 * Chain [40]: 3*s(573)+4*s(574)+10*s(580)+2*s(581)+2*s(582)+2*s(584)+2*s(585)+1*s(597)+6 914.86/294.49 Such that:aux(104) =< V1 914.86/294.49 aux(105) =< V 914.86/294.49 aux(106) =< V+1 914.86/294.49 aux(107) =< 2*V+1 914.86/294.49 aux(108) =< V4 914.86/294.49 s(573) =< aux(104) 914.86/294.49 s(574) =< aux(108) 914.86/294.49 s(580) =< aux(105) 914.86/294.49 s(581) =< aux(106) 914.86/294.50 s(582) =< aux(107) 914.86/294.50 s(580) =< aux(107) 914.86/294.50 s(581) =< aux(107) 914.86/294.50 s(583) =< aux(105)-1 914.86/294.50 s(584) =< s(582)*aux(105) 914.86/294.50 s(585) =< s(580)*s(583) 914.86/294.50 s(597) =< aux(106) 914.86/294.50 914.86/294.50 with precondition: [V=Out,V>=0,V4>=1,V1>=V4+1] 914.86/294.50 914.86/294.50 * Chain [39,46]: 50*s(8)+161*s(10)+14 914.86/294.50 Such that:aux(123) =< 1 914.86/294.50 aux(124) =< V1 914.86/294.50 s(10) =< aux(123) 914.86/294.50 s(8) =< aux(124) 914.86/294.50 914.86/294.50 with precondition: [V=0,V4=0,Out=0,V1>=1] 914.86/294.50 914.86/294.50 * Chain [39,45]: 51*s(434)+20*s(493)+14 914.86/294.50 Such that:aux(125) =< 1 914.86/294.50 aux(126) =< V1 914.86/294.50 s(434) =< aux(125) 914.86/294.50 s(493) =< aux(126) 914.86/294.50 914.86/294.50 with precondition: [V=0,V4=0,V1=Out,V1>=1] 914.86/294.50 914.86/294.50 * Chain [39,40]: 4*s(573)+10*s(574)+13 914.86/294.50 Such that:aux(127) =< 1 914.86/294.50 aux(128) =< V1 914.86/294.50 s(574) =< aux(127) 914.86/294.50 s(573) =< aux(128) 914.86/294.50 914.86/294.50 with precondition: [V=0,V4=0,Out=0,V1>=2] 914.86/294.50 914.86/294.50 * Chain [38,[37],46]: 6*it(37)+50*s(8)+89*s(10)+22*s(13)+130*s(25)+26*s(26)+26*s(27)+26*s(29)+26*s(30)+1*s(422)+2*s(423)+5*s(424)+1*s(425)+1*s(426)+1*s(427)+1*s(428)+1*s(429)+13 914.86/294.50 Such that:aux(58) =< 1 914.86/294.50 aux(130) =< V1 914.86/294.50 aux(131) =< V 914.86/294.50 aux(132) =< V+1 914.86/294.50 aux(133) =< 2*V+1 914.86/294.50 s(8) =< aux(130) 914.86/294.50 it(37) =< aux(131) 914.86/294.50 s(13) =< aux(58) 914.86/294.50 s(10) =< aux(132) 914.86/294.50 s(25) =< aux(131) 914.86/294.50 s(26) =< aux(132) 914.86/294.50 s(27) =< aux(133) 914.86/294.50 s(25) =< aux(133) 914.86/294.50 s(26) =< aux(133) 914.86/294.50 s(28) =< aux(131)-1 914.86/294.50 s(29) =< s(27)*aux(131) 914.86/294.50 s(30) =< s(25)*s(28) 914.86/294.50 aux(69) =< aux(131)*2+1 914.86/294.50 aux(68) =< aux(131)+1 914.86/294.50 aux(67) =< aux(131) 914.86/294.50 s(433) =< it(37)*aux(130) 914.86/294.50 s(422) =< it(37)*aux(130) 914.86/294.50 s(430) =< it(37)*aux(69) 914.86/294.50 s(431) =< it(37)*aux(68) 914.86/294.50 s(432) =< it(37)*aux(67) 914.86/294.50 s(429) =< s(431) 914.86/294.50 s(423) =< s(433) 914.86/294.50 s(424) =< s(432) 914.86/294.50 s(425) =< s(431) 914.86/294.50 s(426) =< s(430) 914.86/294.50 s(424) =< s(430) 914.86/294.50 s(425) =< s(430) 914.86/294.50 s(427) =< s(426)*aux(131) 914.86/294.50 s(428) =< s(424)*s(28) 914.86/294.50 914.86/294.50 with precondition: [V4=0,Out=0,V1>=2,V>=1] 914.86/294.50 914.86/294.50 * Chain [38,[37],45]: 6*it(37)+1*s(422)+2*s(423)+5*s(424)+1*s(425)+1*s(426)+1*s(427)+1*s(428)+1*s(429)+24*s(434)+7*s(435)+55*s(444)+11*s(445)+11*s(446)+11*s(448)+11*s(449)+20*s(493)+13 914.86/294.50 Such that:aux(93) =< 1 914.86/294.50 aux(134) =< V 914.86/294.50 aux(135) =< V+1 914.86/294.50 aux(136) =< 2*V+1 914.86/294.50 aux(137) =< Out 914.86/294.50 it(37) =< aux(134) 914.86/294.50 s(493) =< aux(137) 914.86/294.50 s(435) =< aux(93) 914.86/294.50 s(434) =< aux(135) 914.86/294.50 s(444) =< aux(134) 914.86/294.50 s(445) =< aux(135) 914.86/294.50 s(446) =< aux(136) 914.86/294.50 s(444) =< aux(136) 914.86/294.50 s(445) =< aux(136) 914.86/294.50 s(419) =< aux(134)-1 914.86/294.50 s(448) =< s(446)*aux(134) 914.86/294.50 s(449) =< s(444)*s(419) 914.86/294.50 aux(69) =< aux(134)*2+1 914.86/294.50 aux(68) =< aux(134)+1 914.86/294.50 aux(67) =< aux(134) 914.86/294.50 s(433) =< it(37)*aux(137) 914.86/294.50 s(422) =< it(37)*aux(137) 914.86/294.50 s(430) =< it(37)*aux(69) 914.86/294.50 s(431) =< it(37)*aux(68) 914.86/294.50 s(432) =< it(37)*aux(67) 914.86/294.50 s(429) =< s(431) 914.86/294.50 s(423) =< s(433) 914.86/294.50 s(424) =< s(432) 914.86/294.50 s(425) =< s(431) 914.86/294.50 s(426) =< s(430) 914.86/294.50 s(424) =< s(430) 914.86/294.50 s(425) =< s(430) 914.86/294.50 s(427) =< s(426)*aux(134) 914.86/294.50 s(428) =< s(424)*s(419) 914.86/294.50 914.86/294.50 with precondition: [V4=0,V1=Out,V1>=2,V>=1] 914.86/294.50 914.86/294.50 * Chain [38,[37],40]: 14*it(37)+1*s(422)+2*s(423)+5*s(424)+1*s(425)+1*s(426)+1*s(427)+1*s(428)+1*s(429)+15*s(580)+3*s(581)+3*s(582)+3*s(584)+3*s(585)+2*s(597)+12 914.86/294.50 Such that:aux(138) =< V1 914.86/294.50 aux(139) =< Out 914.86/294.50 aux(140) =< Out+1 914.86/294.50 aux(141) =< 2*Out+1 914.86/294.50 it(37) =< aux(138) 914.86/294.50 s(580) =< aux(139) 914.86/294.50 s(581) =< aux(140) 914.86/294.50 s(582) =< aux(141) 914.86/294.50 s(580) =< aux(141) 914.86/294.50 s(581) =< aux(141) 914.86/294.50 s(419) =< aux(139)-1 914.86/294.50 s(584) =< s(582)*aux(139) 914.86/294.50 s(585) =< s(580)*s(419) 914.86/294.50 s(597) =< aux(140) 914.86/294.50 aux(69) =< aux(139)*2+1 914.86/294.50 aux(68) =< aux(139)+1 914.86/294.50 aux(67) =< aux(139) 914.86/294.50 s(433) =< it(37)*aux(138) 914.86/294.50 s(422) =< it(37)*aux(138) 914.86/294.50 s(430) =< it(37)*aux(69) 914.86/294.50 s(431) =< it(37)*aux(68) 914.86/294.50 s(432) =< it(37)*aux(67) 914.86/294.50 s(429) =< s(431) 914.86/294.50 s(423) =< s(433) 914.86/294.50 s(424) =< s(432) 914.86/294.50 s(425) =< s(431) 914.86/294.50 s(426) =< s(430) 914.86/294.50 s(424) =< s(430) 914.86/294.50 s(425) =< s(430) 914.86/294.50 s(427) =< s(426)*aux(139) 914.86/294.50 s(428) =< s(424)*s(419) 914.86/294.50 914.86/294.50 with precondition: [V4=0,V=Out,V1>=3,V>=1] 914.86/294.50 914.86/294.50 * Chain [38,46]: 50*s(8)+95*s(10)+130*s(25)+26*s(26)+26*s(27)+26*s(29)+26*s(30)+16*s(50)+13 914.86/294.50 Such that:aux(142) =< 1 914.86/294.50 aux(143) =< V1 914.86/294.50 aux(144) =< V 914.86/294.50 aux(145) =< V+1 914.86/294.50 aux(146) =< 2*V+1 914.86/294.50 s(8) =< aux(143) 914.86/294.50 s(10) =< aux(142) 914.86/294.50 s(25) =< aux(144) 914.86/294.50 s(26) =< aux(145) 914.86/294.50 s(27) =< aux(146) 914.86/294.50 s(25) =< aux(146) 914.86/294.50 s(26) =< aux(146) 914.86/294.50 s(28) =< aux(144)-1 914.86/294.50 s(29) =< s(27)*aux(144) 914.86/294.50 s(30) =< s(25)*s(28) 914.86/294.50 s(50) =< aux(145) 914.86/294.50 914.86/294.50 with precondition: [V4=0,Out=0,V1>=1,V>=1] 914.86/294.50 914.86/294.50 * Chain [38,45]: 24*s(434)+55*s(444)+11*s(445)+11*s(446)+11*s(448)+11*s(449)+7*s(469)+20*s(493)+13 914.86/294.50 Such that:aux(147) =< 1 914.86/294.50 aux(148) =< V 914.86/294.50 aux(149) =< V+1 914.86/294.50 aux(150) =< 2*V+1 914.86/294.50 aux(151) =< Out 914.86/294.50 s(493) =< aux(151) 914.86/294.50 s(434) =< aux(147) 914.86/294.50 s(444) =< aux(148) 914.86/294.50 s(445) =< aux(149) 914.86/294.50 s(446) =< aux(150) 914.86/294.50 s(444) =< aux(150) 914.86/294.50 s(445) =< aux(150) 914.86/294.50 s(447) =< aux(148)-1 914.86/294.50 s(448) =< s(446)*aux(148) 914.86/294.50 s(449) =< s(444)*s(447) 914.86/294.50 s(469) =< aux(149) 914.86/294.50 914.86/294.50 with precondition: [V4=0,V1=Out,V1>=1,V>=1] 914.86/294.50 914.86/294.50 * Chain [38,40]: 4*s(573)+4*s(574)+15*s(580)+3*s(581)+3*s(582)+3*s(584)+3*s(585)+2*s(597)+12 914.86/294.50 Such that:aux(108) =< 1 914.86/294.50 aux(152) =< V1 914.86/294.50 aux(153) =< Out 914.86/294.50 aux(154) =< Out+1 914.86/294.50 aux(155) =< 2*Out+1 914.86/294.50 s(573) =< aux(152) 914.86/294.50 s(574) =< aux(108) 914.86/294.50 s(580) =< aux(153) 914.86/294.50 s(581) =< aux(154) 914.86/294.50 s(582) =< aux(155) 914.86/294.50 s(580) =< aux(155) 914.86/294.50 s(581) =< aux(155) 914.86/294.50 s(583) =< aux(153)-1 914.86/294.50 s(584) =< s(582)*aux(153) 914.86/294.50 s(585) =< s(580)*s(583) 914.86/294.50 s(597) =< aux(154) 914.86/294.50 914.86/294.50 with precondition: [V4=0,V=Out,V1>=2,V>=1] 914.86/294.50 914.86/294.50 914.86/294.50 #### Cost of chains of start(V1,V,V4,V13,V11): 914.86/294.50 * Chain [47]: 12*s(1011)+416*s(1018)+1261*s(1019)+630*s(1020)+126*s(1021)+126*s(1022)+126*s(1024)+126*s(1025)+239*s(1026)+6*s(1027)+1*s(1032)+1*s(1036)+2*s(1037)+5*s(1038)+1*s(1039)+1*s(1040)+1*s(1041)+1*s(1042)+94*s(1043)+2*s(1045)+2*s(1049)+4*s(1050)+10*s(1051)+2*s(1052)+2*s(1053)+2*s(1054)+2*s(1055)+6*s(1090)+1*s(1119)+1*s(1123)+2*s(1124)+5*s(1125)+1*s(1126)+1*s(1127)+1*s(1128)+1*s(1129)+570*s(1130)+768*s(1137)+1610*s(1139)+322*s(1140)+322*s(1141)+322*s(1143)+322*s(1144)+26*s(1146)+4*s(1151)+4*s(1155)+8*s(1156)+20*s(1157)+4*s(1158)+4*s(1159)+4*s(1160)+4*s(1161)+2*s(1164)+2*s(1168)+4*s(1169)+10*s(1170)+2*s(1171)+2*s(1172)+2*s(1173)+2*s(1174)+2*s(1272)+2*s(1276)+4*s(1277)+10*s(1278)+2*s(1279)+2*s(1280)+2*s(1281)+2*s(1282)+12*s(1289)+2*s(1323)+2*s(1327)+4*s(1328)+10*s(1329)+2*s(1330)+2*s(1331)+2*s(1332)+2*s(1333)+6*s(1448)+1*s(1477)+1*s(1481)+2*s(1482)+5*s(1483)+1*s(1484)+1*s(1485)+1*s(1486)+1*s(1487)+5*s(1492)+1*s(1493)+1*s(1494)+1*s(1496)+1*s(1497)+15 914.86/294.50 Such that:s(1490) =< V1+1 914.86/294.50 s(1448) =< V1-V4 914.86/294.50 s(1491) =< 2*V1+1 914.86/294.50 s(1090) =< V4-V11 914.86/294.50 aux(193) =< 1 914.86/294.50 aux(194) =< V1 914.86/294.50 aux(195) =< V 914.86/294.50 aux(196) =< V+1 914.86/294.50 aux(197) =< V-V4+1 914.86/294.50 aux(198) =< 2*V+1 914.86/294.50 aux(199) =< V4 914.86/294.50 aux(200) =< V13 914.86/294.50 aux(201) =< V13+1 914.86/294.50 aux(202) =< V13-V11 914.86/294.50 aux(203) =< 2*V13+1 914.86/294.50 aux(204) =< V11+1 914.86/294.50 s(1137) =< aux(194) 914.86/294.50 s(1146) =< aux(195) 914.86/294.50 s(1289) =< aux(197) 914.86/294.50 s(1011) =< aux(202) 914.86/294.50 s(1018) =< aux(199) 914.86/294.50 s(1019) =< aux(193) 914.86/294.50 s(1020) =< aux(200) 914.86/294.50 s(1021) =< aux(201) 914.86/294.50 s(1022) =< aux(203) 914.86/294.50 s(1020) =< aux(203) 914.86/294.50 s(1021) =< aux(203) 914.86/294.50 s(1023) =< aux(200)-1 914.86/294.50 s(1024) =< s(1022)*aux(200) 914.86/294.50 s(1025) =< s(1020)*s(1023) 914.86/294.50 s(1026) =< aux(201) 914.86/294.50 s(1027) =< aux(200) 914.86/294.50 s(1028) =< aux(200)*2+1 914.86/294.50 s(1029) =< aux(200)+1 914.86/294.50 s(1030) =< aux(200) 914.86/294.50 s(1031) =< s(1027)*aux(199) 914.86/294.50 s(1032) =< s(1027)*aux(199) 914.86/294.50 s(1033) =< s(1027)*s(1028) 914.86/294.50 s(1034) =< s(1027)*s(1029) 914.86/294.50 s(1035) =< s(1027)*s(1030) 914.86/294.50 s(1036) =< s(1034) 914.86/294.50 s(1037) =< s(1031) 914.86/294.50 s(1038) =< s(1035) 914.86/294.50 s(1039) =< s(1034) 914.86/294.50 s(1040) =< s(1033) 914.86/294.50 s(1038) =< s(1033) 914.86/294.50 s(1039) =< s(1033) 914.86/294.50 s(1041) =< s(1040)*aux(200) 914.86/294.50 s(1042) =< s(1038)*s(1023) 914.86/294.50 s(1043) =< aux(204) 914.86/294.50 s(1044) =< s(1011)*aux(199) 914.86/294.50 s(1045) =< s(1011)*aux(199) 914.86/294.50 s(1046) =< s(1011)*s(1028) 914.86/294.50 s(1047) =< s(1011)*s(1029) 914.86/294.50 s(1048) =< s(1011)*s(1030) 914.86/294.50 s(1049) =< s(1047) 914.86/294.50 s(1050) =< s(1044) 914.86/294.50 s(1051) =< s(1048) 914.86/294.50 s(1052) =< s(1047) 914.86/294.50 s(1053) =< s(1046) 914.86/294.50 s(1051) =< s(1046) 914.86/294.50 s(1052) =< s(1046) 914.86/294.50 s(1054) =< s(1053)*aux(200) 914.86/294.50 s(1055) =< s(1051)*s(1023) 914.86/294.50 s(1130) =< aux(196) 914.86/294.50 s(1139) =< aux(195) 914.86/294.50 s(1140) =< aux(196) 914.86/294.50 s(1141) =< aux(198) 914.86/294.50 s(1139) =< aux(198) 914.86/294.50 s(1140) =< aux(198) 914.86/294.50 s(1142) =< aux(195)-1 914.86/294.50 s(1143) =< s(1141)*aux(195) 914.86/294.50 s(1144) =< s(1139)*s(1142) 914.86/294.50 s(1147) =< aux(195)*2+1 914.86/294.50 s(1148) =< aux(195)+1 914.86/294.50 s(1149) =< aux(195) 914.86/294.50 s(1150) =< s(1146)*aux(194) 914.86/294.50 s(1151) =< s(1146)*aux(194) 914.86/294.50 s(1152) =< s(1146)*s(1147) 914.86/294.50 s(1153) =< s(1146)*s(1148) 914.86/294.50 s(1154) =< s(1146)*s(1149) 914.86/294.50 s(1155) =< s(1153) 914.86/294.50 s(1156) =< s(1150) 914.86/294.50 s(1157) =< s(1154) 914.86/294.50 s(1158) =< s(1153) 914.86/294.50 s(1159) =< s(1152) 914.86/294.50 s(1157) =< s(1152) 914.86/294.50 s(1158) =< s(1152) 914.86/294.50 s(1160) =< s(1159)*aux(195) 914.86/294.50 s(1161) =< s(1157)*s(1142) 914.86/294.50 s(1163) =< s(1130)*aux(194) 914.86/294.50 s(1164) =< s(1130)*aux(194) 914.86/294.50 s(1165) =< s(1130)*s(1147) 914.86/294.50 s(1166) =< s(1130)*s(1148) 914.86/294.50 s(1167) =< s(1130)*s(1149) 914.86/294.50 s(1168) =< s(1166) 914.86/294.50 s(1169) =< s(1163) 914.86/294.50 s(1170) =< s(1167) 914.86/294.50 s(1171) =< s(1166) 914.86/294.50 s(1172) =< s(1165) 914.86/294.50 s(1170) =< s(1165) 914.86/294.50 s(1171) =< s(1165) 914.86/294.50 s(1173) =< s(1172)*aux(195) 914.86/294.50 s(1174) =< s(1170)*s(1142) 914.86/294.50 s(1271) =< s(1137)*aux(194) 914.86/294.50 s(1272) =< s(1137)*aux(194) 914.86/294.50 s(1273) =< s(1137)*s(1147) 914.86/294.50 s(1274) =< s(1137)*s(1148) 914.86/294.50 s(1275) =< s(1137)*s(1149) 914.86/294.50 s(1276) =< s(1274) 914.86/294.50 s(1277) =< s(1271) 914.86/294.50 s(1278) =< s(1275) 914.86/294.50 s(1279) =< s(1274) 914.86/294.50 s(1280) =< s(1273) 914.86/294.50 s(1278) =< s(1273) 914.86/294.50 s(1279) =< s(1273) 914.86/294.50 s(1281) =< s(1280)*aux(195) 914.86/294.50 s(1282) =< s(1278)*s(1142) 914.86/294.50 s(1322) =< s(1289)*aux(194) 914.86/294.50 s(1323) =< s(1289)*aux(194) 914.86/294.50 s(1324) =< s(1289)*s(1147) 914.86/294.50 s(1325) =< s(1289)*s(1148) 914.86/294.50 s(1326) =< s(1289)*s(1149) 914.86/294.50 s(1327) =< s(1325) 914.86/294.50 s(1328) =< s(1322) 914.86/294.50 s(1329) =< s(1326) 914.86/294.50 s(1330) =< s(1325) 914.86/294.50 s(1331) =< s(1324) 914.86/294.50 s(1329) =< s(1324) 914.86/294.50 s(1330) =< s(1324) 914.86/294.50 s(1332) =< s(1331)*aux(195) 914.86/294.50 s(1333) =< s(1329)*s(1142) 914.86/294.50 s(1476) =< s(1448)*aux(194) 914.86/294.50 s(1477) =< s(1448)*aux(194) 914.86/294.50 s(1478) =< s(1448)*s(1147) 914.86/294.50 s(1479) =< s(1448)*s(1148) 914.86/294.50 s(1480) =< s(1448)*s(1149) 914.86/294.50 s(1481) =< s(1479) 914.86/294.50 s(1482) =< s(1476) 914.86/294.50 s(1483) =< s(1480) 914.86/294.50 s(1484) =< s(1479) 914.86/294.50 s(1485) =< s(1478) 914.86/294.50 s(1483) =< s(1478) 914.86/294.50 s(1484) =< s(1478) 914.86/294.50 s(1486) =< s(1485)*aux(195) 914.86/294.50 s(1487) =< s(1483)*s(1142) 914.86/294.50 s(1492) =< aux(194) 914.86/294.50 s(1493) =< s(1490) 914.86/294.50 s(1494) =< s(1491) 914.86/294.50 s(1492) =< s(1491) 914.86/294.50 s(1493) =< s(1491) 914.86/294.50 s(1495) =< aux(194)-1 914.86/294.50 s(1496) =< s(1494)*aux(194) 914.86/294.50 s(1497) =< s(1492)*s(1495) 914.86/294.50 s(1118) =< s(1090)*aux(199) 914.86/294.50 s(1119) =< s(1090)*aux(199) 914.86/294.50 s(1120) =< s(1090)*s(1028) 914.86/294.50 s(1121) =< s(1090)*s(1029) 914.86/294.50 s(1122) =< s(1090)*s(1030) 914.86/294.50 s(1123) =< s(1121) 914.86/294.50 s(1124) =< s(1118) 914.86/294.50 s(1125) =< s(1122) 914.86/294.50 s(1126) =< s(1121) 914.86/294.50 s(1127) =< s(1120) 914.86/294.50 s(1125) =< s(1120) 914.86/294.50 s(1126) =< s(1120) 914.86/294.50 s(1128) =< s(1127)*aux(200) 914.86/294.50 s(1129) =< s(1125)*s(1023) 914.86/294.50 914.86/294.50 with precondition: [] 914.86/294.50 914.86/294.50 914.86/294.50 Closed-form bounds of start(V1,V,V4,V13,V11): 914.86/294.50 ------------------------------------- 914.86/294.50 * Chain [47] with precondition: [] 914.86/294.50 - Upper bound: nat(V1)*779+1276+nat(V1)*6*nat(V1)+nat(V1)*32*nat(V)+nat(V1)*4*nat(V)*nat(V)+nat(V1)*2*nat(V)*nat(nat(V)+ -1)+nat(nat(V1)+ -1)*nat(V1)+nat(V1)*6*nat(V+1)+nat(2*V1+1)*nat(V1)+nat(V1)*6*nat(V-V4+1)+nat(V1)*3*nat(V1-V4)+nat(V)*1648+nat(V)*40*nat(V)+nat(V)*8*nat(V)*nat(V)+nat(V)*4*nat(V)*nat(nat(V)+ -1)+nat(V)*4*nat(V)*nat(V+1)+nat(V)*4*nat(V)*nat(V-V4+1)+nat(V)*2*nat(V)*nat(V1-V4)+nat(V)*322*nat(nat(V)+ -1)+nat(V)*2*nat(nat(V)+ -1)*nat(V+1)+nat(V)*2*nat(nat(V)+ -1)*nat(V-V4+1)+nat(nat(V)+ -1)*nat(V)*nat(V1-V4)+nat(V)*20*nat(V+1)+nat(V)*322*nat(2*V+1)+nat(V)*20*nat(V-V4+1)+nat(V)*10*nat(V1-V4)+nat(V4)*416+nat(V4)*3*nat(V13)+nat(V4)*3*nat(V4-V11)+nat(V4)*6*nat(V13-V11)+nat(V13)*639+nat(V13)*10*nat(V13)+nat(V13)*2*nat(V13)*nat(V13)+nat(V13)*nat(V13)*nat(nat(V13)+ -1)+nat(V13)*2*nat(V13)*nat(V4-V11)+nat(V13)*4*nat(V13)*nat(V13-V11)+nat(V13)*126*nat(nat(V13)+ -1)+nat(nat(V13)+ -1)*nat(V13)*nat(V4-V11)+nat(V13)*2*nat(nat(V13)+ -1)*nat(V13-V11)+nat(V13)*126*nat(2*V13+1)+nat(V13)*10*nat(V4-V11)+nat(V13)*20*nat(V13-V11)+nat(V1+1)+nat(V+1)*898+nat(V13+1)*365+nat(V11+1)*94+nat(2*V1+1)+nat(2*V+1)*322+nat(2*V13+1)*126+nat(V-V4+1)*18+nat(V1-V4)*9+nat(V4-V11)*9+nat(V13-V11)*18 914.86/294.50 - Complexity: n^3 914.86/294.50 914.86/294.50 ### Maximum cost of start(V1,V,V4,V13,V11): nat(V1)*779+1276+nat(V1)*6*nat(V1)+nat(V1)*32*nat(V)+nat(V1)*4*nat(V)*nat(V)+nat(V1)*2*nat(V)*nat(nat(V)+ -1)+nat(nat(V1)+ -1)*nat(V1)+nat(V1)*6*nat(V+1)+nat(2*V1+1)*nat(V1)+nat(V1)*6*nat(V-V4+1)+nat(V1)*3*nat(V1-V4)+nat(V)*1648+nat(V)*40*nat(V)+nat(V)*8*nat(V)*nat(V)+nat(V)*4*nat(V)*nat(nat(V)+ -1)+nat(V)*4*nat(V)*nat(V+1)+nat(V)*4*nat(V)*nat(V-V4+1)+nat(V)*2*nat(V)*nat(V1-V4)+nat(V)*322*nat(nat(V)+ -1)+nat(V)*2*nat(nat(V)+ -1)*nat(V+1)+nat(V)*2*nat(nat(V)+ -1)*nat(V-V4+1)+nat(nat(V)+ -1)*nat(V)*nat(V1-V4)+nat(V)*20*nat(V+1)+nat(V)*322*nat(2*V+1)+nat(V)*20*nat(V-V4+1)+nat(V)*10*nat(V1-V4)+nat(V4)*416+nat(V4)*3*nat(V13)+nat(V4)*3*nat(V4-V11)+nat(V4)*6*nat(V13-V11)+nat(V13)*639+nat(V13)*10*nat(V13)+nat(V13)*2*nat(V13)*nat(V13)+nat(V13)*nat(V13)*nat(nat(V13)+ -1)+nat(V13)*2*nat(V13)*nat(V4-V11)+nat(V13)*4*nat(V13)*nat(V13-V11)+nat(V13)*126*nat(nat(V13)+ -1)+nat(nat(V13)+ -1)*nat(V13)*nat(V4-V11)+nat(V13)*2*nat(nat(V13)+ -1)*nat(V13-V11)+nat(V13)*126*nat(2*V13+1)+nat(V13)*10*nat(V4-V11)+nat(V13)*20*nat(V13-V11)+nat(V1+1)+nat(V+1)*898+nat(V13+1)*365+nat(V11+1)*94+nat(2*V1+1)+nat(2*V+1)*322+nat(2*V13+1)*126+nat(V-V4+1)*18+nat(V1-V4)*9+nat(V4-V11)*9+nat(V13-V11)*18 914.86/294.50 Asymptotic class: n^3 914.86/294.50 * Total analysis performed in 3193 ms. 914.86/294.50 914.86/294.50 914.86/294.50 ---------------------------------------- 914.86/294.50 914.86/294.50 (10) 914.86/294.50 BOUNDS(1, n^3) 914.86/294.50 914.86/294.50 ---------------------------------------- 914.86/294.50 914.86/294.50 (11) RenamingProof (BOTH BOUNDS(ID, ID)) 914.86/294.50 Renamed function symbols to avoid clashes with predefined symbol. 914.86/294.50 ---------------------------------------- 914.86/294.50 914.86/294.50 (12) 914.86/294.50 Obligation: 914.86/294.50 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 914.86/294.50 914.86/294.50 914.86/294.50 The TRS R consists of the following rules: 914.86/294.50 914.86/294.50 lessElements(l, t) -> lessE(l, t, 0') 914.86/294.50 lessE(l, t, n) -> if(le(length(l), n), le(length(toList(t)), n), l, t, n) 914.86/294.50 if(true, b, l, t, n) -> l 914.86/294.50 if(false, true, l, t, n) -> t 914.86/294.50 if(false, false, l, t, n) -> lessE(l, t, s(n)) 914.86/294.50 length(nil) -> 0' 914.86/294.50 length(cons(n, l)) -> s(length(l)) 914.86/294.50 toList(leaf) -> nil 914.86/294.50 toList(node(t1, n, t2)) -> append(toList(t1), cons(n, toList(t2))) 914.86/294.50 append(nil, l2) -> l2 914.86/294.50 append(cons(n, l1), l2) -> cons(n, append(l1, l2)) 914.86/294.50 le(s(n), 0') -> false 914.86/294.50 le(0', m) -> true 914.86/294.50 le(s(n), s(m)) -> le(n, m) 914.86/294.50 a -> c 914.86/294.50 a -> d 914.86/294.50 914.86/294.50 S is empty. 914.86/294.50 Rewrite Strategy: INNERMOST 914.86/294.50 ---------------------------------------- 914.86/294.50 914.86/294.50 (13) SlicingProof (LOWER BOUND(ID)) 914.86/294.50 Sliced the following arguments: 914.86/294.50 cons/0 914.86/294.50 node/1 914.86/294.50 914.86/294.50 ---------------------------------------- 914.86/294.50 914.86/294.50 (14) 914.86/294.50 Obligation: 914.86/294.50 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 914.86/294.50 914.86/294.50 914.86/294.50 The TRS R consists of the following rules: 914.86/294.50 914.86/294.50 lessElements(l, t) -> lessE(l, t, 0') 914.86/294.50 lessE(l, t, n) -> if(le(length(l), n), le(length(toList(t)), n), l, t, n) 914.86/294.50 if(true, b, l, t, n) -> l 914.86/294.50 if(false, true, l, t, n) -> t 914.86/294.50 if(false, false, l, t, n) -> lessE(l, t, s(n)) 914.86/294.50 length(nil) -> 0' 914.86/294.50 length(cons(l)) -> s(length(l)) 914.86/294.50 toList(leaf) -> nil 914.86/294.50 toList(node(t1, t2)) -> append(toList(t1), cons(toList(t2))) 914.86/294.50 append(nil, l2) -> l2 914.86/294.50 append(cons(l1), l2) -> cons(append(l1, l2)) 914.86/294.50 le(s(n), 0') -> false 914.86/294.50 le(0', m) -> true 914.86/294.50 le(s(n), s(m)) -> le(n, m) 914.86/294.50 a -> c 914.86/294.50 a -> d 914.86/294.50 914.86/294.50 S is empty. 914.86/294.50 Rewrite Strategy: INNERMOST 914.86/294.50 ---------------------------------------- 914.86/294.50 914.86/294.50 (15) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 914.86/294.50 Infered types. 914.86/294.50 ---------------------------------------- 914.86/294.50 914.86/294.50 (16) 914.86/294.50 Obligation: 914.86/294.50 Innermost TRS: 914.86/294.50 Rules: 914.86/294.50 lessElements(l, t) -> lessE(l, t, 0') 914.86/294.50 lessE(l, t, n) -> if(le(length(l), n), le(length(toList(t)), n), l, t, n) 914.86/294.50 if(true, b, l, t, n) -> l 914.86/294.50 if(false, true, l, t, n) -> t 914.86/294.50 if(false, false, l, t, n) -> lessE(l, t, s(n)) 914.86/294.50 length(nil) -> 0' 914.86/294.50 length(cons(l)) -> s(length(l)) 914.86/294.50 toList(leaf) -> nil 914.86/294.50 toList(node(t1, t2)) -> append(toList(t1), cons(toList(t2))) 914.86/294.50 append(nil, l2) -> l2 914.86/294.50 append(cons(l1), l2) -> cons(append(l1, l2)) 914.86/294.50 le(s(n), 0') -> false 914.86/294.50 le(0', m) -> true 914.86/294.50 le(s(n), s(m)) -> le(n, m) 914.86/294.50 a -> c 914.86/294.50 a -> d 914.86/294.50 914.86/294.50 Types: 914.86/294.50 lessElements :: nil:cons:leaf:node -> nil:cons:leaf:node -> nil:cons:leaf:node 914.86/294.50 lessE :: nil:cons:leaf:node -> nil:cons:leaf:node -> 0':s -> nil:cons:leaf:node 914.86/294.50 0' :: 0':s 914.86/294.50 if :: true:false -> true:false -> nil:cons:leaf:node -> nil:cons:leaf:node -> 0':s -> nil:cons:leaf:node 914.86/294.50 le :: 0':s -> 0':s -> true:false 914.86/294.50 length :: nil:cons:leaf:node -> 0':s 914.86/294.50 toList :: nil:cons:leaf:node -> nil:cons:leaf:node 914.86/294.50 true :: true:false 914.86/294.50 false :: true:false 914.86/294.50 s :: 0':s -> 0':s 914.86/294.50 nil :: nil:cons:leaf:node 914.86/294.50 cons :: nil:cons:leaf:node -> nil:cons:leaf:node 914.86/294.50 leaf :: nil:cons:leaf:node 914.86/294.50 node :: nil:cons:leaf:node -> nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.50 append :: nil:cons:leaf:node -> nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.50 a :: c:d 914.96/294.50 c :: c:d 914.96/294.50 d :: c:d 914.96/294.50 hole_nil:cons:leaf:node1_0 :: nil:cons:leaf:node 914.96/294.50 hole_0':s2_0 :: 0':s 914.96/294.50 hole_true:false3_0 :: true:false 914.96/294.50 hole_c:d4_0 :: c:d 914.96/294.50 gen_nil:cons:leaf:node5_0 :: Nat -> nil:cons:leaf:node 914.96/294.50 gen_0':s6_0 :: Nat -> 0':s 914.96/294.50 914.96/294.50 ---------------------------------------- 914.96/294.50 914.96/294.50 (17) OrderProof (LOWER BOUND(ID)) 914.96/294.50 Heuristically decided to analyse the following defined symbols: 914.96/294.50 lessE, le, length, toList, append 914.96/294.50 914.96/294.50 They will be analysed ascendingly in the following order: 914.96/294.50 le < lessE 914.96/294.50 length < lessE 914.96/294.50 toList < lessE 914.96/294.50 append < toList 914.96/294.50 914.96/294.50 ---------------------------------------- 914.96/294.50 914.96/294.50 (18) 914.96/294.50 Obligation: 914.96/294.50 Innermost TRS: 914.96/294.50 Rules: 914.96/294.50 lessElements(l, t) -> lessE(l, t, 0') 914.96/294.50 lessE(l, t, n) -> if(le(length(l), n), le(length(toList(t)), n), l, t, n) 914.96/294.50 if(true, b, l, t, n) -> l 914.96/294.50 if(false, true, l, t, n) -> t 914.96/294.50 if(false, false, l, t, n) -> lessE(l, t, s(n)) 914.96/294.50 length(nil) -> 0' 914.96/294.50 length(cons(l)) -> s(length(l)) 914.96/294.50 toList(leaf) -> nil 914.96/294.50 toList(node(t1, t2)) -> append(toList(t1), cons(toList(t2))) 914.96/294.50 append(nil, l2) -> l2 914.96/294.50 append(cons(l1), l2) -> cons(append(l1, l2)) 914.96/294.50 le(s(n), 0') -> false 914.96/294.50 le(0', m) -> true 914.96/294.50 le(s(n), s(m)) -> le(n, m) 914.96/294.50 a -> c 914.96/294.50 a -> d 914.96/294.50 914.96/294.50 Types: 914.96/294.50 lessElements :: nil:cons:leaf:node -> nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.50 lessE :: nil:cons:leaf:node -> nil:cons:leaf:node -> 0':s -> nil:cons:leaf:node 914.96/294.50 0' :: 0':s 914.96/294.50 if :: true:false -> true:false -> nil:cons:leaf:node -> nil:cons:leaf:node -> 0':s -> nil:cons:leaf:node 914.96/294.50 le :: 0':s -> 0':s -> true:false 914.96/294.50 length :: nil:cons:leaf:node -> 0':s 914.96/294.50 toList :: nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.50 true :: true:false 914.96/294.50 false :: true:false 914.96/294.50 s :: 0':s -> 0':s 914.96/294.50 nil :: nil:cons:leaf:node 914.96/294.50 cons :: nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.50 leaf :: nil:cons:leaf:node 914.96/294.50 node :: nil:cons:leaf:node -> nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.50 append :: nil:cons:leaf:node -> nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.50 a :: c:d 914.96/294.50 c :: c:d 914.96/294.50 d :: c:d 914.96/294.50 hole_nil:cons:leaf:node1_0 :: nil:cons:leaf:node 914.96/294.50 hole_0':s2_0 :: 0':s 914.96/294.50 hole_true:false3_0 :: true:false 914.96/294.50 hole_c:d4_0 :: c:d 914.96/294.50 gen_nil:cons:leaf:node5_0 :: Nat -> nil:cons:leaf:node 914.96/294.50 gen_0':s6_0 :: Nat -> 0':s 914.96/294.50 914.96/294.50 914.96/294.50 Generator Equations: 914.96/294.50 gen_nil:cons:leaf:node5_0(0) <=> nil 914.96/294.50 gen_nil:cons:leaf:node5_0(+(x, 1)) <=> cons(gen_nil:cons:leaf:node5_0(x)) 914.96/294.50 gen_0':s6_0(0) <=> 0' 914.96/294.50 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 914.96/294.50 914.96/294.50 914.96/294.50 The following defined symbols remain to be analysed: 914.96/294.50 le, lessE, length, toList, append 914.96/294.50 914.96/294.50 They will be analysed ascendingly in the following order: 914.96/294.50 le < lessE 914.96/294.50 length < lessE 914.96/294.50 toList < lessE 914.96/294.50 append < toList 914.96/294.50 914.96/294.50 ---------------------------------------- 914.96/294.50 914.96/294.50 (19) RewriteLemmaProof (LOWER BOUND(ID)) 914.96/294.50 Proved the following rewrite lemma: 914.96/294.50 le(gen_0':s6_0(+(1, n8_0)), gen_0':s6_0(n8_0)) -> false, rt in Omega(1 + n8_0) 914.96/294.50 914.96/294.50 Induction Base: 914.96/294.50 le(gen_0':s6_0(+(1, 0)), gen_0':s6_0(0)) ->_R^Omega(1) 914.96/294.50 false 914.96/294.50 914.96/294.50 Induction Step: 914.96/294.50 le(gen_0':s6_0(+(1, +(n8_0, 1))), gen_0':s6_0(+(n8_0, 1))) ->_R^Omega(1) 914.96/294.50 le(gen_0':s6_0(+(1, n8_0)), gen_0':s6_0(n8_0)) ->_IH 914.96/294.50 false 914.96/294.50 914.96/294.50 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 914.96/294.50 ---------------------------------------- 914.96/294.50 914.96/294.50 (20) 914.96/294.50 Complex Obligation (BEST) 914.96/294.50 914.96/294.50 ---------------------------------------- 914.96/294.50 914.96/294.50 (21) 914.96/294.50 Obligation: 914.96/294.50 Proved the lower bound n^1 for the following obligation: 914.96/294.50 914.96/294.50 Innermost TRS: 914.96/294.50 Rules: 914.96/294.50 lessElements(l, t) -> lessE(l, t, 0') 914.96/294.50 lessE(l, t, n) -> if(le(length(l), n), le(length(toList(t)), n), l, t, n) 914.96/294.50 if(true, b, l, t, n) -> l 914.96/294.50 if(false, true, l, t, n) -> t 914.96/294.50 if(false, false, l, t, n) -> lessE(l, t, s(n)) 914.96/294.50 length(nil) -> 0' 914.96/294.50 length(cons(l)) -> s(length(l)) 914.96/294.50 toList(leaf) -> nil 914.96/294.50 toList(node(t1, t2)) -> append(toList(t1), cons(toList(t2))) 914.96/294.50 append(nil, l2) -> l2 914.96/294.50 append(cons(l1), l2) -> cons(append(l1, l2)) 914.96/294.50 le(s(n), 0') -> false 914.96/294.50 le(0', m) -> true 914.96/294.50 le(s(n), s(m)) -> le(n, m) 914.96/294.50 a -> c 914.96/294.50 a -> d 914.96/294.50 914.96/294.50 Types: 914.96/294.50 lessElements :: nil:cons:leaf:node -> nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.50 lessE :: nil:cons:leaf:node -> nil:cons:leaf:node -> 0':s -> nil:cons:leaf:node 914.96/294.50 0' :: 0':s 914.96/294.50 if :: true:false -> true:false -> nil:cons:leaf:node -> nil:cons:leaf:node -> 0':s -> nil:cons:leaf:node 914.96/294.50 le :: 0':s -> 0':s -> true:false 914.96/294.50 length :: nil:cons:leaf:node -> 0':s 914.96/294.50 toList :: nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.50 true :: true:false 914.96/294.50 false :: true:false 914.96/294.50 s :: 0':s -> 0':s 914.96/294.50 nil :: nil:cons:leaf:node 914.96/294.50 cons :: nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.50 leaf :: nil:cons:leaf:node 914.96/294.50 node :: nil:cons:leaf:node -> nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.50 append :: nil:cons:leaf:node -> nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.50 a :: c:d 914.96/294.50 c :: c:d 914.96/294.50 d :: c:d 914.96/294.50 hole_nil:cons:leaf:node1_0 :: nil:cons:leaf:node 914.96/294.50 hole_0':s2_0 :: 0':s 914.96/294.50 hole_true:false3_0 :: true:false 914.96/294.50 hole_c:d4_0 :: c:d 914.96/294.50 gen_nil:cons:leaf:node5_0 :: Nat -> nil:cons:leaf:node 914.96/294.50 gen_0':s6_0 :: Nat -> 0':s 914.96/294.50 914.96/294.50 914.96/294.50 Generator Equations: 914.96/294.50 gen_nil:cons:leaf:node5_0(0) <=> nil 914.96/294.50 gen_nil:cons:leaf:node5_0(+(x, 1)) <=> cons(gen_nil:cons:leaf:node5_0(x)) 914.96/294.50 gen_0':s6_0(0) <=> 0' 914.96/294.50 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 914.96/294.50 914.96/294.50 914.96/294.50 The following defined symbols remain to be analysed: 914.96/294.50 le, lessE, length, toList, append 914.96/294.50 914.96/294.50 They will be analysed ascendingly in the following order: 914.96/294.50 le < lessE 914.96/294.50 length < lessE 914.96/294.50 toList < lessE 914.96/294.50 append < toList 914.96/294.50 914.96/294.50 ---------------------------------------- 914.96/294.51 914.96/294.51 (22) LowerBoundPropagationProof (FINISHED) 914.96/294.51 Propagated lower bound. 914.96/294.51 ---------------------------------------- 914.96/294.51 914.96/294.51 (23) 914.96/294.51 BOUNDS(n^1, INF) 914.96/294.51 914.96/294.51 ---------------------------------------- 914.96/294.51 914.96/294.51 (24) 914.96/294.51 Obligation: 914.96/294.51 Innermost TRS: 914.96/294.51 Rules: 914.96/294.51 lessElements(l, t) -> lessE(l, t, 0') 914.96/294.51 lessE(l, t, n) -> if(le(length(l), n), le(length(toList(t)), n), l, t, n) 914.96/294.51 if(true, b, l, t, n) -> l 914.96/294.51 if(false, true, l, t, n) -> t 914.96/294.51 if(false, false, l, t, n) -> lessE(l, t, s(n)) 914.96/294.51 length(nil) -> 0' 914.96/294.51 length(cons(l)) -> s(length(l)) 914.96/294.51 toList(leaf) -> nil 914.96/294.51 toList(node(t1, t2)) -> append(toList(t1), cons(toList(t2))) 914.96/294.51 append(nil, l2) -> l2 914.96/294.51 append(cons(l1), l2) -> cons(append(l1, l2)) 914.96/294.51 le(s(n), 0') -> false 914.96/294.51 le(0', m) -> true 914.96/294.51 le(s(n), s(m)) -> le(n, m) 914.96/294.51 a -> c 914.96/294.51 a -> d 914.96/294.51 914.96/294.51 Types: 914.96/294.51 lessElements :: nil:cons:leaf:node -> nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.51 lessE :: nil:cons:leaf:node -> nil:cons:leaf:node -> 0':s -> nil:cons:leaf:node 914.96/294.51 0' :: 0':s 914.96/294.51 if :: true:false -> true:false -> nil:cons:leaf:node -> nil:cons:leaf:node -> 0':s -> nil:cons:leaf:node 914.96/294.51 le :: 0':s -> 0':s -> true:false 914.96/294.51 length :: nil:cons:leaf:node -> 0':s 914.96/294.51 toList :: nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.51 true :: true:false 914.96/294.51 false :: true:false 914.96/294.51 s :: 0':s -> 0':s 914.96/294.51 nil :: nil:cons:leaf:node 914.96/294.51 cons :: nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.51 leaf :: nil:cons:leaf:node 914.96/294.51 node :: nil:cons:leaf:node -> nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.51 append :: nil:cons:leaf:node -> nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.51 a :: c:d 914.96/294.51 c :: c:d 914.96/294.51 d :: c:d 914.96/294.51 hole_nil:cons:leaf:node1_0 :: nil:cons:leaf:node 914.96/294.51 hole_0':s2_0 :: 0':s 914.96/294.51 hole_true:false3_0 :: true:false 914.96/294.51 hole_c:d4_0 :: c:d 914.96/294.51 gen_nil:cons:leaf:node5_0 :: Nat -> nil:cons:leaf:node 914.96/294.51 gen_0':s6_0 :: Nat -> 0':s 914.96/294.51 914.96/294.51 914.96/294.51 Lemmas: 914.96/294.51 le(gen_0':s6_0(+(1, n8_0)), gen_0':s6_0(n8_0)) -> false, rt in Omega(1 + n8_0) 914.96/294.51 914.96/294.51 914.96/294.51 Generator Equations: 914.96/294.51 gen_nil:cons:leaf:node5_0(0) <=> nil 914.96/294.51 gen_nil:cons:leaf:node5_0(+(x, 1)) <=> cons(gen_nil:cons:leaf:node5_0(x)) 914.96/294.51 gen_0':s6_0(0) <=> 0' 914.96/294.51 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 914.96/294.51 914.96/294.51 914.96/294.51 The following defined symbols remain to be analysed: 914.96/294.51 length, lessE, toList, append 914.96/294.51 914.96/294.51 They will be analysed ascendingly in the following order: 914.96/294.51 length < lessE 914.96/294.51 toList < lessE 914.96/294.51 append < toList 914.96/294.51 914.96/294.51 ---------------------------------------- 914.96/294.51 914.96/294.51 (25) RewriteLemmaProof (LOWER BOUND(ID)) 914.96/294.51 Proved the following rewrite lemma: 914.96/294.51 length(gen_nil:cons:leaf:node5_0(n307_0)) -> gen_0':s6_0(n307_0), rt in Omega(1 + n307_0) 914.96/294.51 914.96/294.51 Induction Base: 914.96/294.51 length(gen_nil:cons:leaf:node5_0(0)) ->_R^Omega(1) 914.96/294.51 0' 914.96/294.51 914.96/294.51 Induction Step: 914.96/294.51 length(gen_nil:cons:leaf:node5_0(+(n307_0, 1))) ->_R^Omega(1) 914.96/294.51 s(length(gen_nil:cons:leaf:node5_0(n307_0))) ->_IH 914.96/294.51 s(gen_0':s6_0(c308_0)) 914.96/294.51 914.96/294.51 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 914.96/294.51 ---------------------------------------- 914.96/294.51 914.96/294.51 (26) 914.96/294.51 Obligation: 914.96/294.51 Innermost TRS: 914.96/294.51 Rules: 914.96/294.51 lessElements(l, t) -> lessE(l, t, 0') 914.96/294.51 lessE(l, t, n) -> if(le(length(l), n), le(length(toList(t)), n), l, t, n) 914.96/294.51 if(true, b, l, t, n) -> l 914.96/294.51 if(false, true, l, t, n) -> t 914.96/294.51 if(false, false, l, t, n) -> lessE(l, t, s(n)) 914.96/294.51 length(nil) -> 0' 914.96/294.51 length(cons(l)) -> s(length(l)) 914.96/294.51 toList(leaf) -> nil 914.96/294.51 toList(node(t1, t2)) -> append(toList(t1), cons(toList(t2))) 914.96/294.51 append(nil, l2) -> l2 914.96/294.51 append(cons(l1), l2) -> cons(append(l1, l2)) 914.96/294.51 le(s(n), 0') -> false 914.96/294.51 le(0', m) -> true 914.96/294.51 le(s(n), s(m)) -> le(n, m) 914.96/294.51 a -> c 914.96/294.51 a -> d 914.96/294.51 914.96/294.51 Types: 914.96/294.51 lessElements :: nil:cons:leaf:node -> nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.51 lessE :: nil:cons:leaf:node -> nil:cons:leaf:node -> 0':s -> nil:cons:leaf:node 914.96/294.51 0' :: 0':s 914.96/294.51 if :: true:false -> true:false -> nil:cons:leaf:node -> nil:cons:leaf:node -> 0':s -> nil:cons:leaf:node 914.96/294.51 le :: 0':s -> 0':s -> true:false 914.96/294.51 length :: nil:cons:leaf:node -> 0':s 914.96/294.51 toList :: nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.51 true :: true:false 914.96/294.51 false :: true:false 914.96/294.51 s :: 0':s -> 0':s 914.96/294.51 nil :: nil:cons:leaf:node 914.96/294.51 cons :: nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.51 leaf :: nil:cons:leaf:node 914.96/294.51 node :: nil:cons:leaf:node -> nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.51 append :: nil:cons:leaf:node -> nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.51 a :: c:d 914.96/294.51 c :: c:d 914.96/294.51 d :: c:d 914.96/294.51 hole_nil:cons:leaf:node1_0 :: nil:cons:leaf:node 914.96/294.51 hole_0':s2_0 :: 0':s 914.96/294.51 hole_true:false3_0 :: true:false 914.96/294.51 hole_c:d4_0 :: c:d 914.96/294.51 gen_nil:cons:leaf:node5_0 :: Nat -> nil:cons:leaf:node 914.96/294.51 gen_0':s6_0 :: Nat -> 0':s 914.96/294.51 914.96/294.51 914.96/294.51 Lemmas: 914.96/294.51 le(gen_0':s6_0(+(1, n8_0)), gen_0':s6_0(n8_0)) -> false, rt in Omega(1 + n8_0) 914.96/294.51 length(gen_nil:cons:leaf:node5_0(n307_0)) -> gen_0':s6_0(n307_0), rt in Omega(1 + n307_0) 914.96/294.51 914.96/294.51 914.96/294.51 Generator Equations: 914.96/294.51 gen_nil:cons:leaf:node5_0(0) <=> nil 914.96/294.51 gen_nil:cons:leaf:node5_0(+(x, 1)) <=> cons(gen_nil:cons:leaf:node5_0(x)) 914.96/294.51 gen_0':s6_0(0) <=> 0' 914.96/294.51 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 914.96/294.51 914.96/294.51 914.96/294.51 The following defined symbols remain to be analysed: 914.96/294.51 append, lessE, toList 914.96/294.51 914.96/294.51 They will be analysed ascendingly in the following order: 914.96/294.51 toList < lessE 914.96/294.51 append < toList 914.96/294.51 914.96/294.51 ---------------------------------------- 914.96/294.51 914.96/294.51 (27) RewriteLemmaProof (LOWER BOUND(ID)) 914.96/294.51 Proved the following rewrite lemma: 914.96/294.51 append(gen_nil:cons:leaf:node5_0(n592_0), gen_nil:cons:leaf:node5_0(b)) -> gen_nil:cons:leaf:node5_0(+(n592_0, b)), rt in Omega(1 + n592_0) 914.96/294.51 914.96/294.51 Induction Base: 914.96/294.51 append(gen_nil:cons:leaf:node5_0(0), gen_nil:cons:leaf:node5_0(b)) ->_R^Omega(1) 914.96/294.51 gen_nil:cons:leaf:node5_0(b) 914.96/294.51 914.96/294.51 Induction Step: 914.96/294.51 append(gen_nil:cons:leaf:node5_0(+(n592_0, 1)), gen_nil:cons:leaf:node5_0(b)) ->_R^Omega(1) 914.96/294.51 cons(append(gen_nil:cons:leaf:node5_0(n592_0), gen_nil:cons:leaf:node5_0(b))) ->_IH 914.96/294.51 cons(gen_nil:cons:leaf:node5_0(+(b, c593_0))) 914.96/294.51 914.96/294.51 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 914.96/294.51 ---------------------------------------- 914.96/294.51 914.96/294.51 (28) 914.96/294.51 Obligation: 914.96/294.51 Innermost TRS: 914.96/294.51 Rules: 914.96/294.51 lessElements(l, t) -> lessE(l, t, 0') 914.96/294.51 lessE(l, t, n) -> if(le(length(l), n), le(length(toList(t)), n), l, t, n) 914.96/294.51 if(true, b, l, t, n) -> l 914.96/294.51 if(false, true, l, t, n) -> t 914.96/294.51 if(false, false, l, t, n) -> lessE(l, t, s(n)) 914.96/294.51 length(nil) -> 0' 914.96/294.51 length(cons(l)) -> s(length(l)) 914.96/294.51 toList(leaf) -> nil 914.96/294.51 toList(node(t1, t2)) -> append(toList(t1), cons(toList(t2))) 914.96/294.51 append(nil, l2) -> l2 914.96/294.51 append(cons(l1), l2) -> cons(append(l1, l2)) 914.96/294.51 le(s(n), 0') -> false 914.96/294.51 le(0', m) -> true 914.96/294.51 le(s(n), s(m)) -> le(n, m) 914.96/294.51 a -> c 914.96/294.51 a -> d 914.96/294.51 914.96/294.51 Types: 914.96/294.51 lessElements :: nil:cons:leaf:node -> nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.51 lessE :: nil:cons:leaf:node -> nil:cons:leaf:node -> 0':s -> nil:cons:leaf:node 914.96/294.51 0' :: 0':s 914.96/294.51 if :: true:false -> true:false -> nil:cons:leaf:node -> nil:cons:leaf:node -> 0':s -> nil:cons:leaf:node 914.96/294.51 le :: 0':s -> 0':s -> true:false 914.96/294.51 length :: nil:cons:leaf:node -> 0':s 914.96/294.51 toList :: nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.51 true :: true:false 914.96/294.51 false :: true:false 914.96/294.51 s :: 0':s -> 0':s 914.96/294.51 nil :: nil:cons:leaf:node 914.96/294.51 cons :: nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.51 leaf :: nil:cons:leaf:node 914.96/294.51 node :: nil:cons:leaf:node -> nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.51 append :: nil:cons:leaf:node -> nil:cons:leaf:node -> nil:cons:leaf:node 914.96/294.51 a :: c:d 914.96/294.51 c :: c:d 914.96/294.51 d :: c:d 914.96/294.51 hole_nil:cons:leaf:node1_0 :: nil:cons:leaf:node 914.96/294.51 hole_0':s2_0 :: 0':s 914.96/294.51 hole_true:false3_0 :: true:false 914.96/294.51 hole_c:d4_0 :: c:d 914.96/294.51 gen_nil:cons:leaf:node5_0 :: Nat -> nil:cons:leaf:node 914.96/294.51 gen_0':s6_0 :: Nat -> 0':s 914.96/294.51 914.96/294.51 914.96/294.51 Lemmas: 914.96/294.51 le(gen_0':s6_0(+(1, n8_0)), gen_0':s6_0(n8_0)) -> false, rt in Omega(1 + n8_0) 914.96/294.51 length(gen_nil:cons:leaf:node5_0(n307_0)) -> gen_0':s6_0(n307_0), rt in Omega(1 + n307_0) 914.96/294.51 append(gen_nil:cons:leaf:node5_0(n592_0), gen_nil:cons:leaf:node5_0(b)) -> gen_nil:cons:leaf:node5_0(+(n592_0, b)), rt in Omega(1 + n592_0) 914.96/294.51 914.96/294.51 914.96/294.51 Generator Equations: 914.96/294.51 gen_nil:cons:leaf:node5_0(0) <=> nil 914.96/294.51 gen_nil:cons:leaf:node5_0(+(x, 1)) <=> cons(gen_nil:cons:leaf:node5_0(x)) 914.96/294.51 gen_0':s6_0(0) <=> 0' 914.96/294.51 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 914.96/294.51 914.96/294.51 914.96/294.51 The following defined symbols remain to be analysed: 914.96/294.51 toList, lessE 914.96/294.51 914.96/294.51 They will be analysed ascendingly in the following order: 914.96/294.51 toList < lessE 915.02/294.57 EOF