5.86/2.89 MAYBE 5.86/2.90 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 5.86/2.90 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.86/2.90 5.86/2.90 5.86/2.90 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(1, INF). 5.86/2.90 5.86/2.90 (0) CpxIntTrs 5.86/2.90 (1) Loat Proof [FINISHED, 335 ms] 5.86/2.90 (2) BOUNDS(1, INF) 5.86/2.90 5.86/2.90 5.86/2.90 ---------------------------------------- 5.86/2.90 5.86/2.90 (0) 5.86/2.90 Obligation: 5.86/2.90 Complexity Int TRS consisting of the following rules: 5.86/2.90 eval_speedFails1_start(v__0, v_i, v_m, v_n) -> Com_1(eval_speedFails1_bb0_in(v__0, v_i, v_m, v_n)) :|: TRUE 5.86/2.90 eval_speedFails1_bb0_in(v__0, v_i, v_m, v_n) -> Com_1(eval_speedFails1_0(v__0, v_i, v_m, v_n)) :|: TRUE 5.86/2.90 eval_speedFails1_0(v__0, v_i, v_m, v_n) -> Com_1(eval_speedFails1_1(v__0, v_i, v_m, v_n)) :|: TRUE 5.86/2.90 eval_speedFails1_1(v__0, v_i, v_m, v_n) -> Com_1(eval_speedFails1_2(v__0, v_i, v_m, v_n)) :|: TRUE 5.86/2.90 eval_speedFails1_2(v__0, v_i, v_m, v_n) -> Com_1(eval_speedFails1_3(v__0, v_i, v_m, v_n)) :|: TRUE 5.86/2.90 eval_speedFails1_3(v__0, v_i, v_m, v_n) -> Com_1(eval_speedFails1_4(v__0, v_i, v_m, v_n)) :|: TRUE 5.86/2.90 eval_speedFails1_4(v__0, v_i, v_m, v_n) -> Com_1(eval_speedFails1_bb1_in(v_i, v_i, v_m, v_n)) :|: TRUE 5.86/2.90 eval_speedFails1_bb1_in(v__0, v_i, v_m, v_n) -> Com_1(eval_speedFails1_bb2_in(v__0, v_i, v_m, v_n)) :|: v__0 <= v_n 5.86/2.90 eval_speedFails1_bb1_in(v__0, v_i, v_m, v_n) -> Com_1(eval_speedFails1_bb3_in(v__0, v_i, v_m, v_n)) :|: v__0 > v_n 5.86/2.90 eval_speedFails1_bb2_in(v__0, v_i, v_m, v_n) -> Com_1(eval_speedFails1_bb1_in(v__0 + v_m, v_i, v_m, v_n)) :|: TRUE 5.86/2.90 eval_speedFails1_bb3_in(v__0, v_i, v_m, v_n) -> Com_1(eval_speedFails1_stop(v__0, v_i, v_m, v_n)) :|: TRUE 5.86/2.90 5.86/2.90 The start-symbols are:[eval_speedFails1_start_4] 5.86/2.90 5.86/2.90 5.86/2.90 ---------------------------------------- 5.86/2.90 5.86/2.90 (1) Loat Proof (FINISHED) 5.86/2.90 5.86/2.90 5.86/2.90 ### Pre-processing the ITS problem ### 5.86/2.90 5.86/2.90 5.86/2.90 5.86/2.90 Initial linear ITS problem 5.86/2.90 5.86/2.90 Start location: evalspeedFails1start 5.86/2.90 5.86/2.90 0: evalspeedFails1start -> evalspeedFails1bb0in : [], cost: 1 5.86/2.90 5.86/2.90 1: evalspeedFails1bb0in -> evalspeedFails10 : [], cost: 1 5.86/2.90 5.86/2.90 2: evalspeedFails10 -> evalspeedFails11 : [], cost: 1 5.86/2.90 5.86/2.90 3: evalspeedFails11 -> evalspeedFails12 : [], cost: 1 5.86/2.90 5.86/2.90 4: evalspeedFails12 -> evalspeedFails13 : [], cost: 1 5.86/2.90 5.86/2.90 5: evalspeedFails13 -> evalspeedFails14 : [], cost: 1 5.86/2.90 5.86/2.90 6: evalspeedFails14 -> evalspeedFails1bb1in : A'=B, [], cost: 1 5.86/2.90 5.86/2.90 7: evalspeedFails1bb1in -> evalspeedFails1bb2in : [ C>=A ], cost: 1 5.86/2.90 5.86/2.90 8: evalspeedFails1bb1in -> evalspeedFails1bb3in : [ A>=1+C ], cost: 1 5.86/2.90 5.86/2.90 9: evalspeedFails1bb2in -> evalspeedFails1bb1in : A'=D+A, [], cost: 1 5.86/2.90 5.86/2.90 10: evalspeedFails1bb3in -> evalspeedFails1stop : [], cost: 1 5.86/2.90 5.86/2.90 5.86/2.90 5.86/2.90 Removed unreachable and leaf rules: 5.86/2.90 5.86/2.90 Start location: evalspeedFails1start 5.86/2.90 5.86/2.90 0: evalspeedFails1start -> evalspeedFails1bb0in : [], cost: 1 5.86/2.90 5.86/2.90 1: evalspeedFails1bb0in -> evalspeedFails10 : [], cost: 1 5.86/2.90 5.86/2.90 2: evalspeedFails10 -> evalspeedFails11 : [], cost: 1 5.86/2.90 5.86/2.90 3: evalspeedFails11 -> evalspeedFails12 : [], cost: 1 5.86/2.90 5.86/2.90 4: evalspeedFails12 -> evalspeedFails13 : [], cost: 1 5.86/2.90 5.86/2.90 5: evalspeedFails13 -> evalspeedFails14 : [], cost: 1 5.86/2.90 5.86/2.90 6: evalspeedFails14 -> evalspeedFails1bb1in : A'=B, [], cost: 1 5.86/2.90 5.86/2.90 7: evalspeedFails1bb1in -> evalspeedFails1bb2in : [ C>=A ], cost: 1 5.86/2.90 5.86/2.90 9: evalspeedFails1bb2in -> evalspeedFails1bb1in : A'=D+A, [], cost: 1 5.86/2.90 5.86/2.90 5.86/2.90 5.86/2.90 ### Simplification by acceleration and chaining ### 5.86/2.90 5.86/2.90 5.86/2.90 5.86/2.90 Eliminated locations (on linear paths): 5.86/2.90 5.86/2.90 Start location: evalspeedFails1start 5.86/2.90 5.86/2.90 16: evalspeedFails1start -> evalspeedFails1bb1in : A'=B, [], cost: 7 5.86/2.90 5.86/2.90 17: evalspeedFails1bb1in -> evalspeedFails1bb1in : A'=D+A, [ C>=A ], cost: 2 5.86/2.90 5.86/2.90 5.86/2.90 5.86/2.90 Accelerating simple loops of location 7. 5.86/2.90 5.86/2.90 Accelerating the following rules: 5.86/2.90 5.86/2.90 17: evalspeedFails1bb1in -> evalspeedFails1bb1in : A'=D+A, [ C>=A ], cost: 2 5.86/2.90 5.86/2.90 5.86/2.90 5.86/2.90 Found no metering function for rule 17. 5.86/2.90 5.86/2.90 Removing the simple loops:. 5.86/2.90 5.86/2.90 5.86/2.90 5.86/2.90 Accelerated all simple loops using metering functions (where possible): 5.86/2.90 5.86/2.90 Start location: evalspeedFails1start 5.86/2.90 5.86/2.90 16: evalspeedFails1start -> evalspeedFails1bb1in : A'=B, [], cost: 7 5.86/2.90 5.86/2.90 17: evalspeedFails1bb1in -> evalspeedFails1bb1in : A'=D+A, [ C>=A ], cost: 2 5.86/2.90 5.86/2.90 5.86/2.90 5.86/2.90 Chained accelerated rules (with incoming rules): 5.86/2.90 5.86/2.90 Start location: evalspeedFails1start 5.86/2.90 5.86/2.90 16: evalspeedFails1start -> evalspeedFails1bb1in : A'=B, [], cost: 7 5.86/2.90 5.86/2.90 18: evalspeedFails1start -> evalspeedFails1bb1in : A'=D+B, [ C>=B ], cost: 9 5.86/2.90 5.86/2.90 5.86/2.90 5.86/2.90 Removed unreachable locations (and leaf rules with constant cost): 5.86/2.90 5.86/2.90 Start location: evalspeedFails1start 5.86/2.90 5.86/2.90 5.86/2.90 5.86/2.90 ### Computing asymptotic complexity ### 5.86/2.90 5.86/2.90 5.86/2.90 5.86/2.90 Fully simplified ITS problem 5.86/2.90 5.86/2.90 Start location: evalspeedFails1start 5.86/2.90 5.86/2.90 5.86/2.90 5.86/2.90 Obtained the following overall complexity (w.r.t. the length of the input n): 5.86/2.90 5.86/2.90 Complexity: Unknown 5.86/2.90 5.86/2.90 Cpx degree: ? 5.86/2.90 5.86/2.90 Solved cost: 0 5.86/2.90 5.86/2.90 Rule cost: 0 5.86/2.90 5.86/2.90 Rule guard: [] 5.86/2.90 5.86/2.90 5.86/2.90 5.86/2.90 WORST_CASE(Omega(0),?) 5.86/2.90 5.86/2.90 5.86/2.90 ---------------------------------------- 5.86/2.90 5.86/2.90 (2) 5.86/2.90 BOUNDS(1, INF) 5.94/2.94 EOF