/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.koat /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^1)) proof of /export/starexec/sandbox/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, n^1). (0) CpxIntTrs (1) Koat Proof [FINISHED, 104 ms] (2) BOUNDS(1, n^1) (3) Loat Proof [FINISHED, 293 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.109 sec (SMT: 0.099 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 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: 1+C (+), 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)