5.10/2.19 WORST_CASE(NON_POLY, ?) 5.10/2.19 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 5.10/2.19 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.10/2.19 5.10/2.19 5.10/2.19 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 5.10/2.19 5.10/2.19 (0) CpxIntTrs 5.10/2.19 (1) Loat Proof [FINISHED, 627 ms] 5.10/2.19 (2) BOUNDS(INF, INF) 5.10/2.19 5.10/2.19 5.10/2.19 ---------------------------------------- 5.10/2.19 5.10/2.19 (0) 5.10/2.19 Obligation: 5.10/2.19 Complexity Int TRS consisting of the following rules: 5.10/2.19 evalEx3start(A, B, C) -> Com_1(evalEx3entryin(A, B, C)) :|: TRUE 5.10/2.19 evalEx3entryin(A, B, C) -> Com_1(evalEx3bb4in(A, B, C)) :|: TRUE 5.10/2.19 evalEx3bb4in(A, B, C) -> Com_1(evalEx3bbin(A, B, C)) :|: A >= 1 5.10/2.19 evalEx3bb4in(A, B, C) -> Com_1(evalEx3returnin(A, B, C)) :|: 0 >= A 5.10/2.19 evalEx3bbin(A, B, C) -> Com_1(evalEx3bb2in(A, D, A)) :|: TRUE 5.10/2.19 evalEx3bb2in(A, B, C) -> Com_1(evalEx3bb4in(C, B, C)) :|: 0 >= C 5.10/2.19 evalEx3bb2in(A, B, C) -> Com_1(evalEx3bb3in(A, B, C)) :|: C >= 1 5.10/2.19 evalEx3bb3in(A, B, C) -> Com_1(evalEx3bb1in(A, B, C)) :|: TRUE 5.10/2.19 evalEx3bb3in(A, B, C) -> Com_1(evalEx3bb4in(C, B, C)) :|: B >= D + 1 5.10/2.19 evalEx3bb3in(A, B, C) -> Com_1(evalEx3bb4in(C, B, C)) :|: D >= B + 1 5.10/2.20 evalEx3bb1in(A, B, C) -> Com_1(evalEx3bb2in(A, B, C - 1)) :|: TRUE 5.10/2.20 evalEx3returnin(A, B, C) -> Com_1(evalEx3stop(A, B, C)) :|: TRUE 5.10/2.20 5.10/2.20 The start-symbols are:[evalEx3start_3] 5.10/2.20 5.10/2.20 5.10/2.20 ---------------------------------------- 5.10/2.20 5.10/2.20 (1) Loat Proof (FINISHED) 5.10/2.20 5.10/2.20 5.10/2.20 ### Pre-processing the ITS problem ### 5.10/2.20 5.10/2.20 5.10/2.20 5.10/2.20 Initial linear ITS problem 5.10/2.20 5.10/2.20 Start location: evalEx3start 5.10/2.20 5.10/2.20 0: evalEx3start -> evalEx3entryin : [], cost: 1 5.10/2.20 5.10/2.20 1: evalEx3entryin -> evalEx3bb4in : [], cost: 1 5.10/2.20 5.10/2.20 2: evalEx3bb4in -> evalEx3bbin : [ A>=1 ], cost: 1 5.10/2.20 5.10/2.20 3: evalEx3bb4in -> evalEx3returnin : [ 0>=A ], cost: 1 5.10/2.20 5.10/2.20 4: evalEx3bbin -> evalEx3bb2in : B'=free, C'=A, [], cost: 1 5.10/2.20 5.10/2.20 5: evalEx3bb2in -> evalEx3bb4in : A'=C, [ 0>=C ], cost: 1 5.10/2.20 5.10/2.20 6: evalEx3bb2in -> evalEx3bb3in : [ C>=1 ], cost: 1 5.10/2.20 5.10/2.20 7: evalEx3bb3in -> evalEx3bb1in : [], cost: 1 5.10/2.20 5.10/2.20 8: evalEx3bb3in -> evalEx3bb4in : A'=C, [ B>=1+free_1 ], cost: 1 5.10/2.20 5.10/2.20 9: evalEx3bb3in -> evalEx3bb4in : A'=C, [ free_2>=1+B ], cost: 1 5.10/2.20 5.10/2.20 10: evalEx3bb1in -> evalEx3bb2in : C'=-1+C, [], cost: 1 5.10/2.20 5.10/2.20 11: evalEx3returnin -> evalEx3stop : [], cost: 1 5.10/2.20 5.10/2.20 5.10/2.20 5.10/2.20 Removed unreachable and leaf rules: 5.10/2.20 5.10/2.20 Start location: evalEx3start 5.10/2.20 5.10/2.20 0: evalEx3start -> evalEx3entryin : [], cost: 1 5.10/2.20 5.10/2.20 1: evalEx3entryin -> evalEx3bb4in : [], cost: 1 5.10/2.20 5.10/2.20 2: evalEx3bb4in -> evalEx3bbin : [ A>=1 ], cost: 1 5.10/2.20 5.10/2.20 4: evalEx3bbin -> evalEx3bb2in : B'=free, C'=A, [], cost: 1 5.10/2.20 5.10/2.20 5: evalEx3bb2in -> evalEx3bb4in : A'=C, [ 0>=C ], cost: 1 5.10/2.20 5.10/2.20 6: evalEx3bb2in -> evalEx3bb3in : [ C>=1 ], cost: 1 5.10/2.20 5.10/2.20 7: evalEx3bb3in -> evalEx3bb1in : [], cost: 1 5.10/2.20 5.10/2.20 8: evalEx3bb3in -> evalEx3bb4in : A'=C, [ B>=1+free_1 ], cost: 1 5.10/2.20 5.10/2.20 9: evalEx3bb3in -> evalEx3bb4in : A'=C, [ free_2>=1+B ], cost: 1 5.10/2.20 5.10/2.20 10: evalEx3bb1in -> evalEx3bb2in : C'=-1+C, [], cost: 1 5.10/2.20 5.10/2.20 5.10/2.20 5.10/2.20 Simplified all rules, resulting in: 5.10/2.20 5.10/2.20 Start location: evalEx3start 5.10/2.20 5.10/2.20 0: evalEx3start -> evalEx3entryin : [], cost: 1 5.10/2.20 5.10/2.20 1: evalEx3entryin -> evalEx3bb4in : [], cost: 1 5.10/2.20 5.10/2.20 2: evalEx3bb4in -> evalEx3bbin : [ A>=1 ], cost: 1 5.10/2.20 5.10/2.20 4: evalEx3bbin -> evalEx3bb2in : B'=free, C'=A, [], cost: 1 5.10/2.20 5.10/2.20 5: evalEx3bb2in -> evalEx3bb4in : A'=C, [ 0>=C ], cost: 1 5.10/2.20 5.10/2.20 6: evalEx3bb2in -> evalEx3bb3in : [ C>=1 ], cost: 1 5.10/2.20 5.10/2.20 7: evalEx3bb3in -> evalEx3bb1in : [], cost: 1 5.10/2.20 5.10/2.20 9: evalEx3bb3in -> evalEx3bb4in : A'=C, [], cost: 1 5.10/2.20 5.10/2.20 10: evalEx3bb1in -> evalEx3bb2in : C'=-1+C, [], cost: 1 5.10/2.20 5.10/2.20 5.10/2.20 5.10/2.20 ### Simplification by acceleration and chaining ### 5.10/2.20 5.10/2.20 5.10/2.20 5.10/2.20 Eliminated locations (on linear paths): 5.10/2.20 5.10/2.20 Start location: evalEx3start 5.10/2.20 5.10/2.20 12: evalEx3start -> evalEx3bb4in : [], cost: 2 5.10/2.20 5.10/2.20 13: evalEx3bb4in -> evalEx3bb2in : B'=free, C'=A, [ A>=1 ], cost: 2 5.10/2.20 5.10/2.20 5: evalEx3bb2in -> evalEx3bb4in : A'=C, [ 0>=C ], cost: 1 5.10/2.20 5.10/2.20 6: evalEx3bb2in -> evalEx3bb3in : [ C>=1 ], cost: 1 5.10/2.20 5.10/2.20 9: evalEx3bb3in -> evalEx3bb4in : A'=C, [], cost: 1 5.10/2.20 5.10/2.20 14: evalEx3bb3in -> evalEx3bb2in : C'=-1+C, [], cost: 2 5.10/2.20 5.10/2.20 5.10/2.20 5.10/2.20 Eliminated locations (on tree-shaped paths): 5.10/2.20 5.10/2.20 Start location: evalEx3start 5.10/2.20 5.10/2.20 12: evalEx3start -> evalEx3bb4in : [], cost: 2 5.10/2.20 5.10/2.20 13: evalEx3bb4in -> evalEx3bb2in : B'=free, C'=A, [ A>=1 ], cost: 2 5.10/2.20 5.10/2.20 5: evalEx3bb2in -> evalEx3bb4in : A'=C, [ 0>=C ], cost: 1 5.10/2.20 5.10/2.20 15: evalEx3bb2in -> evalEx3bb4in : A'=C, [ C>=1 ], cost: 2 5.10/2.20 5.10/2.20 16: evalEx3bb2in -> evalEx3bb2in : C'=-1+C, [ C>=1 ], cost: 3 5.10/2.20 5.10/2.20 5.10/2.20 5.10/2.20 Accelerating simple loops of location 4. 5.10/2.20 5.10/2.20 Accelerating the following rules: 5.10/2.20 5.10/2.20 16: evalEx3bb2in -> evalEx3bb2in : C'=-1+C, [ C>=1 ], cost: 3 5.10/2.20 5.10/2.20 5.10/2.20 5.10/2.20 Accelerated rule 16 with metering function C, yielding the new rule 17. 5.10/2.20 5.10/2.20 Removing the simple loops: 16. 5.10/2.20 5.10/2.20 5.10/2.20 5.10/2.20 Accelerated all simple loops using metering functions (where possible): 5.10/2.20 5.10/2.20 Start location: evalEx3start 5.10/2.20 5.10/2.20 12: evalEx3start -> evalEx3bb4in : [], cost: 2 5.10/2.20 5.10/2.20 13: evalEx3bb4in -> evalEx3bb2in : B'=free, C'=A, [ A>=1 ], cost: 2 5.10/2.20 5.10/2.20 5: evalEx3bb2in -> evalEx3bb4in : A'=C, [ 0>=C ], cost: 1 5.10/2.20 5.10/2.20 15: evalEx3bb2in -> evalEx3bb4in : A'=C, [ C>=1 ], cost: 2 5.10/2.20 5.10/2.20 17: evalEx3bb2in -> evalEx3bb2in : C'=0, [ C>=1 ], cost: 3*C 5.10/2.20 5.10/2.20 5.10/2.20 5.10/2.20 Chained accelerated rules (with incoming rules): 5.10/2.20 5.10/2.20 Start location: evalEx3start 5.10/2.20 5.10/2.20 12: evalEx3start -> evalEx3bb4in : [], cost: 2 5.10/2.20 5.10/2.20 13: evalEx3bb4in -> evalEx3bb2in : B'=free, C'=A, [ A>=1 ], cost: 2 5.10/2.20 5.10/2.20 18: evalEx3bb4in -> evalEx3bb2in : B'=free, C'=0, [ A>=1 ], cost: 2+3*A 5.10/2.20 5.10/2.20 5: evalEx3bb2in -> evalEx3bb4in : A'=C, [ 0>=C ], cost: 1 5.10/2.20 5.10/2.20 15: evalEx3bb2in -> evalEx3bb4in : A'=C, [ C>=1 ], cost: 2 5.10/2.20 5.10/2.20 5.10/2.20 5.10/2.20 Eliminated locations (on tree-shaped paths): 5.10/2.20 5.10/2.20 Start location: evalEx3start 5.10/2.20 5.10/2.20 12: evalEx3start -> evalEx3bb4in : [], cost: 2 5.10/2.20 5.10/2.20 19: evalEx3bb4in -> evalEx3bb4in : A'=A, B'=free, C'=A, [ A>=1 ], cost: 4 5.10/2.20 5.10/2.20 20: evalEx3bb4in -> evalEx3bb4in : A'=0, B'=free, C'=0, [ A>=1 ], cost: 3+3*A 5.10/2.20 5.10/2.20 21: evalEx3bb4in -> [10] : [ A>=1 ], cost: 2+3*A 5.10/2.20 5.10/2.20 5.10/2.20 5.10/2.20 Accelerating simple loops of location 2. 5.10/2.20 5.10/2.20 Simplified some of the simple loops (and removed duplicate rules). 5.10/2.20 5.10/2.20 Accelerating the following rules: 5.10/2.20 5.10/2.20 19: evalEx3bb4in -> evalEx3bb4in : B'=free, C'=A, [ A>=1 ], cost: 4 5.10/2.20 5.10/2.20 20: evalEx3bb4in -> evalEx3bb4in : A'=0, B'=free, C'=0, [ A>=1 ], cost: 3+3*A 5.10/2.20 5.10/2.20 5.10/2.20 5.10/2.20 Accelerated rule 19 with NONTERM, yielding the new rule 22. 5.10/2.20 5.10/2.20 Found no metering function for rule 20. 5.10/2.20 5.10/2.20 Removing the simple loops: 19. 5.10/2.20 5.10/2.20 5.10/2.20 5.10/2.20 Accelerated all simple loops using metering functions (where possible): 5.10/2.20 5.10/2.20 Start location: evalEx3start 5.10/2.20 5.10/2.20 12: evalEx3start -> evalEx3bb4in : [], cost: 2 5.10/2.20 5.10/2.20 20: evalEx3bb4in -> evalEx3bb4in : A'=0, B'=free, C'=0, [ A>=1 ], cost: 3+3*A 5.10/2.20 5.10/2.20 21: evalEx3bb4in -> [10] : [ A>=1 ], cost: 2+3*A 5.10/2.20 5.10/2.20 22: evalEx3bb4in -> [11] : [ A>=1 ], cost: INF 5.10/2.20 5.10/2.20 5.10/2.20 5.10/2.20 Chained accelerated rules (with incoming rules): 5.10/2.20 5.10/2.20 Start location: evalEx3start 5.10/2.20 5.10/2.20 12: evalEx3start -> evalEx3bb4in : [], cost: 2 5.10/2.20 5.10/2.20 23: evalEx3start -> evalEx3bb4in : A'=0, B'=free, C'=0, [ A>=1 ], cost: 5+3*A 5.10/2.20 5.10/2.20 24: evalEx3start -> [11] : [ A>=1 ], cost: INF 5.10/2.20 5.10/2.20 21: evalEx3bb4in -> [10] : [ A>=1 ], cost: 2+3*A 5.10/2.20 5.10/2.20 5.10/2.20 5.10/2.20 Eliminated locations (on tree-shaped paths): 5.10/2.20 5.10/2.20 Start location: evalEx3start 5.10/2.20 5.10/2.20 24: evalEx3start -> [11] : [ A>=1 ], cost: INF 5.10/2.20 5.10/2.20 25: evalEx3start -> [10] : [ A>=1 ], cost: 4+3*A 5.10/2.20 5.10/2.20 26: evalEx3start -> [12] : [ A>=1 ], cost: 5+3*A 5.10/2.20 5.10/2.20 5.10/2.20 5.10/2.20 ### Computing asymptotic complexity ### 5.10/2.20 5.10/2.20 5.10/2.20 5.10/2.20 Fully simplified ITS problem 5.10/2.20 5.10/2.20 Start location: evalEx3start 5.10/2.20 5.10/2.20 24: evalEx3start -> [11] : [ A>=1 ], cost: INF 5.10/2.20 5.10/2.20 26: evalEx3start -> [12] : [ A>=1 ], cost: 5+3*A 5.10/2.20 5.10/2.20 5.10/2.20 5.10/2.20 Computing asymptotic complexity for rule 24 5.10/2.20 5.10/2.20 Resulting cost INF has complexity: Nonterm 5.10/2.20 5.10/2.20 5.10/2.20 5.10/2.20 Found new complexity Nonterm. 5.10/2.20 5.10/2.20 5.10/2.20 5.10/2.20 Obtained the following overall complexity (w.r.t. the length of the input n): 5.10/2.20 5.10/2.20 Complexity: Nonterm 5.10/2.20 5.10/2.20 Cpx degree: Nonterm 5.10/2.20 5.10/2.20 Solved cost: INF 5.10/2.20 5.10/2.20 Rule cost: INF 5.10/2.20 5.10/2.20 Rule guard: [ A>=1 ] 5.10/2.20 5.10/2.20 5.10/2.20 5.10/2.20 NO 5.10/2.20 5.10/2.20 5.10/2.20 ---------------------------------------- 5.10/2.20 5.10/2.20 (2) 5.10/2.20 BOUNDS(INF, INF) 5.10/2.22 EOF