/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.koat /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^2), O(n^2)) 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(n^2, n^2). (0) CpxIntTrs (1) Koat Proof [FINISHED, 16 ms] (2) BOUNDS(1, n^2) (3) Loat Proof [FINISHED, 296 ms] (4) BOUNDS(n^2, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: l0(A, B, C, D) -> Com_1(l1(0, B, C, D)) :|: TRUE l1(A, B, C, D) -> Com_1(l2(A, B, 0, 0)) :|: B >= 1 l2(A, B, C, D) -> Com_1(l2(A, B, C + 1, D + C)) :|: B >= C + 1 l2(A, B, C, D) -> Com_1(l1(A + D, B - 1, C, D)) :|: C >= B The start-symbols are:[l0_4] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 8*Ar_1 + 2*Ar_1^2 + 7) Initial complexity problem: 1: T: (Comp: ?, Cost: 1) l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, 0, 0)) [ Ar_1 >= 1 ] (Comp: ?, Cost: 1) l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 + 1, Ar_3 + Ar_2)) [ Ar_1 >= Ar_2 + 1 ] (Comp: ?, Cost: 1) l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + Ar_3, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_2 >= Ar_1 ] (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Repeatedly propagating knowledge in problem 1 produces the following problem: 2: T: (Comp: 1, Cost: 1) l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, 0, 0)) [ Ar_1 >= 1 ] (Comp: ?, Cost: 1) l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 + 1, Ar_3 + Ar_2)) [ Ar_1 >= Ar_2 + 1 ] (Comp: ?, Cost: 1) l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + Ar_3, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_2 >= Ar_1 ] (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(l0) = V_2 + 1 Pol(l1) = V_2 + 1 Pol(l2) = V_2 Pol(koat_start) = V_2 + 1 orients all transitions weakly and the transition l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, 0, 0)) [ Ar_1 >= 1 ] strictly and produces the following problem: 3: T: (Comp: 1, Cost: 1) l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3)) (Comp: Ar_1 + 1, Cost: 1) l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, 0, 0)) [ Ar_1 >= 1 ] (Comp: ?, Cost: 1) l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 + 1, Ar_3 + Ar_2)) [ Ar_1 >= Ar_2 + 1 ] (Comp: ?, Cost: 1) l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + Ar_3, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_2 >= Ar_1 ] (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(l2) = 1 Pol(l1) = 0 and size complexities S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-0) = Ar_0 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-1) = Ar_1 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-2) = Ar_2 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-3) = Ar_3 S("l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + Ar_3, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_2 >= Ar_1 ]", 0-0) = ? S("l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + Ar_3, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_2 >= Ar_1 ]", 0-1) = ? S("l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + Ar_3, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_2 >= Ar_1 ]", 0-2) = ? S("l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + Ar_3, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_2 >= Ar_1 ]", 0-3) = ? S("l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 + 1, Ar_3 + Ar_2)) [ Ar_1 >= Ar_2 + 1 ]", 0-0) = ? S("l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 + 1, Ar_3 + Ar_2)) [ Ar_1 >= Ar_2 + 1 ]", 0-1) = ? S("l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 + 1, Ar_3 + Ar_2)) [ Ar_1 >= Ar_2 + 1 ]", 0-2) = ? S("l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 + 1, Ar_3 + Ar_2)) [ Ar_1 >= Ar_2 + 1 ]", 0-3) = ? S("l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, 0, 0)) [ Ar_1 >= 1 ]", 0-0) = ? S("l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, 0, 0)) [ Ar_1 >= 1 ]", 0-1) = ? S("l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, 0, 0)) [ Ar_1 >= 1 ]", 0-2) = 0 S("l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, 0, 0)) [ Ar_1 >= 1 ]", 0-3) = 0 S("l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3))", 0-0) = 0 S("l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3))", 0-1) = Ar_1 S("l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3))", 0-2) = Ar_2 S("l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3))", 0-3) = Ar_3 orients the transitions l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 + 1, Ar_3 + Ar_2)) [ Ar_1 >= Ar_2 + 1 ] l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + Ar_3, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_2 >= Ar_1 ] weakly and the transition l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + Ar_3, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_2 >= Ar_1 ] strictly and produces the following problem: 4: T: (Comp: 1, Cost: 1) l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3)) (Comp: Ar_1 + 1, Cost: 1) l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, 0, 0)) [ Ar_1 >= 1 ] (Comp: ?, Cost: 1) l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 + 1, Ar_3 + Ar_2)) [ Ar_1 >= Ar_2 + 1 ] (Comp: Ar_1 + 1, Cost: 1) l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + Ar_3, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_2 >= Ar_1 ] (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(l2) = V_2 - V_3 and size complexities S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-0) = Ar_0 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-1) = Ar_1 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-2) = Ar_2 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-3) = Ar_3 S("l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + Ar_3, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_2 >= Ar_1 ]", 0-0) = ? S("l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + Ar_3, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_2 >= Ar_1 ]", 0-1) = 2*Ar_1 + 4 S("l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + Ar_3, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_2 >= Ar_1 ]", 0-2) = ? S("l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + Ar_3, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_2 >= Ar_1 ]", 0-3) = ? S("l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 + 1, Ar_3 + Ar_2)) [ Ar_1 >= Ar_2 + 1 ]", 0-0) = ? S("l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 + 1, Ar_3 + Ar_2)) [ Ar_1 >= Ar_2 + 1 ]", 0-1) = 2*Ar_1 + 4 S("l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 + 1, Ar_3 + Ar_2)) [ Ar_1 >= Ar_2 + 1 ]", 0-2) = ? S("l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 + 1, Ar_3 + Ar_2)) [ Ar_1 >= Ar_2 + 1 ]", 0-3) = ? S("l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, 0, 0)) [ Ar_1 >= 1 ]", 0-0) = ? S("l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, 0, 0)) [ Ar_1 >= 1 ]", 0-1) = 2*Ar_1 + 4 S("l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, 0, 0)) [ Ar_1 >= 1 ]", 0-2) = 0 S("l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, 0, 0)) [ Ar_1 >= 1 ]", 0-3) = 0 S("l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3))", 0-0) = 0 S("l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3))", 0-1) = Ar_1 S("l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3))", 0-2) = Ar_2 S("l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3))", 0-3) = Ar_3 orients the transitions l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 + 1, Ar_3 + Ar_2)) [ Ar_1 >= Ar_2 + 1 ] weakly and the transition l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 + 1, Ar_3 + Ar_2)) [ Ar_1 >= Ar_2 + 1 ] strictly and produces the following problem: 5: T: (Comp: 1, Cost: 1) l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3)) (Comp: Ar_1 + 1, Cost: 1) l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, 0, 0)) [ Ar_1 >= 1 ] (Comp: 2*Ar_1^2 + 6*Ar_1 + 4, Cost: 1) l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 + 1, Ar_3 + Ar_2)) [ Ar_1 >= Ar_2 + 1 ] (Comp: Ar_1 + 1, Cost: 1) l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + Ar_3, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_2 >= Ar_1 ] (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Complexity upper bound 8*Ar_1 + 2*Ar_1^2 + 7 Time: 0.116 sec (SMT: 0.101 sec) ---------------------------------------- (2) BOUNDS(1, n^2) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: l0 0: l0 -> l1 : A'=0, [], cost: 1 1: l1 -> l2 : C'=0, D'=0, [ B>=1 ], cost: 1 2: l2 -> l2 : C'=1+C, D'=C+D, [ B>=1+C ], cost: 1 3: l2 -> l1 : A'=D+A, B'=-1+B, [ C>=B ], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: l0 -> l1 : A'=0, [], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 2. Accelerating the following rules: 2: l2 -> l2 : C'=1+C, D'=C+D, [ B>=1+C ], cost: 1 Accelerated rule 2 with metering function -C+B, yielding the new rule 4. Removing the simple loops: 2. Accelerated all simple loops using metering functions (where possible): Start location: l0 0: l0 -> l1 : A'=0, [], cost: 1 1: l1 -> l2 : C'=0, D'=0, [ B>=1 ], cost: 1 3: l2 -> l1 : A'=D+A, B'=-1+B, [ C>=B ], cost: 1 4: l2 -> l2 : C'=B, D'=1/2*C-(C-B)*C+D+1/2*(C-B)^2-1/2*B, [ B>=1+C ], cost: -C+B Chained accelerated rules (with incoming rules): Start location: l0 0: l0 -> l1 : A'=0, [], cost: 1 1: l1 -> l2 : C'=0, D'=0, [ B>=1 ], cost: 1 5: l1 -> l2 : C'=B, D'=-1/2*B+1/2*B^2, [ B>=1 ], cost: 1+B 3: l2 -> l1 : A'=D+A, B'=-1+B, [ C>=B ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: l0 0: l0 -> l1 : A'=0, [], cost: 1 6: l1 -> l1 : A'=A-1/2*B+1/2*B^2, B'=-1+B, C'=B, D'=-1/2*B+1/2*B^2, [ B>=1 ], cost: 2+B Accelerating simple loops of location 1. Accelerating the following rules: 6: l1 -> l1 : A'=A-1/2*B+1/2*B^2, B'=-1+B, C'=B, D'=-1/2*B+1/2*B^2, [ B>=1 ], cost: 2+B Accelerated rule 6 with metering function B, yielding the new rule 7. Removing the simple loops: 6. Accelerated all simple loops using metering functions (where possible): Start location: l0 0: l0 -> l1 : A'=0, [], cost: 1 7: l1 -> l1 : A'=A+1/6*B^3-1/6*B, B'=0, C'=1, D'=0, [ B>=1 ], cost: 5/2*B+1/2*B^2 Chained accelerated rules (with incoming rules): Start location: l0 0: l0 -> l1 : A'=0, [], cost: 1 8: l0 -> l1 : A'=1/6*B^3-1/6*B, B'=0, C'=1, D'=0, [ B>=1 ], cost: 1+5/2*B+1/2*B^2 Removed unreachable locations (and leaf rules with constant cost): Start location: l0 8: l0 -> l1 : A'=1/6*B^3-1/6*B, B'=0, C'=1, D'=0, [ B>=1 ], cost: 1+5/2*B+1/2*B^2 ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: l0 8: l0 -> l1 : A'=1/6*B^3-1/6*B, B'=0, C'=1, D'=0, [ B>=1 ], cost: 1+5/2*B+1/2*B^2 Computing asymptotic complexity for rule 8 Solved the limit problem by the following transformations: Created initial limit problem: 1+5/2*B+1/2*B^2 (+), B (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {B==n} resulting limit problem: [solved] Solution: B / n Resulting cost 1+5/2*n+1/2*n^2 has complexity: Poly(n^2) Found new complexity Poly(n^2). Obtained the following overall complexity (w.r.t. the length of the input n): Complexity: Poly(n^2) Cpx degree: 2 Solved cost: 1+5/2*n+1/2*n^2 Rule cost: 1+5/2*B+1/2*B^2 Rule guard: [ B>=1 ] WORST_CASE(Omega(n^2),?) ---------------------------------------- (4) BOUNDS(n^2, INF)