/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, n^1). (0) CpxIntTrs (1) Koat Proof [FINISHED, 224 ms] (2) BOUNDS(1, n^1) (3) Loat Proof [FINISHED, 2035 ms] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: start(A, B, C, D, E, F) -> Com_1(m1(A, B, C, D, E, F)) :|: A >= 0 && B + A + 2 >= 2 * C && B >= A + 1 && 2 * C >= B + A && D >= 0 && E + 1 >= C && E + 1 <= C && F >= A && F <= A m1(A, B, C, D, E, F) -> Com_1(m1(A, B, H, D, E, G)) :|: B >= 1 && D >= 0 && A >= E + 1 && B + 1 >= G && C + 1 >= H && H >= 1 + C && F + 1 >= G && G >= 1 + F m1(A, B, C, D, E, F) -> Com_1(m1(H, B, C, D, E, G)) :|: B >= 1 && D >= 0 && B >= F && E + 1 >= H && C >= B + 1 && F + 1 >= G && G >= 1 + F && A + 1 >= H && H >= 1 + A m1(A, B, C, D, E, F) -> Com_1(m1(A, B, H, D, E, G)) :|: B >= 1 && D >= 0 && B >= F && B + 1 >= H && E >= A && F + 1 >= G && G >= 1 + F && C + 1 >= H && H >= 1 + C m1(A, B, C, D, E, F) -> Com_1(m1(H, B, C, D, E, G)) :|: B >= 1 && D >= 0 && B >= F && B >= C && E + 1 >= H && A + 1 >= H && H >= 1 + A && F + 1 >= G && G >= 1 + F The start-symbols are:[start_6] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 4*ar_1 + 5) Initial complexity problem: 1: T: (Comp: ?, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_0 >= 0 /\ ar_1 + ar_0 + 2 >= 2*ar_2 /\ ar_1 >= ar_0 + 1 /\ 2*ar_2 >= ar_1 + ar_0 /\ ar_3 >= 0 /\ ar_4 + 1 = ar_2 /\ ar_5 = ar_0 ] (Comp: ?, Cost: 1) m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0, ar_1, ar_2 + 1, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_0 >= ar_4 + 1 /\ ar_1 >= ar_5 ] (Comp: ?, Cost: 1) m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0 + 1, ar_1, ar_2, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_1 >= ar_5 /\ ar_4 >= ar_0 /\ ar_2 >= ar_1 + 1 ] (Comp: ?, Cost: 1) m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0, ar_1, ar_2 + 1, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_1 >= ar_5 /\ ar_1 >= ar_2 /\ ar_4 >= ar_0 ] (Comp: ?, Cost: 1) m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0 + 1, ar_1, ar_2, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_1 >= ar_5 /\ ar_1 >= ar_2 /\ ar_4 >= ar_0 ] (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 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) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_0 >= 0 /\ ar_1 + ar_0 + 2 >= 2*ar_2 /\ ar_1 >= ar_0 + 1 /\ 2*ar_2 >= ar_1 + ar_0 /\ ar_3 >= 0 /\ ar_4 + 1 = ar_2 /\ ar_5 = ar_0 ] (Comp: ?, Cost: 1) m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0, ar_1, ar_2 + 1, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_0 >= ar_4 + 1 /\ ar_1 >= ar_5 ] (Comp: ?, Cost: 1) m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0 + 1, ar_1, ar_2, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_1 >= ar_5 /\ ar_4 >= ar_0 /\ ar_2 >= ar_1 + 1 ] (Comp: ?, Cost: 1) m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0, ar_1, ar_2 + 1, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_1 >= ar_5 /\ ar_1 >= ar_2 /\ ar_4 >= ar_0 ] (Comp: ?, Cost: 1) m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0 + 1, ar_1, ar_2, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_1 >= ar_5 /\ ar_1 >= ar_2 /\ ar_4 >= ar_0 ] (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(start) = V_2 + 1 Pol(m1) = V_2 - V_6 + 1 Pol(koat_start) = V_2 + 1 orients all transitions weakly and the transitions m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0 + 1, ar_1, ar_2, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_1 >= ar_5 /\ ar_4 >= ar_0 /\ ar_2 >= ar_1 + 1 ] m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0 + 1, ar_1, ar_2, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_1 >= ar_5 /\ ar_1 >= ar_2 /\ ar_4 >= ar_0 ] m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0, ar_1, ar_2 + 1, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_1 >= ar_5 /\ ar_1 >= ar_2 /\ ar_4 >= ar_0 ] m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0, ar_1, ar_2 + 1, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_0 >= ar_4 + 1 /\ ar_1 >= ar_5 ] strictly and produces the following problem: 3: T: (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_0 >= 0 /\ ar_1 + ar_0 + 2 >= 2*ar_2 /\ ar_1 >= ar_0 + 1 /\ 2*ar_2 >= ar_1 + ar_0 /\ ar_3 >= 0 /\ ar_4 + 1 = ar_2 /\ ar_5 = ar_0 ] (Comp: ar_1 + 1, Cost: 1) m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0, ar_1, ar_2 + 1, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_0 >= ar_4 + 1 /\ ar_1 >= ar_5 ] (Comp: ar_1 + 1, Cost: 1) m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0 + 1, ar_1, ar_2, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_1 >= ar_5 /\ ar_4 >= ar_0 /\ ar_2 >= ar_1 + 1 ] (Comp: ar_1 + 1, Cost: 1) m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0, ar_1, ar_2 + 1, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_1 >= ar_5 /\ ar_1 >= ar_2 /\ ar_4 >= ar_0 ] (Comp: ar_1 + 1, Cost: 1) m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0 + 1, ar_1, ar_2, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_1 >= ar_5 /\ ar_1 >= ar_2 /\ ar_4 >= ar_0 ] (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Complexity upper bound 4*ar_1 + 5 Time: 0.175 sec (SMT: 0.160 sec) ---------------------------------------- (2) BOUNDS(1, n^1) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: start 0: start -> m1 : [ A>=0 && 2+A+B>=2*C && B>=1+A && 2*C>=A+B && D>=0 && 1+E==C && F==A ], cost: 1 1: m1 -> m1 : C'=1+C, F'=1+F, [ B>=1 && D>=0 && A>=1+E && B>=F ], cost: 1 2: m1 -> m1 : A'=1+A, F'=1+F, [ B>=1 && D>=0 && B>=F && E>=A && C>=1+B ], cost: 1 3: m1 -> m1 : C'=1+C, F'=1+F, [ B>=1 && D>=0 && B>=F && B>=C && E>=A ], cost: 1 4: m1 -> m1 : A'=1+A, F'=1+F, [ B>=1 && D>=0 && B>=F && B>=C && E>=A ], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 1. Accelerating the following rules: 1: m1 -> m1 : C'=1+C, F'=1+F, [ B>=1 && D>=0 && A>=1+E && B>=F ], cost: 1 2: m1 -> m1 : A'=1+A, F'=1+F, [ B>=1 && D>=0 && B>=F && E>=A && C>=1+B ], cost: 1 3: m1 -> m1 : C'=1+C, F'=1+F, [ B>=1 && D>=0 && B>=F && B>=C && E>=A ], cost: 1 4: m1 -> m1 : A'=1+A, F'=1+F, [ B>=1 && D>=0 && B>=F && B>=C && E>=A ], cost: 1 Accelerated rule 1 with metering function 1-F+B, yielding the new rule 5. Accelerated rule 2 with backward acceleration, yielding the new rule 6. Accelerated rule 2 with backward acceleration, yielding the new rule 7. Accelerated rule 3 with backward acceleration, yielding the new rule 8. Accelerated rule 3 with backward acceleration, yielding the new rule 9. Accelerated rule 4 with backward acceleration, yielding the new rule 10. Accelerated rule 4 with backward acceleration, yielding the new rule 11. Removing the simple loops: 1 2 3 4. Accelerated all simple loops using metering functions (where possible): Start location: start 0: start -> m1 : [ A>=0 && 2+A+B>=2*C && B>=1+A && 2*C>=A+B && D>=0 && 1+E==C && F==A ], cost: 1 5: m1 -> m1 : C'=1-F+C+B, F'=1+B, [ B>=1 && D>=0 && A>=1+E && B>=F ], cost: 1-F+B 6: m1 -> m1 : A'=1-F+A+B, F'=1+B, [ B>=1 && D>=0 && B>=F && E>=A && C>=1+B && E>=-F+A+B ], cost: 1-F+B 7: m1 -> m1 : A'=1+E, F'=1+F-A+E, [ B>=1 && D>=0 && B>=F && E>=A && C>=1+B && B>=F-A+E ], cost: 1-A+E 8: m1 -> m1 : C'=1-F+C+B, F'=1+B, [ B>=1 && D>=0 && B>=F && B>=C && E>=A && B>=-F+C+B ], cost: 1-F+B 9: m1 -> m1 : C'=1+B, F'=1+F-C+B, [ B>=1 && D>=0 && B>=F && B>=C && E>=A && B>=F-C+B ], cost: 1-C+B 10: m1 -> m1 : A'=1-F+A+B, F'=1+B, [ B>=1 && D>=0 && B>=F && B>=C && E>=A && E>=-F+A+B ], cost: 1-F+B 11: m1 -> m1 : A'=1+E, F'=1+F-A+E, [ B>=1 && D>=0 && B>=F && B>=C && E>=A && B>=F-A+E ], cost: 1-A+E Chained accelerated rules (with incoming rules): Start location: start 0: start -> m1 : [ A>=0 && 2+A+B>=2*C && B>=1+A && 2*C>=A+B && D>=0 && 1+E==C && F==A ], cost: 1 12: start -> m1 : C'=1+B, F'=1+F-C+B, [ A>=0 && 2+A+B>=2*C && B>=1+A && 2*C>=A+B && D>=0 && 1+E==C && F==A && B>=1 && B>=F && B>=C && E>=A && B>=F-C+B ], cost: 2-C+B 13: start -> m1 : A'=1+E, F'=1+F-A+E, [ A>=0 && 2+A+B>=2*C && B>=1+A && 2*C>=A+B && D>=0 && 1+E==C && F==A && B>=1 && B>=F && B>=C && E>=A && B>=F-A+E ], cost: 2-A+E Removed unreachable locations (and leaf rules with constant cost): Start location: start 12: start -> m1 : C'=1+B, F'=1+F-C+B, [ A>=0 && 2+A+B>=2*C && B>=1+A && 2*C>=A+B && D>=0 && 1+E==C && F==A && B>=1 && B>=F && B>=C && E>=A && B>=F-C+B ], cost: 2-C+B 13: start -> m1 : A'=1+E, F'=1+F-A+E, [ A>=0 && 2+A+B>=2*C && B>=1+A && 2*C>=A+B && D>=0 && 1+E==C && F==A && B>=1 && B>=F && B>=C && E>=A && B>=F-A+E ], cost: 2-A+E ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: start 12: start -> m1 : C'=1+B, F'=1+F-C+B, [ A>=0 && 2+A+B>=2*C && B>=1+A && 2*C>=A+B && D>=0 && 1+E==C && F==A && B>=1 && B>=F && B>=C && E>=A && B>=F-C+B ], cost: 2-C+B 13: start -> m1 : A'=1+E, F'=1+F-A+E, [ A>=0 && 2+A+B>=2*C && B>=1+A && 2*C>=A+B && D>=0 && 1+E==C && F==A && B>=1 && B>=F && B>=C && E>=A && B>=F-A+E ], cost: 2-A+E Computing asymptotic complexity for rule 12 Solved the limit problem by the following transformations: Created initial limit problem: 1+F-A (+/+!), 1+2*C-A-B (+/+!), 2-C+B (+), C-E (+/+!), 3-2*C+A+B (+/+!), 1-F+A (+/+!), 2-C+E (+/+!), 1+D (+/+!), -A+B (+/+!), 1+A (+/+!) [not solved] applying transformation rule (C) using substitution {C==1+E} resulting limit problem: 1 (+/+!), 1+F-A (+/+!), 1-F+A (+/+!), 1+D (+/+!), 1-E+B (+), 1+A-2*E+B (+/+!), 3-A+2*E-B (+/+!), -A+B (+/+!), 1+A (+/+!) [not solved] applying transformation rule (C) using substitution {F==A} resulting limit problem: 1 (+/+!), 1+D (+/+!), 1-E+B (+), 1+A-2*E+B (+/+!), 3-A+2*E-B (+/+!), -A+B (+/+!), 1+A (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 1+D (+/+!), 1-E+B (+), 1+A-2*E+B (+/+!), 3-A+2*E-B (+/+!), -A+B (+/+!), 1+A (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {D==n,A==0,E==n,B==2*n} resulting limit problem: [solved] Solution: F / 0 C / 1+n D / n A / 0 E / n B / 2*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: 2-C+B Rule guard: [ A>=0 && 2+A+B>=2*C && B>=1+A && 2*C>=A+B && D>=0 && 1+E==C && F==A ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (4) BOUNDS(n^1, INF)