/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, 1340 ms] (2) BOUNDS(INF, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: f11(A, B, C) -> Com_1(f14(A, B, C)) :|: A >= 6 f11(A, B, C) -> Com_1(f14(A, B, C)) :|: 5 >= A && 0 >= B f14(A, B, C) -> Com_1(f11(A + 1, D, C)) :|: A >= 6 f26(A, B, C) -> Com_1(f27(A, B, C)) :|: TRUE f27(A, B, C) -> Com_1(f27(A, B, C)) :|: TRUE f29(A, B, C) -> Com_1(f32(A, B, C)) :|: TRUE f20(A, B, C) -> Com_1(f20(A - 1, B, C)) :|: A >= 3 f20(A, B, C) -> Com_1(f11(A, D, C)) :|: 2 >= A f14(A, B, C) -> Com_1(f11(A + 1, D, C)) :|: 5 >= A f11(A, B, C) -> Com_1(f20(A, B, C)) :|: 5 >= A && B >= 1 f0(A, B, C) -> Com_1(f11(D, E, D)) :|: TRUE The start-symbols are:[f0_3] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: f0 0: f11 -> f14 : [ A>=6 ], cost: 1 1: f11 -> f14 : [ 5>=A && 0>=B ], cost: 1 9: f11 -> f20 : [ 5>=A && B>=1 ], cost: 1 2: f14 -> f11 : A'=1+A, B'=free, [ A>=6 ], cost: 1 8: f14 -> f11 : A'=1+A, B'=free_2, [ 5>=A ], cost: 1 3: f26 -> f27 : [], cost: 1 4: f27 -> f27 : [], cost: 1 5: f29 -> f32 : [], cost: 1 6: f20 -> f20 : A'=-1+A, [ A>=3 ], cost: 1 7: f20 -> f11 : B'=free_1, [ 2>=A ], cost: 1 10: f0 -> f11 : A'=free_3, B'=free_4, C'=free_3, [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 10: f0 -> f11 : A'=free_3, B'=free_4, C'=free_3, [], cost: 1 Removed unreachable and leaf rules: Start location: f0 0: f11 -> f14 : [ A>=6 ], cost: 1 1: f11 -> f14 : [ 5>=A && 0>=B ], cost: 1 9: f11 -> f20 : [ 5>=A && B>=1 ], cost: 1 2: f14 -> f11 : A'=1+A, B'=free, [ A>=6 ], cost: 1 8: f14 -> f11 : A'=1+A, B'=free_2, [ 5>=A ], cost: 1 6: f20 -> f20 : A'=-1+A, [ A>=3 ], cost: 1 7: f20 -> f11 : B'=free_1, [ 2>=A ], cost: 1 10: f0 -> f11 : A'=free_3, B'=free_4, C'=free_3, [], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 5. Accelerating the following rules: 6: f20 -> f20 : A'=-1+A, [ A>=3 ], cost: 1 Accelerated rule 6 with metering function -2+A, yielding the new rule 11. Removing the simple loops: 6. Accelerated all simple loops using metering functions (where possible): Start location: f0 0: f11 -> f14 : [ A>=6 ], cost: 1 1: f11 -> f14 : [ 5>=A && 0>=B ], cost: 1 9: f11 -> f20 : [ 5>=A && B>=1 ], cost: 1 2: f14 -> f11 : A'=1+A, B'=free, [ A>=6 ], cost: 1 8: f14 -> f11 : A'=1+A, B'=free_2, [ 5>=A ], cost: 1 7: f20 -> f11 : B'=free_1, [ 2>=A ], cost: 1 11: f20 -> f20 : A'=2, [ A>=3 ], cost: -2+A 10: f0 -> f11 : A'=free_3, B'=free_4, C'=free_3, [], cost: 1 Chained accelerated rules (with incoming rules): Start location: f0 0: f11 -> f14 : [ A>=6 ], cost: 1 1: f11 -> f14 : [ 5>=A && 0>=B ], cost: 1 9: f11 -> f20 : [ 5>=A && B>=1 ], cost: 1 12: f11 -> f20 : A'=2, [ 5>=A && B>=1 && A>=3 ], cost: -1+A 2: f14 -> f11 : A'=1+A, B'=free, [ A>=6 ], cost: 1 8: f14 -> f11 : A'=1+A, B'=free_2, [ 5>=A ], cost: 1 7: f20 -> f11 : B'=free_1, [ 2>=A ], cost: 1 10: f0 -> f11 : A'=free_3, B'=free_4, C'=free_3, [], cost: 1 Eliminated locations (on tree-shaped paths): Start location: f0 13: f11 -> f11 : A'=1+A, B'=free, [ A>=6 ], cost: 2 14: f11 -> f11 : A'=1+A, B'=free_2, [ 5>=A && 0>=B ], cost: 2 15: f11 -> f11 : B'=free_1, [ B>=1 && 2>=A ], cost: 2 16: f11 -> f11 : A'=2, B'=free_1, [ 5>=A && B>=1 && A>=3 ], cost: A 10: f0 -> f11 : A'=free_3, B'=free_4, C'=free_3, [], cost: 1 Accelerating simple loops of location 0. Accelerating the following rules: 13: f11 -> f11 : A'=1+A, B'=free, [ A>=6 ], cost: 2 14: f11 -> f11 : A'=1+A, B'=free_2, [ 5>=A && 0>=B ], cost: 2 15: f11 -> f11 : B'=free_1, [ B>=1 && 2>=A ], cost: 2 16: f11 -> f11 : A'=2, B'=free_1, [ 5>=A && B>=1 && A>=3 ], cost: A Accelerated rule 13 with NONTERM, yielding the new rule 17. Accelerated rule 14 with metering function 6-A (after strengthening guard), yielding the new rule 18. Accelerated rule 15 with NONTERM (after strengthening guard), yielding the new rule 19. Accelerated rule 16 with metering function meter (where 3*meter==-2+A) (after strengthening guard), yielding the new rule 20. Nested simple loops 14 (outer loop) and 20 (inner loop) with metering function meter_1 (where 2*meter_1==-3-meter+A), resulting in the new rules: 21. Nested simple loops 15 (outer loop) and 20 (inner loop) with metering function meter_2 (where 3*meter_2==-4-meter+A), resulting in the new rules: 22. Removing the simple loops: 13 14 15. Accelerated all simple loops using metering functions (where possible): Start location: f0 16: f11 -> f11 : A'=2, B'=free_1, [ 5>=A && B>=1 && A>=3 ], cost: A 17: f11 -> [9] : [ A>=6 ], cost: NONTERM 18: f11 -> f11 : A'=6, B'=free_2, [ 5>=A && 0>=B && 0>=free_2 ], cost: 12-2*A 19: f11 -> [9] : [ B>=1 && 2>=A && free_1>=1 ], cost: NONTERM 20: f11 -> f11 : A'=2, B'=free_1, [ 5>=A && B>=1 && A>=3 && free_1>=1 && 3*meter==-2+A && meter>=1 ], cost: 2*meter 21: f11 -> f11 : A'=2, B'=free_1, [ 0>=B && 5>=1+A && 1+A>=3 && free_1>=1 && 3*meter==-1+A && meter>=1 && 2*meter_1==-3-meter+A && meter_1>=1 ], cost: 2*meter*meter_1+2*meter_1 22: f11 -> f11 : A'=2, B'=free_1, [ 5>=A && B>=1 && A>=3 && free_1>=1 && 3*meter==-2+A && meter>=1 && 3*meter_2==-4-meter+A && meter_2>=1 ], cost: 2*meter_2+2*meter*meter_2 10: f0 -> f11 : A'=free_3, B'=free_4, C'=free_3, [], cost: 1 Chained accelerated rules (with incoming rules): Start location: f0 10: f0 -> f11 : A'=free_3, B'=free_4, C'=free_3, [], cost: 1 23: f0 -> f11 : A'=2, B'=free_1, C'=free_3, [ 5>=free_3 && free_3>=3 ], cost: 1+free_3 24: f0 -> [9] : A'=free_3, B'=free_4, C'=free_3, [ free_3>=6 ], cost: NONTERM 25: f0 -> f11 : A'=6, B'=free_2, C'=free_3, [ 5>=free_3 && 0>=free_2 ], cost: 13-2*free_3 26: f0 -> [9] : A'=free_3, B'=free_4, C'=free_3, [ free_4>=1 && 2>=free_3 ], cost: NONTERM 27: f0 -> f11 : A'=2, B'=free_1, C'=2+3*meter, [ 5>=2+3*meter && 2+3*meter>=3 && free_1>=1 && meter>=1 ], cost: 1+2*meter Removed unreachable locations (and leaf rules with constant cost): Start location: f0 23: f0 -> f11 : A'=2, B'=free_1, C'=free_3, [ 5>=free_3 && free_3>=3 ], cost: 1+free_3 24: f0 -> [9] : A'=free_3, B'=free_4, C'=free_3, [ free_3>=6 ], cost: NONTERM 25: f0 -> f11 : A'=6, B'=free_2, C'=free_3, [ 5>=free_3 && 0>=free_2 ], cost: 13-2*free_3 26: f0 -> [9] : A'=free_3, B'=free_4, C'=free_3, [ free_4>=1 && 2>=free_3 ], cost: NONTERM 27: f0 -> f11 : A'=2, B'=free_1, C'=2+3*meter, [ 5>=2+3*meter && 2+3*meter>=3 && free_1>=1 && meter>=1 ], cost: 1+2*meter ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: f0 23: f0 -> f11 : A'=2, B'=free_1, C'=free_3, [ 5>=free_3 && free_3>=3 ], cost: 1+free_3 24: f0 -> [9] : A'=free_3, B'=free_4, C'=free_3, [ free_3>=6 ], cost: NONTERM 25: f0 -> f11 : A'=6, B'=free_2, C'=free_3, [ 5>=free_3 && 0>=free_2 ], cost: 13-2*free_3 26: f0 -> [9] : A'=free_3, B'=free_4, C'=free_3, [ free_4>=1 && 2>=free_3 ], cost: NONTERM 27: f0 -> f11 : A'=2, B'=free_1, C'=2+3*meter, [ 5>=2+3*meter && 2+3*meter>=3 && free_1>=1 && meter>=1 ], cost: 1+2*meter Computing asymptotic complexity for rule 23 Could not solve the limit problem. Resulting cost 0 has complexity: Unknown 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: [ free_3>=6 ] NO ---------------------------------------- (2) BOUNDS(INF, INF)