8.05/3.22 WORST_CASE(NON_POLY, ?) 8.36/3.23 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 8.36/3.23 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.36/3.23 8.36/3.23 8.36/3.23 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 8.36/3.23 8.36/3.23 (0) CpxIntTrs 8.36/3.23 (1) Loat Proof [FINISHED, 1531 ms] 8.36/3.23 (2) BOUNDS(INF, INF) 8.36/3.23 8.36/3.23 8.36/3.23 ---------------------------------------- 8.36/3.23 8.36/3.23 (0) 8.36/3.23 Obligation: 8.36/3.23 Complexity Int TRS consisting of the following rules: 8.36/3.23 eval_real2_start(v_again_0, v_again_1, v_again_2, v_i_0, v_len) -> Com_1(eval_real2_bb0_in(v_again_0, v_again_1, v_again_2, v_i_0, v_len)) :|: TRUE 8.36/3.23 eval_real2_bb0_in(v_again_0, v_again_1, v_again_2, v_i_0, v_len) -> Com_1(eval_real2_0(v_again_0, v_again_1, v_again_2, v_i_0, v_len)) :|: TRUE 8.36/3.23 eval_real2_0(v_again_0, v_again_1, v_again_2, v_i_0, v_len) -> Com_1(eval_real2_1(v_again_0, v_again_1, v_again_2, v_i_0, v_len)) :|: TRUE 8.36/3.23 eval_real2_1(v_again_0, v_again_1, v_again_2, v_i_0, v_len) -> Com_1(eval_real2_2(v_again_0, v_again_1, v_again_2, v_i_0, v_len)) :|: TRUE 8.36/3.23 eval_real2_2(v_again_0, v_again_1, v_again_2, v_i_0, v_len) -> Com_1(eval_real2_3(v_again_0, v_again_1, v_again_2, v_i_0, v_len)) :|: TRUE 8.36/3.23 eval_real2_3(v_again_0, v_again_1, v_again_2, v_i_0, v_len) -> Com_1(eval_real2_4(v_again_0, v_again_1, v_again_2, v_i_0, v_len)) :|: TRUE 8.36/3.23 eval_real2_4(v_again_0, v_again_1, v_again_2, v_i_0, v_len) -> Com_1(eval_real2_5(v_again_0, v_again_1, v_again_2, v_i_0, v_len)) :|: TRUE 8.36/3.23 eval_real2_5(v_again_0, v_again_1, v_again_2, v_i_0, v_len) -> Com_1(eval_real2_6(v_again_0, v_again_1, v_again_2, v_i_0, v_len)) :|: TRUE 8.36/3.23 eval_real2_6(v_again_0, v_again_1, v_again_2, v_i_0, v_len) -> Com_1(eval_real2_7(v_again_0, v_again_1, v_again_2, v_i_0, v_len)) :|: TRUE 8.36/3.23 eval_real2_7(v_again_0, v_again_1, v_again_2, v_i_0, v_len) -> Com_1(eval_real2_8(v_again_0, v_again_1, v_again_2, v_i_0, v_len)) :|: TRUE 8.36/3.23 eval_real2_8(v_again_0, v_again_1, v_again_2, v_i_0, v_len) -> Com_1(eval_real2_bb1_in(1, v_again_1, v_again_2, v_i_0, v_len)) :|: TRUE 8.36/3.23 eval_real2_bb1_in(v_again_0, v_again_1, v_again_2, v_i_0, v_len) -> Com_1(eval_real2_bb2_in(v_again_0, 0, v_again_2, 0, v_len)) :|: v_again_0 < 0 8.36/3.23 eval_real2_bb1_in(v_again_0, v_again_1, v_again_2, v_i_0, v_len) -> Com_1(eval_real2_bb2_in(v_again_0, 0, v_again_2, 0, v_len)) :|: v_again_0 > 0 8.36/3.23 eval_real2_bb1_in(v_again_0, v_again_1, v_again_2, v_i_0, v_len) -> Com_1(eval_real2_bb6_in(v_again_0, v_again_1, v_again_2, v_i_0, v_len)) :|: v_again_0 >= 0 && v_again_0 <= 0 8.36/3.23 eval_real2_bb2_in(v_again_0, v_again_1, v_again_2, v_i_0, v_len) -> Com_1(eval_real2_bb3_in(v_again_0, v_again_1, v_again_2, v_i_0, v_len)) :|: v_i_0 < v_len - 1 8.36/3.23 eval_real2_bb2_in(v_again_0, v_again_1, v_again_2, v_i_0, v_len) -> Com_1(eval_real2_bb1_in(v_again_1, v_again_1, v_again_2, v_i_0, v_len)) :|: v_i_0 >= v_len - 1 8.36/3.23 eval_real2_bb3_in(v_again_0, v_again_1, v_again_2, v_i_0, v_len) -> Com_1(eval_real2_bb4_in(v_again_0, v_again_1, v_again_2, v_i_0, v_len)) :|: nondef_0 > nondef_1 8.36/3.23 eval_real2_bb3_in(v_again_0, v_again_1, v_again_2, v_i_0, v_len) -> Com_1(eval_real2_bb5_in(v_again_0, v_again_1, v_again_1, v_i_0, v_len)) :|: nondef_0 <= nondef_1 8.36/3.23 eval_real2_bb4_in(v_again_0, v_again_1, v_again_2, v_i_0, v_len) -> Com_1(eval_real2_bb5_in(v_again_0, v_again_1, 1, v_i_0, v_len)) :|: TRUE 8.36/3.23 eval_real2_bb5_in(v_again_0, v_again_1, v_again_2, v_i_0, v_len) -> Com_1(eval_real2_bb2_in(v_again_0, v_again_2, v_again_2, v_i_0 + 1, v_len)) :|: TRUE 8.36/3.23 eval_real2_bb6_in(v_again_0, v_again_1, v_again_2, v_i_0, v_len) -> Com_1(eval_real2_stop(v_again_0, v_again_1, v_again_2, v_i_0, v_len)) :|: TRUE 8.36/3.23 8.36/3.23 The start-symbols are:[eval_real2_start_5] 8.36/3.23 8.36/3.23 8.36/3.23 ---------------------------------------- 8.36/3.23 8.36/3.23 (1) Loat Proof (FINISHED) 8.36/3.23 8.36/3.23 8.36/3.23 ### Pre-processing the ITS problem ### 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 Initial linear ITS problem 8.36/3.23 8.36/3.23 Start location: evalreal2start 8.36/3.23 8.36/3.23 0: evalreal2start -> evalreal2bb0in : [], cost: 1 8.36/3.23 8.36/3.23 1: evalreal2bb0in -> evalreal20 : [], cost: 1 8.36/3.23 8.36/3.23 2: evalreal20 -> evalreal21 : [], cost: 1 8.36/3.23 8.36/3.23 3: evalreal21 -> evalreal22 : [], cost: 1 8.36/3.23 8.36/3.23 4: evalreal22 -> evalreal23 : [], cost: 1 8.36/3.23 8.36/3.23 5: evalreal23 -> evalreal24 : [], cost: 1 8.36/3.23 8.36/3.23 6: evalreal24 -> evalreal25 : [], cost: 1 8.36/3.23 8.36/3.23 7: evalreal25 -> evalreal26 : [], cost: 1 8.36/3.23 8.36/3.23 8: evalreal26 -> evalreal27 : [], cost: 1 8.36/3.23 8.36/3.23 9: evalreal27 -> evalreal28 : [], cost: 1 8.36/3.23 8.36/3.23 10: evalreal28 -> evalreal2bb1in : A'=1, [], cost: 1 8.36/3.23 8.36/3.23 11: evalreal2bb1in -> evalreal2bb2in : B'=0, C'=0, [ 0>=1+A ], cost: 1 8.36/3.23 8.36/3.23 12: evalreal2bb1in -> evalreal2bb2in : B'=0, C'=0, [ A>=1 ], cost: 1 8.36/3.23 8.36/3.23 13: evalreal2bb1in -> evalreal2bb6in : [ A==0 ], cost: 1 8.36/3.23 8.36/3.23 14: evalreal2bb2in -> evalreal2bb3in : [ D>=2+C ], cost: 1 8.36/3.23 8.36/3.23 15: evalreal2bb2in -> evalreal2bb1in : A'=B, [ 1+C>=D ], cost: 1 8.36/3.23 8.36/3.23 16: evalreal2bb3in -> evalreal2bb4in : [ free>=1+free_1 ], cost: 1 8.36/3.23 8.36/3.23 17: evalreal2bb3in -> evalreal2bb5in : E'=B, [ free_3>=free_2 ], cost: 1 8.36/3.23 8.36/3.23 18: evalreal2bb4in -> evalreal2bb5in : E'=1, [], cost: 1 8.36/3.23 8.36/3.23 19: evalreal2bb5in -> evalreal2bb2in : B'=E, C'=1+C, [], cost: 1 8.36/3.23 8.36/3.23 20: evalreal2bb6in -> evalreal2stop : [], cost: 1 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 Removed unreachable and leaf rules: 8.36/3.23 8.36/3.23 Start location: evalreal2start 8.36/3.23 8.36/3.23 0: evalreal2start -> evalreal2bb0in : [], cost: 1 8.36/3.23 8.36/3.23 1: evalreal2bb0in -> evalreal20 : [], cost: 1 8.36/3.23 8.36/3.23 2: evalreal20 -> evalreal21 : [], cost: 1 8.36/3.23 8.36/3.23 3: evalreal21 -> evalreal22 : [], cost: 1 8.36/3.23 8.36/3.23 4: evalreal22 -> evalreal23 : [], cost: 1 8.36/3.23 8.36/3.23 5: evalreal23 -> evalreal24 : [], cost: 1 8.36/3.23 8.36/3.23 6: evalreal24 -> evalreal25 : [], cost: 1 8.36/3.23 8.36/3.23 7: evalreal25 -> evalreal26 : [], cost: 1 8.36/3.23 8.36/3.23 8: evalreal26 -> evalreal27 : [], cost: 1 8.36/3.23 8.36/3.23 9: evalreal27 -> evalreal28 : [], cost: 1 8.36/3.23 8.36/3.23 10: evalreal28 -> evalreal2bb1in : A'=1, [], cost: 1 8.36/3.23 8.36/3.23 11: evalreal2bb1in -> evalreal2bb2in : B'=0, C'=0, [ 0>=1+A ], cost: 1 8.36/3.23 8.36/3.23 12: evalreal2bb1in -> evalreal2bb2in : B'=0, C'=0, [ A>=1 ], cost: 1 8.36/3.23 8.36/3.23 14: evalreal2bb2in -> evalreal2bb3in : [ D>=2+C ], cost: 1 8.36/3.23 8.36/3.23 15: evalreal2bb2in -> evalreal2bb1in : A'=B, [ 1+C>=D ], cost: 1 8.36/3.23 8.36/3.23 16: evalreal2bb3in -> evalreal2bb4in : [ free>=1+free_1 ], cost: 1 8.36/3.23 8.36/3.23 17: evalreal2bb3in -> evalreal2bb5in : E'=B, [ free_3>=free_2 ], cost: 1 8.36/3.23 8.36/3.23 18: evalreal2bb4in -> evalreal2bb5in : E'=1, [], cost: 1 8.36/3.23 8.36/3.23 19: evalreal2bb5in -> evalreal2bb2in : B'=E, C'=1+C, [], cost: 1 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 Simplified all rules, resulting in: 8.36/3.23 8.36/3.23 Start location: evalreal2start 8.36/3.23 8.36/3.23 0: evalreal2start -> evalreal2bb0in : [], cost: 1 8.36/3.23 8.36/3.23 1: evalreal2bb0in -> evalreal20 : [], cost: 1 8.36/3.23 8.36/3.23 2: evalreal20 -> evalreal21 : [], cost: 1 8.36/3.23 8.36/3.23 3: evalreal21 -> evalreal22 : [], cost: 1 8.36/3.23 8.36/3.23 4: evalreal22 -> evalreal23 : [], cost: 1 8.36/3.23 8.36/3.23 5: evalreal23 -> evalreal24 : [], cost: 1 8.36/3.23 8.36/3.23 6: evalreal24 -> evalreal25 : [], cost: 1 8.36/3.23 8.36/3.23 7: evalreal25 -> evalreal26 : [], cost: 1 8.36/3.23 8.36/3.23 8: evalreal26 -> evalreal27 : [], cost: 1 8.36/3.23 8.36/3.23 9: evalreal27 -> evalreal28 : [], cost: 1 8.36/3.23 8.36/3.23 10: evalreal28 -> evalreal2bb1in : A'=1, [], cost: 1 8.36/3.23 8.36/3.23 11: evalreal2bb1in -> evalreal2bb2in : B'=0, C'=0, [ 0>=1+A ], cost: 1 8.36/3.23 8.36/3.23 12: evalreal2bb1in -> evalreal2bb2in : B'=0, C'=0, [ A>=1 ], cost: 1 8.36/3.23 8.36/3.23 14: evalreal2bb2in -> evalreal2bb3in : [ D>=2+C ], cost: 1 8.36/3.23 8.36/3.23 15: evalreal2bb2in -> evalreal2bb1in : A'=B, [ 1+C>=D ], cost: 1 8.36/3.23 8.36/3.23 16: evalreal2bb3in -> evalreal2bb4in : [], cost: 1 8.36/3.23 8.36/3.23 17: evalreal2bb3in -> evalreal2bb5in : E'=B, [], cost: 1 8.36/3.23 8.36/3.23 18: evalreal2bb4in -> evalreal2bb5in : E'=1, [], cost: 1 8.36/3.23 8.36/3.23 19: evalreal2bb5in -> evalreal2bb2in : B'=E, C'=1+C, [], cost: 1 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 ### Simplification by acceleration and chaining ### 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 Eliminated locations (on linear paths): 8.36/3.23 8.36/3.23 Start location: evalreal2start 8.36/3.23 8.36/3.23 30: evalreal2start -> evalreal2bb1in : A'=1, [], cost: 11 8.36/3.23 8.36/3.23 11: evalreal2bb1in -> evalreal2bb2in : B'=0, C'=0, [ 0>=1+A ], cost: 1 8.36/3.23 8.36/3.23 12: evalreal2bb1in -> evalreal2bb2in : B'=0, C'=0, [ A>=1 ], cost: 1 8.36/3.23 8.36/3.23 14: evalreal2bb2in -> evalreal2bb3in : [ D>=2+C ], cost: 1 8.36/3.23 8.36/3.23 15: evalreal2bb2in -> evalreal2bb1in : A'=B, [ 1+C>=D ], cost: 1 8.36/3.23 8.36/3.23 17: evalreal2bb3in -> evalreal2bb5in : E'=B, [], cost: 1 8.36/3.23 8.36/3.23 31: evalreal2bb3in -> evalreal2bb5in : E'=1, [], cost: 2 8.36/3.23 8.36/3.23 19: evalreal2bb5in -> evalreal2bb2in : B'=E, C'=1+C, [], cost: 1 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 Eliminated locations (on tree-shaped paths): 8.36/3.23 8.36/3.23 Start location: evalreal2start 8.36/3.23 8.36/3.23 30: evalreal2start -> evalreal2bb1in : A'=1, [], cost: 11 8.36/3.23 8.36/3.23 11: evalreal2bb1in -> evalreal2bb2in : B'=0, C'=0, [ 0>=1+A ], cost: 1 8.36/3.23 8.36/3.23 12: evalreal2bb1in -> evalreal2bb2in : B'=0, C'=0, [ A>=1 ], cost: 1 8.36/3.23 8.36/3.23 15: evalreal2bb2in -> evalreal2bb1in : A'=B, [ 1+C>=D ], cost: 1 8.36/3.23 8.36/3.23 32: evalreal2bb2in -> evalreal2bb5in : E'=B, [ D>=2+C ], cost: 2 8.36/3.23 8.36/3.23 33: evalreal2bb2in -> evalreal2bb5in : E'=1, [ D>=2+C ], cost: 3 8.36/3.23 8.36/3.23 19: evalreal2bb5in -> evalreal2bb2in : B'=E, C'=1+C, [], cost: 1 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 Eliminated locations (on tree-shaped paths): 8.36/3.23 8.36/3.23 Start location: evalreal2start 8.36/3.23 8.36/3.23 30: evalreal2start -> evalreal2bb1in : A'=1, [], cost: 11 8.36/3.23 8.36/3.23 11: evalreal2bb1in -> evalreal2bb2in : B'=0, C'=0, [ 0>=1+A ], cost: 1 8.36/3.23 8.36/3.23 12: evalreal2bb1in -> evalreal2bb2in : B'=0, C'=0, [ A>=1 ], cost: 1 8.36/3.23 8.36/3.23 15: evalreal2bb2in -> evalreal2bb1in : A'=B, [ 1+C>=D ], cost: 1 8.36/3.23 8.36/3.23 34: evalreal2bb2in -> evalreal2bb2in : B'=B, C'=1+C, E'=B, [ D>=2+C ], cost: 3 8.36/3.23 8.36/3.23 35: evalreal2bb2in -> evalreal2bb2in : B'=1, C'=1+C, E'=1, [ D>=2+C ], cost: 4 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 Accelerating simple loops of location 12. 8.36/3.23 8.36/3.23 Simplified some of the simple loops (and removed duplicate rules). 8.36/3.23 8.36/3.23 Accelerating the following rules: 8.36/3.23 8.36/3.23 34: evalreal2bb2in -> evalreal2bb2in : C'=1+C, E'=B, [ D>=2+C ], cost: 3 8.36/3.23 8.36/3.23 35: evalreal2bb2in -> evalreal2bb2in : B'=1, C'=1+C, E'=1, [ D>=2+C ], cost: 4 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 Accelerated rule 34 with metering function -1-C+D, yielding the new rule 36. 8.36/3.23 8.36/3.23 Accelerated rule 35 with metering function -1-C+D, yielding the new rule 37. 8.36/3.23 8.36/3.23 Removing the simple loops: 34 35. 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 Accelerated all simple loops using metering functions (where possible): 8.36/3.23 8.36/3.23 Start location: evalreal2start 8.36/3.23 8.36/3.23 30: evalreal2start -> evalreal2bb1in : A'=1, [], cost: 11 8.36/3.23 8.36/3.23 11: evalreal2bb1in -> evalreal2bb2in : B'=0, C'=0, [ 0>=1+A ], cost: 1 8.36/3.23 8.36/3.23 12: evalreal2bb1in -> evalreal2bb2in : B'=0, C'=0, [ A>=1 ], cost: 1 8.36/3.23 8.36/3.23 15: evalreal2bb2in -> evalreal2bb1in : A'=B, [ 1+C>=D ], cost: 1 8.36/3.23 8.36/3.23 36: evalreal2bb2in -> evalreal2bb2in : C'=-1+D, E'=B, [ D>=2+C ], cost: -3-3*C+3*D 8.36/3.23 8.36/3.23 37: evalreal2bb2in -> evalreal2bb2in : B'=1, C'=-1+D, E'=1, [ D>=2+C ], cost: -4-4*C+4*D 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 Chained accelerated rules (with incoming rules): 8.36/3.23 8.36/3.23 Start location: evalreal2start 8.36/3.23 8.36/3.23 30: evalreal2start -> evalreal2bb1in : A'=1, [], cost: 11 8.36/3.23 8.36/3.23 11: evalreal2bb1in -> evalreal2bb2in : B'=0, C'=0, [ 0>=1+A ], cost: 1 8.36/3.23 8.36/3.23 12: evalreal2bb1in -> evalreal2bb2in : B'=0, C'=0, [ A>=1 ], cost: 1 8.36/3.23 8.36/3.23 38: evalreal2bb1in -> evalreal2bb2in : B'=0, C'=-1+D, E'=0, [ 0>=1+A && D>=2 ], cost: -2+3*D 8.36/3.23 8.36/3.23 39: evalreal2bb1in -> evalreal2bb2in : B'=0, C'=-1+D, E'=0, [ A>=1 && D>=2 ], cost: -2+3*D 8.36/3.23 8.36/3.23 40: evalreal2bb1in -> evalreal2bb2in : B'=1, C'=-1+D, E'=1, [ 0>=1+A && D>=2 ], cost: -3+4*D 8.36/3.23 8.36/3.23 41: evalreal2bb1in -> evalreal2bb2in : B'=1, C'=-1+D, E'=1, [ A>=1 && D>=2 ], cost: -3+4*D 8.36/3.23 8.36/3.23 15: evalreal2bb2in -> evalreal2bb1in : A'=B, [ 1+C>=D ], cost: 1 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 Eliminated locations (on tree-shaped paths): 8.36/3.23 8.36/3.23 Start location: evalreal2start 8.36/3.23 8.36/3.23 30: evalreal2start -> evalreal2bb1in : A'=1, [], cost: 11 8.36/3.23 8.36/3.23 42: evalreal2bb1in -> evalreal2bb1in : A'=0, B'=0, C'=0, [ 0>=1+A && 1>=D ], cost: 2 8.36/3.23 8.36/3.23 43: evalreal2bb1in -> evalreal2bb1in : A'=0, B'=0, C'=0, [ A>=1 && 1>=D ], cost: 2 8.36/3.23 8.36/3.23 44: evalreal2bb1in -> evalreal2bb1in : A'=0, B'=0, C'=-1+D, E'=0, [ 0>=1+A && D>=2 ], cost: -1+3*D 8.36/3.23 8.36/3.23 45: evalreal2bb1in -> evalreal2bb1in : A'=0, B'=0, C'=-1+D, E'=0, [ A>=1 && D>=2 ], cost: -1+3*D 8.36/3.23 8.36/3.23 46: evalreal2bb1in -> evalreal2bb1in : A'=1, B'=1, C'=-1+D, E'=1, [ 0>=1+A && D>=2 ], cost: -2+4*D 8.36/3.23 8.36/3.23 47: evalreal2bb1in -> evalreal2bb1in : A'=1, B'=1, C'=-1+D, E'=1, [ A>=1 && D>=2 ], cost: -2+4*D 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 Applied pruning (of leafs and parallel rules): 8.36/3.23 8.36/3.23 Start location: evalreal2start 8.36/3.23 8.36/3.23 30: evalreal2start -> evalreal2bb1in : A'=1, [], cost: 11 8.36/3.23 8.36/3.23 42: evalreal2bb1in -> evalreal2bb1in : A'=0, B'=0, C'=0, [ 0>=1+A && 1>=D ], cost: 2 8.36/3.23 8.36/3.23 44: evalreal2bb1in -> evalreal2bb1in : A'=0, B'=0, C'=-1+D, E'=0, [ 0>=1+A && D>=2 ], cost: -1+3*D 8.36/3.23 8.36/3.23 45: evalreal2bb1in -> evalreal2bb1in : A'=0, B'=0, C'=-1+D, E'=0, [ A>=1 && D>=2 ], cost: -1+3*D 8.36/3.23 8.36/3.23 46: evalreal2bb1in -> evalreal2bb1in : A'=1, B'=1, C'=-1+D, E'=1, [ 0>=1+A && D>=2 ], cost: -2+4*D 8.36/3.23 8.36/3.23 47: evalreal2bb1in -> evalreal2bb1in : A'=1, B'=1, C'=-1+D, E'=1, [ A>=1 && D>=2 ], cost: -2+4*D 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 Accelerating simple loops of location 11. 8.36/3.23 8.36/3.23 Accelerating the following rules: 8.36/3.23 8.36/3.23 42: evalreal2bb1in -> evalreal2bb1in : A'=0, B'=0, C'=0, [ 0>=1+A && 1>=D ], cost: 2 8.36/3.23 8.36/3.23 44: evalreal2bb1in -> evalreal2bb1in : A'=0, B'=0, C'=-1+D, E'=0, [ 0>=1+A && D>=2 ], cost: -1+3*D 8.36/3.23 8.36/3.23 45: evalreal2bb1in -> evalreal2bb1in : A'=0, B'=0, C'=-1+D, E'=0, [ A>=1 && D>=2 ], cost: -1+3*D 8.36/3.23 8.36/3.23 46: evalreal2bb1in -> evalreal2bb1in : A'=1, B'=1, C'=-1+D, E'=1, [ 0>=1+A && D>=2 ], cost: -2+4*D 8.36/3.23 8.36/3.23 47: evalreal2bb1in -> evalreal2bb1in : A'=1, B'=1, C'=-1+D, E'=1, [ A>=1 && D>=2 ], cost: -2+4*D 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 Found no metering function for rule 42. 8.36/3.23 8.36/3.23 Found no metering function for rule 44. 8.36/3.23 8.36/3.23 Found no metering function for rule 45. 8.36/3.23 8.36/3.23 Found no metering function for rule 46. 8.36/3.23 8.36/3.23 Accelerated rule 47 with NONTERM, yielding the new rule 48. 8.36/3.23 8.36/3.23 Removing the simple loops: 47. 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 Accelerated all simple loops using metering functions (where possible): 8.36/3.23 8.36/3.23 Start location: evalreal2start 8.36/3.23 8.36/3.23 30: evalreal2start -> evalreal2bb1in : A'=1, [], cost: 11 8.36/3.23 8.36/3.23 42: evalreal2bb1in -> evalreal2bb1in : A'=0, B'=0, C'=0, [ 0>=1+A && 1>=D ], cost: 2 8.36/3.23 8.36/3.23 44: evalreal2bb1in -> evalreal2bb1in : A'=0, B'=0, C'=-1+D, E'=0, [ 0>=1+A && D>=2 ], cost: -1+3*D 8.36/3.23 8.36/3.23 45: evalreal2bb1in -> evalreal2bb1in : A'=0, B'=0, C'=-1+D, E'=0, [ A>=1 && D>=2 ], cost: -1+3*D 8.36/3.23 8.36/3.23 46: evalreal2bb1in -> evalreal2bb1in : A'=1, B'=1, C'=-1+D, E'=1, [ 0>=1+A && D>=2 ], cost: -2+4*D 8.36/3.23 8.36/3.23 48: evalreal2bb1in -> [19] : [ A>=1 && D>=2 && -2+4*D>=1 ], cost: INF 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 Chained accelerated rules (with incoming rules): 8.36/3.23 8.36/3.23 Start location: evalreal2start 8.36/3.23 8.36/3.23 30: evalreal2start -> evalreal2bb1in : A'=1, [], cost: 11 8.36/3.23 8.36/3.23 49: evalreal2start -> evalreal2bb1in : A'=0, B'=0, C'=-1+D, E'=0, [ D>=2 ], cost: 10+3*D 8.36/3.23 8.36/3.23 50: evalreal2start -> [19] : A'=1, [ D>=2 && -2+4*D>=1 ], cost: INF 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 Removed unreachable locations (and leaf rules with constant cost): 8.36/3.23 8.36/3.23 Start location: evalreal2start 8.36/3.23 8.36/3.23 49: evalreal2start -> evalreal2bb1in : A'=0, B'=0, C'=-1+D, E'=0, [ D>=2 ], cost: 10+3*D 8.36/3.23 8.36/3.23 50: evalreal2start -> [19] : A'=1, [ D>=2 && -2+4*D>=1 ], cost: INF 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 ### Computing asymptotic complexity ### 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 Fully simplified ITS problem 8.36/3.23 8.36/3.23 Start location: evalreal2start 8.36/3.23 8.36/3.23 49: evalreal2start -> evalreal2bb1in : A'=0, B'=0, C'=-1+D, E'=0, [ D>=2 ], cost: 10+3*D 8.36/3.23 8.36/3.23 50: evalreal2start -> [19] : A'=1, [ D>=2 && -2+4*D>=1 ], cost: INF 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 Computing asymptotic complexity for rule 49 8.36/3.23 8.36/3.23 Solved the limit problem by the following transformations: 8.36/3.23 8.36/3.23 Created initial limit problem: 8.36/3.23 8.36/3.23 10+3*D (+), -1+D (+/+!) [not solved] 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 removing all constraints (solved by SMT) 8.36/3.23 8.36/3.23 resulting limit problem: [solved] 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 applying transformation rule (C) using substitution {D==n} 8.36/3.23 8.36/3.23 resulting limit problem: 8.36/3.23 8.36/3.23 [solved] 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 Solution: 8.36/3.23 8.36/3.23 D / n 8.36/3.23 8.36/3.23 Resulting cost 10+3*n has complexity: Poly(n^1) 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 Found new complexity Poly(n^1). 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 Computing asymptotic complexity for rule 50 8.36/3.23 8.36/3.23 Resulting cost INF has complexity: Nonterm 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 Found new complexity Nonterm. 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 Obtained the following overall complexity (w.r.t. the length of the input n): 8.36/3.23 8.36/3.23 Complexity: Nonterm 8.36/3.23 8.36/3.23 Cpx degree: Nonterm 8.36/3.23 8.36/3.23 Solved cost: INF 8.36/3.23 8.36/3.23 Rule cost: INF 8.36/3.23 8.36/3.23 Rule guard: [ D>=2 ] 8.36/3.23 8.36/3.23 8.36/3.23 8.36/3.23 NO 8.36/3.23 8.36/3.23 8.36/3.23 ---------------------------------------- 8.36/3.23 8.36/3.23 (2) 8.36/3.23 BOUNDS(INF, INF) 8.36/3.26 EOF