5.65/2.54 WORST_CASE(NON_POLY, ?) 5.65/2.54 proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat 5.65/2.54 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.65/2.54 5.65/2.54 5.65/2.54 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 5.65/2.54 5.65/2.54 (0) CpxIntTrs 5.65/2.54 (1) Loat Proof [FINISHED, 890 ms] 5.65/2.54 (2) BOUNDS(INF, INF) 5.65/2.54 5.65/2.54 5.65/2.54 ---------------------------------------- 5.65/2.54 5.65/2.54 (0) 5.65/2.54 Obligation: 5.65/2.54 Complexity Int TRS consisting of the following rules: 5.65/2.54 eval_catmouse_start(v_m, v_n, v_x_0) -> Com_1(eval_catmouse_bb0_in(v_m, v_n, v_x_0)) :|: TRUE 5.65/2.54 eval_catmouse_bb0_in(v_m, v_n, v_x_0) -> Com_1(eval_catmouse_0(v_m, v_n, v_x_0)) :|: TRUE 5.65/2.54 eval_catmouse_0(v_m, v_n, v_x_0) -> Com_1(eval_catmouse_1(v_m, v_n, v_x_0)) :|: TRUE 5.65/2.54 eval_catmouse_1(v_m, v_n, v_x_0) -> Com_1(eval_catmouse_2(v_m, v_n, v_x_0)) :|: TRUE 5.65/2.54 eval_catmouse_2(v_m, v_n, v_x_0) -> Com_1(eval_catmouse_3(v_m, v_n, v_x_0)) :|: TRUE 5.65/2.54 eval_catmouse_3(v_m, v_n, v_x_0) -> Com_1(eval_catmouse_4(v_m, v_n, v_x_0)) :|: TRUE 5.65/2.54 eval_catmouse_4(v_m, v_n, v_x_0) -> Com_1(eval_catmouse_5(v_m, v_n, v_x_0)) :|: TRUE 5.65/2.54 eval_catmouse_5(v_m, v_n, v_x_0) -> Com_1(eval_catmouse_bb1_in(v_m, v_n, 0)) :|: TRUE 5.65/2.54 eval_catmouse_bb1_in(v_m, v_n, v_x_0) -> Com_1(eval_catmouse_bb2_in(v_m, v_n, v_x_0)) :|: v_x_0 <= v_n 5.65/2.54 eval_catmouse_bb1_in(v_m, v_n, v_x_0) -> Com_1(eval_catmouse_bb3_in(v_m, v_n, v_x_0)) :|: v_x_0 > v_n 5.65/2.54 eval_catmouse_bb2_in(v_m, v_n, v_x_0) -> Com_1(eval_catmouse_bb1_in(v_m, v_n, v_x_0 + 1)) :|: v_x_0 <= v_m 5.65/2.54 eval_catmouse_bb2_in(v_m, v_n, v_x_0) -> Com_1(eval_catmouse_bb1_in(v_m, v_n, v_x_0 - 1)) :|: v_x_0 > v_m 5.65/2.54 eval_catmouse_bb3_in(v_m, v_n, v_x_0) -> Com_1(eval_catmouse_stop(v_m, v_n, v_x_0)) :|: TRUE 5.65/2.54 5.65/2.54 The start-symbols are:[eval_catmouse_start_3] 5.65/2.54 5.65/2.54 5.65/2.54 ---------------------------------------- 5.65/2.54 5.65/2.54 (1) Loat Proof (FINISHED) 5.65/2.54 5.65/2.54 5.65/2.54 ### Pre-processing the ITS problem ### 5.65/2.54 5.65/2.54 5.65/2.54 5.65/2.54 Initial linear ITS problem 5.65/2.54 5.65/2.54 Start location: evalcatmousestart 5.65/2.54 5.65/2.54 0: evalcatmousestart -> evalcatmousebb0in : [], cost: 1 5.65/2.54 5.65/2.54 1: evalcatmousebb0in -> evalcatmouse0 : [], cost: 1 5.65/2.54 5.65/2.54 2: evalcatmouse0 -> evalcatmouse1 : [], cost: 1 5.65/2.54 5.65/2.54 3: evalcatmouse1 -> evalcatmouse2 : [], cost: 1 5.65/2.55 5.65/2.55 4: evalcatmouse2 -> evalcatmouse3 : [], cost: 1 5.65/2.55 5.65/2.55 5: evalcatmouse3 -> evalcatmouse4 : [], cost: 1 5.65/2.55 5.65/2.55 6: evalcatmouse4 -> evalcatmouse5 : [], cost: 1 5.65/2.55 5.65/2.55 7: evalcatmouse5 -> evalcatmousebb1in : A'=0, [], cost: 1 5.65/2.55 5.65/2.55 8: evalcatmousebb1in -> evalcatmousebb2in : [ B>=A ], cost: 1 5.65/2.55 5.65/2.55 9: evalcatmousebb1in -> evalcatmousebb3in : [ A>=1+B ], cost: 1 5.65/2.55 5.65/2.55 10: evalcatmousebb2in -> evalcatmousebb1in : A'=1+A, [ C>=A ], cost: 1 5.65/2.55 5.65/2.55 11: evalcatmousebb2in -> evalcatmousebb1in : A'=-1+A, [ A>=1+C ], cost: 1 5.65/2.55 5.65/2.55 12: evalcatmousebb3in -> evalcatmousestop : [], cost: 1 5.65/2.55 5.65/2.55 5.65/2.55 5.65/2.55 Removed unreachable and leaf rules: 5.65/2.55 5.65/2.55 Start location: evalcatmousestart 5.65/2.55 5.65/2.55 0: evalcatmousestart -> evalcatmousebb0in : [], cost: 1 5.65/2.55 5.65/2.55 1: evalcatmousebb0in -> evalcatmouse0 : [], cost: 1 5.65/2.55 5.65/2.55 2: evalcatmouse0 -> evalcatmouse1 : [], cost: 1 5.65/2.55 5.65/2.55 3: evalcatmouse1 -> evalcatmouse2 : [], cost: 1 5.65/2.55 5.65/2.55 4: evalcatmouse2 -> evalcatmouse3 : [], cost: 1 5.65/2.55 5.65/2.55 5: evalcatmouse3 -> evalcatmouse4 : [], cost: 1 5.65/2.55 5.65/2.55 6: evalcatmouse4 -> evalcatmouse5 : [], cost: 1 5.65/2.55 5.65/2.55 7: evalcatmouse5 -> evalcatmousebb1in : A'=0, [], cost: 1 5.65/2.55 5.65/2.55 8: evalcatmousebb1in -> evalcatmousebb2in : [ B>=A ], cost: 1 5.65/2.55 5.65/2.55 10: evalcatmousebb2in -> evalcatmousebb1in : A'=1+A, [ C>=A ], cost: 1 5.65/2.55 5.65/2.55 11: evalcatmousebb2in -> evalcatmousebb1in : A'=-1+A, [ A>=1+C ], cost: 1 5.65/2.55 5.65/2.55 5.65/2.55 5.65/2.55 ### Simplification by acceleration and chaining ### 5.65/2.55 5.65/2.55 5.65/2.55 5.65/2.55 Eliminated locations (on linear paths): 5.65/2.55 5.65/2.55 Start location: evalcatmousestart 5.65/2.55 5.65/2.55 19: evalcatmousestart -> evalcatmousebb1in : A'=0, [], cost: 8 5.65/2.55 5.65/2.55 8: evalcatmousebb1in -> evalcatmousebb2in : [ B>=A ], cost: 1 5.65/2.55 5.65/2.55 10: evalcatmousebb2in -> evalcatmousebb1in : A'=1+A, [ C>=A ], cost: 1 5.65/2.55 5.65/2.55 11: evalcatmousebb2in -> evalcatmousebb1in : A'=-1+A, [ A>=1+C ], cost: 1 5.65/2.55 5.65/2.55 5.65/2.55 5.65/2.55 Eliminated locations (on tree-shaped paths): 5.65/2.55 5.65/2.55 Start location: evalcatmousestart 5.65/2.55 5.65/2.55 19: evalcatmousestart -> evalcatmousebb1in : A'=0, [], cost: 8 5.65/2.55 5.65/2.55 20: evalcatmousebb1in -> evalcatmousebb1in : A'=1+A, [ B>=A && C>=A ], cost: 2 5.65/2.55 5.65/2.55 21: evalcatmousebb1in -> evalcatmousebb1in : A'=-1+A, [ B>=A && A>=1+C ], cost: 2 5.65/2.55 5.65/2.55 5.65/2.55 5.65/2.55 Accelerating simple loops of location 8. 5.65/2.55 5.65/2.55 Accelerating the following rules: 5.65/2.55 5.65/2.55 20: evalcatmousebb1in -> evalcatmousebb1in : A'=1+A, [ B>=A && C>=A ], cost: 2 5.65/2.55 5.65/2.55 21: evalcatmousebb1in -> evalcatmousebb1in : A'=-1+A, [ B>=A && A>=1+C ], cost: 2 5.65/2.55 5.65/2.55 5.65/2.55 5.65/2.55 Accelerated rule 20 with backward acceleration, yielding the new rule 22. 5.65/2.55 5.65/2.55 Accelerated rule 20 with backward acceleration, yielding the new rule 23. 5.65/2.55 5.65/2.55 Accelerated rule 21 with metering function -C+A, yielding the new rule 24. 5.65/2.55 5.65/2.55 Nested simple loops 21 (outer loop) and 23 (inner loop) with NONTERM, resulting in the new rules: 25, 26. 5.65/2.55 5.65/2.55 Nested simple loops 20 (outer loop) and 24 (inner loop) with NONTERM, resulting in the new rules: 27, 28. 5.65/2.55 5.65/2.55 Removing the simple loops: 20 21. 5.65/2.55 5.65/2.55 5.65/2.55 5.65/2.55 Accelerated all simple loops using metering functions (where possible): 5.65/2.55 5.65/2.55 Start location: evalcatmousestart 5.65/2.55 5.65/2.55 19: evalcatmousestart -> evalcatmousebb1in : A'=0, [], cost: 8 5.65/2.55 5.65/2.55 22: evalcatmousebb1in -> evalcatmousebb1in : A'=1+B, [ B>=A && C>=A && C>=B ], cost: 2-2*A+2*B 5.65/2.55 5.65/2.55 23: evalcatmousebb1in -> evalcatmousebb1in : A'=1+C, [ B>=A && C>=A && B>=C ], cost: 2+2*C-2*A 5.65/2.55 5.65/2.55 24: evalcatmousebb1in -> evalcatmousebb1in : A'=C, [ B>=A && A>=1+C ], cost: -2*C+2*A 5.65/2.55 5.65/2.55 25: evalcatmousebb1in -> [12] : [ B>=A && C>=A && B>=1+C && 4+2*C-2*A>=1 ], cost: INF 5.65/2.55 5.65/2.55 26: evalcatmousebb1in -> [12] : A'=-1+A, [ B>=A && A>=1+C && C>=-1+A && B>=1+C && 6+2*C-2*A>=1 ], cost: INF 5.65/2.55 5.65/2.55 27: evalcatmousebb1in -> [12] : [ B>=A && A>=1+C && B>=C && 2-2*C+2*A>=1 ], cost: INF 5.65/2.55 5.65/2.55 28: evalcatmousebb1in -> [12] : A'=1+A, [ C>=A && B>=1+A && 1+A>=1+C && B>=C && 4-2*C+2*A>=1 ], cost: INF 5.65/2.55 5.65/2.55 5.65/2.55 5.65/2.55 Chained accelerated rules (with incoming rules): 5.65/2.55 5.65/2.55 Start location: evalcatmousestart 5.65/2.55 5.65/2.55 19: evalcatmousestart -> evalcatmousebb1in : A'=0, [], cost: 8 5.65/2.55 5.65/2.55 29: evalcatmousestart -> evalcatmousebb1in : A'=1+B, [ B>=0 && C>=0 && C>=B ], cost: 10+2*B 5.65/2.55 5.65/2.55 30: evalcatmousestart -> evalcatmousebb1in : A'=1+C, [ B>=0 && C>=0 && B>=C ], cost: 10+2*C 5.65/2.55 5.65/2.55 31: evalcatmousestart -> evalcatmousebb1in : A'=C, [ B>=0 && 0>=1+C ], cost: 8-2*C 5.65/2.55 5.65/2.55 32: evalcatmousestart -> [12] : A'=0, [ B>=0 && C>=0 && B>=1+C && 4+2*C>=1 ], cost: INF 5.65/2.55 5.65/2.55 33: evalcatmousestart -> [12] : A'=-1, [ B>=0 && 1+C==0 && B>=1+C && 6+2*C>=1 ], cost: INF 5.65/2.55 5.65/2.55 34: evalcatmousestart -> [12] : A'=0, [ B>=0 && 0>=1+C && B>=C && 2-2*C>=1 ], cost: INF 5.65/2.55 5.65/2.55 35: evalcatmousestart -> [12] : A'=1, [ -C==0 && B>=1 && B>=C && 4-2*C>=1 ], cost: INF 5.65/2.55 5.65/2.55 5.65/2.55 5.65/2.55 Removed unreachable locations (and leaf rules with constant cost): 5.65/2.55 5.65/2.55 Start location: evalcatmousestart 5.65/2.55 5.65/2.55 29: evalcatmousestart -> evalcatmousebb1in : A'=1+B, [ B>=0 && C>=0 && C>=B ], cost: 10+2*B 5.65/2.55 5.65/2.55 30: evalcatmousestart -> evalcatmousebb1in : A'=1+C, [ B>=0 && C>=0 && B>=C ], cost: 10+2*C 5.65/2.55 5.65/2.55 31: evalcatmousestart -> evalcatmousebb1in : A'=C, [ B>=0 && 0>=1+C ], cost: 8-2*C 5.65/2.55 5.65/2.55 32: evalcatmousestart -> [12] : A'=0, [ B>=0 && C>=0 && B>=1+C && 4+2*C>=1 ], cost: INF 5.65/2.55 5.65/2.55 33: evalcatmousestart -> [12] : A'=-1, [ B>=0 && 1+C==0 && B>=1+C && 6+2*C>=1 ], cost: INF 5.65/2.55 5.65/2.55 34: evalcatmousestart -> [12] : A'=0, [ B>=0 && 0>=1+C && B>=C && 2-2*C>=1 ], cost: INF 5.65/2.55 5.65/2.55 35: evalcatmousestart -> [12] : A'=1, [ -C==0 && B>=1 && B>=C && 4-2*C>=1 ], cost: INF 5.65/2.55 5.65/2.55 5.65/2.55 5.65/2.55 ### Computing asymptotic complexity ### 5.65/2.55 5.65/2.55 5.65/2.55 5.65/2.55 Fully simplified ITS problem 5.65/2.55 5.65/2.55 Start location: evalcatmousestart 5.65/2.55 5.65/2.55 29: evalcatmousestart -> evalcatmousebb1in : A'=1+B, [ B>=0 && C>=0 && C>=B ], cost: 10+2*B 5.65/2.55 5.65/2.55 30: evalcatmousestart -> evalcatmousebb1in : A'=1+C, [ B>=0 && C>=0 && B>=C ], cost: 10+2*C 5.65/2.55 5.65/2.55 31: evalcatmousestart -> evalcatmousebb1in : A'=C, [ B>=0 && 0>=1+C ], cost: 8-2*C 5.65/2.55 5.65/2.55 32: evalcatmousestart -> [12] : A'=0, [ B>=0 && C>=0 && B>=1+C && 4+2*C>=1 ], cost: INF 5.65/2.55 5.65/2.55 33: evalcatmousestart -> [12] : A'=-1, [ B>=0 && 1+C==0 && B>=1+C && 6+2*C>=1 ], cost: INF 5.65/2.55 5.65/2.55 34: evalcatmousestart -> [12] : A'=0, [ B>=0 && 0>=1+C && B>=C && 2-2*C>=1 ], cost: INF 5.65/2.55 5.65/2.55 35: evalcatmousestart -> [12] : A'=1, [ -C==0 && B>=1 && B>=C && 4-2*C>=1 ], cost: INF 5.65/2.55 5.65/2.55 5.65/2.55 5.65/2.55 Computing asymptotic complexity for rule 29 5.65/2.55 5.65/2.55 Solved the limit problem by the following transformations: 5.65/2.55 5.65/2.55 Created initial limit problem: 5.65/2.55 5.65/2.55 1+C (+/+!), 1+B (+/+!), 1+C-B (+/+!), 10+2*B (+) [not solved] 5.65/2.55 5.65/2.55 5.65/2.55 5.65/2.55 removing all constraints (solved by SMT) 5.65/2.55 5.65/2.55 resulting limit problem: [solved] 5.65/2.55 5.65/2.55 5.65/2.55 5.65/2.55 applying transformation rule (C) using substitution {C==n,B==n} 5.65/2.55 5.65/2.55 resulting limit problem: 5.65/2.55 5.65/2.55 [solved] 5.65/2.55 5.65/2.55 5.65/2.55 5.65/2.55 Solution: 5.65/2.55 5.65/2.55 C / n 5.65/2.55 5.65/2.55 B / n 5.65/2.55 5.65/2.55 Resulting cost 10+2*n has complexity: Poly(n^1) 5.65/2.55 5.65/2.55 5.65/2.55 5.65/2.55 Found new complexity Poly(n^1). 5.65/2.55 5.65/2.55 5.65/2.55 5.65/2.55 Computing asymptotic complexity for rule 32 5.65/2.55 5.65/2.55 Simplified the guard: 5.65/2.55 5.65/2.55 32: evalcatmousestart -> [12] : A'=0, [ C>=0 && B>=1+C ], cost: INF 5.65/2.55 5.65/2.55 Resulting cost INF has complexity: Nonterm 5.65/2.55 5.65/2.55 5.65/2.55 5.65/2.55 Found new complexity Nonterm. 5.65/2.55 5.65/2.55 5.65/2.55 5.65/2.55 Obtained the following overall complexity (w.r.t. the length of the input n): 5.65/2.55 5.65/2.55 Complexity: Nonterm 5.65/2.55 5.65/2.55 Cpx degree: Nonterm 5.65/2.55 5.65/2.55 Solved cost: INF 5.65/2.55 5.65/2.55 Rule cost: INF 5.65/2.55 5.65/2.55 Rule guard: [ C>=0 && B>=1+C ] 5.65/2.55 5.65/2.55 5.65/2.55 5.65/2.55 NO 5.65/2.55 5.65/2.55 5.65/2.55 ---------------------------------------- 5.65/2.55 5.65/2.55 (2) 5.65/2.55 BOUNDS(INF, INF) 5.65/2.57 EOF