1150.39/291.53 WORST_CASE(Omega(n^1), O(n^2)) 1150.39/291.54 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 1150.39/291.54 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1150.39/291.54 1150.39/291.54 1150.39/291.54 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1150.39/291.54 1150.39/291.54 (0) CpxTRS 1150.39/291.54 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 1150.39/291.54 (2) CpxWeightedTrs 1150.39/291.54 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1150.39/291.54 (4) CpxTypedWeightedTrs 1150.39/291.54 (5) CompletionProof [UPPER BOUND(ID), 0 ms] 1150.39/291.54 (6) CpxTypedWeightedCompleteTrs 1150.39/291.54 (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 1150.39/291.54 (8) CpxRNTS 1150.39/291.54 (9) CompleteCoflocoProof [FINISHED, 1860 ms] 1150.39/291.54 (10) BOUNDS(1, n^2) 1150.39/291.54 (11) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 1150.39/291.54 (12) TRS for Loop Detection 1150.39/291.54 (13) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 1150.39/291.54 (14) BEST 1150.39/291.54 (15) proven lower bound 1150.39/291.54 (16) LowerBoundPropagationProof [FINISHED, 0 ms] 1150.39/291.54 (17) BOUNDS(n^1, INF) 1150.39/291.54 (18) TRS for Loop Detection 1150.39/291.54 1150.39/291.54 1150.39/291.54 ---------------------------------------- 1150.39/291.54 1150.39/291.54 (0) 1150.39/291.54 Obligation: 1150.39/291.54 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1150.39/291.54 1150.39/291.54 1150.39/291.54 The TRS R consists of the following rules: 1150.39/291.54 1150.39/291.54 ge(0, 0) -> true 1150.39/291.54 ge(s(x), 0) -> ge(x, 0) 1150.39/291.54 ge(0, s(0)) -> false 1150.39/291.54 ge(0, s(s(x))) -> ge(0, s(x)) 1150.39/291.54 ge(s(x), s(y)) -> ge(x, y) 1150.39/291.54 minus(0, 0) -> 0 1150.39/291.54 minus(0, s(x)) -> minus(0, x) 1150.39/291.54 minus(s(x), 0) -> s(minus(x, 0)) 1150.39/291.54 minus(s(x), s(y)) -> minus(x, y) 1150.39/291.54 plus(0, 0) -> 0 1150.39/291.54 plus(0, s(x)) -> s(plus(0, x)) 1150.39/291.54 plus(s(x), y) -> s(plus(x, y)) 1150.39/291.54 div(x, y) -> ify(ge(y, s(0)), x, y) 1150.39/291.54 ify(false, x, y) -> divByZeroError 1150.39/291.54 ify(true, x, y) -> if(ge(x, y), x, y) 1150.39/291.54 if(false, x, y) -> 0 1150.39/291.54 if(true, x, y) -> s(div(minus(x, y), y)) 1150.39/291.54 1150.39/291.54 S is empty. 1150.39/291.54 Rewrite Strategy: INNERMOST 1150.39/291.54 ---------------------------------------- 1150.39/291.54 1150.39/291.54 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 1150.39/291.54 Transformed relative TRS to weighted TRS 1150.39/291.54 ---------------------------------------- 1150.39/291.54 1150.39/291.54 (2) 1150.39/291.54 Obligation: 1150.39/291.54 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). 1150.39/291.55 1150.39/291.55 1150.39/291.55 The TRS R consists of the following rules: 1150.39/291.55 1150.39/291.55 ge(0, 0) -> true [1] 1150.39/291.55 ge(s(x), 0) -> ge(x, 0) [1] 1150.39/291.55 ge(0, s(0)) -> false [1] 1150.39/291.55 ge(0, s(s(x))) -> ge(0, s(x)) [1] 1150.39/291.55 ge(s(x), s(y)) -> ge(x, y) [1] 1150.39/291.55 minus(0, 0) -> 0 [1] 1150.39/291.55 minus(0, s(x)) -> minus(0, x) [1] 1150.39/291.55 minus(s(x), 0) -> s(minus(x, 0)) [1] 1150.39/291.55 minus(s(x), s(y)) -> minus(x, y) [1] 1150.39/291.55 plus(0, 0) -> 0 [1] 1150.39/291.55 plus(0, s(x)) -> s(plus(0, x)) [1] 1150.39/291.55 plus(s(x), y) -> s(plus(x, y)) [1] 1150.39/291.55 div(x, y) -> ify(ge(y, s(0)), x, y) [1] 1150.39/291.55 ify(false, x, y) -> divByZeroError [1] 1150.39/291.55 ify(true, x, y) -> if(ge(x, y), x, y) [1] 1150.39/291.55 if(false, x, y) -> 0 [1] 1150.39/291.55 if(true, x, y) -> s(div(minus(x, y), y)) [1] 1150.39/291.55 1150.39/291.55 Rewrite Strategy: INNERMOST 1150.39/291.55 ---------------------------------------- 1150.39/291.55 1150.39/291.55 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1150.39/291.55 Infered types. 1150.39/291.55 ---------------------------------------- 1150.39/291.55 1150.39/291.55 (4) 1150.39/291.55 Obligation: 1150.39/291.55 Runtime Complexity Weighted TRS with Types. 1150.39/291.55 The TRS R consists of the following rules: 1150.39/291.55 1150.39/291.55 ge(0, 0) -> true [1] 1150.39/291.55 ge(s(x), 0) -> ge(x, 0) [1] 1150.39/291.55 ge(0, s(0)) -> false [1] 1150.39/291.55 ge(0, s(s(x))) -> ge(0, s(x)) [1] 1150.39/291.55 ge(s(x), s(y)) -> ge(x, y) [1] 1150.39/291.55 minus(0, 0) -> 0 [1] 1150.39/291.55 minus(0, s(x)) -> minus(0, x) [1] 1150.39/291.55 minus(s(x), 0) -> s(minus(x, 0)) [1] 1150.39/291.55 minus(s(x), s(y)) -> minus(x, y) [1] 1150.39/291.55 plus(0, 0) -> 0 [1] 1150.39/291.55 plus(0, s(x)) -> s(plus(0, x)) [1] 1150.39/291.55 plus(s(x), y) -> s(plus(x, y)) [1] 1150.39/291.55 div(x, y) -> ify(ge(y, s(0)), x, y) [1] 1150.39/291.55 ify(false, x, y) -> divByZeroError [1] 1150.39/291.55 ify(true, x, y) -> if(ge(x, y), x, y) [1] 1150.39/291.55 if(false, x, y) -> 0 [1] 1150.39/291.55 if(true, x, y) -> s(div(minus(x, y), y)) [1] 1150.39/291.55 1150.39/291.55 The TRS has the following type information: 1150.39/291.55 ge :: 0:s:divByZeroError -> 0:s:divByZeroError -> true:false 1150.39/291.55 0 :: 0:s:divByZeroError 1150.39/291.55 true :: true:false 1150.39/291.55 s :: 0:s:divByZeroError -> 0:s:divByZeroError 1150.39/291.55 false :: true:false 1150.39/291.55 minus :: 0:s:divByZeroError -> 0:s:divByZeroError -> 0:s:divByZeroError 1150.39/291.55 plus :: 0:s:divByZeroError -> 0:s:divByZeroError -> 0:s:divByZeroError 1150.39/291.55 div :: 0:s:divByZeroError -> 0:s:divByZeroError -> 0:s:divByZeroError 1150.39/291.55 ify :: true:false -> 0:s:divByZeroError -> 0:s:divByZeroError -> 0:s:divByZeroError 1150.39/291.55 divByZeroError :: 0:s:divByZeroError 1150.39/291.55 if :: true:false -> 0:s:divByZeroError -> 0:s:divByZeroError -> 0:s:divByZeroError 1150.39/291.55 1150.39/291.55 Rewrite Strategy: INNERMOST 1150.39/291.55 ---------------------------------------- 1150.39/291.55 1150.39/291.55 (5) CompletionProof (UPPER BOUND(ID)) 1150.39/291.55 The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: 1150.39/291.55 1150.39/291.55 ge(v0, v1) -> null_ge [0] 1150.39/291.55 minus(v0, v1) -> null_minus [0] 1150.39/291.55 plus(v0, v1) -> null_plus [0] 1150.39/291.55 ify(v0, v1, v2) -> null_ify [0] 1150.39/291.55 if(v0, v1, v2) -> null_if [0] 1150.39/291.55 1150.39/291.55 And the following fresh constants: null_ge, null_minus, null_plus, null_ify, null_if 1150.39/291.55 1150.39/291.55 ---------------------------------------- 1150.39/291.55 1150.39/291.55 (6) 1150.39/291.55 Obligation: 1150.39/291.55 Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: 1150.39/291.55 1150.39/291.55 Runtime Complexity Weighted TRS with Types. 1150.39/291.55 The TRS R consists of the following rules: 1150.39/291.55 1150.39/291.55 ge(0, 0) -> true [1] 1150.39/291.55 ge(s(x), 0) -> ge(x, 0) [1] 1150.39/291.55 ge(0, s(0)) -> false [1] 1150.39/291.55 ge(0, s(s(x))) -> ge(0, s(x)) [1] 1150.39/291.55 ge(s(x), s(y)) -> ge(x, y) [1] 1150.39/291.55 minus(0, 0) -> 0 [1] 1150.39/291.55 minus(0, s(x)) -> minus(0, x) [1] 1150.39/291.55 minus(s(x), 0) -> s(minus(x, 0)) [1] 1150.39/291.55 minus(s(x), s(y)) -> minus(x, y) [1] 1150.39/291.55 plus(0, 0) -> 0 [1] 1150.39/291.55 plus(0, s(x)) -> s(plus(0, x)) [1] 1150.39/291.55 plus(s(x), y) -> s(plus(x, y)) [1] 1150.39/291.55 div(x, y) -> ify(ge(y, s(0)), x, y) [1] 1150.39/291.55 ify(false, x, y) -> divByZeroError [1] 1150.39/291.55 ify(true, x, y) -> if(ge(x, y), x, y) [1] 1150.39/291.55 if(false, x, y) -> 0 [1] 1150.39/291.55 if(true, x, y) -> s(div(minus(x, y), y)) [1] 1150.39/291.55 ge(v0, v1) -> null_ge [0] 1150.39/291.55 minus(v0, v1) -> null_minus [0] 1150.39/291.55 plus(v0, v1) -> null_plus [0] 1150.39/291.55 ify(v0, v1, v2) -> null_ify [0] 1150.39/291.55 if(v0, v1, v2) -> null_if [0] 1150.39/291.55 1150.39/291.55 The TRS has the following type information: 1150.39/291.55 ge :: 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if -> true:false:null_ge 1150.39/291.55 0 :: 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if 1150.39/291.55 true :: true:false:null_ge 1150.39/291.55 s :: 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if 1150.39/291.55 false :: true:false:null_ge 1150.39/291.55 minus :: 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if 1150.39/291.55 plus :: 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if 1150.39/291.55 div :: 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if 1150.39/291.55 ify :: true:false:null_ge -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if 1150.39/291.55 divByZeroError :: 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if 1150.39/291.55 if :: true:false:null_ge -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if 1150.39/291.55 null_ge :: true:false:null_ge 1150.39/291.55 null_minus :: 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if 1150.39/291.55 null_plus :: 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if 1150.39/291.55 null_ify :: 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if 1150.39/291.55 null_if :: 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if 1150.39/291.55 1150.39/291.55 Rewrite Strategy: INNERMOST 1150.39/291.55 ---------------------------------------- 1150.39/291.55 1150.39/291.55 (7) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 1150.39/291.55 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 1150.39/291.55 The constant constructors are abstracted as follows: 1150.39/291.55 1150.39/291.55 0 => 0 1150.39/291.55 true => 2 1150.39/291.55 false => 1 1150.39/291.55 divByZeroError => 1 1150.39/291.55 null_ge => 0 1150.39/291.55 null_minus => 0 1150.39/291.55 null_plus => 0 1150.39/291.55 null_ify => 0 1150.39/291.55 null_if => 0 1150.39/291.55 1150.39/291.55 ---------------------------------------- 1150.39/291.55 1150.39/291.55 (8) 1150.39/291.55 Obligation: 1150.39/291.55 Complexity RNTS consisting of the following rules: 1150.39/291.55 1150.39/291.55 div(z, z') -{ 1 }-> ify(ge(y, 1 + 0), x, y) :|: x >= 0, y >= 0, z = x, z' = y 1150.39/291.55 ge(z, z') -{ 1 }-> ge(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 1150.39/291.55 ge(z, z') -{ 1 }-> ge(x, 0) :|: x >= 0, z = 1 + x, z' = 0 1150.39/291.55 ge(z, z') -{ 1 }-> ge(0, 1 + x) :|: x >= 0, z = 0, z' = 1 + (1 + x) 1150.39/291.55 ge(z, z') -{ 1 }-> 2 :|: z = 0, z' = 0 1150.39/291.55 ge(z, z') -{ 1 }-> 1 :|: z' = 1 + 0, z = 0 1150.39/291.55 ge(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 1150.39/291.55 if(z, z', z'') -{ 1 }-> 0 :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0 1150.39/291.55 if(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 1150.39/291.55 if(z, z', z'') -{ 1 }-> 1 + div(minus(x, y), y) :|: z = 2, z' = x, z'' = y, x >= 0, y >= 0 1150.39/291.55 ify(z, z', z'') -{ 1 }-> if(ge(x, y), x, y) :|: z = 2, z' = x, z'' = y, x >= 0, y >= 0 1150.39/291.55 ify(z, z', z'') -{ 1 }-> 1 :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0 1150.39/291.55 ify(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 1150.39/291.55 minus(z, z') -{ 1 }-> minus(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 1150.39/291.55 minus(z, z') -{ 1 }-> minus(0, x) :|: z' = 1 + x, x >= 0, z = 0 1150.39/291.55 minus(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0 1150.39/291.55 minus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 1150.39/291.55 minus(z, z') -{ 1 }-> 1 + minus(x, 0) :|: x >= 0, z = 1 + x, z' = 0 1150.39/291.55 plus(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0 1150.39/291.55 plus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 1150.39/291.55 plus(z, z') -{ 1 }-> 1 + plus(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y 1150.39/291.55 plus(z, z') -{ 1 }-> 1 + plus(0, x) :|: z' = 1 + x, x >= 0, z = 0 1150.39/291.55 1150.39/291.55 Only complete derivations are relevant for the runtime complexity. 1150.39/291.55 1150.39/291.55 ---------------------------------------- 1150.39/291.55 1150.39/291.55 (9) CompleteCoflocoProof (FINISHED) 1150.39/291.55 Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: 1150.39/291.55 1150.39/291.55 eq(start(V1, V, V16),0,[ge(V1, V, Out)],[V1 >= 0,V >= 0]). 1150.39/291.55 eq(start(V1, V, V16),0,[minus(V1, V, Out)],[V1 >= 0,V >= 0]). 1150.39/291.55 eq(start(V1, V, V16),0,[plus(V1, V, Out)],[V1 >= 0,V >= 0]). 1150.39/291.55 eq(start(V1, V, V16),0,[div(V1, V, Out)],[V1 >= 0,V >= 0]). 1150.39/291.55 eq(start(V1, V, V16),0,[ify(V1, V, V16, Out)],[V1 >= 0,V >= 0,V16 >= 0]). 1150.39/291.55 eq(start(V1, V, V16),0,[if(V1, V, V16, Out)],[V1 >= 0,V >= 0,V16 >= 0]). 1150.39/291.55 eq(ge(V1, V, Out),1,[],[Out = 2,V1 = 0,V = 0]). 1150.39/291.55 eq(ge(V1, V, Out),1,[ge(V2, 0, Ret)],[Out = Ret,V2 >= 0,V1 = 1 + V2,V = 0]). 1150.39/291.55 eq(ge(V1, V, Out),1,[],[Out = 1,V = 1,V1 = 0]). 1150.39/291.55 eq(ge(V1, V, Out),1,[ge(0, 1 + V3, Ret1)],[Out = Ret1,V3 >= 0,V1 = 0,V = 2 + V3]). 1150.39/291.55 eq(ge(V1, V, Out),1,[ge(V4, V5, Ret2)],[Out = Ret2,V = 1 + V5,V4 >= 0,V5 >= 0,V1 = 1 + V4]). 1150.39/291.55 eq(minus(V1, V, Out),1,[],[Out = 0,V1 = 0,V = 0]). 1150.39/291.55 eq(minus(V1, V, Out),1,[minus(0, V6, Ret3)],[Out = Ret3,V = 1 + V6,V6 >= 0,V1 = 0]). 1150.39/291.55 eq(minus(V1, V, Out),1,[minus(V7, 0, Ret11)],[Out = 1 + Ret11,V7 >= 0,V1 = 1 + V7,V = 0]). 1150.39/291.55 eq(minus(V1, V, Out),1,[minus(V8, V9, Ret4)],[Out = Ret4,V = 1 + V9,V8 >= 0,V9 >= 0,V1 = 1 + V8]). 1150.39/291.55 eq(plus(V1, V, Out),1,[],[Out = 0,V1 = 0,V = 0]). 1150.39/291.55 eq(plus(V1, V, Out),1,[plus(0, V10, Ret12)],[Out = 1 + Ret12,V = 1 + V10,V10 >= 0,V1 = 0]). 1150.39/291.55 eq(plus(V1, V, Out),1,[plus(V12, V11, Ret13)],[Out = 1 + Ret13,V12 >= 0,V11 >= 0,V1 = 1 + V12,V = V11]). 1150.39/291.55 eq(div(V1, V, Out),1,[ge(V13, 1 + 0, Ret0),ify(Ret0, V14, V13, Ret5)],[Out = Ret5,V14 >= 0,V13 >= 0,V1 = V14,V = V13]). 1150.39/291.55 eq(ify(V1, V, V16, Out),1,[],[Out = 1,V = V17,V16 = V15,V1 = 1,V17 >= 0,V15 >= 0]). 1150.39/291.55 eq(ify(V1, V, V16, Out),1,[ge(V19, V18, Ret01),if(Ret01, V19, V18, Ret6)],[Out = Ret6,V1 = 2,V = V19,V16 = V18,V19 >= 0,V18 >= 0]). 1150.39/291.55 eq(if(V1, V, V16, Out),1,[],[Out = 0,V = V21,V16 = V20,V1 = 1,V21 >= 0,V20 >= 0]). 1150.39/291.55 eq(if(V1, V, V16, Out),1,[minus(V22, V23, Ret10),div(Ret10, V23, Ret14)],[Out = 1 + Ret14,V1 = 2,V = V22,V16 = V23,V22 >= 0,V23 >= 0]). 1150.39/291.55 eq(ge(V1, V, Out),0,[],[Out = 0,V25 >= 0,V24 >= 0,V1 = V25,V = V24]). 1150.39/291.55 eq(minus(V1, V, Out),0,[],[Out = 0,V27 >= 0,V26 >= 0,V1 = V27,V = V26]). 1150.39/291.55 eq(plus(V1, V, Out),0,[],[Out = 0,V29 >= 0,V28 >= 0,V1 = V29,V = V28]). 1150.39/291.55 eq(ify(V1, V, V16, Out),0,[],[Out = 0,V30 >= 0,V16 = V32,V31 >= 0,V1 = V30,V = V31,V32 >= 0]). 1150.39/291.55 eq(if(V1, V, V16, Out),0,[],[Out = 0,V34 >= 0,V16 = V35,V33 >= 0,V1 = V34,V = V33,V35 >= 0]). 1150.39/291.55 input_output_vars(ge(V1,V,Out),[V1,V],[Out]). 1150.39/291.55 input_output_vars(minus(V1,V,Out),[V1,V],[Out]). 1150.39/291.55 input_output_vars(plus(V1,V,Out),[V1,V],[Out]). 1150.39/291.55 input_output_vars(div(V1,V,Out),[V1,V],[Out]). 1150.39/291.55 input_output_vars(ify(V1,V,V16,Out),[V1,V,V16],[Out]). 1150.39/291.55 input_output_vars(if(V1,V,V16,Out),[V1,V,V16],[Out]). 1150.39/291.55 1150.39/291.55 1150.39/291.55 CoFloCo proof output: 1150.39/291.55 Preprocessing Cost Relations 1150.39/291.55 ===================================== 1150.39/291.55 1150.39/291.55 #### Computed strongly connected components 1150.39/291.55 0. recursive : [ge/3] 1150.39/291.55 1. recursive : [minus/3] 1150.39/291.55 2. recursive : [(div)/3,if/4,ify/4] 1150.39/291.55 3. recursive : [plus/3] 1150.39/291.55 4. non_recursive : [start/3] 1150.39/291.55 1150.39/291.55 #### Obtained direct recursion through partial evaluation 1150.39/291.55 0. SCC is partially evaluated into ge/3 1150.39/291.55 1. SCC is partially evaluated into minus/3 1150.39/291.55 2. SCC is partially evaluated into (div)/3 1150.39/291.55 3. SCC is partially evaluated into plus/3 1150.39/291.55 4. SCC is partially evaluated into start/3 1150.39/291.55 1150.39/291.55 Control-Flow Refinement of Cost Relations 1150.39/291.55 ===================================== 1150.39/291.55 1150.39/291.55 ### Specialization of cost equations ge/3 1150.39/291.55 * CE 16 is refined into CE [31] 1150.39/291.55 * CE 13 is refined into CE [32] 1150.39/291.55 * CE 11 is refined into CE [33] 1150.39/291.55 * CE 15 is refined into CE [34] 1150.39/291.55 * CE 12 is refined into CE [35] 1150.39/291.55 * CE 14 is refined into CE [36] 1150.39/291.55 1150.39/291.55 1150.39/291.55 ### Cost equations --> "Loop" of ge/3 1150.39/291.55 * CEs [34] --> Loop 19 1150.39/291.55 * CEs [35] --> Loop 20 1150.39/291.55 * CEs [36] --> Loop 21 1150.39/291.55 * CEs [31] --> Loop 22 1150.39/291.55 * CEs [32] --> Loop 23 1150.39/291.55 * CEs [33] --> Loop 24 1150.39/291.55 1150.39/291.55 ### Ranking functions of CR ge(V1,V,Out) 1150.39/291.55 * RF of phase [19]: [V,V1] 1150.39/291.55 * RF of phase [20]: [V1] 1150.39/291.55 * RF of phase [21]: [V-1] 1150.39/291.55 1150.39/291.55 #### Partial ranking functions of CR ge(V1,V,Out) 1150.39/291.55 * Partial RF of phase [19]: 1150.39/291.55 - RF of loop [19:1]: 1150.39/291.55 V 1150.39/291.55 V1 1150.39/291.55 * Partial RF of phase [20]: 1150.39/291.55 - RF of loop [20:1]: 1150.39/291.55 V1 1150.39/291.55 * Partial RF of phase [21]: 1150.39/291.55 - RF of loop [21:1]: 1150.39/291.55 V-1 1150.39/291.55 1150.39/291.55 1150.39/291.55 ### Specialization of cost equations minus/3 1150.39/291.55 * CE 17 is refined into CE [37] 1150.39/291.55 * CE 21 is refined into CE [38] 1150.39/291.55 * CE 20 is refined into CE [39] 1150.39/291.55 * CE 19 is refined into CE [40] 1150.39/291.55 * CE 18 is refined into CE [41] 1150.39/291.55 1150.39/291.55 1150.39/291.55 ### Cost equations --> "Loop" of minus/3 1150.39/291.55 * CEs [39] --> Loop 25 1150.39/291.55 * CEs [40] --> Loop 26 1150.39/291.55 * CEs [41] --> Loop 27 1150.39/291.55 * CEs [37,38] --> Loop 28 1150.39/291.55 1150.39/291.55 ### Ranking functions of CR minus(V1,V,Out) 1150.39/291.55 * RF of phase [25]: [V,V1] 1150.39/291.55 * RF of phase [26]: [V1] 1150.39/291.55 * RF of phase [27]: [V] 1150.39/291.55 1150.39/291.55 #### Partial ranking functions of CR minus(V1,V,Out) 1150.39/291.55 * Partial RF of phase [25]: 1150.39/291.55 - RF of loop [25:1]: 1150.39/291.55 V 1150.39/291.55 V1 1150.39/291.55 * Partial RF of phase [26]: 1150.39/291.55 - RF of loop [26:1]: 1150.39/291.55 V1 1150.39/291.55 * Partial RF of phase [27]: 1150.39/291.55 - RF of loop [27:1]: 1150.39/291.55 V 1150.39/291.55 1150.39/291.55 1150.39/291.55 ### Specialization of cost equations (div)/3 1150.39/291.55 * CE 23 is refined into CE [42] 1150.39/291.55 * CE 22 is refined into CE [43,44,45,46] 1150.39/291.55 * CE 24 is refined into CE [47,48,49,50] 1150.39/291.55 * CE 26 is refined into CE [51,52,53,54,55,56,57,58,59,60] 1150.39/291.55 * CE 25 is refined into CE [61,62,63,64,65,66] 1150.39/291.55 1150.39/291.55 1150.39/291.55 ### Cost equations --> "Loop" of (div)/3 1150.39/291.55 * CEs [66] --> Loop 29 1150.39/291.55 * CEs [65] --> Loop 30 1150.39/291.55 * CEs [64] --> Loop 31 1150.39/291.55 * CEs [63] --> Loop 32 1150.39/291.55 * CEs [62] --> Loop 33 1150.39/291.55 * CEs [61] --> Loop 34 1150.39/291.55 * CEs [59] --> Loop 35 1150.39/291.55 * CEs [49,57] --> Loop 36 1150.39/291.55 * CEs [42] --> Loop 37 1150.39/291.55 * CEs [43] --> Loop 38 1150.39/291.55 * CEs [53] --> Loop 39 1150.39/291.55 * CEs [48,56] --> Loop 40 1150.39/291.55 * CEs [44,45,46,47,50,51,52,54,55,58,60] --> Loop 41 1150.39/291.55 1150.39/291.55 ### Ranking functions of CR div(V1,V,Out) 1150.39/291.55 * RF of phase [29]: [V1/2-1,V1/2-V/2] 1150.39/291.55 * RF of phase [32]: [V1-1] 1150.39/291.55 1150.39/291.55 #### Partial ranking functions of CR div(V1,V,Out) 1150.39/291.55 * Partial RF of phase [29]: 1150.39/291.55 - RF of loop [29:1]: 1150.39/291.55 V1/2-1 1150.39/291.55 V1/2-V/2 1150.39/291.55 * Partial RF of phase [32]: 1150.39/291.55 - RF of loop [32:1]: 1150.39/291.55 V1-1 1150.39/291.55 1150.39/291.55 1150.39/291.55 ### Specialization of cost equations plus/3 1150.39/291.55 * CE 27 is refined into CE [67] 1150.39/291.55 * CE 30 is refined into CE [68] 1150.39/291.55 * CE 29 is refined into CE [69] 1150.39/291.55 * CE 28 is refined into CE [70] 1150.39/291.55 1150.39/291.55 1150.39/291.55 ### Cost equations --> "Loop" of plus/3 1150.39/291.55 * CEs [69] --> Loop 42 1150.39/291.55 * CEs [70] --> Loop 43 1150.39/291.55 * CEs [67,68] --> Loop 44 1150.39/291.55 1150.39/291.55 ### Ranking functions of CR plus(V1,V,Out) 1150.39/291.55 * RF of phase [42]: [V1] 1150.39/291.55 * RF of phase [43]: [V] 1150.39/291.55 1150.39/291.55 #### Partial ranking functions of CR plus(V1,V,Out) 1150.39/291.55 * Partial RF of phase [42]: 1150.39/291.55 - RF of loop [42:1]: 1150.39/291.55 V1 1150.39/291.55 * Partial RF of phase [43]: 1150.39/291.55 - RF of loop [43:1]: 1150.39/291.55 V 1150.39/291.55 1150.39/291.55 1150.39/291.55 ### Specialization of cost equations start/3 1150.39/291.55 * CE 3 is refined into CE [71,72,73,74] 1150.39/291.55 * CE 4 is refined into CE [75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96] 1150.39/291.55 * CE 5 is refined into CE [97,98,99,100,101,102,103,104,105,106] 1150.39/291.55 * CE 6 is refined into CE [107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123] 1150.39/291.55 * CE 1 is refined into CE [124] 1150.39/291.55 * CE 2 is refined into CE [125] 1150.39/291.55 * CE 7 is refined into CE [126,127,128,129,130,131,132,133,134,135] 1150.39/291.55 * CE 8 is refined into CE [136,137,138] 1150.39/291.55 * CE 9 is refined into CE [139,140,141,142] 1150.39/291.55 * CE 10 is refined into CE [143,144,145,146,147,148,149,150,151,152,153,154,155] 1150.39/291.55 1150.39/291.55 1150.39/291.55 ### Cost equations --> "Loop" of start/3 1150.39/291.55 * CEs [132,151] --> Loop 45 1150.39/291.55 * CEs [148,149] --> Loop 46 1150.39/291.55 * CEs [84,105] --> Loop 47 1150.39/291.55 * CEs [73,103] --> Loop 48 1150.39/291.55 * CEs [87,88,89,90,114,115,116,117] --> Loop 49 1150.39/291.55 * CEs [72,100] --> Loop 50 1150.39/291.55 * CEs [71,98] --> Loop 51 1150.39/291.55 * CEs [74,75,76,77,78,79,80,81,82,83,85,86,91,92,93,94,95,96,97,99,101,102,104,106,107,108,109,110,111,112,113,118,119,120,121,122,123] --> Loop 52 1150.39/291.55 * CEs [125] --> Loop 53 1150.39/291.55 * CEs [134,144,145,150,152] --> Loop 54 1150.39/291.55 * CEs [127,129,139] --> Loop 55 1150.39/291.55 * CEs [124,126,128,130,131,133,135,136,137,138,140,141,142,143,146,147,153,154,155] --> Loop 56 1150.39/291.55 1150.39/291.55 ### Ranking functions of CR start(V1,V,V16) 1150.39/291.55 1150.39/291.55 #### Partial ranking functions of CR start(V1,V,V16) 1150.39/291.55 1150.39/291.55 1150.39/291.55 Computing Bounds 1150.39/291.55 ===================================== 1150.39/291.55 1150.39/291.55 #### Cost of chains of ge(V1,V,Out): 1150.39/291.55 * Chain [[21],23]: 1*it(21)+1 1150.39/291.55 Such that:it(21) =< V 1150.39/291.55 1150.39/291.55 with precondition: [V1=0,Out=1,V>=2] 1150.39/291.55 1150.39/291.55 * Chain [[21],22]: 1*it(21)+0 1150.39/291.55 Such that:it(21) =< V 1150.39/291.55 1150.39/291.55 with precondition: [V1=0,Out=0,V>=2] 1150.39/291.55 1150.39/291.55 * Chain [[20],24]: 1*it(20)+1 1150.39/291.55 Such that:it(20) =< V1 1150.39/291.55 1150.39/291.55 with precondition: [V=0,Out=2,V1>=1] 1150.39/291.55 1150.39/291.55 * Chain [[20],22]: 1*it(20)+0 1150.39/291.55 Such that:it(20) =< V1 1150.39/291.55 1150.39/291.55 with precondition: [V=0,Out=0,V1>=1] 1150.39/291.55 1150.39/291.55 * Chain [[19],[21],23]: 1*it(19)+1*it(21)+1 1150.39/291.55 Such that:it(21) =< -V1+V 1150.39/291.55 it(19) =< V1 1150.39/291.55 1150.39/291.55 with precondition: [Out=1,V1>=1,V>=V1+2] 1150.39/291.55 1150.39/291.55 * Chain [[19],[21],22]: 1*it(19)+1*it(21)+0 1150.39/291.55 Such that:it(21) =< -V1+V 1150.39/291.55 it(19) =< V1 1150.39/291.55 1150.39/291.55 with precondition: [Out=0,V1>=1,V>=V1+2] 1150.39/291.55 1150.39/291.55 * Chain [[19],[20],24]: 1*it(19)+1*it(20)+1 1150.39/291.55 Such that:it(20) =< V1-V 1150.39/291.55 it(19) =< V 1150.39/291.55 1150.39/291.55 with precondition: [Out=2,V>=1,V1>=V+1] 1150.39/291.55 1150.39/291.55 * Chain [[19],[20],22]: 1*it(19)+1*it(20)+0 1150.39/291.55 Such that:it(20) =< V1-V 1150.39/291.55 it(19) =< V 1150.39/291.55 1150.39/291.55 with precondition: [Out=0,V>=1,V1>=V+1] 1150.39/291.55 1150.39/291.55 * Chain [[19],24]: 1*it(19)+1 1150.39/291.55 Such that:it(19) =< V1 1150.39/291.55 1150.39/291.55 with precondition: [Out=2,V1=V,V1>=1] 1150.39/291.55 1150.39/291.55 * Chain [[19],23]: 1*it(19)+1 1150.39/291.55 Such that:it(19) =< V1 1150.39/291.55 1150.39/291.55 with precondition: [Out=1,V1+1=V,V1>=1] 1150.39/291.55 1150.39/291.55 * Chain [[19],22]: 1*it(19)+0 1150.39/291.55 Such that:it(19) =< V 1150.39/291.55 1150.39/291.55 with precondition: [Out=0,V1>=1,V>=1] 1150.39/291.55 1150.39/291.55 * Chain [24]: 1 1150.39/291.55 with precondition: [V1=0,V=0,Out=2] 1150.39/291.55 1150.39/291.55 * Chain [23]: 1 1150.39/291.55 with precondition: [V1=0,V=1,Out=1] 1150.39/291.55 1150.39/291.55 * Chain [22]: 0 1150.39/291.55 with precondition: [Out=0,V1>=0,V>=0] 1150.39/291.55 1150.39/291.55 1150.39/291.55 #### Cost of chains of minus(V1,V,Out): 1150.39/291.55 * Chain [[27],28]: 1*it(27)+1 1150.39/291.55 Such that:it(27) =< V 1150.39/291.55 1150.39/291.55 with precondition: [V1=0,Out=0,V>=1] 1150.39/291.55 1150.39/291.55 * Chain [[26],28]: 1*it(26)+1 1150.39/291.55 Such that:it(26) =< Out 1150.39/291.55 1150.39/291.55 with precondition: [V=0,Out>=1,V1>=Out] 1150.39/291.55 1150.39/291.55 * Chain [[25],[27],28]: 1*it(25)+1*it(27)+1 1150.39/291.55 Such that:it(27) =< -V1+V 1150.39/291.55 it(25) =< V1 1150.39/291.55 1150.39/291.55 with precondition: [Out=0,V1>=1,V>=V1+1] 1150.39/291.55 1150.39/291.55 * Chain [[25],[26],28]: 1*it(25)+1*it(26)+1 1150.39/291.55 Such that:it(25) =< V 1150.39/291.55 it(26) =< Out 1150.39/291.55 1150.39/291.55 with precondition: [V>=1,Out>=1,V1>=Out+V] 1150.39/291.55 1150.39/291.55 * Chain [[25],28]: 1*it(25)+1 1150.39/291.55 Such that:it(25) =< V 1150.39/291.55 1150.39/291.55 with precondition: [Out=0,V1>=1,V>=1] 1150.39/291.55 1150.39/291.55 * Chain [28]: 1 1150.39/291.55 with precondition: [Out=0,V1>=0,V>=0] 1150.39/291.55 1150.39/291.55 1150.39/291.55 #### Cost of chains of div(V1,V,Out): 1150.39/291.55 * Chain [[32],41]: 17*it(32)+28*s(12)+1*s(59)+1*s(60)+5 1150.39/291.55 Such that:aux(21) =< 1 1150.39/291.55 aux(22) =< V1 1150.39/291.55 s(12) =< aux(21) 1150.39/291.55 it(32) =< aux(22) 1150.39/291.55 aux(17) =< aux(22)-1 1150.39/291.55 s(59) =< it(32)*aux(22) 1150.39/291.55 s(60) =< it(32)*aux(17) 1150.39/291.55 1150.39/291.55 with precondition: [V=1,Out>=1,V1>=Out+1] 1150.39/291.55 1150.39/291.55 * Chain [[32],39]: 9*it(32)+1*s(59)+1*s(60)+2*s(62)+4 1150.39/291.55 Such that:aux(23) =< 1 1150.39/291.55 aux(24) =< V1 1150.39/291.55 s(62) =< aux(23) 1150.39/291.55 it(32) =< aux(24) 1150.39/291.55 aux(17) =< aux(24)-1 1150.39/291.55 s(59) =< it(32)*aux(24) 1150.39/291.55 s(60) =< it(32)*aux(17) 1150.39/291.55 1150.39/291.55 with precondition: [V=1,Out>=1,V1>=Out+1] 1150.39/291.55 1150.39/291.55 * Chain [[32],34,41]: 9*it(32)+37*s(12)+1*s(59)+1*s(60)+11 1150.39/291.55 Such that:aux(27) =< 1 1150.39/291.55 aux(28) =< V1 1150.39/291.55 s(12) =< aux(27) 1150.39/291.55 it(32) =< aux(28) 1150.39/291.55 aux(17) =< aux(28)-1 1150.39/291.55 s(59) =< it(32)*aux(28) 1150.39/291.55 s(60) =< it(32)*aux(17) 1150.39/291.55 1150.39/291.55 with precondition: [V=1,Out>=2,V1>=Out] 1150.39/291.55 1150.39/291.55 * Chain [[32],33,41]: 11*it(32)+36*s(12)+1*s(59)+1*s(60)+11 1150.39/291.55 Such that:aux(32) =< 1 1150.39/291.55 aux(33) =< V1 1150.39/291.55 s(12) =< aux(32) 1150.39/291.55 it(32) =< aux(33) 1150.39/291.55 aux(17) =< aux(33)-1 1150.39/291.55 s(59) =< it(32)*aux(33) 1150.39/291.55 s(60) =< it(32)*aux(17) 1150.39/291.55 1150.39/291.55 with precondition: [V=1,Out>=2,V1>=Out+1] 1150.39/291.55 1150.39/291.55 * Chain [[29],41]: 6*it(29)+1*s(11)+14*s(12)+17*s(15)+9*s(23)+2*s(38)+1*s(89)+1*s(90)+1*s(91)+5 1150.39/291.55 Such that:aux(9) =< 1 1150.39/291.55 aux(12) =< V1-2*V-2*Out+2 1150.39/291.55 aux(36) =< V1-V 1150.39/291.55 aux(38) =< V1/2 1150.39/291.55 aux(39) =< V1/2-V/2 1150.39/291.55 s(11) =< -V+1 1150.39/291.55 aux(42) =< V1 1150.39/291.55 aux(43) =< V 1150.39/291.55 s(15) =< aux(9) 1150.39/291.55 s(12) =< aux(43) 1150.39/291.55 s(23) =< aux(42) 1150.39/291.55 s(38) =< aux(12) 1150.39/291.55 aux(35) =< aux(38) 1150.39/291.55 it(29) =< aux(38) 1150.39/291.55 aux(35) =< aux(39) 1150.39/291.55 it(29) =< aux(39) 1150.39/291.55 aux(35) =< aux(42) 1150.39/291.55 it(29) =< aux(42) 1150.39/291.55 aux(37) =< aux(36) 1150.39/291.55 s(90) =< it(29)*aux(36) 1150.39/291.55 s(89) =< aux(35) 1150.39/291.55 s(91) =< it(29)*aux(37) 1150.39/291.55 1150.39/291.55 with precondition: [V>=2,Out>=1,V1+1>=2*Out+V] 1150.39/291.55 1150.39/291.55 * Chain [[29],36]: 6*it(29)+3*s(88)+1*s(89)+1*s(90)+1*s(91)+4*s(93)+2*s(94)+5 1150.39/291.55 Such that:aux(46) =< 1 1150.39/291.55 aux(36) =< V1-V 1150.39/291.55 s(92) =< V1-V+1 1150.39/291.55 aux(38) =< V1/2 1150.39/291.55 aux(39) =< V1/2-V/2 1150.39/291.55 aux(47) =< V 1150.39/291.55 aux(48) =< V1/2-V/2+1/2 1150.39/291.55 s(94) =< aux(46) 1150.39/291.55 s(93) =< aux(47) 1150.39/291.55 aux(35) =< aux(38) 1150.39/291.55 it(29) =< aux(38) 1150.39/291.55 aux(35) =< aux(39) 1150.39/291.55 it(29) =< aux(39) 1150.39/291.55 aux(35) =< aux(48) 1150.39/291.55 it(29) =< aux(48) 1150.39/291.55 aux(37) =< aux(36) 1150.39/291.55 s(90) =< it(29)*aux(36) 1150.39/291.55 s(89) =< aux(35) 1150.39/291.55 s(91) =< it(29)*aux(37) 1150.39/291.55 s(88) =< s(92) 1150.39/291.55 1150.39/291.55 with precondition: [V>=2,Out>=1,V1+3>=2*Out+2*V] 1150.39/291.55 1150.39/291.55 * Chain [[29],35]: 6*it(29)+3*s(88)+1*s(89)+1*s(90)+1*s(91)+2*s(99)+1*s(100)+4 1150.39/291.55 Such that:s(100) =< 1 1150.39/291.55 aux(38) =< V1/2 1150.39/291.55 aux(49) =< V 1150.39/291.55 aux(50) =< V1-V 1150.39/291.55 aux(51) =< V1/2-V/2 1150.39/291.55 s(99) =< aux(49) 1150.39/291.55 aux(35) =< aux(38) 1150.39/291.55 it(29) =< aux(38) 1150.39/291.55 aux(35) =< aux(51) 1150.39/291.55 it(29) =< aux(51) 1150.39/291.55 aux(37) =< aux(50) 1150.39/291.55 s(90) =< it(29)*aux(50) 1150.39/291.55 s(89) =< aux(35) 1150.39/291.55 s(91) =< it(29)*aux(37) 1150.39/291.55 s(88) =< aux(50) 1150.39/291.55 1150.39/291.55 with precondition: [V>=2,Out>=1,V1+2>=2*Out+2*V] 1150.39/291.55 1150.39/291.55 * Chain [[29],31,41]: 6*it(29)+1*s(11)+19*s(12)+19*s(15)+2*s(38)+3*s(88)+1*s(89)+1*s(90)+1*s(91)+11 1150.39/291.55 Such that:aux(53) =< 1 1150.39/291.55 aux(38) =< V1/2 1150.39/291.55 aux(12) =< -V 1150.39/291.55 s(11) =< -V+1 1150.39/291.55 aux(54) =< V 1150.39/291.55 aux(55) =< V1-V 1150.39/291.55 aux(56) =< V1/2-V/2 1150.39/291.55 s(15) =< aux(53) 1150.39/291.55 s(12) =< aux(54) 1150.39/291.55 s(38) =< aux(12) 1150.39/291.55 aux(35) =< aux(38) 1150.39/291.55 it(29) =< aux(38) 1150.39/291.55 aux(35) =< aux(56) 1150.39/291.55 it(29) =< aux(56) 1150.39/291.55 aux(37) =< aux(55) 1150.39/291.55 s(90) =< it(29)*aux(55) 1150.39/291.55 s(89) =< aux(35) 1150.39/291.55 s(91) =< it(29)*aux(37) 1150.39/291.55 s(88) =< aux(55) 1150.39/291.55 1150.39/291.55 with precondition: [V>=2,Out>=2,V1+4>=2*Out+2*V] 1150.39/291.55 1150.39/291.55 * Chain [[29],31,40]: 6*it(29)+3*s(88)+1*s(89)+1*s(90)+1*s(91)+9*s(102)+3*s(103)+11 1150.39/291.55 Such that:aux(61) =< 1 1150.39/291.55 aux(38) =< V1/2 1150.39/291.55 aux(62) =< V 1150.39/291.55 aux(63) =< V1-V 1150.39/291.55 aux(64) =< V1/2-V/2 1150.39/291.55 s(103) =< aux(61) 1150.39/291.55 s(102) =< aux(62) 1150.39/291.55 aux(35) =< aux(38) 1150.39/291.55 it(29) =< aux(38) 1150.39/291.55 aux(35) =< aux(64) 1150.39/291.55 it(29) =< aux(64) 1150.39/291.55 aux(37) =< aux(63) 1150.39/291.55 s(90) =< it(29)*aux(63) 1150.39/291.55 s(89) =< aux(35) 1150.39/291.55 s(91) =< it(29)*aux(37) 1150.39/291.55 s(88) =< aux(63) 1150.39/291.55 1150.39/291.55 with precondition: [V>=2,Out>=2,V1+4>=2*Out+2*V] 1150.39/291.55 1150.39/291.55 * Chain [[29],30,41]: 6*it(29)+1*s(11)+18*s(12)+19*s(15)+2*s(38)+4*s(88)+1*s(89)+1*s(90)+1*s(91)+1*s(117)+11 1150.39/291.55 Such that:aux(66) =< 1 1150.39/291.55 aux(38) =< V1/2 1150.39/291.55 aux(39) =< V1/2-V/2 1150.39/291.55 aux(12) =< -V 1150.39/291.55 s(11) =< -V+1 1150.39/291.55 aux(67) =< V 1150.39/291.55 aux(68) =< V1 1150.39/291.55 aux(69) =< V1-V 1150.39/291.55 s(88) =< aux(68) 1150.39/291.55 s(117) =< aux(69) 1150.39/291.55 s(15) =< aux(66) 1150.39/291.55 s(12) =< aux(67) 1150.39/291.55 s(38) =< aux(12) 1150.39/291.55 aux(35) =< aux(38) 1150.39/291.55 it(29) =< aux(38) 1150.39/291.55 aux(35) =< aux(39) 1150.39/291.55 it(29) =< aux(39) 1150.39/291.55 aux(35) =< aux(68) 1150.39/291.55 it(29) =< aux(68) 1150.39/291.55 aux(37) =< aux(69) 1150.39/291.55 s(90) =< it(29)*aux(69) 1150.39/291.55 s(89) =< aux(35) 1150.39/291.55 s(91) =< it(29)*aux(37) 1150.39/291.55 1150.39/291.55 with precondition: [V>=2,Out>=2,V1+3>=2*Out+2*V] 1150.39/291.55 1150.39/291.55 * Chain [[29],30,40]: 6*it(29)+4*s(88)+1*s(89)+1*s(90)+1*s(91)+8*s(109)+3*s(110)+1*s(117)+11 1150.39/291.55 Such that:aux(70) =< 1 1150.39/291.55 aux(38) =< V1/2 1150.39/291.55 aux(39) =< V1/2-V/2 1150.39/291.55 aux(71) =< V 1150.39/291.55 aux(72) =< V1 1150.39/291.55 aux(73) =< V1-V 1150.39/291.55 s(88) =< aux(72) 1150.39/291.55 s(117) =< aux(73) 1150.39/291.55 s(110) =< aux(70) 1150.39/291.55 s(109) =< aux(71) 1150.39/291.55 aux(35) =< aux(38) 1150.39/291.55 it(29) =< aux(38) 1150.39/291.55 aux(35) =< aux(39) 1150.39/291.55 it(29) =< aux(39) 1150.39/291.55 aux(35) =< aux(72) 1150.39/291.55 it(29) =< aux(72) 1150.39/291.55 aux(37) =< aux(73) 1150.39/291.55 s(90) =< it(29)*aux(73) 1150.39/291.55 s(89) =< aux(35) 1150.39/291.55 s(91) =< it(29)*aux(37) 1150.39/291.55 1150.39/291.55 with precondition: [V>=2,Out>=2,V1+3>=2*Out+2*V] 1150.39/291.55 1150.39/291.55 * Chain [41]: 1*s(11)+11*s(12)+17*s(15)+3*s(22)+6*s(23)+1*s(26)+2*s(38)+5 1150.39/291.55 Such that:s(26) =< -V1+1 1150.39/291.55 s(11) =< -V+1 1150.39/291.55 aux(9) =< 1 1150.39/291.55 aux(10) =< -V1+V 1150.39/291.55 aux(11) =< V1 1150.39/291.55 aux(12) =< V1-V 1150.39/291.55 aux(13) =< V 1150.39/291.55 s(15) =< aux(9) 1150.39/291.55 s(22) =< aux(10) 1150.39/291.55 s(23) =< aux(11) 1150.39/291.55 s(38) =< aux(12) 1150.39/291.55 s(12) =< aux(13) 1150.39/291.55 1150.39/291.55 with precondition: [Out=0,V1>=0,V>=0] 1150.39/291.55 1150.39/291.55 * Chain [40]: 4*s(109)+2*s(110)+5 1150.39/291.55 Such that:aux(59) =< 1 1150.39/291.55 aux(60) =< V 1150.39/291.55 s(110) =< aux(59) 1150.39/291.55 s(109) =< aux(60) 1150.39/291.55 1150.39/291.55 with precondition: [V1=0,Out=0,V>=2] 1150.39/291.55 1150.39/291.55 * Chain [39]: 2*s(62)+4 1150.39/291.55 Such that:aux(23) =< 1 1150.39/291.55 s(62) =< aux(23) 1150.39/291.55 1150.39/291.55 with precondition: [V1=1,V=1,Out=0] 1150.39/291.55 1150.39/291.55 * Chain [38]: 2 1150.39/291.55 with precondition: [V=0,Out=0,V1>=0] 1150.39/291.55 1150.39/291.55 * Chain [37]: 3 1150.39/291.55 with precondition: [V=0,Out=1,V1>=0] 1150.39/291.55 1150.39/291.55 * Chain [36]: 4*s(93)+2*s(94)+5 1150.39/291.55 Such that:aux(46) =< 1 1150.39/291.55 aux(47) =< V 1150.39/291.55 s(94) =< aux(46) 1150.39/291.55 s(93) =< aux(47) 1150.39/291.55 1150.39/291.55 with precondition: [Out=0,V=V1+1,V>=2] 1150.39/291.55 1150.39/291.55 * Chain [35]: 2*s(99)+1*s(100)+4 1150.39/291.55 Such that:s(100) =< 1 1150.39/291.55 aux(49) =< V 1150.39/291.55 s(99) =< aux(49) 1150.39/291.55 1150.39/291.55 with precondition: [Out=0,V=V1,V>=2] 1150.39/291.55 1150.39/291.55 * Chain [34,41]: 37*s(12)+11 1150.39/291.55 Such that:aux(27) =< 1 1150.39/291.55 s(12) =< aux(27) 1150.39/291.55 1150.39/291.55 with precondition: [V1=1,V=1,Out=1] 1150.39/291.55 1150.39/291.55 * Chain [33,41]: 36*s(12)+2*s(71)+1*s(73)+11 1150.39/291.55 Such that:s(73) =< -V1+1 1150.39/291.55 aux(30) =< V1 1150.39/291.55 aux(32) =< 1 1150.39/291.55 s(12) =< aux(32) 1150.39/291.55 s(71) =< aux(30) 1150.39/291.55 1150.39/291.55 with precondition: [V=1,Out=1,V1>=2] 1150.39/291.55 1150.39/291.55 * Chain [31,41]: 1*s(11)+19*s(12)+19*s(15)+2*s(38)+11 1150.39/291.55 Such that:aux(12) =< -V1 1150.39/291.55 s(11) =< -V1+1 1150.39/291.55 aux(53) =< 1 1150.39/291.55 aux(54) =< V1 1150.39/291.55 s(15) =< aux(53) 1150.39/291.55 s(12) =< aux(54) 1150.39/291.55 s(38) =< aux(12) 1150.39/291.55 1150.39/291.55 with precondition: [Out=1,V1=V,V1>=2] 1150.39/291.55 1150.39/291.55 * Chain [31,40]: 9*s(102)+3*s(103)+11 1150.39/291.55 Such that:aux(61) =< 1 1150.39/291.55 aux(62) =< V1 1150.39/291.55 s(103) =< aux(61) 1150.39/291.55 s(102) =< aux(62) 1150.39/291.55 1150.39/291.55 with precondition: [Out=1,V1=V,V1>=2] 1150.39/291.55 1150.39/291.55 * Chain [30,41]: 1*s(11)+18*s(12)+19*s(15)+2*s(38)+1*s(117)+1*s(119)+1*s(120)+11 1150.39/291.55 Such that:s(119) =< -V1+V 1150.39/291.55 s(120) =< V1 1150.39/291.55 s(117) =< V1-V 1150.39/291.55 aux(12) =< -V 1150.39/291.55 s(11) =< -V+1 1150.39/291.55 aux(66) =< 1 1150.39/291.55 aux(67) =< V 1150.39/291.55 s(15) =< aux(66) 1150.39/291.55 s(12) =< aux(67) 1150.39/291.55 s(38) =< aux(12) 1150.39/291.55 1150.39/291.55 with precondition: [Out=1,V>=2,V1>=V+1] 1150.39/291.55 1150.39/291.55 * Chain [30,40]: 8*s(109)+3*s(110)+1*s(117)+1*s(119)+1*s(120)+11 1150.39/291.55 Such that:s(119) =< -V1+V 1150.39/291.55 s(120) =< V1 1150.39/291.55 s(117) =< V1-V 1150.39/291.55 aux(70) =< 1 1150.39/291.55 aux(71) =< V 1150.39/291.55 s(110) =< aux(70) 1150.39/291.55 s(109) =< aux(71) 1150.39/291.55 1150.39/291.55 with precondition: [Out=1,V>=2,V1>=V+1] 1150.39/291.55 1150.39/291.55 1150.39/291.55 #### Cost of chains of plus(V1,V,Out): 1150.39/291.55 * Chain [[43],44]: 1*it(43)+1 1150.39/291.55 Such that:it(43) =< Out 1150.39/291.55 1150.39/291.55 with precondition: [V1=0,Out>=1,V>=Out] 1150.39/291.55 1150.39/291.55 * Chain [[42],[43],44]: 1*it(42)+1*it(43)+1 1150.39/291.55 Such that:it(43) =< -V1+Out 1150.39/291.55 it(42) =< V1 1150.39/291.55 1150.39/291.55 with precondition: [V1>=1,Out>=V1+1,V+V1>=Out] 1150.39/291.55 1150.39/291.55 * Chain [[42],44]: 1*it(42)+1 1150.39/291.55 Such that:it(42) =< Out 1150.39/291.55 1150.39/291.55 with precondition: [V>=0,Out>=1,V1>=Out] 1150.39/291.55 1150.39/291.55 * Chain [44]: 1 1150.39/291.55 with precondition: [Out=0,V1>=0,V>=0] 1150.39/291.55 1150.39/291.55 1150.39/291.55 #### Cost of chains of start(V1,V,V16): 1150.39/291.55 * Chain [56]: 8*s(306)+33*s(307)+18*s(308)+123*s(310)+1*s(327)+5*s(331)+105*s(334)+18*s(356)+3*s(358)+3*s(359)+3*s(360)+6*s(361)+2*s(362)+18*s(373)+3*s(375)+3*s(376)+3*s(377)+6*s(380)+1*s(381)+1*s(382)+1*s(383)+3*s(384)+11 1150.39/291.55 Such that:s(327) =< -V1+1 1150.39/291.55 s(339) =< V1-2*V 1150.39/291.55 s(363) =< V1-V+1 1150.39/291.55 s(364) =< V1/2-V/2+1/2 1150.39/291.55 aux(99) =< 1 1150.39/291.55 aux(100) =< -V1+V 1150.39/291.55 aux(101) =< V1 1150.39/291.55 aux(102) =< V1-V 1150.39/291.55 aux(103) =< V1/2 1150.39/291.55 aux(104) =< V1/2-V/2 1150.39/291.55 aux(105) =< -V 1150.39/291.55 aux(106) =< -V+1 1150.39/291.55 aux(107) =< V 1150.39/291.55 s(306) =< aux(100) 1150.39/291.55 s(307) =< aux(101) 1150.39/291.55 s(308) =< aux(102) 1150.39/291.55 s(331) =< aux(106) 1150.39/291.55 s(310) =< aux(107) 1150.39/291.55 s(334) =< aux(99) 1150.39/291.55 s(355) =< aux(103) 1150.39/291.55 s(356) =< aux(103) 1150.39/291.55 s(355) =< aux(104) 1150.39/291.55 s(356) =< aux(104) 1150.39/291.55 s(355) =< aux(101) 1150.39/291.55 s(356) =< aux(101) 1150.39/291.55 s(357) =< aux(102) 1150.39/291.55 s(358) =< s(356)*aux(102) 1150.39/291.55 s(359) =< s(355) 1150.39/291.55 s(360) =< s(356)*s(357) 1150.39/291.55 s(361) =< aux(105) 1150.39/291.55 s(362) =< s(339) 1150.39/291.55 s(372) =< aux(103) 1150.39/291.55 s(373) =< aux(103) 1150.39/291.55 s(372) =< aux(104) 1150.39/291.55 s(373) =< aux(104) 1150.39/291.55 s(375) =< s(373)*aux(102) 1150.39/291.55 s(376) =< s(372) 1150.39/291.55 s(377) =< s(373)*s(357) 1150.39/291.55 s(379) =< aux(103) 1150.39/291.55 s(380) =< aux(103) 1150.39/291.55 s(379) =< aux(104) 1150.39/291.55 s(380) =< aux(104) 1150.39/291.55 s(379) =< s(364) 1150.39/291.55 s(380) =< s(364) 1150.39/291.55 s(381) =< s(380)*aux(102) 1150.39/291.55 s(382) =< s(379) 1150.39/291.55 s(383) =< s(380)*s(357) 1150.39/291.55 s(384) =< s(363) 1150.39/291.55 1150.39/291.55 with precondition: [V1>=0,V>=0] 1150.39/291.55 1150.39/291.55 * Chain [55]: 2*s(402)+1 1150.39/291.55 Such that:aux(108) =< V 1150.39/291.55 s(402) =< aux(108) 1150.39/291.55 1150.39/291.55 with precondition: [V1=0,V>=1] 1150.39/291.55 1150.39/291.55 * Chain [54]: 31*s(404)+62*s(406)+1*s(413)+2*s(418)+11 1150.39/291.55 Such that:s(412) =< -V 1150.39/291.55 s(413) =< -V+1 1150.39/291.55 aux(109) =< 1 1150.39/291.55 aux(110) =< V 1150.39/291.55 s(406) =< aux(109) 1150.39/291.55 s(404) =< aux(110) 1150.39/291.55 s(418) =< s(412) 1150.39/291.55 1150.39/291.55 with precondition: [V1=V,V1>=1] 1150.39/291.55 1150.39/291.55 * Chain [53]: 1 1150.39/291.55 with precondition: [V1=1,V>=0,V16>=0] 1150.39/291.55 1150.39/291.55 * Chain [52]: 5*s(419)+40*s(420)+382*s(425)+5*s(446)+68*s(490)+376*s(491)+14*s(500)+20*s(507)+30*s(523)+36*s(571)+6*s(573)+6*s(574)+6*s(575)+4*s(577)+36*s(592)+6*s(594)+6*s(595)+6*s(596)+12*s(599)+2*s(600)+2*s(601)+2*s(602)+6*s(603)+15 1150.39/291.55 Such that:aux(152) =< 1 1150.39/291.55 aux(153) =< -V 1150.39/291.55 aux(154) =< -V+V16 1150.39/291.55 aux(155) =< V 1150.39/291.55 aux(156) =< V-3*V16 1150.39/291.55 aux(157) =< V-2*V16 1150.39/291.55 aux(158) =< V-2*V16+1 1150.39/291.55 aux(159) =< V-V16 1150.39/291.55 aux(160) =< V/2-V16 1150.39/291.55 aux(161) =< V/2-V16+1/2 1150.39/291.55 aux(162) =< V/2-V16/2 1150.39/291.55 aux(163) =< -V16 1150.39/291.55 aux(164) =< -V16+1 1150.39/291.55 aux(165) =< V16 1150.39/291.55 s(425) =< aux(152) 1150.39/291.55 s(446) =< aux(153) 1150.39/291.55 s(419) =< aux(154) 1150.39/291.55 s(420) =< aux(155) 1150.39/291.55 s(490) =< aux(159) 1150.39/291.55 s(500) =< aux(164) 1150.39/291.55 s(491) =< aux(165) 1150.39/291.55 s(523) =< aux(157) 1150.39/291.55 s(507) =< aux(163) 1150.39/291.55 s(570) =< aux(162) 1150.39/291.55 s(571) =< aux(162) 1150.39/291.55 s(570) =< aux(160) 1150.39/291.55 s(571) =< aux(160) 1150.39/291.55 s(570) =< aux(159) 1150.39/291.55 s(571) =< aux(159) 1150.39/291.55 s(572) =< aux(157) 1150.39/291.55 s(573) =< s(571)*aux(157) 1150.39/291.55 s(574) =< s(570) 1150.39/291.55 s(575) =< s(571)*s(572) 1150.39/291.55 s(577) =< aux(156) 1150.39/291.55 s(591) =< aux(162) 1150.39/291.55 s(592) =< aux(162) 1150.39/291.55 s(591) =< aux(160) 1150.39/291.55 s(592) =< aux(160) 1150.39/291.55 s(594) =< s(592)*aux(157) 1150.39/291.55 s(595) =< s(591) 1150.39/291.55 s(596) =< s(592)*s(572) 1150.39/291.55 s(598) =< aux(162) 1150.39/291.55 s(599) =< aux(162) 1150.39/291.55 s(598) =< aux(160) 1150.39/291.55 s(599) =< aux(160) 1150.39/291.55 s(598) =< aux(161) 1150.39/291.55 s(599) =< aux(161) 1150.39/291.55 s(600) =< s(599)*aux(157) 1150.39/291.55 s(601) =< s(598) 1150.39/291.55 s(602) =< s(599)*s(572) 1150.39/291.55 s(603) =< aux(158) 1150.39/291.55 1150.39/291.55 with precondition: [V1=2,V>=0,V16>=0] 1150.39/291.55 1150.39/291.55 * Chain [51]: 3 1150.39/291.55 with precondition: [V1=2,V=0,V16=1] 1150.39/291.55 1150.39/291.55 * Chain [50]: 2*s(778)+3 1150.39/291.55 Such that:aux(166) =< V16 1150.39/291.55 s(778) =< aux(166) 1150.39/291.55 1150.39/291.55 with precondition: [V1=2,V=0,V16>=2] 1150.39/291.55 1150.39/291.55 * Chain [49]: 104*s(780)+372*s(781)+8*s(802)+8*s(803)+15 1150.39/291.55 Such that:aux(179) =< 1 1150.39/291.55 aux(180) =< V 1150.39/291.55 s(780) =< aux(180) 1150.39/291.55 s(781) =< aux(179) 1150.39/291.55 s(801) =< aux(180)-1 1150.39/291.55 s(802) =< s(780)*aux(180) 1150.39/291.55 s(803) =< s(780)*s(801) 1150.39/291.55 1150.39/291.55 with precondition: [V1=2,V16=1,V>=2] 1150.39/291.55 1150.39/291.55 * Chain [48]: 2*s(842)+3 1150.39/291.55 Such that:aux(181) =< V16 1150.39/291.55 s(842) =< aux(181) 1150.39/291.55 1150.39/291.55 with precondition: [V1=2,V+1=V16,V>=1] 1150.39/291.55 1150.39/291.55 * Chain [47]: 23*s(844)+20*s(849)+1*s(853)+2*s(860)+9 1150.39/291.55 Such that:aux(183) =< 1 1150.39/291.55 s(852) =< -V16 1150.39/291.55 s(853) =< -V16+1 1150.39/291.55 aux(185) =< V16 1150.39/291.55 s(844) =< aux(185) 1150.39/291.55 s(849) =< aux(183) 1150.39/291.55 s(860) =< s(852) 1150.39/291.55 1150.39/291.55 with precondition: [V1=2,V=V16,V>=1] 1150.39/291.55 1150.39/291.55 * Chain [46]: 1*s(862)+139*s(865)+48*s(866)+4*s(868)+4*s(869)+11 1150.39/291.55 Such that:s(862) =< -V1+1 1150.39/291.55 aux(186) =< 1 1150.39/291.55 aux(187) =< V1 1150.39/291.55 s(865) =< aux(186) 1150.39/291.55 s(866) =< aux(187) 1150.39/291.55 s(867) =< aux(187)-1 1150.39/291.55 s(868) =< s(866)*aux(187) 1150.39/291.55 s(869) =< s(866)*s(867) 1150.39/291.55 1150.39/291.55 with precondition: [V=1,V1>=2] 1150.39/291.55 1150.39/291.55 * Chain [45]: 5*s(877)+2*s(880)+5 1150.39/291.55 Such that:s(878) =< 1 1150.39/291.55 aux(188) =< V 1150.39/291.55 s(877) =< aux(188) 1150.39/291.55 s(880) =< s(878) 1150.39/291.55 1150.39/291.55 with precondition: [V1+1=V,V1>=1] 1150.39/291.55 1150.39/291.55 1150.39/291.55 Closed-form bounds of start(V1,V,V16): 1150.39/291.55 ------------------------------------- 1150.39/291.55 * Chain [56] with precondition: [V1>=0,V>=0] 1150.39/291.55 - Upper bound: 33*V1+123*V+116+nat(-V1+V)*8+nat(-V1+1)+nat(-V+1)*5+nat(V1-V+1)*3+nat(V1-V)*18+V1/2*(nat(V1-V)*14)+nat(V1-2*V)*2+49/2*V1 1150.39/291.55 - Complexity: n^2 1150.39/291.55 * Chain [55] with precondition: [V1=0,V>=1] 1150.39/291.55 - Upper bound: 2*V+1 1150.39/291.55 - Complexity: n 1150.39/291.55 * Chain [54] with precondition: [V1=V,V1>=1] 1150.39/291.55 - Upper bound: 31*V+73 1150.39/291.55 - Complexity: n 1150.39/291.55 * Chain [53] with precondition: [V1=1,V>=0,V16>=0] 1150.39/291.55 - Upper bound: 1 1150.39/291.55 - Complexity: constant 1150.39/291.55 * Chain [52] with precondition: [V1=2,V>=0,V16>=0] 1150.39/291.55 - Upper bound: 40*V+376*V16+397+nat(-V+V16)*5+nat(-V16+1)*14+nat(V-2*V16+1)*6+nat(V-V16)*68+nat(V-2*V16)*30+nat(V-2*V16)*28*nat(V/2-V16/2)+nat(V-3*V16)*4+nat(V/2-V16/2)*98 1150.39/291.55 - Complexity: n^2 1150.39/291.55 * Chain [51] with precondition: [V1=2,V=0,V16=1] 1150.39/291.55 - Upper bound: 3 1150.39/291.55 - Complexity: constant 1150.39/291.55 * Chain [50] with precondition: [V1=2,V=0,V16>=2] 1150.39/291.55 - Upper bound: 2*V16+3 1150.39/291.55 - Complexity: n 1150.39/291.55 * Chain [49] with precondition: [V1=2,V16=1,V>=2] 1150.39/291.55 - Upper bound: 104*V+387+8*V*V+(V-1)*(8*V) 1150.39/291.55 - Complexity: n^2 1150.39/291.55 * Chain [48] with precondition: [V1=2,V+1=V16,V>=1] 1150.39/291.55 - Upper bound: 2*V16+3 1150.39/291.55 - Complexity: n 1150.39/291.55 * Chain [47] with precondition: [V1=2,V=V16,V>=1] 1150.39/291.55 - Upper bound: 23*V16+29 1150.39/291.55 - Complexity: n 1150.39/291.55 * Chain [46] with precondition: [V=1,V1>=2] 1150.39/291.55 - Upper bound: 48*V1+150+4*V1*V1+(V1-1)*(4*V1) 1150.39/291.55 - Complexity: n^2 1150.39/291.55 * Chain [45] with precondition: [V1+1=V,V1>=1] 1150.39/291.55 - Upper bound: 5*V+7 1150.39/291.55 - Complexity: n 1150.39/291.55 1150.39/291.55 ### Maximum cost of start(V1,V,V16): max([max([max([2,48*V1+149+4*V1*V1+4*V1*nat(V1-1)]),nat(V16)*21+26+(nat(V16)*2+2)]),9*V+43+max([64*V+max([8*V*V+271+8*V*nat(V-1),33*V1+19*V+nat(-V1+V)*8+nat(-V1+1)+nat(-V+1)*5+nat(V1-V+1)*3+nat(V1-V)*18+V1/2*(nat(V1-V)*14)+nat(V1-2*V)*2+49/2*V1]),nat(V16)*376+281+nat(-V+V16)*5+nat(-V16+1)*14+nat(V-2*V16+1)*6+nat(V-V16)*68+nat(V-2*V16)*30+nat(V-2*V16)*28*nat(V/2-V16/2)+nat(V-3*V16)*4+nat(V/2-V16/2)*98])+(26*V+66)+(3*V+6)+2*V])+1 1150.39/291.55 Asymptotic class: n^2 1150.39/291.55 * Total analysis performed in 1623 ms. 1150.39/291.55 1150.39/291.55 1150.39/291.55 ---------------------------------------- 1150.39/291.55 1150.39/291.55 (10) 1150.39/291.55 BOUNDS(1, n^2) 1150.39/291.55 1150.39/291.55 ---------------------------------------- 1150.39/291.55 1150.39/291.55 (11) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 1150.39/291.55 Transformed a relative TRS into a decreasing-loop problem. 1150.39/291.55 ---------------------------------------- 1150.39/291.55 1150.39/291.55 (12) 1150.39/291.55 Obligation: 1150.39/291.55 Analyzing the following TRS for decreasing loops: 1150.39/291.55 1150.39/291.55 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1150.39/291.55 1150.39/291.55 1150.39/291.55 The TRS R consists of the following rules: 1150.39/291.55 1150.39/291.55 ge(0, 0) -> true 1150.39/291.55 ge(s(x), 0) -> ge(x, 0) 1150.39/291.55 ge(0, s(0)) -> false 1150.39/291.55 ge(0, s(s(x))) -> ge(0, s(x)) 1150.39/291.55 ge(s(x), s(y)) -> ge(x, y) 1150.39/291.55 minus(0, 0) -> 0 1150.39/291.55 minus(0, s(x)) -> minus(0, x) 1150.39/291.55 minus(s(x), 0) -> s(minus(x, 0)) 1150.39/291.55 minus(s(x), s(y)) -> minus(x, y) 1150.39/291.55 plus(0, 0) -> 0 1150.39/291.55 plus(0, s(x)) -> s(plus(0, x)) 1150.39/291.55 plus(s(x), y) -> s(plus(x, y)) 1150.39/291.55 div(x, y) -> ify(ge(y, s(0)), x, y) 1150.39/291.55 ify(false, x, y) -> divByZeroError 1150.39/291.55 ify(true, x, y) -> if(ge(x, y), x, y) 1150.39/291.55 if(false, x, y) -> 0 1150.39/291.55 if(true, x, y) -> s(div(minus(x, y), y)) 1150.39/291.55 1150.39/291.55 S is empty. 1150.39/291.55 Rewrite Strategy: INNERMOST 1150.39/291.55 ---------------------------------------- 1150.39/291.55 1150.39/291.55 (13) DecreasingLoopProof (LOWER BOUND(ID)) 1150.39/291.55 The following loop(s) give(s) rise to the lower bound Omega(n^1): 1150.39/291.55 1150.39/291.55 The rewrite sequence 1150.39/291.55 1150.39/291.55 minus(s(x), 0) ->^+ s(minus(x, 0)) 1150.39/291.55 1150.39/291.55 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 1150.39/291.55 1150.39/291.55 The pumping substitution is [x / s(x)]. 1150.39/291.55 1150.39/291.55 The result substitution is [ ]. 1150.39/291.55 1150.39/291.55 1150.39/291.55 1150.39/291.55 1150.39/291.55 ---------------------------------------- 1150.39/291.55 1150.39/291.55 (14) 1150.39/291.55 Complex Obligation (BEST) 1150.39/291.55 1150.39/291.55 ---------------------------------------- 1150.39/291.55 1150.39/291.55 (15) 1150.39/291.55 Obligation: 1150.39/291.55 Proved the lower bound n^1 for the following obligation: 1150.39/291.55 1150.39/291.55 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1150.39/291.55 1150.39/291.55 1150.39/291.55 The TRS R consists of the following rules: 1150.39/291.55 1150.39/291.55 ge(0, 0) -> true 1150.39/291.55 ge(s(x), 0) -> ge(x, 0) 1150.39/291.55 ge(0, s(0)) -> false 1150.39/291.55 ge(0, s(s(x))) -> ge(0, s(x)) 1150.39/291.55 ge(s(x), s(y)) -> ge(x, y) 1150.39/291.55 minus(0, 0) -> 0 1150.39/291.55 minus(0, s(x)) -> minus(0, x) 1150.39/291.55 minus(s(x), 0) -> s(minus(x, 0)) 1150.39/291.55 minus(s(x), s(y)) -> minus(x, y) 1150.39/291.55 plus(0, 0) -> 0 1150.39/291.55 plus(0, s(x)) -> s(plus(0, x)) 1150.39/291.55 plus(s(x), y) -> s(plus(x, y)) 1150.39/291.55 div(x, y) -> ify(ge(y, s(0)), x, y) 1150.39/291.55 ify(false, x, y) -> divByZeroError 1150.39/291.55 ify(true, x, y) -> if(ge(x, y), x, y) 1150.39/291.55 if(false, x, y) -> 0 1150.39/291.55 if(true, x, y) -> s(div(minus(x, y), y)) 1150.39/291.55 1150.39/291.55 S is empty. 1150.39/291.55 Rewrite Strategy: INNERMOST 1150.39/291.55 ---------------------------------------- 1150.39/291.55 1150.39/291.55 (16) LowerBoundPropagationProof (FINISHED) 1150.39/291.55 Propagated lower bound. 1150.39/291.55 ---------------------------------------- 1150.39/291.55 1150.39/291.55 (17) 1150.39/291.55 BOUNDS(n^1, INF) 1150.39/291.55 1150.39/291.55 ---------------------------------------- 1150.39/291.55 1150.39/291.55 (18) 1150.39/291.55 Obligation: 1150.39/291.55 Analyzing the following TRS for decreasing loops: 1150.39/291.55 1150.39/291.55 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1150.39/291.55 1150.39/291.55 1150.39/291.55 The TRS R consists of the following rules: 1150.39/291.55 1150.39/291.55 ge(0, 0) -> true 1150.39/291.55 ge(s(x), 0) -> ge(x, 0) 1150.39/291.55 ge(0, s(0)) -> false 1150.39/291.55 ge(0, s(s(x))) -> ge(0, s(x)) 1150.39/291.55 ge(s(x), s(y)) -> ge(x, y) 1150.39/291.55 minus(0, 0) -> 0 1150.39/291.55 minus(0, s(x)) -> minus(0, x) 1150.39/291.55 minus(s(x), 0) -> s(minus(x, 0)) 1150.39/291.55 minus(s(x), s(y)) -> minus(x, y) 1150.39/291.55 plus(0, 0) -> 0 1150.39/291.55 plus(0, s(x)) -> s(plus(0, x)) 1150.39/291.55 plus(s(x), y) -> s(plus(x, y)) 1150.39/291.55 div(x, y) -> ify(ge(y, s(0)), x, y) 1150.39/291.55 ify(false, x, y) -> divByZeroError 1150.39/291.55 ify(true, x, y) -> if(ge(x, y), x, y) 1150.39/291.55 if(false, x, y) -> 0 1150.39/291.55 if(true, x, y) -> s(div(minus(x, y), y)) 1150.39/291.55 1150.39/291.55 S is empty. 1150.39/291.55 Rewrite Strategy: INNERMOST 1150.52/291.60 EOF