5.20/2.41 WORST_CASE(Omega(n^1), O(n^1)) 5.20/2.42 proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat 5.20/2.42 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.20/2.42 5.20/2.42 5.20/2.42 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, n^1). 5.20/2.42 5.20/2.42 (0) CpxIntTrs 5.20/2.42 (1) Koat Proof [FINISHED, 295 ms] 5.20/2.42 (2) BOUNDS(1, n^1) 5.20/2.42 (3) Loat Proof [FINISHED, 713 ms] 5.20/2.42 (4) BOUNDS(n^1, INF) 5.20/2.42 5.20/2.42 5.20/2.42 ---------------------------------------- 5.20/2.42 5.20/2.42 (0) 5.20/2.42 Obligation: 5.20/2.42 Complexity Int TRS consisting of the following rules: 5.20/2.42 eval_speedSimpleMultiple_start(v_m, v_n, v_x_0, v_y_0) -> Com_1(eval_speedSimpleMultiple_bb0_in(v_m, v_n, v_x_0, v_y_0)) :|: TRUE 5.20/2.42 eval_speedSimpleMultiple_bb0_in(v_m, v_n, v_x_0, v_y_0) -> Com_1(eval_speedSimpleMultiple_0(v_m, v_n, v_x_0, v_y_0)) :|: TRUE 5.20/2.42 eval_speedSimpleMultiple_0(v_m, v_n, v_x_0, v_y_0) -> Com_1(eval_speedSimpleMultiple_1(v_m, v_n, v_x_0, v_y_0)) :|: TRUE 5.20/2.42 eval_speedSimpleMultiple_1(v_m, v_n, v_x_0, v_y_0) -> Com_1(eval_speedSimpleMultiple_2(v_m, v_n, v_x_0, v_y_0)) :|: TRUE 5.20/2.42 eval_speedSimpleMultiple_2(v_m, v_n, v_x_0, v_y_0) -> Com_1(eval_speedSimpleMultiple_3(v_m, v_n, v_x_0, v_y_0)) :|: TRUE 5.20/2.42 eval_speedSimpleMultiple_3(v_m, v_n, v_x_0, v_y_0) -> Com_1(eval_speedSimpleMultiple_4(v_m, v_n, v_x_0, v_y_0)) :|: TRUE 5.20/2.42 eval_speedSimpleMultiple_4(v_m, v_n, v_x_0, v_y_0) -> Com_1(eval_speedSimpleMultiple_5(v_m, v_n, v_x_0, v_y_0)) :|: TRUE 5.20/2.42 eval_speedSimpleMultiple_5(v_m, v_n, v_x_0, v_y_0) -> Com_1(eval_speedSimpleMultiple_6(v_m, v_n, v_x_0, v_y_0)) :|: TRUE 5.20/2.42 eval_speedSimpleMultiple_6(v_m, v_n, v_x_0, v_y_0) -> Com_1(eval_speedSimpleMultiple_bb1_in(v_m, v_n, 0, 0)) :|: TRUE 5.20/2.42 eval_speedSimpleMultiple_bb1_in(v_m, v_n, v_x_0, v_y_0) -> Com_1(eval_speedSimpleMultiple_bb2_in(v_m, v_n, v_x_0, v_y_0)) :|: v_x_0 < v_n 5.20/2.42 eval_speedSimpleMultiple_bb1_in(v_m, v_n, v_x_0, v_y_0) -> Com_1(eval_speedSimpleMultiple_bb3_in(v_m, v_n, v_x_0, v_y_0)) :|: v_x_0 >= v_n 5.20/2.42 eval_speedSimpleMultiple_bb2_in(v_m, v_n, v_x_0, v_y_0) -> Com_1(eval_speedSimpleMultiple_bb1_in(v_m, v_n, v_x_0, v_y_0 + 1)) :|: v_y_0 < v_m 5.20/2.42 eval_speedSimpleMultiple_bb2_in(v_m, v_n, v_x_0, v_y_0) -> Com_1(eval_speedSimpleMultiple_bb1_in(v_m, v_n, v_x_0 + 1, v_y_0 + 1)) :|: v_y_0 < v_m && v_y_0 >= v_m 5.20/2.42 eval_speedSimpleMultiple_bb2_in(v_m, v_n, v_x_0, v_y_0) -> Com_1(eval_speedSimpleMultiple_bb1_in(v_m, v_n, v_x_0, v_y_0)) :|: v_y_0 >= v_m && v_y_0 < v_m 5.20/2.42 eval_speedSimpleMultiple_bb2_in(v_m, v_n, v_x_0, v_y_0) -> Com_1(eval_speedSimpleMultiple_bb1_in(v_m, v_n, v_x_0 + 1, v_y_0)) :|: v_y_0 >= v_m 5.20/2.42 eval_speedSimpleMultiple_bb3_in(v_m, v_n, v_x_0, v_y_0) -> Com_1(eval_speedSimpleMultiple_stop(v_m, v_n, v_x_0, v_y_0)) :|: TRUE 5.20/2.42 5.20/2.42 The start-symbols are:[eval_speedSimpleMultiple_start_4] 5.20/2.42 5.20/2.42 5.20/2.42 ---------------------------------------- 5.20/2.42 5.20/2.42 (1) Koat Proof (FINISHED) 5.20/2.42 YES(?, 2*ar_2 + 2*ar_3 + 14) 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 Initial complexity problem: 5.20/2.42 5.20/2.42 1: T: 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplestart(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb0in(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple0(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiple0(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple1(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiple1(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple2(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiple2(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple3(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiple3(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple4(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiple4(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple5(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiple5(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple6(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiple6(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(0, 0, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= ar_0 + 1 ] 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb3in(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_2 ] 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(ar_0, ar_1 + 1, ar_2, ar_3)) [ ar_3 >= ar_1 + 1 ] 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(ar_0 + 1, ar_1 + 1, ar_2, ar_3)) [ ar_3 >= ar_1 + 1 /\ ar_1 >= ar_3 ] 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= ar_3 /\ ar_3 >= ar_1 + 1 ] 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_1 >= ar_3 ] 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplestop(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplestart(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] 5.20/2.42 5.20/2.42 start location: koat_start 5.20/2.42 5.20/2.42 leaf cost: 0 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 Testing for reachability in the complexity graph removes the following transitions from problem 1: 5.20/2.42 5.20/2.42 evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(ar_0 + 1, ar_1 + 1, ar_2, ar_3)) [ ar_3 >= ar_1 + 1 /\ ar_1 >= ar_3 ] 5.20/2.42 5.20/2.42 evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= ar_3 /\ ar_3 >= ar_1 + 1 ] 5.20/2.42 5.20/2.42 We thus obtain the following problem: 5.20/2.42 5.20/2.42 2: T: 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplestop(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_1 >= ar_3 ] 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(ar_0, ar_1 + 1, ar_2, ar_3)) [ ar_3 >= ar_1 + 1 ] 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb3in(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_2 ] 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= ar_0 + 1 ] 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiple6(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(0, 0, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiple5(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple6(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiple4(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple5(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiple3(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple4(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiple2(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple3(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiple1(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple2(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiple0(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple1(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple0(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplestart(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb0in(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplestart(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] 5.20/2.42 5.20/2.42 start location: koat_start 5.20/2.42 5.20/2.42 leaf cost: 0 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 Repeatedly propagating knowledge in problem 2 produces the following problem: 5.20/2.42 5.20/2.42 3: T: 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplestop(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_1 >= ar_3 ] 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(ar_0, ar_1 + 1, ar_2, ar_3)) [ ar_3 >= ar_1 + 1 ] 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb3in(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_2 ] 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= ar_0 + 1 ] 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple6(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(0, 0, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple5(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple6(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple4(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple5(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple3(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple4(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple2(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple3(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple1(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple2(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple0(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple1(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiplebb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple0(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiplestart(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb0in(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplestart(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] 5.20/2.42 5.20/2.42 start location: koat_start 5.20/2.42 5.20/2.42 leaf cost: 0 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 A polynomial rank function with 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiplebb3in) = 1 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiplestop) = 0 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiplebb2in) = 2 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiplebb1in) = 2 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiple6) = 2 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiple5) = 2 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiple4) = 2 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiple3) = 2 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiple2) = 2 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiple1) = 2 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiple0) = 2 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiplebb0in) = 2 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiplestart) = 2 5.20/2.42 5.20/2.42 Pol(koat_start) = 2 5.20/2.42 5.20/2.42 orients all transitions weakly and the transitions 5.20/2.42 5.20/2.42 evalspeedSimpleMultiplebb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplestop(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 evalspeedSimpleMultiplebb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb3in(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_2 ] 5.20/2.42 5.20/2.42 strictly and produces the following problem: 5.20/2.42 5.20/2.42 4: T: 5.20/2.42 5.20/2.42 (Comp: 2, Cost: 1) evalspeedSimpleMultiplebb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplestop(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_1 >= ar_3 ] 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(ar_0, ar_1 + 1, ar_2, ar_3)) [ ar_3 >= ar_1 + 1 ] 5.20/2.42 5.20/2.42 (Comp: 2, Cost: 1) evalspeedSimpleMultiplebb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb3in(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_2 ] 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= ar_0 + 1 ] 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple6(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(0, 0, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple5(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple6(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple4(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple5(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple3(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple4(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple2(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple3(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple1(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple2(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple0(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple1(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiplebb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple0(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiplestart(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb0in(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplestart(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] 5.20/2.42 5.20/2.42 start location: koat_start 5.20/2.42 5.20/2.42 leaf cost: 0 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 A polynomial rank function with 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiplebb3in) = -V_2 + V_4 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiplestop) = -V_2 + V_4 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiplebb2in) = -V_2 + V_4 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiplebb1in) = -V_2 + V_4 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiple6) = V_4 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiple5) = V_4 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiple4) = V_4 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiple3) = V_4 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiple2) = V_4 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiple1) = V_4 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiple0) = V_4 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiplebb0in) = V_4 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiplestart) = V_4 5.20/2.42 5.20/2.42 Pol(koat_start) = V_4 5.20/2.42 5.20/2.42 orients all transitions weakly and the transition 5.20/2.42 5.20/2.42 evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(ar_0, ar_1 + 1, ar_2, ar_3)) [ ar_3 >= ar_1 + 1 ] 5.20/2.42 5.20/2.42 strictly and produces the following problem: 5.20/2.42 5.20/2.42 5: T: 5.20/2.42 5.20/2.42 (Comp: 2, Cost: 1) evalspeedSimpleMultiplebb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplestop(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_1 >= ar_3 ] 5.20/2.42 5.20/2.42 (Comp: ar_3, Cost: 1) evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(ar_0, ar_1 + 1, ar_2, ar_3)) [ ar_3 >= ar_1 + 1 ] 5.20/2.42 5.20/2.42 (Comp: 2, Cost: 1) evalspeedSimpleMultiplebb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb3in(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_2 ] 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= ar_0 + 1 ] 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple6(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(0, 0, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple5(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple6(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple4(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple5(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple3(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple4(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple2(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple3(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple1(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple2(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple0(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple1(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiplebb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple0(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiplestart(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb0in(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplestart(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] 5.20/2.42 5.20/2.42 start location: koat_start 5.20/2.42 5.20/2.42 leaf cost: 0 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 Applied AI with 'oct' on problem 5 to obtain the following invariants: 5.20/2.42 5.20/2.42 For symbol evalspeedSimpleMultiplebb1in: X_2 >= 0 /\ X_1 + X_2 >= 0 /\ X_1 >= 0 5.20/2.42 5.20/2.42 For symbol evalspeedSimpleMultiplebb2in: X_3 - 1 >= 0 /\ X_2 + X_3 - 1 >= 0 /\ X_1 + X_3 - 1 >= 0 /\ -X_1 + X_3 - 1 >= 0 /\ X_2 >= 0 /\ X_1 + X_2 >= 0 /\ X_1 >= 0 5.20/2.42 5.20/2.42 For symbol evalspeedSimpleMultiplebb3in: X_1 - X_3 >= 0 /\ X_2 >= 0 /\ X_1 + X_2 >= 0 /\ X_1 >= 0 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 This yielded the following problem: 5.20/2.42 5.20/2.42 6: T: 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplestart(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiplestart(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb0in(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiplebb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple0(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple0(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple1(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple1(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple2(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple2(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple3(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple3(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple4(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple4(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple5(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple5(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple6(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple6(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(0, 0, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_2 >= ar_0 + 1 ] 5.20/2.42 5.20/2.42 (Comp: 2, Cost: 1) evalspeedSimpleMultiplebb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb3in(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_0 >= ar_2 ] 5.20/2.42 5.20/2.42 (Comp: ar_3, Cost: 1) evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(ar_0, ar_1 + 1, ar_2, ar_3)) [ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ -ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_3 >= ar_1 + 1 ] 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ -ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_1 >= ar_3 ] 5.20/2.42 5.20/2.42 (Comp: 2, Cost: 1) evalspeedSimpleMultiplebb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplestop(ar_0, ar_1, ar_2, ar_3)) [ ar_0 - ar_2 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 ] 5.20/2.42 5.20/2.42 start location: koat_start 5.20/2.42 5.20/2.42 leaf cost: 0 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 A polynomial rank function with 5.20/2.42 5.20/2.42 Pol(koat_start) = V_3 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiplestart) = V_3 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiplebb0in) = V_3 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiple0) = V_3 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiple1) = V_3 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiple2) = V_3 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiple3) = V_3 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiple4) = V_3 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiple5) = V_3 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiple6) = V_3 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiplebb1in) = -V_1 + V_3 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiplebb2in) = -V_1 + V_3 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiplebb3in) = -V_1 + V_3 5.20/2.42 5.20/2.42 Pol(evalspeedSimpleMultiplestop) = -V_1 + V_3 5.20/2.42 5.20/2.42 orients all transitions weakly and the transition 5.20/2.42 5.20/2.42 evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ -ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_1 >= ar_3 ] 5.20/2.42 5.20/2.42 strictly and produces the following problem: 5.20/2.42 5.20/2.42 7: T: 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplestart(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiplestart(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb0in(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiplebb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple0(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple0(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple1(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple1(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple2(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple2(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple3(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple3(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple4(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple4(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple5(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple5(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple6(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple6(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(0, 0, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: ?, Cost: 1) evalspeedSimpleMultiplebb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_2 >= ar_0 + 1 ] 5.20/2.42 5.20/2.42 (Comp: 2, Cost: 1) evalspeedSimpleMultiplebb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb3in(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_0 >= ar_2 ] 5.20/2.42 5.20/2.42 (Comp: ar_3, Cost: 1) evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(ar_0, ar_1 + 1, ar_2, ar_3)) [ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ -ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_3 >= ar_1 + 1 ] 5.20/2.42 5.20/2.42 (Comp: ar_2, Cost: 1) evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ -ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_1 >= ar_3 ] 5.20/2.42 5.20/2.42 (Comp: 2, Cost: 1) evalspeedSimpleMultiplebb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplestop(ar_0, ar_1, ar_2, ar_3)) [ ar_0 - ar_2 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 ] 5.20/2.42 5.20/2.42 start location: koat_start 5.20/2.42 5.20/2.42 leaf cost: 0 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 Repeatedly propagating knowledge in problem 7 produces the following problem: 5.20/2.42 5.20/2.42 8: T: 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplestart(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiplestart(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb0in(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiplebb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple0(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple0(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple1(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple1(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple2(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple2(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple3(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple3(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple4(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple4(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple5(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple5(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiple6(ar_0, ar_1, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: 1, Cost: 1) evalspeedSimpleMultiple6(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(0, 0, ar_2, ar_3)) 5.20/2.42 5.20/2.42 (Comp: ar_2 + ar_3 + 1, Cost: 1) evalspeedSimpleMultiplebb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_2 >= ar_0 + 1 ] 5.20/2.42 5.20/2.42 (Comp: 2, Cost: 1) evalspeedSimpleMultiplebb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb3in(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_0 >= ar_2 ] 5.20/2.42 5.20/2.42 (Comp: ar_3, Cost: 1) evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(ar_0, ar_1 + 1, ar_2, ar_3)) [ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ -ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_3 >= ar_1 + 1 ] 5.20/2.42 5.20/2.42 (Comp: ar_2, Cost: 1) evalspeedSimpleMultiplebb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplebb1in(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ -ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_1 >= ar_3 ] 5.20/2.42 5.20/2.42 (Comp: 2, Cost: 1) evalspeedSimpleMultiplebb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedSimpleMultiplestop(ar_0, ar_1, ar_2, ar_3)) [ ar_0 - ar_2 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 ] 5.20/2.42 5.20/2.42 start location: koat_start 5.20/2.42 5.20/2.42 leaf cost: 0 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 Complexity upper bound 2*ar_2 + 2*ar_3 + 14 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 Time: 0.301 sec (SMT: 0.245 sec) 5.20/2.42 5.20/2.42 5.20/2.42 ---------------------------------------- 5.20/2.42 5.20/2.42 (2) 5.20/2.42 BOUNDS(1, n^1) 5.20/2.42 5.20/2.42 ---------------------------------------- 5.20/2.42 5.20/2.42 (3) Loat Proof (FINISHED) 5.20/2.42 5.20/2.42 5.20/2.42 ### Pre-processing the ITS problem ### 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 Initial linear ITS problem 5.20/2.42 5.20/2.42 Start location: evalspeedSimpleMultiplestart 5.20/2.42 5.20/2.42 0: evalspeedSimpleMultiplestart -> evalspeedSimpleMultiplebb0in : [], cost: 1 5.20/2.42 5.20/2.42 1: evalspeedSimpleMultiplebb0in -> evalspeedSimpleMultiple0 : [], cost: 1 5.20/2.42 5.20/2.42 2: evalspeedSimpleMultiple0 -> evalspeedSimpleMultiple1 : [], cost: 1 5.20/2.42 5.20/2.42 3: evalspeedSimpleMultiple1 -> evalspeedSimpleMultiple2 : [], cost: 1 5.20/2.42 5.20/2.42 4: evalspeedSimpleMultiple2 -> evalspeedSimpleMultiple3 : [], cost: 1 5.20/2.42 5.20/2.42 5: evalspeedSimpleMultiple3 -> evalspeedSimpleMultiple4 : [], cost: 1 5.20/2.42 5.20/2.42 6: evalspeedSimpleMultiple4 -> evalspeedSimpleMultiple5 : [], cost: 1 5.20/2.42 5.20/2.42 7: evalspeedSimpleMultiple5 -> evalspeedSimpleMultiple6 : [], cost: 1 5.20/2.42 5.20/2.42 8: evalspeedSimpleMultiple6 -> evalspeedSimpleMultiplebb1in : A'=0, B'=0, [], cost: 1 5.20/2.42 5.20/2.42 9: evalspeedSimpleMultiplebb1in -> evalspeedSimpleMultiplebb2in : [ C>=1+A ], cost: 1 5.20/2.42 5.20/2.42 10: evalspeedSimpleMultiplebb1in -> evalspeedSimpleMultiplebb3in : [ A>=C ], cost: 1 5.20/2.42 5.20/2.42 11: evalspeedSimpleMultiplebb2in -> evalspeedSimpleMultiplebb1in : B'=1+B, [ D>=1+B ], cost: 1 5.20/2.42 5.20/2.42 12: evalspeedSimpleMultiplebb2in -> evalspeedSimpleMultiplebb1in : A'=1+A, B'=1+B, [ D>=1+B && B>=D ], cost: 1 5.20/2.42 5.20/2.42 13: evalspeedSimpleMultiplebb2in -> evalspeedSimpleMultiplebb1in : [ B>=D && D>=1+B ], cost: 1 5.20/2.42 5.20/2.42 14: evalspeedSimpleMultiplebb2in -> evalspeedSimpleMultiplebb1in : A'=1+A, [ B>=D ], cost: 1 5.20/2.42 5.20/2.42 15: evalspeedSimpleMultiplebb3in -> evalspeedSimpleMultiplestop : [], cost: 1 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 Removed unreachable and leaf rules: 5.20/2.42 5.20/2.42 Start location: evalspeedSimpleMultiplestart 5.20/2.42 5.20/2.42 0: evalspeedSimpleMultiplestart -> evalspeedSimpleMultiplebb0in : [], cost: 1 5.20/2.42 5.20/2.42 1: evalspeedSimpleMultiplebb0in -> evalspeedSimpleMultiple0 : [], cost: 1 5.20/2.42 5.20/2.42 2: evalspeedSimpleMultiple0 -> evalspeedSimpleMultiple1 : [], cost: 1 5.20/2.42 5.20/2.42 3: evalspeedSimpleMultiple1 -> evalspeedSimpleMultiple2 : [], cost: 1 5.20/2.42 5.20/2.42 4: evalspeedSimpleMultiple2 -> evalspeedSimpleMultiple3 : [], cost: 1 5.20/2.42 5.20/2.42 5: evalspeedSimpleMultiple3 -> evalspeedSimpleMultiple4 : [], cost: 1 5.20/2.42 5.20/2.42 6: evalspeedSimpleMultiple4 -> evalspeedSimpleMultiple5 : [], cost: 1 5.20/2.42 5.20/2.42 7: evalspeedSimpleMultiple5 -> evalspeedSimpleMultiple6 : [], cost: 1 5.20/2.42 5.20/2.42 8: evalspeedSimpleMultiple6 -> evalspeedSimpleMultiplebb1in : A'=0, B'=0, [], cost: 1 5.20/2.42 5.20/2.42 9: evalspeedSimpleMultiplebb1in -> evalspeedSimpleMultiplebb2in : [ C>=1+A ], cost: 1 5.20/2.42 5.20/2.42 11: evalspeedSimpleMultiplebb2in -> evalspeedSimpleMultiplebb1in : B'=1+B, [ D>=1+B ], cost: 1 5.20/2.42 5.20/2.42 12: evalspeedSimpleMultiplebb2in -> evalspeedSimpleMultiplebb1in : A'=1+A, B'=1+B, [ D>=1+B && B>=D ], cost: 1 5.20/2.42 5.20/2.42 13: evalspeedSimpleMultiplebb2in -> evalspeedSimpleMultiplebb1in : [ B>=D && D>=1+B ], cost: 1 5.20/2.42 5.20/2.42 14: evalspeedSimpleMultiplebb2in -> evalspeedSimpleMultiplebb1in : A'=1+A, [ B>=D ], cost: 1 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 Removed rules with unsatisfiable guard: 5.20/2.42 5.20/2.42 Start location: evalspeedSimpleMultiplestart 5.20/2.42 5.20/2.42 0: evalspeedSimpleMultiplestart -> evalspeedSimpleMultiplebb0in : [], cost: 1 5.20/2.42 5.20/2.42 1: evalspeedSimpleMultiplebb0in -> evalspeedSimpleMultiple0 : [], cost: 1 5.20/2.42 5.20/2.42 2: evalspeedSimpleMultiple0 -> evalspeedSimpleMultiple1 : [], cost: 1 5.20/2.42 5.20/2.42 3: evalspeedSimpleMultiple1 -> evalspeedSimpleMultiple2 : [], cost: 1 5.20/2.42 5.20/2.42 4: evalspeedSimpleMultiple2 -> evalspeedSimpleMultiple3 : [], cost: 1 5.20/2.42 5.20/2.42 5: evalspeedSimpleMultiple3 -> evalspeedSimpleMultiple4 : [], cost: 1 5.20/2.42 5.20/2.42 6: evalspeedSimpleMultiple4 -> evalspeedSimpleMultiple5 : [], cost: 1 5.20/2.42 5.20/2.42 7: evalspeedSimpleMultiple5 -> evalspeedSimpleMultiple6 : [], cost: 1 5.20/2.42 5.20/2.42 8: evalspeedSimpleMultiple6 -> evalspeedSimpleMultiplebb1in : A'=0, B'=0, [], cost: 1 5.20/2.42 5.20/2.42 9: evalspeedSimpleMultiplebb1in -> evalspeedSimpleMultiplebb2in : [ C>=1+A ], cost: 1 5.20/2.42 5.20/2.42 11: evalspeedSimpleMultiplebb2in -> evalspeedSimpleMultiplebb1in : B'=1+B, [ D>=1+B ], cost: 1 5.20/2.42 5.20/2.42 14: evalspeedSimpleMultiplebb2in -> evalspeedSimpleMultiplebb1in : A'=1+A, [ B>=D ], cost: 1 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 ### Simplification by acceleration and chaining ### 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 Eliminated locations (on linear paths): 5.20/2.42 5.20/2.42 Start location: evalspeedSimpleMultiplestart 5.20/2.42 5.20/2.42 23: evalspeedSimpleMultiplestart -> evalspeedSimpleMultiplebb1in : A'=0, B'=0, [], cost: 9 5.20/2.42 5.20/2.42 9: evalspeedSimpleMultiplebb1in -> evalspeedSimpleMultiplebb2in : [ C>=1+A ], cost: 1 5.20/2.42 5.20/2.42 11: evalspeedSimpleMultiplebb2in -> evalspeedSimpleMultiplebb1in : B'=1+B, [ D>=1+B ], cost: 1 5.20/2.42 5.20/2.42 14: evalspeedSimpleMultiplebb2in -> evalspeedSimpleMultiplebb1in : A'=1+A, [ B>=D ], cost: 1 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 Eliminated locations (on tree-shaped paths): 5.20/2.42 5.20/2.42 Start location: evalspeedSimpleMultiplestart 5.20/2.42 5.20/2.42 23: evalspeedSimpleMultiplestart -> evalspeedSimpleMultiplebb1in : A'=0, B'=0, [], cost: 9 5.20/2.42 5.20/2.42 24: evalspeedSimpleMultiplebb1in -> evalspeedSimpleMultiplebb1in : B'=1+B, [ C>=1+A && D>=1+B ], cost: 2 5.20/2.42 5.20/2.42 25: evalspeedSimpleMultiplebb1in -> evalspeedSimpleMultiplebb1in : A'=1+A, [ C>=1+A && B>=D ], cost: 2 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 Accelerating simple loops of location 9. 5.20/2.42 5.20/2.42 Accelerating the following rules: 5.20/2.42 5.20/2.42 24: evalspeedSimpleMultiplebb1in -> evalspeedSimpleMultiplebb1in : B'=1+B, [ C>=1+A && D>=1+B ], cost: 2 5.20/2.42 5.20/2.42 25: evalspeedSimpleMultiplebb1in -> evalspeedSimpleMultiplebb1in : A'=1+A, [ C>=1+A && B>=D ], cost: 2 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 Accelerated rule 24 with metering function D-B, yielding the new rule 26. 5.20/2.42 5.20/2.42 Accelerated rule 25 with metering function C-A, yielding the new rule 27. 5.20/2.42 5.20/2.42 Removing the simple loops: 24 25. 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 Accelerated all simple loops using metering functions (where possible): 5.20/2.42 5.20/2.42 Start location: evalspeedSimpleMultiplestart 5.20/2.42 5.20/2.42 23: evalspeedSimpleMultiplestart -> evalspeedSimpleMultiplebb1in : A'=0, B'=0, [], cost: 9 5.20/2.42 5.20/2.42 26: evalspeedSimpleMultiplebb1in -> evalspeedSimpleMultiplebb1in : B'=D, [ C>=1+A && D>=1+B ], cost: 2*D-2*B 5.20/2.42 5.20/2.42 27: evalspeedSimpleMultiplebb1in -> evalspeedSimpleMultiplebb1in : A'=C, [ C>=1+A && B>=D ], cost: 2*C-2*A 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 Chained accelerated rules (with incoming rules): 5.20/2.42 5.20/2.42 Start location: evalspeedSimpleMultiplestart 5.20/2.42 5.20/2.42 23: evalspeedSimpleMultiplestart -> evalspeedSimpleMultiplebb1in : A'=0, B'=0, [], cost: 9 5.20/2.42 5.20/2.42 28: evalspeedSimpleMultiplestart -> evalspeedSimpleMultiplebb1in : A'=0, B'=D, [ C>=1 && D>=1 ], cost: 9+2*D 5.20/2.42 5.20/2.42 29: evalspeedSimpleMultiplestart -> evalspeedSimpleMultiplebb1in : A'=C, B'=0, [ C>=1 && 0>=D ], cost: 9+2*C 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 Removed unreachable locations (and leaf rules with constant cost): 5.20/2.42 5.20/2.42 Start location: evalspeedSimpleMultiplestart 5.20/2.42 5.20/2.42 28: evalspeedSimpleMultiplestart -> evalspeedSimpleMultiplebb1in : A'=0, B'=D, [ C>=1 && D>=1 ], cost: 9+2*D 5.20/2.42 5.20/2.42 29: evalspeedSimpleMultiplestart -> evalspeedSimpleMultiplebb1in : A'=C, B'=0, [ C>=1 && 0>=D ], cost: 9+2*C 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 ### Computing asymptotic complexity ### 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 Fully simplified ITS problem 5.20/2.42 5.20/2.42 Start location: evalspeedSimpleMultiplestart 5.20/2.42 5.20/2.42 28: evalspeedSimpleMultiplestart -> evalspeedSimpleMultiplebb1in : A'=0, B'=D, [ C>=1 && D>=1 ], cost: 9+2*D 5.20/2.42 5.20/2.42 29: evalspeedSimpleMultiplestart -> evalspeedSimpleMultiplebb1in : A'=C, B'=0, [ C>=1 && 0>=D ], cost: 9+2*C 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 Computing asymptotic complexity for rule 28 5.20/2.42 5.20/2.42 Solved the limit problem by the following transformations: 5.20/2.42 5.20/2.42 Created initial limit problem: 5.20/2.42 5.20/2.42 C (+/+!), 9+2*D (+), D (+/+!) [not solved] 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 removing all constraints (solved by SMT) 5.20/2.42 5.20/2.42 resulting limit problem: [solved] 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 applying transformation rule (C) using substitution {C==1,D==n} 5.20/2.42 5.20/2.42 resulting limit problem: 5.20/2.42 5.20/2.42 [solved] 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 Solution: 5.20/2.42 5.20/2.42 C / 1 5.20/2.42 5.20/2.42 D / n 5.20/2.42 5.20/2.42 Resulting cost 9+2*n has complexity: Poly(n^1) 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 Found new complexity Poly(n^1). 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 Obtained the following overall complexity (w.r.t. the length of the input n): 5.20/2.42 5.20/2.42 Complexity: Poly(n^1) 5.20/2.42 5.20/2.42 Cpx degree: 1 5.20/2.42 5.20/2.42 Solved cost: 9+2*n 5.20/2.42 5.20/2.42 Rule cost: 9+2*D 5.20/2.42 5.20/2.42 Rule guard: [ C>=1 && D>=1 ] 5.20/2.42 5.20/2.42 5.20/2.42 5.20/2.42 WORST_CASE(Omega(n^1),?) 5.20/2.42 5.20/2.42 5.20/2.42 ---------------------------------------- 5.20/2.42 5.20/2.42 (4) 5.20/2.42 BOUNDS(n^1, INF) 5.20/2.44 EOF