/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, 937 ms] (2) BOUNDS(INF, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: f0(A, B, C) -> Com_1(f1(0, B, C)) :|: TRUE f1(A, B, C) -> Com_1(f1(A, B - 1, D)) :|: B >= 1 && D >= 1 f1(A, B, C) -> Com_1(f1(A, B - 2, D)) :|: B >= 1 && 0 >= D f1(A, B, C) -> Com_1(f4(A, B, D)) :|: 0 >= B f4(A, B, C) -> Com_1(f4(1, B, D)) :|: C >= 1 f4(A, B, C) -> Com_1(f4(2, B, D)) :|: 0 >= C The start-symbols are:[f0_3] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: f0 0: f0 -> f1 : A'=0, [], cost: 1 1: f1 -> f1 : B'=-1+B, C'=free, [ B>=1 && free>=1 ], cost: 1 2: f1 -> f1 : B'=-2+B, C'=free_1, [ B>=1 && 0>=free_1 ], cost: 1 3: f1 -> f4 : C'=free_2, [ 0>=B ], cost: 1 4: f4 -> f4 : A'=1, C'=free_3, [ C>=1 ], cost: 1 5: f4 -> f4 : A'=2, C'=free_4, [ 0>=C ], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: f0 -> f1 : A'=0, [], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 1. Accelerating the following rules: 1: f1 -> f1 : B'=-1+B, C'=free, [ B>=1 && free>=1 ], cost: 1 2: f1 -> f1 : B'=-2+B, C'=free_1, [ B>=1 && 0>=free_1 ], cost: 1 Accelerated rule 1 with metering function B, yielding the new rule 6. Accelerated rule 2 with metering function meter (where 2*meter==B), yielding the new rule 7. During metering: Instantiating temporary variables by {meter==1} Removing the simple loops: 1 2. Accelerating simple loops of location 2. Accelerating the following rules: 4: f4 -> f4 : A'=1, C'=free_3, [ C>=1 ], cost: 1 5: f4 -> f4 : A'=2, C'=free_4, [ 0>=C ], cost: 1 Accelerated rule 4 with NONTERM (after strengthening guard), yielding the new rule 8. Accelerated rule 5 with NONTERM (after strengthening guard), yielding the new rule 9. Removing the simple loops:. Accelerated all simple loops using metering functions (where possible): Start location: f0 0: f0 -> f1 : A'=0, [], cost: 1 3: f1 -> f4 : C'=free_2, [ 0>=B ], cost: 1 6: f1 -> f1 : B'=0, C'=free, [ B>=1 && free>=1 ], cost: B 7: f1 -> f1 : B'=-2*meter+B, C'=free_1, [ B>=1 && 0>=free_1 && 2*meter==B && meter>=1 ], cost: meter 4: f4 -> f4 : A'=1, C'=free_3, [ C>=1 ], cost: 1 5: f4 -> f4 : A'=2, C'=free_4, [ 0>=C ], cost: 1 8: f4 -> [4] : [ C>=1 && free_3>=1 ], cost: NONTERM 9: f4 -> [4] : [ 0>=C && 0>=free_4 ], cost: NONTERM Chained accelerated rules (with incoming rules): Start location: f0 0: f0 -> f1 : A'=0, [], cost: 1 10: f0 -> f1 : A'=0, B'=0, C'=free, [ B>=1 && free>=1 ], cost: 1+B 11: f0 -> f1 : A'=0, B'=-2*meter+B, C'=free_1, [ B>=1 && 0>=free_1 && 2*meter==B && meter>=1 ], cost: 1+meter 3: f1 -> f4 : C'=free_2, [ 0>=B ], cost: 1 12: f1 -> f4 : A'=1, C'=free_3, [ 0>=B ], cost: 2 13: f1 -> f4 : A'=2, C'=free_4, [ 0>=B ], cost: 2 14: f1 -> [4] : C'=free_2, [ 0>=B && free_2>=1 ], cost: NONTERM 15: f1 -> [4] : C'=free_2, [ 0>=B && 0>=free_2 ], cost: NONTERM Removed unreachable locations (and leaf rules with constant cost): Start location: f0 0: f0 -> f1 : A'=0, [], cost: 1 10: f0 -> f1 : A'=0, B'=0, C'=free, [ B>=1 && free>=1 ], cost: 1+B 11: f0 -> f1 : A'=0, B'=-2*meter+B, C'=free_1, [ B>=1 && 0>=free_1 && 2*meter==B && meter>=1 ], cost: 1+meter 14: f1 -> [4] : C'=free_2, [ 0>=B && free_2>=1 ], cost: NONTERM 15: f1 -> [4] : C'=free_2, [ 0>=B && 0>=free_2 ], cost: NONTERM Eliminated locations (on tree-shaped paths): Start location: f0 16: f0 -> [4] : A'=0, C'=free_2, [ 0>=B && free_2>=1 ], cost: NONTERM 17: f0 -> [4] : A'=0, C'=free_2, [ 0>=B && 0>=free_2 ], cost: NONTERM 18: f0 -> [4] : A'=0, B'=0, C'=free_2, [ B>=1 && free>=1 && free_2>=1 ], cost: NONTERM 19: f0 -> [4] : A'=0, B'=0, C'=free_2, [ B>=1 && free>=1 && 0>=free_2 ], cost: NONTERM 20: f0 -> [4] : A'=0, B'=-2*meter+B, C'=free_2, [ B>=1 && 0>=free_1 && 2*meter==B && meter>=1 && free_2>=1 ], cost: NONTERM 21: f0 -> [4] : A'=0, B'=-2*meter+B, C'=free_2, [ B>=1 && 0>=free_1 && 2*meter==B && meter>=1 && 0>=free_2 ], cost: NONTERM Applied pruning (of leafs and parallel rules): Start location: f0 16: f0 -> [4] : A'=0, C'=free_2, [ 0>=B && free_2>=1 ], cost: NONTERM 17: f0 -> [4] : A'=0, C'=free_2, [ 0>=B && 0>=free_2 ], cost: NONTERM 18: f0 -> [4] : A'=0, B'=0, C'=free_2, [ B>=1 && free>=1 && free_2>=1 ], cost: NONTERM 19: f0 -> [4] : A'=0, B'=0, C'=free_2, [ B>=1 && free>=1 && 0>=free_2 ], cost: NONTERM 21: f0 -> [4] : A'=0, B'=-2*meter+B, C'=free_2, [ B>=1 && 0>=free_1 && 2*meter==B && meter>=1 && 0>=free_2 ], cost: NONTERM ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: f0 16: f0 -> [4] : A'=0, C'=free_2, [ 0>=B && free_2>=1 ], cost: NONTERM 17: f0 -> [4] : A'=0, C'=free_2, [ 0>=B && 0>=free_2 ], cost: NONTERM 18: f0 -> [4] : A'=0, B'=0, C'=free_2, [ B>=1 && free>=1 && free_2>=1 ], cost: NONTERM 19: f0 -> [4] : A'=0, B'=0, C'=free_2, [ B>=1 && free>=1 && 0>=free_2 ], cost: NONTERM 21: f0 -> [4] : A'=0, B'=-2*meter+B, C'=free_2, [ B>=1 && 0>=free_1 && 2*meter==B && meter>=1 && 0>=free_2 ], cost: NONTERM Computing asymptotic complexity for rule 16 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>=B && free_2>=1 ] NO ---------------------------------------- (2) BOUNDS(INF, INF)