5.70/2.35 WORST_CASE(NON_POLY, ?) 5.70/2.36 proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat 5.70/2.36 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.70/2.36 5.70/2.36 5.70/2.36 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 5.70/2.36 5.70/2.36 (0) CpxIntTrs 5.70/2.36 (1) Loat Proof [FINISHED, 709 ms] 5.70/2.36 (2) BOUNDS(INF, INF) 5.70/2.36 5.70/2.36 5.70/2.36 ---------------------------------------- 5.70/2.36 5.70/2.36 (0) 5.70/2.36 Obligation: 5.70/2.36 Complexity Int TRS consisting of the following rules: 5.70/2.36 evalEx5start(A, B, C, D, E) -> Com_1(evalEx5entryin(A, B, C, D, E)) :|: TRUE 5.70/2.36 evalEx5entryin(A, B, C, D, E) -> Com_1(evalEx5bb6in(0, A, C, D, E)) :|: TRUE 5.70/2.36 evalEx5bb6in(A, B, C, D, E) -> Com_1(evalEx5bb3in(A, B, 0, B, E)) :|: B >= A + 1 5.70/2.36 evalEx5bb6in(A, B, C, D, E) -> Com_1(evalEx5returnin(A, B, C, D, E)) :|: A >= B 5.70/2.36 evalEx5bb3in(A, B, C, D, E) -> Com_1(evalEx5bb1in(A, B, C, D, E)) :|: 0 >= F + 1 5.70/2.36 evalEx5bb3in(A, B, C, D, E) -> Com_1(evalEx5bb1in(A, B, C, D, E)) :|: F >= 1 5.70/2.36 evalEx5bb3in(A, B, C, D, E) -> Com_1(evalEx5bb4in(A, B, C, D, E)) :|: TRUE 5.70/2.36 evalEx5bb1in(A, B, C, D, E) -> Com_1(evalEx5bb2in(A, B, C, D, D - 1)) :|: 0 >= F + 1 5.70/2.36 evalEx5bb1in(A, B, C, D, E) -> Com_1(evalEx5bb2in(A, B, C, D, D - 1)) :|: 0 >= F + 1 && F >= 1 5.70/2.36 evalEx5bb1in(A, B, C, D, E) -> Com_1(evalEx5bb2in(A, B, C, D, D - 1)) :|: F >= 1 5.70/2.36 evalEx5bb1in(A, B, C, D, E) -> Com_1(evalEx5bb3in(A, B, C, D - 1, E)) :|: 0 >= 1 5.70/2.36 evalEx5bb1in(A, B, C, D, E) -> Com_1(evalEx5bb2in(A, B, C, D, D)) :|: 0 >= 1 5.70/2.36 evalEx5bb1in(A, B, C, D, E) -> Com_1(evalEx5bb3in(A, B, C, D, E)) :|: TRUE 5.70/2.36 evalEx5bb2in(A, B, C, D, E) -> Com_1(evalEx5bb3in(A, B, 1, E, E)) :|: TRUE 5.70/2.36 evalEx5bb4in(A, B, C, D, E) -> Com_1(evalEx5bb6in(A + 1, D, C, D, E)) :|: C >= 0 && C <= 0 5.70/2.36 evalEx5bb4in(A, B, C, D, E) -> Com_1(evalEx5bb6in(A, D, C, D, E)) :|: 0 >= C + 1 5.70/2.36 evalEx5bb4in(A, B, C, D, E) -> Com_1(evalEx5bb6in(A, D, C, D, E)) :|: C >= 1 5.70/2.36 evalEx5returnin(A, B, C, D, E) -> Com_1(evalEx5stop(A, B, C, D, E)) :|: TRUE 5.70/2.36 5.70/2.36 The start-symbols are:[evalEx5start_5] 5.70/2.36 5.70/2.36 5.70/2.36 ---------------------------------------- 5.70/2.36 5.70/2.36 (1) Loat Proof (FINISHED) 5.70/2.36 5.70/2.36 5.70/2.36 ### Pre-processing the ITS problem ### 5.70/2.36 5.70/2.36 5.70/2.36 5.70/2.36 Initial linear ITS problem 5.70/2.36 5.70/2.36 Start location: evalEx5start 5.70/2.36 5.70/2.36 0: evalEx5start -> evalEx5entryin : [], cost: 1 5.70/2.36 5.70/2.36 1: evalEx5entryin -> evalEx5bb6in : A'=0, B'=A, [], cost: 1 5.70/2.36 5.70/2.36 2: evalEx5bb6in -> evalEx5bb3in : C'=0, D'=B, [ B>=1+A ], cost: 1 5.70/2.36 5.70/2.36 3: evalEx5bb6in -> evalEx5returnin : [ A>=B ], cost: 1 5.70/2.36 5.70/2.36 4: evalEx5bb3in -> evalEx5bb1in : [ 0>=1+free ], cost: 1 5.70/2.36 5.70/2.36 5: evalEx5bb3in -> evalEx5bb1in : [ free_1>=1 ], cost: 1 5.70/2.36 5.70/2.36 6: evalEx5bb3in -> evalEx5bb4in : [], cost: 1 5.70/2.36 5.70/2.36 7: evalEx5bb1in -> evalEx5bb2in : E'=-1+D, [ 0>=1+free_2 ], cost: 1 5.70/2.36 5.70/2.36 8: evalEx5bb1in -> evalEx5bb2in : E'=-1+D, [ 0>=1+free_3 && free_3>=1 ], cost: 1 5.70/2.36 5.70/2.36 9: evalEx5bb1in -> evalEx5bb2in : E'=-1+D, [ free_4>=1 ], cost: 1 5.70/2.36 5.70/2.36 10: evalEx5bb1in -> evalEx5bb3in : D'=-1+D, [ 0>=1 ], cost: 1 5.70/2.36 5.70/2.36 11: evalEx5bb1in -> evalEx5bb2in : E'=D, [ 0>=1 ], cost: 1 5.70/2.36 5.70/2.36 12: evalEx5bb1in -> evalEx5bb3in : [], cost: 1 5.70/2.36 5.70/2.36 13: evalEx5bb2in -> evalEx5bb3in : C'=1, D'=E, [], cost: 1 5.70/2.36 5.70/2.36 14: evalEx5bb4in -> evalEx5bb6in : A'=1+A, B'=D, [ C==0 ], cost: 1 5.70/2.36 5.70/2.36 15: evalEx5bb4in -> evalEx5bb6in : B'=D, [ 0>=1+C ], cost: 1 5.70/2.36 5.70/2.36 16: evalEx5bb4in -> evalEx5bb6in : B'=D, [ C>=1 ], cost: 1 5.70/2.36 5.70/2.36 17: evalEx5returnin -> evalEx5stop : [], cost: 1 5.70/2.36 5.70/2.36 5.70/2.36 5.70/2.36 Removed unreachable and leaf rules: 5.70/2.36 5.70/2.36 Start location: evalEx5start 5.70/2.36 5.70/2.36 0: evalEx5start -> evalEx5entryin : [], cost: 1 5.70/2.36 5.70/2.36 1: evalEx5entryin -> evalEx5bb6in : A'=0, B'=A, [], cost: 1 5.70/2.36 5.70/2.36 2: evalEx5bb6in -> evalEx5bb3in : C'=0, D'=B, [ B>=1+A ], cost: 1 5.70/2.36 5.70/2.36 4: evalEx5bb3in -> evalEx5bb1in : [ 0>=1+free ], cost: 1 5.70/2.36 5.70/2.36 5: evalEx5bb3in -> evalEx5bb1in : [ free_1>=1 ], cost: 1 5.70/2.36 5.70/2.36 6: evalEx5bb3in -> evalEx5bb4in : [], cost: 1 5.70/2.36 5.70/2.36 7: evalEx5bb1in -> evalEx5bb2in : E'=-1+D, [ 0>=1+free_2 ], cost: 1 5.70/2.36 5.70/2.36 8: evalEx5bb1in -> evalEx5bb2in : E'=-1+D, [ 0>=1+free_3 && free_3>=1 ], cost: 1 5.70/2.36 5.70/2.36 9: evalEx5bb1in -> evalEx5bb2in : E'=-1+D, [ free_4>=1 ], cost: 1 5.70/2.36 5.70/2.36 10: evalEx5bb1in -> evalEx5bb3in : D'=-1+D, [ 0>=1 ], cost: 1 5.70/2.36 5.70/2.36 11: evalEx5bb1in -> evalEx5bb2in : E'=D, [ 0>=1 ], cost: 1 5.70/2.36 5.70/2.36 12: evalEx5bb1in -> evalEx5bb3in : [], cost: 1 5.70/2.36 5.70/2.36 13: evalEx5bb2in -> evalEx5bb3in : C'=1, D'=E, [], cost: 1 5.70/2.36 5.70/2.36 14: evalEx5bb4in -> evalEx5bb6in : A'=1+A, B'=D, [ C==0 ], cost: 1 5.70/2.36 5.70/2.36 15: evalEx5bb4in -> evalEx5bb6in : B'=D, [ 0>=1+C ], cost: 1 5.70/2.36 5.70/2.36 16: evalEx5bb4in -> evalEx5bb6in : B'=D, [ C>=1 ], cost: 1 5.70/2.36 5.70/2.36 5.70/2.36 5.70/2.36 Removed rules with unsatisfiable guard: 5.70/2.36 5.70/2.36 Start location: evalEx5start 5.70/2.36 5.70/2.36 0: evalEx5start -> evalEx5entryin : [], cost: 1 5.70/2.36 5.70/2.36 1: evalEx5entryin -> evalEx5bb6in : A'=0, B'=A, [], cost: 1 5.70/2.36 5.70/2.36 2: evalEx5bb6in -> evalEx5bb3in : C'=0, D'=B, [ B>=1+A ], cost: 1 5.70/2.36 5.70/2.36 4: evalEx5bb3in -> evalEx5bb1in : [ 0>=1+free ], cost: 1 5.70/2.36 5.70/2.36 5: evalEx5bb3in -> evalEx5bb1in : [ free_1>=1 ], cost: 1 5.70/2.36 5.70/2.36 6: evalEx5bb3in -> evalEx5bb4in : [], cost: 1 5.70/2.36 5.70/2.36 7: evalEx5bb1in -> evalEx5bb2in : E'=-1+D, [ 0>=1+free_2 ], cost: 1 5.70/2.36 5.70/2.36 9: evalEx5bb1in -> evalEx5bb2in : E'=-1+D, [ free_4>=1 ], cost: 1 5.70/2.36 5.70/2.36 12: evalEx5bb1in -> evalEx5bb3in : [], cost: 1 5.70/2.36 5.70/2.36 13: evalEx5bb2in -> evalEx5bb3in : C'=1, D'=E, [], cost: 1 5.70/2.36 5.70/2.36 14: evalEx5bb4in -> evalEx5bb6in : A'=1+A, B'=D, [ C==0 ], cost: 1 5.70/2.36 5.70/2.36 15: evalEx5bb4in -> evalEx5bb6in : B'=D, [ 0>=1+C ], cost: 1 5.70/2.36 5.70/2.36 16: evalEx5bb4in -> evalEx5bb6in : B'=D, [ C>=1 ], cost: 1 5.70/2.36 5.70/2.36 5.70/2.36 5.70/2.36 Simplified all rules, resulting in: 5.70/2.36 5.70/2.36 Start location: evalEx5start 5.70/2.36 5.70/2.36 0: evalEx5start -> evalEx5entryin : [], cost: 1 5.70/2.36 5.70/2.36 1: evalEx5entryin -> evalEx5bb6in : A'=0, B'=A, [], cost: 1 5.70/2.36 5.70/2.36 2: evalEx5bb6in -> evalEx5bb3in : C'=0, D'=B, [ B>=1+A ], cost: 1 5.70/2.36 5.70/2.36 5: evalEx5bb3in -> evalEx5bb1in : [], cost: 1 5.70/2.36 5.70/2.36 6: evalEx5bb3in -> evalEx5bb4in : [], cost: 1 5.70/2.36 5.70/2.36 9: evalEx5bb1in -> evalEx5bb2in : E'=-1+D, [], cost: 1 5.70/2.36 5.70/2.36 12: evalEx5bb1in -> evalEx5bb3in : [], cost: 1 5.70/2.36 5.70/2.36 13: evalEx5bb2in -> evalEx5bb3in : C'=1, D'=E, [], cost: 1 5.70/2.36 5.70/2.36 14: evalEx5bb4in -> evalEx5bb6in : A'=1+A, B'=D, [ C==0 ], cost: 1 5.70/2.36 5.70/2.36 15: evalEx5bb4in -> evalEx5bb6in : B'=D, [ 0>=1+C ], cost: 1 5.70/2.36 5.70/2.36 16: evalEx5bb4in -> evalEx5bb6in : B'=D, [ C>=1 ], cost: 1 5.70/2.36 5.70/2.36 5.70/2.36 5.70/2.36 ### Simplification by acceleration and chaining ### 5.70/2.36 5.70/2.36 5.70/2.36 5.70/2.36 Eliminated locations (on linear paths): 5.70/2.36 5.70/2.36 Start location: evalEx5start 5.70/2.36 5.70/2.36 18: evalEx5start -> evalEx5bb6in : A'=0, B'=A, [], cost: 2 5.70/2.36 5.70/2.36 2: evalEx5bb6in -> evalEx5bb3in : C'=0, D'=B, [ B>=1+A ], cost: 1 5.70/2.36 5.70/2.36 5: evalEx5bb3in -> evalEx5bb1in : [], cost: 1 5.70/2.36 5.70/2.36 6: evalEx5bb3in -> evalEx5bb4in : [], cost: 1 5.70/2.36 5.70/2.36 12: evalEx5bb1in -> evalEx5bb3in : [], cost: 1 5.70/2.36 5.70/2.36 19: evalEx5bb1in -> evalEx5bb3in : C'=1, D'=-1+D, E'=-1+D, [], cost: 2 5.70/2.36 5.70/2.36 14: evalEx5bb4in -> evalEx5bb6in : A'=1+A, B'=D, [ C==0 ], cost: 1 5.70/2.36 5.70/2.36 15: evalEx5bb4in -> evalEx5bb6in : B'=D, [ 0>=1+C ], cost: 1 5.70/2.36 5.70/2.36 16: evalEx5bb4in -> evalEx5bb6in : B'=D, [ C>=1 ], cost: 1 5.70/2.36 5.70/2.36 5.70/2.36 5.70/2.36 Eliminated locations (on tree-shaped paths): 5.70/2.36 5.70/2.36 Start location: evalEx5start 5.70/2.36 5.70/2.36 18: evalEx5start -> evalEx5bb6in : A'=0, B'=A, [], cost: 2 5.70/2.36 5.70/2.36 2: evalEx5bb6in -> evalEx5bb3in : C'=0, D'=B, [ B>=1+A ], cost: 1 5.70/2.36 5.70/2.36 20: evalEx5bb3in -> evalEx5bb3in : [], cost: 2 5.70/2.36 5.70/2.36 21: evalEx5bb3in -> evalEx5bb3in : C'=1, D'=-1+D, E'=-1+D, [], cost: 3 5.70/2.36 5.70/2.36 22: evalEx5bb3in -> evalEx5bb6in : A'=1+A, B'=D, [ C==0 ], cost: 2 5.70/2.36 5.70/2.36 23: evalEx5bb3in -> evalEx5bb6in : B'=D, [ 0>=1+C ], cost: 2 5.70/2.36 5.70/2.36 24: evalEx5bb3in -> evalEx5bb6in : B'=D, [ C>=1 ], cost: 2 5.70/2.36 5.70/2.36 5.70/2.36 5.70/2.36 Accelerating simple loops of location 3. 5.70/2.36 5.70/2.36 Accelerating the following rules: 5.70/2.36 5.70/2.36 20: evalEx5bb3in -> evalEx5bb3in : [], cost: 2 5.70/2.36 5.70/2.36 21: evalEx5bb3in -> evalEx5bb3in : C'=1, D'=-1+D, E'=-1+D, [], cost: 3 5.70/2.36 5.70/2.36 5.70/2.36 5.70/2.36 Accelerated rule 20 with NONTERM, yielding the new rule 25. 5.70/2.36 5.70/2.36 Accelerated rule 21 with NONTERM, yielding the new rule 26. 5.70/2.36 5.70/2.36 Removing the simple loops: 20 21. 5.70/2.36 5.70/2.36 Also removing duplicate rules:. 5.70/2.36 5.70/2.36 5.70/2.36 5.70/2.36 Accelerated all simple loops using metering functions (where possible): 5.70/2.36 5.70/2.36 Start location: evalEx5start 5.70/2.36 5.70/2.36 18: evalEx5start -> evalEx5bb6in : A'=0, B'=A, [], cost: 2 5.70/2.36 5.70/2.36 2: evalEx5bb6in -> evalEx5bb3in : C'=0, D'=B, [ B>=1+A ], cost: 1 5.70/2.36 5.70/2.36 22: evalEx5bb3in -> evalEx5bb6in : A'=1+A, B'=D, [ C==0 ], cost: 2 5.70/2.36 5.70/2.36 23: evalEx5bb3in -> evalEx5bb6in : B'=D, [ 0>=1+C ], cost: 2 5.70/2.36 5.70/2.36 24: evalEx5bb3in -> evalEx5bb6in : B'=D, [ C>=1 ], cost: 2 5.70/2.36 5.70/2.36 26: evalEx5bb3in -> [9] : [], cost: INF 5.70/2.36 5.70/2.36 5.70/2.36 5.70/2.36 Chained accelerated rules (with incoming rules): 5.70/2.36 5.70/2.36 Start location: evalEx5start 5.70/2.36 5.70/2.36 18: evalEx5start -> evalEx5bb6in : A'=0, B'=A, [], cost: 2 5.70/2.36 5.70/2.36 2: evalEx5bb6in -> evalEx5bb3in : C'=0, D'=B, [ B>=1+A ], cost: 1 5.70/2.36 5.70/2.36 27: evalEx5bb6in -> [9] : C'=0, D'=B, [ B>=1+A ], cost: INF 5.70/2.36 5.70/2.36 22: evalEx5bb3in -> evalEx5bb6in : A'=1+A, B'=D, [ C==0 ], cost: 2 5.70/2.36 5.70/2.36 23: evalEx5bb3in -> evalEx5bb6in : B'=D, [ 0>=1+C ], cost: 2 5.70/2.36 5.70/2.36 24: evalEx5bb3in -> evalEx5bb6in : B'=D, [ C>=1 ], cost: 2 5.70/2.36 5.70/2.36 5.70/2.36 5.70/2.36 Eliminated locations (on tree-shaped paths): 5.70/2.36 5.70/2.36 Start location: evalEx5start 5.70/2.36 5.70/2.36 18: evalEx5start -> evalEx5bb6in : A'=0, B'=A, [], cost: 2 5.70/2.36 5.70/2.36 27: evalEx5bb6in -> [9] : C'=0, D'=B, [ B>=1+A ], cost: INF 5.70/2.36 5.70/2.36 28: evalEx5bb6in -> evalEx5bb6in : A'=1+A, B'=B, C'=0, D'=B, [ B>=1+A ], cost: 3 5.70/2.36 5.70/2.36 5.70/2.36 5.70/2.36 Accelerating simple loops of location 2. 5.70/2.36 5.70/2.36 Simplified some of the simple loops (and removed duplicate rules). 5.70/2.36 5.70/2.36 Accelerating the following rules: 5.70/2.36 5.70/2.36 28: evalEx5bb6in -> evalEx5bb6in : A'=1+A, C'=0, D'=B, [ B>=1+A ], cost: 3 5.70/2.36 5.70/2.36 5.70/2.36 5.70/2.36 Accelerated rule 28 with metering function -A+B, yielding the new rule 29. 5.70/2.36 5.70/2.36 Removing the simple loops: 28. 5.70/2.36 5.70/2.36 5.70/2.36 5.70/2.36 Accelerated all simple loops using metering functions (where possible): 5.70/2.36 5.70/2.36 Start location: evalEx5start 5.70/2.36 5.70/2.36 18: evalEx5start -> evalEx5bb6in : A'=0, B'=A, [], cost: 2 5.70/2.36 5.70/2.36 27: evalEx5bb6in -> [9] : C'=0, D'=B, [ B>=1+A ], cost: INF 5.70/2.36 5.70/2.36 29: evalEx5bb6in -> evalEx5bb6in : A'=B, C'=0, D'=B, [ B>=1+A ], cost: -3*A+3*B 5.70/2.36 5.70/2.36 5.70/2.36 5.70/2.36 Chained accelerated rules (with incoming rules): 5.70/2.36 5.70/2.36 Start location: evalEx5start 5.70/2.36 5.70/2.36 18: evalEx5start -> evalEx5bb6in : A'=0, B'=A, [], cost: 2 5.70/2.36 5.70/2.36 30: evalEx5start -> evalEx5bb6in : B'=A, C'=0, D'=A, [ A>=1 ], cost: 2+3*A 5.70/2.36 5.70/2.36 27: evalEx5bb6in -> [9] : C'=0, D'=B, [ B>=1+A ], cost: INF 5.70/2.36 5.70/2.36 5.70/2.36 5.70/2.36 Eliminated locations (on tree-shaped paths): 5.70/2.36 5.70/2.36 Start location: evalEx5start 5.70/2.36 5.70/2.36 31: evalEx5start -> [9] : A'=0, B'=A, C'=0, D'=A, [ A>=1 ], cost: INF 5.70/2.36 5.70/2.36 32: evalEx5start -> [11] : [ A>=1 ], cost: 2+3*A 5.70/2.36 5.70/2.36 5.70/2.36 5.70/2.36 ### Computing asymptotic complexity ### 5.70/2.36 5.70/2.36 5.70/2.36 5.70/2.36 Fully simplified ITS problem 5.70/2.36 5.70/2.36 Start location: evalEx5start 5.70/2.36 5.70/2.36 31: evalEx5start -> [9] : A'=0, B'=A, C'=0, D'=A, [ A>=1 ], cost: INF 5.70/2.36 5.70/2.36 32: evalEx5start -> [11] : [ A>=1 ], cost: 2+3*A 5.70/2.36 5.70/2.36 5.70/2.36 5.70/2.36 Computing asymptotic complexity for rule 31 5.70/2.36 5.70/2.36 Resulting cost INF has complexity: Nonterm 5.70/2.36 5.70/2.36 5.70/2.36 5.70/2.36 Found new complexity Nonterm. 5.70/2.36 5.70/2.36 5.70/2.36 5.70/2.36 Obtained the following overall complexity (w.r.t. the length of the input n): 5.70/2.36 5.70/2.36 Complexity: Nonterm 5.70/2.36 5.70/2.36 Cpx degree: Nonterm 5.70/2.36 5.70/2.36 Solved cost: INF 5.70/2.36 5.70/2.36 Rule cost: INF 5.70/2.36 5.70/2.36 Rule guard: [ A>=1 ] 5.70/2.36 5.70/2.36 5.70/2.36 5.70/2.36 NO 5.70/2.36 5.70/2.36 5.70/2.36 ---------------------------------------- 5.70/2.36 5.70/2.36 (2) 5.70/2.36 BOUNDS(INF, INF) 5.70/2.39 EOF