/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.koat /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(NON_POLY, ?) proof of /export/starexec/sandbox2/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, 812 ms] (2) BOUNDS(INF, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: f3(A, B, C) -> Com_1(f2(A, B, C)) :|: TRUE f2(A, B, C) -> Com_1(f2(-(1) + E, B, C)) :|: 0 >= A + 1 && 0 >= D && B >= 1 f2(A, B, C) -> Com_1(f2(-(1) + E, B, C)) :|: 0 >= A + 1 && 0 >= D && 0 >= B f2(A, B, C) -> Com_1(f2(1 + E, B, C)) :|: D >= 2 && 0 >= A + 1 f2(A, B, C) -> Com_1(f2(-(1) + E, B, C)) :|: A >= 1 && 0 >= 2 + D && B >= 1 f2(A, B, C) -> Com_1(f2(-(1) + E, B, C)) :|: A >= 1 && 0 >= 2 + D && 0 >= B f2(A, B, C) -> Com_1(f2(1 + E, B, C)) :|: D >= 0 && A >= 1 f2(A, B, C) -> Com_1(f300(0, B, E)) :|: 0 >= A + 1 f2(A, B, C) -> Com_1(f300(0, B, E)) :|: A >= 1 f2(A, B, C) -> Com_1(f300(A, B, E)) :|: A >= 0 && A <= 0 The start-symbols are:[f3_3] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: f3 0: f3 -> f2 : [], cost: 1 1: f2 -> f2 : A'=-1+free_1, [ 0>=1+A && 0>=free && B>=1 ], cost: 1 2: f2 -> f2 : A'=-1+free_3, [ 0>=1+A && 0>=free_2 && 0>=B ], cost: 1 3: f2 -> f2 : A'=1+free_5, [ free_4>=2 && 0>=1+A ], cost: 1 4: f2 -> f2 : A'=-1+free_7, [ A>=1 && 0>=2+free_6 && B>=1 ], cost: 1 5: f2 -> f2 : A'=-1+free_9, [ A>=1 && 0>=2+free_8 && 0>=B ], cost: 1 6: f2 -> f2 : A'=1+free_11, [ free_10>=0 && A>=1 ], cost: 1 7: f2 -> f300 : A'=0, C'=free_12, [ 0>=1+A ], cost: 1 8: f2 -> f300 : A'=0, C'=free_13, [ A>=1 ], cost: 1 9: f2 -> f300 : C'=free_14, [ A==0 ], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: f3 -> f2 : [], cost: 1 Removed unreachable and leaf rules: Start location: f3 0: f3 -> f2 : [], cost: 1 1: f2 -> f2 : A'=-1+free_1, [ 0>=1+A && 0>=free && B>=1 ], cost: 1 2: f2 -> f2 : A'=-1+free_3, [ 0>=1+A && 0>=free_2 && 0>=B ], cost: 1 3: f2 -> f2 : A'=1+free_5, [ free_4>=2 && 0>=1+A ], cost: 1 4: f2 -> f2 : A'=-1+free_7, [ A>=1 && 0>=2+free_6 && B>=1 ], cost: 1 5: f2 -> f2 : A'=-1+free_9, [ A>=1 && 0>=2+free_8 && 0>=B ], cost: 1 6: f2 -> f2 : A'=1+free_11, [ free_10>=0 && A>=1 ], cost: 1 Simplified all rules, resulting in: Start location: f3 0: f3 -> f2 : [], cost: 1 1: f2 -> f2 : A'=-1+free_1, [ 0>=1+A && B>=1 ], cost: 1 2: f2 -> f2 : A'=-1+free_3, [ 0>=1+A && 0>=B ], cost: 1 3: f2 -> f2 : A'=1+free_5, [ 0>=1+A ], cost: 1 4: f2 -> f2 : A'=-1+free_7, [ A>=1 && B>=1 ], cost: 1 5: f2 -> f2 : A'=-1+free_9, [ A>=1 && 0>=B ], cost: 1 6: f2 -> f2 : A'=1+free_11, [ A>=1 ], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 1. Accelerating the following rules: 1: f2 -> f2 : A'=-1+free_1, [ 0>=1+A && B>=1 ], cost: 1 2: f2 -> f2 : A'=-1+free_3, [ 0>=1+A && 0>=B ], cost: 1 3: f2 -> f2 : A'=1+free_5, [ 0>=1+A ], cost: 1 4: f2 -> f2 : A'=-1+free_7, [ A>=1 && B>=1 ], cost: 1 5: f2 -> f2 : A'=-1+free_9, [ A>=1 && 0>=B ], cost: 1 6: f2 -> f2 : A'=1+free_11, [ A>=1 ], cost: 1 Accelerated rule 1 with NONTERM (after strengthening guard), yielding the new rule 10. Accelerated rule 2 with NONTERM (after strengthening guard), yielding the new rule 11. Accelerated rule 3 with NONTERM (after strengthening guard), yielding the new rule 12. Accelerated rule 4 with NONTERM (after strengthening guard), yielding the new rule 13. Accelerated rule 5 with NONTERM (after strengthening guard), yielding the new rule 14. Accelerated rule 6 with NONTERM (after strengthening guard), yielding the new rule 15. Removing the simple loops:. Accelerated all simple loops using metering functions (where possible): Start location: f3 0: f3 -> f2 : [], cost: 1 1: f2 -> f2 : A'=-1+free_1, [ 0>=1+A && B>=1 ], cost: 1 2: f2 -> f2 : A'=-1+free_3, [ 0>=1+A && 0>=B ], cost: 1 3: f2 -> f2 : A'=1+free_5, [ 0>=1+A ], cost: 1 4: f2 -> f2 : A'=-1+free_7, [ A>=1 && B>=1 ], cost: 1 5: f2 -> f2 : A'=-1+free_9, [ A>=1 && 0>=B ], cost: 1 6: f2 -> f2 : A'=1+free_11, [ A>=1 ], cost: 1 10: f2 -> [3] : [ 0>=1+A && B>=1 && 0>=free_1 ], cost: NONTERM 11: f2 -> [3] : [ 0>=1+A && 0>=B && 0>=free_3 ], cost: NONTERM 12: f2 -> [3] : [ 0>=1+A && 0>=2+free_5 ], cost: NONTERM 13: f2 -> [3] : [ A>=1 && B>=1 && -1+free_7>=1 ], cost: NONTERM 14: f2 -> [3] : [ A>=1 && 0>=B && -1+free_9>=1 ], cost: NONTERM 15: f2 -> [3] : [ A>=1 && 1+free_11>=1 ], cost: NONTERM Chained accelerated rules (with incoming rules): Start location: f3 0: f3 -> f2 : [], cost: 1 16: f3 -> f2 : A'=-1+free_1, [ 0>=1+A && B>=1 ], cost: 2 17: f3 -> f2 : A'=-1+free_3, [ 0>=1+A && 0>=B ], cost: 2 18: f3 -> f2 : A'=1+free_5, [ 0>=1+A ], cost: 2 19: f3 -> f2 : A'=-1+free_7, [ A>=1 && B>=1 ], cost: 2 20: f3 -> f2 : A'=-1+free_9, [ A>=1 && 0>=B ], cost: 2 21: f3 -> f2 : A'=1+free_11, [ A>=1 ], cost: 2 22: f3 -> [3] : [ 0>=1+A && B>=1 ], cost: NONTERM 23: f3 -> [3] : [ 0>=1+A && 0>=B ], cost: NONTERM 24: f3 -> [3] : [ 0>=1+A ], cost: NONTERM 25: f3 -> [3] : [ A>=1 && B>=1 ], cost: NONTERM 26: f3 -> [3] : [ A>=1 && 0>=B ], cost: NONTERM 27: f3 -> [3] : [ A>=1 ], cost: NONTERM Removed unreachable locations (and leaf rules with constant cost): Start location: f3 22: f3 -> [3] : [ 0>=1+A && B>=1 ], cost: NONTERM 23: f3 -> [3] : [ 0>=1+A && 0>=B ], cost: NONTERM 24: f3 -> [3] : [ 0>=1+A ], cost: NONTERM 25: f3 -> [3] : [ A>=1 && B>=1 ], cost: NONTERM 26: f3 -> [3] : [ A>=1 && 0>=B ], cost: NONTERM 27: f3 -> [3] : [ A>=1 ], cost: NONTERM ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: f3 22: f3 -> [3] : [ 0>=1+A && B>=1 ], cost: NONTERM 23: f3 -> [3] : [ 0>=1+A && 0>=B ], cost: NONTERM 24: f3 -> [3] : [ 0>=1+A ], cost: NONTERM 25: f3 -> [3] : [ A>=1 && B>=1 ], cost: NONTERM 26: f3 -> [3] : [ A>=1 && 0>=B ], cost: NONTERM 27: f3 -> [3] : [ A>=1 ], cost: NONTERM Computing asymptotic complexity for rule 22 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: [ 0>=1+A && B>=1 ] NO ---------------------------------------- (2) BOUNDS(INF, INF)