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