/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: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, n^1). (0) CpxIntTrs (1) Koat Proof [FINISHED, 86 ms] (2) BOUNDS(1, n^1) (3) Loat Proof [FINISHED, 311 ms] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: f0(A, B, C, D) -> Com_1(f6(0, 0, C, D)) :|: TRUE f6(A, B, C, D) -> Com_1(f6(A, B + 1, C, D)) :|: C >= B + 1 f6(A, B, C, D) -> Com_1(f6(A + 2, B + 1, C, D)) :|: C >= B + 1 f15(A, B, C, D) -> Com_1(f19(C + 1, B, C, 1)) :|: A >= C + 1 && A <= C + 1 f15(A, B, C, D) -> Com_1(f19(A, B, C, 0)) :|: C >= A f15(A, B, C, D) -> Com_1(f19(A, B, C, 0)) :|: A >= 2 + C f6(A, B, C, D) -> Com_1(f15(A, B, C, D)) :|: B >= C && C >= A + 1 f6(A, B, C, D) -> Com_1(f15(A, B, C, D)) :|: A >= 1 + C && B >= C f6(A, B, C, D) -> Com_1(f19(A, B, A, 1)) :|: B >= C && A >= C && A <= C The start-symbols are:[f0_4] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 2*Ar_2 + 13) Initial complexity problem: 1: T: (Comp: ?, Cost: 1) f0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(f6(0, 0, Ar_2, Ar_3)) (Comp: ?, Cost: 1) f6(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(f6(Ar_0, Ar_1 + 1, Ar_2, Ar_3)) [ Ar_2 >= Ar_1 + 1 ] (Comp: ?, Cost: 1) f6(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(f6(Ar_0 + 2, Ar_1 + 1, Ar_2, Ar_3)) [ Ar_2 >= Ar_1 + 1 ] (Comp: ?, Cost: 1) f15(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(f19(Ar_2 + 1, Ar_1, Ar_2, 1)) [ Ar_0 = Ar_2 + 1 ] (Comp: ?, Cost: 1) f15(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(f19(Ar_0, Ar_1, Ar_2, 0)) [ Ar_2 >= Ar_0 ] (Comp: ?, Cost: 1) f15(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(f19(Ar_0, Ar_1, Ar_2, 0)) [ Ar_0 >= Ar_2 + 2 ] (Comp: ?, Cost: 1) f6(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(f15(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 >= Ar_2 /\ Ar_2 >= Ar_0 + 1 ] (Comp: ?, Cost: 1) f6(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(f15(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= Ar_2 + 1 /\ Ar_1 >= Ar_2 ] (Comp: ?, Cost: 1) f6(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(f19(Ar_0, Ar_1, Ar_0, 1)) [ Ar_1 >= Ar_2 /\ Ar_0 = Ar_2 ] (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(f0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Slicing away variables that do not contribute to conditions from problem 1 leaves variables [Ar_0, Ar_1, Ar_2]. We thus obtain the following problem: 2: T: (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(f0(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ] (Comp: ?, Cost: 1) f6(Ar_0, Ar_1, Ar_2) -> Com_1(f19(Ar_0, Ar_1, Ar_0)) [ Ar_1 >= Ar_2 /\ Ar_0 = Ar_2 ] (Comp: ?, Cost: 1) f6(Ar_0, Ar_1, Ar_2) -> Com_1(f15(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= Ar_2 + 1 /\ Ar_1 >= Ar_2 ] (Comp: ?, Cost: 1) f6(Ar_0, Ar_1, Ar_2) -> Com_1(f15(Ar_0, Ar_1, Ar_2)) [ Ar_1 >= Ar_2 /\ Ar_2 >= Ar_0 + 1 ] (Comp: ?, Cost: 1) f15(Ar_0, Ar_1, Ar_2) -> Com_1(f19(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= Ar_2 + 2 ] (Comp: ?, Cost: 1) f15(Ar_0, Ar_1, Ar_2) -> Com_1(f19(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= Ar_0 ] (Comp: ?, Cost: 1) f15(Ar_0, Ar_1, Ar_2) -> Com_1(f19(Ar_2 + 1, Ar_1, Ar_2)) [ Ar_0 = Ar_2 + 1 ] (Comp: ?, Cost: 1) f6(Ar_0, Ar_1, Ar_2) -> Com_1(f6(Ar_0 + 2, Ar_1 + 1, Ar_2)) [ Ar_2 >= Ar_1 + 1 ] (Comp: ?, Cost: 1) f6(Ar_0, Ar_1, Ar_2) -> Com_1(f6(Ar_0, Ar_1 + 1, Ar_2)) [ Ar_2 >= Ar_1 + 1 ] (Comp: ?, Cost: 1) f0(Ar_0, Ar_1, Ar_2) -> Com_1(f6(0, 0, Ar_2)) start location: koat_start leaf cost: 0 Repeatedly propagating knowledge in problem 2 produces the following problem: 3: T: (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(f0(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ] (Comp: ?, Cost: 1) f6(Ar_0, Ar_1, Ar_2) -> Com_1(f19(Ar_0, Ar_1, Ar_0)) [ Ar_1 >= Ar_2 /\ Ar_0 = Ar_2 ] (Comp: ?, Cost: 1) f6(Ar_0, Ar_1, Ar_2) -> Com_1(f15(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= Ar_2 + 1 /\ Ar_1 >= Ar_2 ] (Comp: ?, Cost: 1) f6(Ar_0, Ar_1, Ar_2) -> Com_1(f15(Ar_0, Ar_1, Ar_2)) [ Ar_1 >= Ar_2 /\ Ar_2 >= Ar_0 + 1 ] (Comp: ?, Cost: 1) f15(Ar_0, Ar_1, Ar_2) -> Com_1(f19(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= Ar_2 + 2 ] (Comp: ?, Cost: 1) f15(Ar_0, Ar_1, Ar_2) -> Com_1(f19(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= Ar_0 ] (Comp: ?, Cost: 1) f15(Ar_0, Ar_1, Ar_2) -> Com_1(f19(Ar_2 + 1, Ar_1, Ar_2)) [ Ar_0 = Ar_2 + 1 ] (Comp: ?, Cost: 1) f6(Ar_0, Ar_1, Ar_2) -> Com_1(f6(Ar_0 + 2, Ar_1 + 1, Ar_2)) [ Ar_2 >= Ar_1 + 1 ] (Comp: ?, Cost: 1) f6(Ar_0, Ar_1, Ar_2) -> Com_1(f6(Ar_0, Ar_1 + 1, Ar_2)) [ Ar_2 >= Ar_1 + 1 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_1, Ar_2) -> Com_1(f6(0, 0, Ar_2)) start location: koat_start leaf cost: 0 A polynomial rank function with Pol(koat_start) = 2 Pol(f0) = 2 Pol(f6) = 2 Pol(f19) = 0 Pol(f15) = 1 orients all transitions weakly and the transitions f6(Ar_0, Ar_1, Ar_2) -> Com_1(f19(Ar_0, Ar_1, Ar_0)) [ Ar_1 >= Ar_2 /\ Ar_0 = Ar_2 ] f6(Ar_0, Ar_1, Ar_2) -> Com_1(f15(Ar_0, Ar_1, Ar_2)) [ Ar_1 >= Ar_2 /\ Ar_2 >= Ar_0 + 1 ] f6(Ar_0, Ar_1, Ar_2) -> Com_1(f15(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= Ar_2 + 1 /\ Ar_1 >= Ar_2 ] f15(Ar_0, Ar_1, Ar_2) -> Com_1(f19(Ar_2 + 1, Ar_1, Ar_2)) [ Ar_0 = Ar_2 + 1 ] f15(Ar_0, Ar_1, Ar_2) -> Com_1(f19(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= Ar_0 ] f15(Ar_0, Ar_1, Ar_2) -> Com_1(f19(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= Ar_2 + 2 ] strictly and produces the following problem: 4: T: (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(f0(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ] (Comp: 2, Cost: 1) f6(Ar_0, Ar_1, Ar_2) -> Com_1(f19(Ar_0, Ar_1, Ar_0)) [ Ar_1 >= Ar_2 /\ Ar_0 = Ar_2 ] (Comp: 2, Cost: 1) f6(Ar_0, Ar_1, Ar_2) -> Com_1(f15(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= Ar_2 + 1 /\ Ar_1 >= Ar_2 ] (Comp: 2, Cost: 1) f6(Ar_0, Ar_1, Ar_2) -> Com_1(f15(Ar_0, Ar_1, Ar_2)) [ Ar_1 >= Ar_2 /\ Ar_2 >= Ar_0 + 1 ] (Comp: 2, Cost: 1) f15(Ar_0, Ar_1, Ar_2) -> Com_1(f19(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= Ar_2 + 2 ] (Comp: 2, Cost: 1) f15(Ar_0, Ar_1, Ar_2) -> Com_1(f19(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= Ar_0 ] (Comp: 2, Cost: 1) f15(Ar_0, Ar_1, Ar_2) -> Com_1(f19(Ar_2 + 1, Ar_1, Ar_2)) [ Ar_0 = Ar_2 + 1 ] (Comp: ?, Cost: 1) f6(Ar_0, Ar_1, Ar_2) -> Com_1(f6(Ar_0 + 2, Ar_1 + 1, Ar_2)) [ Ar_2 >= Ar_1 + 1 ] (Comp: ?, Cost: 1) f6(Ar_0, Ar_1, Ar_2) -> Com_1(f6(Ar_0, Ar_1 + 1, Ar_2)) [ Ar_2 >= Ar_1 + 1 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_1, Ar_2) -> Com_1(f6(0, 0, Ar_2)) start location: koat_start leaf cost: 0 A polynomial rank function with Pol(koat_start) = V_3 Pol(f0) = V_3 Pol(f6) = -V_2 + V_3 Pol(f19) = -V_2 + V_3 Pol(f15) = -V_2 + V_3 orients all transitions weakly and the transitions f6(Ar_0, Ar_1, Ar_2) -> Com_1(f6(Ar_0 + 2, Ar_1 + 1, Ar_2)) [ Ar_2 >= Ar_1 + 1 ] f6(Ar_0, Ar_1, Ar_2) -> Com_1(f6(Ar_0, Ar_1 + 1, Ar_2)) [ Ar_2 >= Ar_1 + 1 ] strictly and produces the following problem: 5: T: (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(f0(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ] (Comp: 2, Cost: 1) f6(Ar_0, Ar_1, Ar_2) -> Com_1(f19(Ar_0, Ar_1, Ar_0)) [ Ar_1 >= Ar_2 /\ Ar_0 = Ar_2 ] (Comp: 2, Cost: 1) f6(Ar_0, Ar_1, Ar_2) -> Com_1(f15(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= Ar_2 + 1 /\ Ar_1 >= Ar_2 ] (Comp: 2, Cost: 1) f6(Ar_0, Ar_1, Ar_2) -> Com_1(f15(Ar_0, Ar_1, Ar_2)) [ Ar_1 >= Ar_2 /\ Ar_2 >= Ar_0 + 1 ] (Comp: 2, Cost: 1) f15(Ar_0, Ar_1, Ar_2) -> Com_1(f19(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= Ar_2 + 2 ] (Comp: 2, Cost: 1) f15(Ar_0, Ar_1, Ar_2) -> Com_1(f19(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= Ar_0 ] (Comp: 2, Cost: 1) f15(Ar_0, Ar_1, Ar_2) -> Com_1(f19(Ar_2 + 1, Ar_1, Ar_2)) [ Ar_0 = Ar_2 + 1 ] (Comp: Ar_2, Cost: 1) f6(Ar_0, Ar_1, Ar_2) -> Com_1(f6(Ar_0 + 2, Ar_1 + 1, Ar_2)) [ Ar_2 >= Ar_1 + 1 ] (Comp: Ar_2, Cost: 1) f6(Ar_0, Ar_1, Ar_2) -> Com_1(f6(Ar_0, Ar_1 + 1, Ar_2)) [ Ar_2 >= Ar_1 + 1 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_1, Ar_2) -> Com_1(f6(0, 0, Ar_2)) start location: koat_start leaf cost: 0 Complexity upper bound 2*Ar_2 + 13 Time: 0.100 sec (SMT: 0.078 sec) ---------------------------------------- (2) BOUNDS(1, n^1) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: f0 0: f0 -> f6 : A'=0, B'=0, [], cost: 1 1: f6 -> f6 : B'=1+B, [ C>=1+B ], cost: 1 2: f6 -> f6 : A'=2+A, B'=1+B, [ C>=1+B ], cost: 1 6: f6 -> f15 : [ B>=C && C>=1+A ], cost: 1 7: f6 -> f15 : [ A>=1+C && B>=C ], cost: 1 8: f6 -> f19 : C'=A, D'=1, [ B>=C && A==C ], cost: 1 3: f15 -> f19 : A'=1+C, D'=1, [ A==1+C ], cost: 1 4: f15 -> f19 : D'=0, [ C>=A ], cost: 1 5: f15 -> f19 : D'=0, [ A>=2+C ], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: f0 -> f6 : A'=0, B'=0, [], cost: 1 Removed unreachable and leaf rules: Start location: f0 0: f0 -> f6 : A'=0, B'=0, [], cost: 1 1: f6 -> f6 : B'=1+B, [ C>=1+B ], cost: 1 2: f6 -> f6 : A'=2+A, B'=1+B, [ C>=1+B ], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 1. Accelerating the following rules: 1: f6 -> f6 : B'=1+B, [ C>=1+B ], cost: 1 2: f6 -> f6 : A'=2+A, B'=1+B, [ C>=1+B ], cost: 1 Accelerated rule 1 with metering function C-B, yielding the new rule 9. Accelerated rule 2 with metering function C-B, yielding the new rule 10. Removing the simple loops: 1 2. Accelerated all simple loops using metering functions (where possible): Start location: f0 0: f0 -> f6 : A'=0, B'=0, [], cost: 1 9: f6 -> f6 : B'=C, [ C>=1+B ], cost: C-B 10: f6 -> f6 : A'=2*C+A-2*B, B'=C, [ C>=1+B ], cost: C-B Chained accelerated rules (with incoming rules): Start location: f0 0: f0 -> f6 : A'=0, B'=0, [], cost: 1 11: f0 -> f6 : A'=0, B'=C, [ C>=1 ], cost: 1+C 12: f0 -> f6 : A'=2*C, B'=C, [ C>=1 ], cost: 1+C Removed unreachable locations (and leaf rules with constant cost): Start location: f0 11: f0 -> f6 : A'=0, B'=C, [ C>=1 ], cost: 1+C 12: f0 -> f6 : A'=2*C, B'=C, [ C>=1 ], cost: 1+C ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: f0 12: f0 -> f6 : A'=2*C, B'=C, [ C>=1 ], cost: 1+C Computing asymptotic complexity for rule 12 Solved the limit problem by the following transformations: Created initial limit problem: C (+/+!), 1+C (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {C==n} resulting limit problem: [solved] Solution: C / n Resulting cost 1+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: 1+n Rule cost: 1+C Rule guard: [ C>=1 ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (4) BOUNDS(n^1, INF)