4.82/2.13 WORST_CASE(NON_POLY, ?) 4.82/2.14 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 4.82/2.14 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.82/2.14 4.82/2.14 4.82/2.14 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 4.82/2.14 4.82/2.14 (0) CpxIntTrs 4.82/2.14 (1) Loat Proof [FINISHED, 415 ms] 4.82/2.14 (2) BOUNDS(INF, INF) 4.82/2.14 4.82/2.14 4.82/2.14 ---------------------------------------- 4.82/2.14 4.82/2.14 (0) 4.82/2.14 Obligation: 4.82/2.14 Complexity Int TRS consisting of the following rules: 4.82/2.14 evalEx2start(A, B, C, D) -> Com_1(evalEx2entryin(A, B, C, D)) :|: TRUE 4.82/2.14 evalEx2entryin(A, B, C, D) -> Com_1(evalEx2bb3in(B, A, C, D)) :|: TRUE 4.82/2.14 evalEx2bb3in(A, B, C, D) -> Com_1(evalEx2bbin(A, B, C, D)) :|: B >= 1 && A >= 1 4.82/2.14 evalEx2bb3in(A, B, C, D) -> Com_1(evalEx2returnin(A, B, C, D)) :|: 0 >= B 4.82/2.14 evalEx2bb3in(A, B, C, D) -> Com_1(evalEx2returnin(A, B, C, D)) :|: 0 >= A 4.82/2.14 evalEx2bbin(A, B, C, D) -> Com_1(evalEx2bb2in(A, B, A - 1, B - 1)) :|: TRUE 4.82/2.14 evalEx2bb2in(A, B, C, D) -> Com_1(evalEx2bb1in(A, B, C, D)) :|: 0 >= E + 1 4.82/2.14 evalEx2bb2in(A, B, C, D) -> Com_1(evalEx2bb1in(A, B, C, D)) :|: E >= 1 4.82/2.14 evalEx2bb2in(A, B, C, D) -> Com_1(evalEx2bb3in(C, D, C, D)) :|: TRUE 4.82/2.14 evalEx2bb1in(A, B, C, D) -> Com_1(evalEx2bb2in(A, B, C + 1, D - 1)) :|: TRUE 4.82/2.14 evalEx2returnin(A, B, C, D) -> Com_1(evalEx2stop(A, B, C, D)) :|: TRUE 4.82/2.14 4.82/2.14 The start-symbols are:[evalEx2start_4] 4.82/2.14 4.82/2.14 4.82/2.14 ---------------------------------------- 4.82/2.14 4.82/2.14 (1) Loat Proof (FINISHED) 4.82/2.14 4.82/2.14 4.82/2.14 ### Pre-processing the ITS problem ### 4.82/2.14 4.82/2.14 4.82/2.14 4.82/2.14 Initial linear ITS problem 4.82/2.14 4.82/2.14 Start location: evalEx2start 4.82/2.14 4.82/2.14 0: evalEx2start -> evalEx2entryin : [], cost: 1 4.82/2.14 4.82/2.14 1: evalEx2entryin -> evalEx2bb3in : A'=B, B'=A, [], cost: 1 4.82/2.14 4.82/2.14 2: evalEx2bb3in -> evalEx2bbin : [ B>=1 && A>=1 ], cost: 1 4.82/2.14 4.82/2.14 3: evalEx2bb3in -> evalEx2returnin : [ 0>=B ], cost: 1 4.82/2.14 4.82/2.14 4: evalEx2bb3in -> evalEx2returnin : [ 0>=A ], cost: 1 4.82/2.14 4.82/2.14 5: evalEx2bbin -> evalEx2bb2in : C'=-1+A, D'=-1+B, [], cost: 1 4.82/2.14 4.82/2.14 6: evalEx2bb2in -> evalEx2bb1in : [ 0>=1+free ], cost: 1 4.82/2.14 4.82/2.14 7: evalEx2bb2in -> evalEx2bb1in : [ free_1>=1 ], cost: 1 4.82/2.14 4.82/2.14 8: evalEx2bb2in -> evalEx2bb3in : A'=C, B'=D, [], cost: 1 4.82/2.14 4.82/2.14 9: evalEx2bb1in -> evalEx2bb2in : C'=1+C, D'=-1+D, [], cost: 1 4.82/2.14 4.82/2.14 10: evalEx2returnin -> evalEx2stop : [], cost: 1 4.82/2.14 4.82/2.14 4.82/2.14 4.82/2.14 Removed unreachable and leaf rules: 4.82/2.14 4.82/2.14 Start location: evalEx2start 4.82/2.14 4.82/2.14 0: evalEx2start -> evalEx2entryin : [], cost: 1 4.82/2.14 4.82/2.14 1: evalEx2entryin -> evalEx2bb3in : A'=B, B'=A, [], cost: 1 4.82/2.14 4.82/2.14 2: evalEx2bb3in -> evalEx2bbin : [ B>=1 && A>=1 ], cost: 1 4.82/2.14 4.82/2.14 5: evalEx2bbin -> evalEx2bb2in : C'=-1+A, D'=-1+B, [], cost: 1 4.82/2.14 4.82/2.14 6: evalEx2bb2in -> evalEx2bb1in : [ 0>=1+free ], cost: 1 4.82/2.14 4.82/2.14 7: evalEx2bb2in -> evalEx2bb1in : [ free_1>=1 ], cost: 1 4.82/2.14 4.82/2.14 8: evalEx2bb2in -> evalEx2bb3in : A'=C, B'=D, [], cost: 1 4.82/2.14 4.82/2.14 9: evalEx2bb1in -> evalEx2bb2in : C'=1+C, D'=-1+D, [], cost: 1 4.82/2.14 4.82/2.14 4.82/2.14 4.82/2.14 Simplified all rules, resulting in: 4.82/2.14 4.82/2.14 Start location: evalEx2start 4.82/2.14 4.82/2.14 0: evalEx2start -> evalEx2entryin : [], cost: 1 4.82/2.14 4.82/2.14 1: evalEx2entryin -> evalEx2bb3in : A'=B, B'=A, [], cost: 1 4.82/2.14 4.82/2.14 2: evalEx2bb3in -> evalEx2bbin : [ B>=1 && A>=1 ], cost: 1 4.82/2.14 4.82/2.14 5: evalEx2bbin -> evalEx2bb2in : C'=-1+A, D'=-1+B, [], cost: 1 4.82/2.14 4.82/2.14 7: evalEx2bb2in -> evalEx2bb1in : [], cost: 1 4.82/2.14 4.82/2.14 8: evalEx2bb2in -> evalEx2bb3in : A'=C, B'=D, [], cost: 1 4.82/2.14 4.82/2.14 9: evalEx2bb1in -> evalEx2bb2in : C'=1+C, D'=-1+D, [], cost: 1 4.82/2.14 4.82/2.14 4.82/2.14 4.82/2.14 ### Simplification by acceleration and chaining ### 4.82/2.14 4.82/2.14 4.82/2.14 4.82/2.14 Eliminated locations (on linear paths): 4.82/2.14 4.82/2.14 Start location: evalEx2start 4.82/2.14 4.82/2.14 11: evalEx2start -> evalEx2bb3in : A'=B, B'=A, [], cost: 2 4.82/2.14 4.82/2.14 12: evalEx2bb3in -> evalEx2bb2in : C'=-1+A, D'=-1+B, [ B>=1 && A>=1 ], cost: 2 4.82/2.14 4.82/2.14 8: evalEx2bb2in -> evalEx2bb3in : A'=C, B'=D, [], cost: 1 4.82/2.14 4.82/2.14 13: evalEx2bb2in -> evalEx2bb2in : C'=1+C, D'=-1+D, [], cost: 2 4.82/2.14 4.82/2.14 4.82/2.14 4.82/2.14 Accelerating simple loops of location 4. 4.82/2.14 4.82/2.14 Accelerating the following rules: 4.82/2.14 4.82/2.14 13: evalEx2bb2in -> evalEx2bb2in : C'=1+C, D'=-1+D, [], cost: 2 4.82/2.14 4.82/2.14 4.82/2.14 4.82/2.14 Accelerated rule 13 with NONTERM, yielding the new rule 14. 4.82/2.14 4.82/2.14 Removing the simple loops: 13. 4.82/2.14 4.82/2.14 4.82/2.14 4.82/2.14 Accelerated all simple loops using metering functions (where possible): 4.82/2.14 4.82/2.14 Start location: evalEx2start 4.82/2.14 4.82/2.14 11: evalEx2start -> evalEx2bb3in : A'=B, B'=A, [], cost: 2 5.14/2.14 5.14/2.14 12: evalEx2bb3in -> evalEx2bb2in : C'=-1+A, D'=-1+B, [ B>=1 && A>=1 ], cost: 2 5.14/2.14 5.14/2.14 8: evalEx2bb2in -> evalEx2bb3in : A'=C, B'=D, [], cost: 1 5.14/2.14 5.14/2.14 14: evalEx2bb2in -> [8] : [], cost: INF 5.14/2.14 5.14/2.14 5.14/2.14 5.14/2.14 Chained accelerated rules (with incoming rules): 5.14/2.14 5.14/2.14 Start location: evalEx2start 5.14/2.14 5.14/2.14 11: evalEx2start -> evalEx2bb3in : A'=B, B'=A, [], cost: 2 5.14/2.14 5.14/2.14 12: evalEx2bb3in -> evalEx2bb2in : C'=-1+A, D'=-1+B, [ B>=1 && A>=1 ], cost: 2 5.14/2.14 5.14/2.14 15: evalEx2bb3in -> [8] : C'=-1+A, D'=-1+B, [ B>=1 && A>=1 ], cost: INF 5.14/2.14 5.14/2.14 8: evalEx2bb2in -> evalEx2bb3in : A'=C, B'=D, [], cost: 1 5.14/2.14 5.14/2.14 5.14/2.14 5.14/2.14 Eliminated locations (on linear paths): 5.14/2.14 5.14/2.14 Start location: evalEx2start 5.14/2.14 5.14/2.14 11: evalEx2start -> evalEx2bb3in : A'=B, B'=A, [], cost: 2 5.14/2.14 5.14/2.14 15: evalEx2bb3in -> [8] : C'=-1+A, D'=-1+B, [ B>=1 && A>=1 ], cost: INF 5.14/2.14 5.14/2.14 16: evalEx2bb3in -> evalEx2bb3in : A'=-1+A, B'=-1+B, C'=-1+A, D'=-1+B, [ B>=1 && A>=1 ], cost: 3 5.14/2.14 5.14/2.14 5.14/2.14 5.14/2.14 Accelerating simple loops of location 2. 5.14/2.14 5.14/2.14 Accelerating the following rules: 5.14/2.14 5.14/2.14 16: evalEx2bb3in -> evalEx2bb3in : A'=-1+A, B'=-1+B, C'=-1+A, D'=-1+B, [ B>=1 && A>=1 ], cost: 3 5.14/2.14 5.14/2.14 5.14/2.14 5.14/2.14 Accelerated rule 16 with metering function B (after adding A>=B), yielding the new rule 17. 5.14/2.14 5.14/2.14 Accelerated rule 16 with metering function A (after adding A<=B), yielding the new rule 18. 5.14/2.14 5.14/2.14 Removing the simple loops: 16. 5.14/2.14 5.14/2.14 5.14/2.14 5.14/2.14 Accelerated all simple loops using metering functions (where possible): 5.14/2.14 5.14/2.14 Start location: evalEx2start 5.14/2.14 5.14/2.14 11: evalEx2start -> evalEx2bb3in : A'=B, B'=A, [], cost: 2 5.14/2.14 5.14/2.14 15: evalEx2bb3in -> [8] : C'=-1+A, D'=-1+B, [ B>=1 && A>=1 ], cost: INF 5.14/2.14 5.14/2.14 17: evalEx2bb3in -> evalEx2bb3in : A'=A-B, B'=0, C'=A-B, D'=0, [ B>=1 && A>=1 && A>=B ], cost: 3*B 5.14/2.14 5.14/2.14 18: evalEx2bb3in -> evalEx2bb3in : A'=0, B'=-A+B, C'=0, D'=-A+B, [ B>=1 && A>=1 && A<=B ], cost: 3*A 5.14/2.14 5.14/2.14 5.14/2.14 5.14/2.14 Chained accelerated rules (with incoming rules): 5.14/2.14 5.14/2.14 Start location: evalEx2start 5.14/2.14 5.14/2.14 11: evalEx2start -> evalEx2bb3in : A'=B, B'=A, [], cost: 2 5.14/2.14 5.14/2.14 19: evalEx2start -> evalEx2bb3in : A'=-A+B, B'=0, C'=-A+B, D'=0, [ A>=1 && B>=1 && B>=A ], cost: 2+3*A 5.14/2.14 5.14/2.14 20: evalEx2start -> evalEx2bb3in : A'=0, B'=A-B, C'=0, D'=A-B, [ A>=1 && B>=1 && B<=A ], cost: 2+3*B 5.14/2.14 5.14/2.14 15: evalEx2bb3in -> [8] : C'=-1+A, D'=-1+B, [ B>=1 && A>=1 ], cost: INF 5.14/2.14 5.14/2.14 5.14/2.14 5.14/2.14 Eliminated locations (on tree-shaped paths): 5.14/2.14 5.14/2.14 Start location: evalEx2start 5.14/2.14 5.14/2.14 21: evalEx2start -> [8] : A'=B, B'=A, C'=-1+B, D'=-1+A, [ A>=1 && B>=1 ], cost: INF 5.14/2.14 5.14/2.14 22: evalEx2start -> [10] : [ A>=1 && B>=1 && B>=A ], cost: 2+3*A 5.14/2.14 5.14/2.14 23: evalEx2start -> [10] : [ A>=1 && B>=1 && B<=A ], cost: 2+3*B 5.14/2.14 5.14/2.14 5.14/2.14 5.14/2.14 ### Computing asymptotic complexity ### 5.14/2.14 5.14/2.14 5.14/2.14 5.14/2.14 Fully simplified ITS problem 5.14/2.14 5.14/2.14 Start location: evalEx2start 5.14/2.14 5.14/2.14 21: evalEx2start -> [8] : A'=B, B'=A, C'=-1+B, D'=-1+A, [ A>=1 && B>=1 ], cost: INF 5.14/2.14 5.14/2.14 22: evalEx2start -> [10] : [ A>=1 && B>=1 && B>=A ], cost: 2+3*A 5.14/2.14 5.14/2.14 23: evalEx2start -> [10] : [ A>=1 && B>=1 && B<=A ], cost: 2+3*B 5.14/2.14 5.14/2.14 5.14/2.14 5.14/2.14 Computing asymptotic complexity for rule 21 5.14/2.14 5.14/2.14 Resulting cost INF has complexity: Nonterm 5.14/2.14 5.14/2.14 5.14/2.14 5.14/2.14 Found new complexity Nonterm. 5.14/2.14 5.14/2.14 5.14/2.14 5.14/2.14 Obtained the following overall complexity (w.r.t. the length of the input n): 5.14/2.14 5.14/2.14 Complexity: Nonterm 5.14/2.14 5.14/2.14 Cpx degree: Nonterm 5.14/2.14 5.14/2.14 Solved cost: INF 5.14/2.14 5.14/2.14 Rule cost: INF 5.14/2.14 5.14/2.14 Rule guard: [ A>=1 && B>=1 ] 5.14/2.14 5.14/2.14 5.14/2.14 5.14/2.14 NO 5.14/2.14 5.14/2.14 5.14/2.14 ---------------------------------------- 5.14/2.14 5.14/2.14 (2) 5.14/2.14 BOUNDS(INF, INF) 5.14/2.16 EOF