/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, 3533 ms] (2) BOUNDS(INF, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: f2(A, B, C) -> Com_1(f300(A, B, D)) :|: A >= 3 && B >= 2 f2(A, B, C) -> Com_1(f2(1, 2, C)) :|: 1 >= D && B >= 1 && B <= 1 && A >= 1 && A <= 1 f2(A, B, C) -> Com_1(f2(1 + A, 2, C)) :|: A >= 2 && 1 >= D && B >= 1 && B <= 1 f2(A, B, C) -> Com_1(f2(1 + A, 2, C)) :|: 0 >= A && 1 >= D && B >= 1 && B <= 1 f2(A, B, C) -> Com_1(f2(1, 1 + B, C)) :|: B >= 2 && 1 >= B && A >= 1 && A <= 1 f2(A, B, C) -> Com_1(f2(1, 1 + B, C)) :|: 0 >= B && 1 >= B && A >= 1 && A <= 1 f2(A, B, C) -> Com_1(f2(1 + A, 1 + B, C)) :|: 1 >= B && A >= 2 && B >= 2 f2(A, B, C) -> Com_1(f2(1 + A, 1 + B, C)) :|: 1 >= B && A >= 2 && 0 >= B f2(A, B, C) -> Com_1(f2(1 + A, 1 + B, C)) :|: 1 >= B && 0 >= A && B >= 2 f2(A, B, C) -> Com_1(f2(1 + A, 1 + B, C)) :|: 1 >= B && 0 >= A && 0 >= B f2(A, B, C) -> Com_1(f2(1, 1 + B, C)) :|: B >= 2 && 2 >= D && A >= 1 && A <= 1 f2(A, B, C) -> Com_1(f2(1, 1 + B, C)) :|: B >= 2 && 0 >= B && 2 >= D && A >= 1 && A <= 1 f2(A, B, C) -> Com_1(f2(1 + A, 1 + B, C)) :|: B >= 2 && A >= 2 && A <= 2 f2(A, B, C) -> Com_1(f2(1 + A, 1 + B, C)) :|: B >= 2 && 0 >= B && A >= 2 && A <= 2 f2(A, B, C) -> Com_1(f2(1 + A, 1 + B, C)) :|: B >= 2 && 2 >= A && 0 >= A f2(A, B, C) -> Com_1(f2(1 + A, 1 + B, C)) :|: B >= 2 && 2 >= A && 0 >= A && 0 >= B f1(A, B, C) -> Com_1(f2(A, B, C)) :|: TRUE The start-symbols are:[f1_3] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: f1 0: f2 -> f300 : C'=free, [ A>=3 && B>=2 ], cost: 1 1: f2 -> f2 : A'=1, B'=2, [ 1>=free_1 && B==1 && A==1 ], cost: 1 2: f2 -> f2 : A'=1+A, B'=2, [ A>=2 && 1>=free_2 && B==1 ], cost: 1 3: f2 -> f2 : A'=1+A, B'=2, [ 0>=A && 1>=free_3 && B==1 ], cost: 1 4: f2 -> f2 : A'=1, B'=1+B, [ B>=2 && 1>=B && A==1 ], cost: 1 5: f2 -> f2 : A'=1, B'=1+B, [ 0>=B && 1>=B && A==1 ], cost: 1 6: f2 -> f2 : A'=1+A, B'=1+B, [ 1>=B && A>=2 && B>=2 ], cost: 1 7: f2 -> f2 : A'=1+A, B'=1+B, [ 1>=B && A>=2 && 0>=B ], cost: 1 8: f2 -> f2 : A'=1+A, B'=1+B, [ 1>=B && 0>=A && B>=2 ], cost: 1 9: f2 -> f2 : A'=1+A, B'=1+B, [ 1>=B && 0>=A && 0>=B ], cost: 1 10: f2 -> f2 : A'=1, B'=1+B, [ B>=2 && 2>=free_4 && A==1 ], cost: 1 11: f2 -> f2 : A'=1, B'=1+B, [ B>=2 && 0>=B && 2>=free_5 && A==1 ], cost: 1 12: f2 -> f2 : A'=1+A, B'=1+B, [ B>=2 && A==2 ], cost: 1 13: f2 -> f2 : A'=1+A, B'=1+B, [ B>=2 && 0>=B && A==2 ], cost: 1 14: f2 -> f2 : A'=1+A, B'=1+B, [ B>=2 && 2>=A && 0>=A ], cost: 1 15: f2 -> f2 : A'=1+A, B'=1+B, [ B>=2 && 2>=A && 0>=A && 0>=B ], cost: 1 16: f1 -> f2 : [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 16: f1 -> f2 : [], cost: 1 Removed unreachable and leaf rules: Start location: f1 1: f2 -> f2 : A'=1, B'=2, [ 1>=free_1 && B==1 && A==1 ], cost: 1 2: f2 -> f2 : A'=1+A, B'=2, [ A>=2 && 1>=free_2 && B==1 ], cost: 1 3: f2 -> f2 : A'=1+A, B'=2, [ 0>=A && 1>=free_3 && B==1 ], cost: 1 4: f2 -> f2 : A'=1, B'=1+B, [ B>=2 && 1>=B && A==1 ], cost: 1 5: f2 -> f2 : A'=1, B'=1+B, [ 0>=B && 1>=B && A==1 ], cost: 1 6: f2 -> f2 : A'=1+A, B'=1+B, [ 1>=B && A>=2 && B>=2 ], cost: 1 7: f2 -> f2 : A'=1+A, B'=1+B, [ 1>=B && A>=2 && 0>=B ], cost: 1 8: f2 -> f2 : A'=1+A, B'=1+B, [ 1>=B && 0>=A && B>=2 ], cost: 1 9: f2 -> f2 : A'=1+A, B'=1+B, [ 1>=B && 0>=A && 0>=B ], cost: 1 10: f2 -> f2 : A'=1, B'=1+B, [ B>=2 && 2>=free_4 && A==1 ], cost: 1 11: f2 -> f2 : A'=1, B'=1+B, [ B>=2 && 0>=B && 2>=free_5 && A==1 ], cost: 1 12: f2 -> f2 : A'=1+A, B'=1+B, [ B>=2 && A==2 ], cost: 1 13: f2 -> f2 : A'=1+A, B'=1+B, [ B>=2 && 0>=B && A==2 ], cost: 1 14: f2 -> f2 : A'=1+A, B'=1+B, [ B>=2 && 2>=A && 0>=A ], cost: 1 15: f2 -> f2 : A'=1+A, B'=1+B, [ B>=2 && 2>=A && 0>=A && 0>=B ], cost: 1 16: f1 -> f2 : [], cost: 1 Removed rules with unsatisfiable guard: Start location: f1 1: f2 -> f2 : A'=1, B'=2, [ 1>=free_1 && B==1 && A==1 ], cost: 1 2: f2 -> f2 : A'=1+A, B'=2, [ A>=2 && 1>=free_2 && B==1 ], cost: 1 3: f2 -> f2 : A'=1+A, B'=2, [ 0>=A && 1>=free_3 && B==1 ], cost: 1 5: f2 -> f2 : A'=1, B'=1+B, [ 0>=B && 1>=B && A==1 ], cost: 1 7: f2 -> f2 : A'=1+A, B'=1+B, [ 1>=B && A>=2 && 0>=B ], cost: 1 9: f2 -> f2 : A'=1+A, B'=1+B, [ 1>=B && 0>=A && 0>=B ], cost: 1 10: f2 -> f2 : A'=1, B'=1+B, [ B>=2 && 2>=free_4 && A==1 ], cost: 1 12: f2 -> f2 : A'=1+A, B'=1+B, [ B>=2 && A==2 ], cost: 1 14: f2 -> f2 : A'=1+A, B'=1+B, [ B>=2 && 2>=A && 0>=A ], cost: 1 16: f1 -> f2 : [], cost: 1 Simplified all rules, resulting in: Start location: f1 1: f2 -> f2 : A'=1, B'=2, [ B==1 && A==1 ], cost: 1 2: f2 -> f2 : A'=1+A, B'=2, [ A>=2 && B==1 ], cost: 1 3: f2 -> f2 : A'=1+A, B'=2, [ 0>=A && B==1 ], cost: 1 5: f2 -> f2 : A'=1, B'=1+B, [ 0>=B && A==1 ], cost: 1 7: f2 -> f2 : A'=1+A, B'=1+B, [ A>=2 && 0>=B ], cost: 1 9: f2 -> f2 : A'=1+A, B'=1+B, [ 0>=A && 0>=B ], cost: 1 10: f2 -> f2 : A'=1, B'=1+B, [ B>=2 && A==1 ], cost: 1 12: f2 -> f2 : A'=1+A, B'=1+B, [ B>=2 && A==2 ], cost: 1 14: f2 -> f2 : A'=1+A, B'=1+B, [ B>=2 && 0>=A ], cost: 1 16: f1 -> f2 : [], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 0. Accelerating the following rules: 1: f2 -> f2 : A'=1, B'=2, [ B==1 && A==1 ], cost: 1 2: f2 -> f2 : A'=1+A, B'=2, [ A>=2 && B==1 ], cost: 1 3: f2 -> f2 : A'=1+A, B'=2, [ 0>=A && B==1 ], cost: 1 5: f2 -> f2 : A'=1, B'=1+B, [ 0>=B && A==1 ], cost: 1 7: f2 -> f2 : A'=1+A, B'=1+B, [ A>=2 && 0>=B ], cost: 1 9: f2 -> f2 : A'=1+A, B'=1+B, [ 0>=A && 0>=B ], cost: 1 10: f2 -> f2 : A'=1, B'=1+B, [ B>=2 && A==1 ], cost: 1 12: f2 -> f2 : A'=1+A, B'=1+B, [ B>=2 && A==2 ], cost: 1 14: f2 -> f2 : A'=1+A, B'=1+B, [ B>=2 && 0>=A ], cost: 1 Accelerated rule 1 with metering function 2-B, yielding the new rule 17. Accelerated rule 2 with metering function 2-B, yielding the new rule 18. Accelerated rule 3 with metering function 1-B, yielding the new rule 19. Accelerated rule 5 with metering function 1-B, yielding the new rule 20. Accelerated rule 7 with metering function 1-B, yielding the new rule 21. Accelerated rule 9 with metering function 1-A (after adding A>=B), yielding the new rule 22. Accelerated rule 9 with metering function 1-B (after adding A<=B), yielding the new rule 23. Accelerated rule 10 with NONTERM, yielding the new rule 24. Accelerated rule 12 with metering function 3-A, yielding the new rule 25. Accelerated rule 14 with metering function 1-A, yielding the new rule 26. Removing the simple loops: 1 2 3 5 7 9 10 12 14. Accelerated all simple loops using metering functions (where possible): Start location: f1 17: f2 -> f2 : A'=1, B'=2, [ B==1 && A==1 ], cost: 2-B 18: f2 -> f2 : A'=2+A-B, B'=2, [ A>=2 && B==1 ], cost: 2-B 19: f2 -> f2 : A'=1+A-B, B'=2, [ 0>=A && B==1 && 1-B>=1 ], cost: 1-B 20: f2 -> f2 : A'=1, B'=1, [ 0>=B && A==1 ], cost: 1-B 21: f2 -> f2 : A'=1+A-B, B'=1, [ A>=2 && 0>=B ], cost: 1-B 22: f2 -> f2 : A'=1, B'=1-A+B, [ 0>=A && 0>=B && A>=B ], cost: 1-A 23: f2 -> f2 : A'=1+A-B, B'=1, [ 0>=A && 0>=B && A<=B ], cost: 1-B 24: f2 -> [3] : [ B>=2 && A==1 ], cost: NONTERM 25: f2 -> f2 : A'=3, B'=3-A+B, [ B>=2 && A==2 ], cost: 3-A 26: f2 -> f2 : A'=1, B'=1-A+B, [ B>=2 && 0>=A ], cost: 1-A 16: f1 -> f2 : [], cost: 1 Chained accelerated rules (with incoming rules): Start location: f1 16: f1 -> f2 : [], cost: 1 27: f1 -> f2 : A'=1, B'=2, [ B==1 && A==1 ], cost: 3-B 28: f1 -> f2 : A'=2+A-B, B'=2, [ A>=2 && B==1 ], cost: 3-B 29: f1 -> f2 : A'=1, B'=1, [ 0>=B && A==1 ], cost: 2-B 30: f1 -> f2 : A'=1+A-B, B'=1, [ A>=2 && 0>=B ], cost: 2-B 31: f1 -> f2 : A'=1, B'=1-A+B, [ 0>=A && 0>=B && A>=B ], cost: 2-A 32: f1 -> f2 : A'=1+A-B, B'=1, [ 0>=A && 0>=B && A<=B ], cost: 2-B 33: f1 -> [3] : [ B>=2 && A==1 ], cost: NONTERM 34: f1 -> f2 : A'=3, B'=3-A+B, [ B>=2 && A==2 ], cost: 4-A 35: f1 -> f2 : A'=1, B'=1-A+B, [ B>=2 && 0>=A ], cost: 2-A Removed unreachable locations (and leaf rules with constant cost): Start location: f1 27: f1 -> f2 : A'=1, B'=2, [ B==1 && A==1 ], cost: 3-B 28: f1 -> f2 : A'=2+A-B, B'=2, [ A>=2 && B==1 ], cost: 3-B 29: f1 -> f2 : A'=1, B'=1, [ 0>=B && A==1 ], cost: 2-B 30: f1 -> f2 : A'=1+A-B, B'=1, [ A>=2 && 0>=B ], cost: 2-B 31: f1 -> f2 : A'=1, B'=1-A+B, [ 0>=A && 0>=B && A>=B ], cost: 2-A 32: f1 -> f2 : A'=1+A-B, B'=1, [ 0>=A && 0>=B && A<=B ], cost: 2-B 33: f1 -> [3] : [ B>=2 && A==1 ], cost: NONTERM 34: f1 -> f2 : A'=3, B'=3-A+B, [ B>=2 && A==2 ], cost: 4-A 35: f1 -> f2 : A'=1, B'=1-A+B, [ B>=2 && 0>=A ], cost: 2-A ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: f1 27: f1 -> f2 : A'=1, B'=2, [ B==1 && A==1 ], cost: 3-B 28: f1 -> f2 : A'=2+A-B, B'=2, [ A>=2 && B==1 ], cost: 3-B 29: f1 -> f2 : A'=1, B'=1, [ 0>=B && A==1 ], cost: 2-B 30: f1 -> f2 : A'=1+A-B, B'=1, [ A>=2 && 0>=B ], cost: 2-B 31: f1 -> f2 : A'=1, B'=1-A+B, [ 0>=A && 0>=B && A>=B ], cost: 2-A 32: f1 -> f2 : A'=1+A-B, B'=1, [ 0>=A && 0>=B && A<=B ], cost: 2-B 33: f1 -> [3] : [ B>=2 && A==1 ], cost: NONTERM 34: f1 -> f2 : A'=3, B'=3-A+B, [ B>=2 && A==2 ], cost: 4-A 35: f1 -> f2 : A'=1, B'=1-A+B, [ B>=2 && 0>=A ], cost: 2-A Computing asymptotic complexity for rule 27 Could not solve the limit problem. Resulting cost 0 has complexity: Unknown Computing asymptotic complexity for rule 28 Could not solve the limit problem. Resulting cost 0 has complexity: Unknown Computing asymptotic complexity for rule 29 Solved the limit problem by the following transformations: Created initial limit problem: 2-B (+), 2-A (+/+!), 1-B (+/+!), A (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {A==1,B==-n} resulting limit problem: [solved] Solution: A / 1 B / -n Resulting cost 2+n has complexity: Poly(n^1) Found new complexity Poly(n^1). Computing asymptotic complexity for rule 33 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: [ B>=2 && A==1 ] NO ---------------------------------------- (2) BOUNDS(INF, INF)