/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.koat /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^1)) proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, nat(2 * Arg_2) + max(1, 1 + Arg_0 + -1 * Arg_1)). (0) CpxIntTrs (1) Koat2 Proof [FINISHED, 231 ms] (2) BOUNDS(1, nat(2 * Arg_2) + max(1, 1 + Arg_0 + -1 * Arg_1)) (3) Loat Proof [FINISHED, 1528 ms] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: eval0(A, B, C) -> Com_1(eval1(A, B, C)) :|: A >= 1 eval1(A, B, C) -> Com_1(eval1(A, B + A, C)) :|: A >= B + 1 && C >= A + 1 && A >= 1 eval1(A, B, C) -> Com_1(eval1(A, B, B - A)) :|: A >= B + 1 && C >= A + 1 && A >= 1 The start-symbols are:[eval0_3] ---------------------------------------- (1) Koat2 Proof (FINISHED) YES( ?, max([0, 2*Arg_2])+max([1, 1+Arg_0-Arg_1]) {O(n)}) Initial Complexity Problem: Start: eval0 Program_Vars: Arg_0, Arg_1, Arg_2 Temp_Vars: Locations: eval0, eval1 Transitions: eval0(Arg_0,Arg_1,Arg_2) -> eval1(Arg_0,Arg_1,Arg_2):|:1 <= Arg_0 eval1(Arg_0,Arg_1,Arg_2) -> eval1(Arg_0,Arg_1+Arg_0,Arg_2):|:1 <= Arg_0 && Arg_1+1 <= Arg_0 && Arg_0+1 <= Arg_2 && 1 <= Arg_0 eval1(Arg_0,Arg_1,Arg_2) -> eval1(Arg_0,Arg_1,Arg_1-Arg_0):|:1 <= Arg_0 && Arg_1+1 <= Arg_0 && Arg_0+1 <= Arg_2 && 1 <= Arg_0 Timebounds: Overall timebound: max([0, 2*Arg_2])+max([1, 1+Arg_0-Arg_1]) {O(n)} 0: eval0->eval1: 1 {O(1)} 1: eval1->eval1: max([0, Arg_0-Arg_1]) {O(n)} 2: eval1->eval1: max([0, 2*Arg_2]) {O(n)} Costbounds: Overall costbound: max([0, 2*Arg_2])+max([1, 1+Arg_0-Arg_1]) {O(n)} 0: eval0->eval1: 1 {O(1)} 1: eval1->eval1: max([0, Arg_0-Arg_1]) {O(n)} 2: eval1->eval1: max([0, 2*Arg_2]) {O(n)} Sizebounds: `Lower: 0: eval0->eval1, Arg_0: 1 {O(1)} 0: eval0->eval1, Arg_1: Arg_1 {O(n)} 0: eval0->eval1, Arg_2: Arg_2 {O(n)} 1: eval1->eval1, Arg_0: 1 {O(1)} 1: eval1->eval1, Arg_1: Arg_1 {O(n)} 1: eval1->eval1, Arg_2: 2 {O(1)} 2: eval1->eval1, Arg_0: 1 {O(1)} 2: eval1->eval1, Arg_1: Arg_1 {O(n)} 2: eval1->eval1, Arg_2: Arg_1-Arg_0 {O(n)} `Upper: 0: eval0->eval1, Arg_0: Arg_0 {O(n)} 0: eval0->eval1, Arg_1: Arg_1 {O(n)} 0: eval0->eval1, Arg_2: Arg_2 {O(n)} 1: eval1->eval1, Arg_0: Arg_0 {O(n)} 1: eval1->eval1, Arg_1: 2*Arg_0 {O(n)} 1: eval1->eval1, Arg_2: Arg_2 {O(n)} 2: eval1->eval1, Arg_0: Arg_0 {O(n)} 2: eval1->eval1, Arg_1: max([Arg_1, 2*Arg_0]) {O(n)} 2: eval1->eval1, Arg_2: -1 {O(1)} ---------------------------------------- (2) BOUNDS(1, nat(2 * Arg_2) + max(1, 1 + Arg_0 + -1 * Arg_1)) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: eval0 0: eval0 -> eval1 : [ A>=1 ], cost: 1 1: eval1 -> eval1 : B'=A+B, [ A>=1+B && C>=1+A && A>=1 ], cost: 1 2: eval1 -> eval1 : C'=-A+B, [ A>=1+B && C>=1+A && A>=1 ], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 1. Accelerating the following rules: 1: eval1 -> eval1 : B'=A+B, [ A>=1+B && C>=1+A && A>=1 ], cost: 1 2: eval1 -> eval1 : C'=-A+B, [ A>=1+B && C>=1+A && A>=1 ], cost: 1 Accelerated rule 1 with backward acceleration, yielding the new rule 3. Accelerated rule 2 with NONTERM (after strengthening guard), yielding the new rule 4. Removing the simple loops: 1. Accelerated all simple loops using metering functions (where possible): Start location: eval0 0: eval0 -> eval1 : [ A>=1 ], cost: 1 2: eval1 -> eval1 : C'=-A+B, [ A>=1+B && C>=1+A && A>=1 ], cost: 1 3: eval1 -> eval1 : B'=A*k+B, [ A>=1+B && C>=1+A && A>=1 && k>0 && A>=1+A*(-1+k)+B ], cost: k 4: eval1 -> [2] : [ A>=1+B && C>=1+A && A>=1 && -A+B>=1+A ], cost: INF Chained accelerated rules (with incoming rules): Start location: eval0 0: eval0 -> eval1 : [ A>=1 ], cost: 1 5: eval0 -> eval1 : C'=-A+B, [ A>=1 && A>=1+B && C>=1+A ], cost: 2 6: eval0 -> eval1 : B'=A*k+B, [ A>=1 && A>=1+B && C>=1+A && k>0 && A>=1+A*(-1+k)+B ], cost: 1+k Removed unreachable locations (and leaf rules with constant cost): Start location: eval0 6: eval0 -> eval1 : B'=A*k+B, [ A>=1 && A>=1+B && C>=1+A && k>0 && A>=1+A*(-1+k)+B ], cost: 1+k ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: eval0 6: eval0 -> eval1 : B'=A*k+B, [ A>=1 && A>=1+B && C>=1+A && k>0 && A>=1+A*(-1+k)+B ], cost: 1+k Computing asymptotic complexity for rule 6 Solved the limit problem by the following transformations: Created initial limit problem: 1+k (+), -A*(-1+k)+A-B (+/+!), A (+/+!), C-A (+/+!), k (+/+!), A-B (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {C==n,A==1,k==1+n,B==-n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 1+k (+), -A*(-1+k)+A-B (+/+!), A (+/+!), C-A (+/+!), k (+/+!), A-B (+/+!) [not solved] applying transformation rule (C) using substitution {A==1} resulting limit problem: 2-k-B (+/+!), 1 (+/+!), 1+k (+), 1-B (+/+!), k (+/+!), -1+C (+/+!) [not solved] applying transformation rule (C) using substitution {A==1+B} resulting limit problem: 2-k-B (+/+!), 1 (+/+!), 1+k (+), 1-B (+/+!), k (+/+!), -1+C (+/+!) [not solved] applying transformation rule (C) using substitution {C==1+A} resulting limit problem: 2-k-B (+/+!), 1 (+/+!), 1+k (+), 1-B (+/+!), A (+/+!), k (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 2-k-B (+/+!), 1+k (+), 1-B (+/+!), A (+/+!), k (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {A==n,k==n,B==-n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 1+k (+), -A*(-1+k)+A-B (+/+!), A (+/+!), C-A (+/+!), k (+/+!), A-B (+/+!) [not solved] applying transformation rule (C) using substitution {A==1} resulting limit problem: 2-k-B (+/+!), 1 (+/+!), 1+k (+), 1-B (+/+!), k (+/+!), -1+C (+/+!) [not solved] applying transformation rule (C) using substitution {C==1+A} resulting limit problem: 2-k-B (+/+!), 1 (+/+!), 1+k (+), 1-B (+/+!), A (+/+!), k (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 2-k-B (+/+!), 1+k (+), 1-B (+/+!), A (+/+!), k (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {A==n,k==n,B==-n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 1+k (+), -A*(-1+k)+A-B (+/+!), A (+/+!), C-A (+/+!), k (+/+!), A-B (+/+!) [not solved] applying transformation rule (C) using substitution {C==1+A} resulting limit problem: 1 (+/+!), 1+k (+), -A*(-1+k)+A-B (+/+!), A (+/+!), k (+/+!), A-B (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 1+k (+), -A*(-1+k)+A-B (+/+!), A (+/+!), k (+/+!), A-B (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {A==1,k==n,B==1-n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 1+k (+), -A*(-1+k)+A-B (+/+!), A (+/+!), C-A (+/+!), k (+/+!), A-B (+/+!) [not solved] applying transformation rule (C) using substitution {A==1} resulting limit problem: 2-k-B (+/+!), 1 (+/+!), 1+k (+), 1-B (+/+!), k (+/+!), -1+C (+/+!) [not solved] applying transformation rule (C) using substitution {A==1+B} resulting limit problem: 2-k-B (+/+!), 1 (+/+!), 1+k (+), 1-B (+/+!), k (+/+!), -1+C (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 2-k-B (+/+!), 1+k (+), 1-B (+/+!), k (+/+!), -1+C (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {C==n,k==n,B==-n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 1+k (+), -A*(-1+k)+A-B (+/+!), A (+/+!), C-A (+/+!), k (+/+!), A-B (+/+!) [not solved] applying transformation rule (C) using substitution {A==1} resulting limit problem: 2-k-B (+/+!), 1 (+/+!), 1+k (+), 1-B (+/+!), k (+/+!), -1+C (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 2-k-B (+/+!), 1+k (+), 1-B (+/+!), k (+/+!), -1+C (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {C==n,k==n,B==-n} resulting limit problem: [solved] Solution: C / n A / 1 k / 1+n B / -n Resulting cost 2+n has complexity: Poly(n^1) Found new complexity Poly(n^1). Obtained the following overall complexity (w.r.t. the length of the input n): Complexity: Poly(n^1) Cpx degree: 1 Solved cost: 2+n Rule cost: 1+k Rule guard: [ A>=1 && A>=1+B && C>=1+A && k>0 && A>=1+A*(-1+k)+B ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (4) BOUNDS(n^1, INF)