/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, 124 ms] (2) BOUNDS(1, n^1) (3) Loat Proof [FINISHED, 440 ms] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: start(A, B, C, D) -> Com_1(stop1(A, B, C, D)) :|: A >= 0 && B >= 0 && C >= 0 && D >= 0 && D <= 0 start(A, B, C, D) -> Com_1(cont1(A, B, C, D)) :|: D >= 1 && A >= 0 && B >= 0 && C >= 0 && D >= 0 && A >= D cont1(A, B, C, D) -> Com_1(stop2(A, B, 1, D - 1)) :|: D >= 1 && B >= 0 && A >= D && C >= 0 && C <= 0 cont1(A, B, C, D) -> Com_1(a(A, B, C - 1, D)) :|: C >= 1 && D >= 1 && C >= 0 && B >= 0 && A >= D a(A, B, C, D) -> Com_1(b(A, B, E, D - 1)) :|: A >= D && B >= 0 && C >= 0 && D >= 1 b(A, B, C, D) -> Com_1(start(A, B, C, D)) :|: C >= 0 && D >= 0 && B >= 0 && A >= D + 1 b(A, B, C, D) -> Com_1(stop3(A, B, C, D)) :|: 0 >= C + 1 && D >= 0 && B >= 0 && A >= D + 1 start0(A, B, C, D) -> Com_1(start(A, B, B, A)) :|: A >= 0 && B >= 0 The start-symbols are:[start0_4] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 16*ar_0 + 4) Initial complexity problem: 1: T: (Comp: ?, Cost: 1) start(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop1(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= 0 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 = 0 ] (Comp: ?, Cost: 1) start(ar_0, ar_1, ar_2, ar_3) -> Com_1(cont1(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 1 /\ ar_0 >= 0 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 >= 0 /\ ar_0 >= ar_3 ] (Comp: ?, Cost: 1) cont1(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop2(ar_0, ar_1, 1, ar_3 - 1)) [ ar_3 >= 1 /\ ar_1 >= 0 /\ ar_0 >= ar_3 /\ ar_2 = 0 ] (Comp: ?, Cost: 1) cont1(ar_0, ar_1, ar_2, ar_3) -> Com_1(a(ar_0, ar_1, ar_2 - 1, ar_3)) [ ar_2 >= 1 /\ ar_3 >= 1 /\ ar_2 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 ] (Comp: ?, Cost: 1) a(ar_0, ar_1, ar_2, ar_3) -> Com_1(b(ar_0, ar_1, e, ar_3 - 1)) [ ar_0 >= ar_3 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 >= 1 ] (Comp: ?, Cost: 1) b(ar_0, ar_1, ar_2, ar_3) -> Com_1(start(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= 0 /\ ar_3 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 + 1 ] (Comp: ?, Cost: 1) b(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop3(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_2 + 1 /\ ar_3 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 + 1 ] (Comp: ?, Cost: 1) start0(ar_0, ar_1, ar_2, ar_3) -> Com_1(start(ar_0, ar_1, ar_1, ar_0)) [ ar_0 >= 0 /\ ar_1 >= 0 ] (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(start0(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: ?, Cost: 1) start(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop1(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= 0 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 = 0 ] (Comp: ?, Cost: 1) start(ar_0, ar_1, ar_2, ar_3) -> Com_1(cont1(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 1 /\ ar_0 >= 0 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 >= 0 /\ ar_0 >= ar_3 ] (Comp: ?, Cost: 1) cont1(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop2(ar_0, ar_1, 1, ar_3 - 1)) [ ar_3 >= 1 /\ ar_1 >= 0 /\ ar_0 >= ar_3 /\ ar_2 = 0 ] (Comp: ?, Cost: 1) cont1(ar_0, ar_1, ar_2, ar_3) -> Com_1(a(ar_0, ar_1, ar_2 - 1, ar_3)) [ ar_2 >= 1 /\ ar_3 >= 1 /\ ar_2 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 ] (Comp: ?, Cost: 1) a(ar_0, ar_1, ar_2, ar_3) -> Com_1(b(ar_0, ar_1, e, ar_3 - 1)) [ ar_0 >= ar_3 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 >= 1 ] (Comp: ?, Cost: 1) b(ar_0, ar_1, ar_2, ar_3) -> Com_1(start(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= 0 /\ ar_3 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 + 1 ] (Comp: ?, Cost: 1) b(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop3(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_2 + 1 /\ ar_3 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 + 1 ] (Comp: 1, Cost: 1) start0(ar_0, ar_1, ar_2, ar_3) -> Com_1(start(ar_0, ar_1, ar_1, ar_0)) [ ar_0 >= 0 /\ ar_1 >= 0 ] (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(start) = 1 Pol(stop1) = 0 Pol(cont1) = 1 Pol(stop2) = 0 Pol(a) = 1 Pol(b) = 1 Pol(stop3) = 0 Pol(start0) = 1 Pol(koat_start) = 1 orients all transitions weakly and the transitions start(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop1(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= 0 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 = 0 ] cont1(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop2(ar_0, ar_1, 1, ar_3 - 1)) [ ar_3 >= 1 /\ ar_1 >= 0 /\ ar_0 >= ar_3 /\ ar_2 = 0 ] b(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop3(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_2 + 1 /\ ar_3 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 + 1 ] strictly and produces the following problem: 3: T: (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop1(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= 0 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 = 0 ] (Comp: ?, Cost: 1) start(ar_0, ar_1, ar_2, ar_3) -> Com_1(cont1(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 1 /\ ar_0 >= 0 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 >= 0 /\ ar_0 >= ar_3 ] (Comp: 1, Cost: 1) cont1(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop2(ar_0, ar_1, 1, ar_3 - 1)) [ ar_3 >= 1 /\ ar_1 >= 0 /\ ar_0 >= ar_3 /\ ar_2 = 0 ] (Comp: ?, Cost: 1) cont1(ar_0, ar_1, ar_2, ar_3) -> Com_1(a(ar_0, ar_1, ar_2 - 1, ar_3)) [ ar_2 >= 1 /\ ar_3 >= 1 /\ ar_2 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 ] (Comp: ?, Cost: 1) a(ar_0, ar_1, ar_2, ar_3) -> Com_1(b(ar_0, ar_1, e, ar_3 - 1)) [ ar_0 >= ar_3 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 >= 1 ] (Comp: ?, Cost: 1) b(ar_0, ar_1, ar_2, ar_3) -> Com_1(start(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= 0 /\ ar_3 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 + 1 ] (Comp: 1, Cost: 1) b(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop3(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_2 + 1 /\ ar_3 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 + 1 ] (Comp: 1, Cost: 1) start0(ar_0, ar_1, ar_2, ar_3) -> Com_1(start(ar_0, ar_1, ar_1, ar_0)) [ ar_0 >= 0 /\ ar_1 >= 0 ] (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(start) = 4*V_4 Pol(stop1) = 4*V_4 Pol(cont1) = 4*V_4 - 1 Pol(stop2) = 4*V_4 Pol(a) = 4*V_4 - 2 Pol(b) = 4*V_4 + 1 Pol(stop3) = 4*V_4 Pol(start0) = 4*V_1 Pol(koat_start) = 4*V_1 orients all transitions weakly and the transitions start(ar_0, ar_1, ar_2, ar_3) -> Com_1(cont1(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 1 /\ ar_0 >= 0 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 >= 0 /\ ar_0 >= ar_3 ] cont1(ar_0, ar_1, ar_2, ar_3) -> Com_1(a(ar_0, ar_1, ar_2 - 1, ar_3)) [ ar_2 >= 1 /\ ar_3 >= 1 /\ ar_2 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 ] b(ar_0, ar_1, ar_2, ar_3) -> Com_1(start(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= 0 /\ ar_3 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 + 1 ] a(ar_0, ar_1, ar_2, ar_3) -> Com_1(b(ar_0, ar_1, e, ar_3 - 1)) [ ar_0 >= ar_3 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 >= 1 ] strictly and produces the following problem: 4: T: (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop1(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= 0 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 = 0 ] (Comp: 4*ar_0, Cost: 1) start(ar_0, ar_1, ar_2, ar_3) -> Com_1(cont1(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 1 /\ ar_0 >= 0 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 >= 0 /\ ar_0 >= ar_3 ] (Comp: 1, Cost: 1) cont1(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop2(ar_0, ar_1, 1, ar_3 - 1)) [ ar_3 >= 1 /\ ar_1 >= 0 /\ ar_0 >= ar_3 /\ ar_2 = 0 ] (Comp: 4*ar_0, Cost: 1) cont1(ar_0, ar_1, ar_2, ar_3) -> Com_1(a(ar_0, ar_1, ar_2 - 1, ar_3)) [ ar_2 >= 1 /\ ar_3 >= 1 /\ ar_2 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 ] (Comp: 4*ar_0, Cost: 1) a(ar_0, ar_1, ar_2, ar_3) -> Com_1(b(ar_0, ar_1, e, ar_3 - 1)) [ ar_0 >= ar_3 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 >= 1 ] (Comp: 4*ar_0, Cost: 1) b(ar_0, ar_1, ar_2, ar_3) -> Com_1(start(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= 0 /\ ar_3 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 + 1 ] (Comp: 1, Cost: 1) b(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop3(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_2 + 1 /\ ar_3 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 + 1 ] (Comp: 1, Cost: 1) start0(ar_0, ar_1, ar_2, ar_3) -> Com_1(start(ar_0, ar_1, ar_1, ar_0)) [ ar_0 >= 0 /\ ar_1 >= 0 ] (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Complexity upper bound 16*ar_0 + 4 Time: 0.138 sec (SMT: 0.126 sec) ---------------------------------------- (2) BOUNDS(1, n^1) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: start0 0: start -> stop1 : [ A>=0 && B>=0 && C>=0 && D==0 ], cost: 1 1: start -> cont1 : [ D>=1 && A>=0 && B>=0 && C>=0 && D>=0 && A>=D ], cost: 1 2: cont1 -> stop2 : C'=1, D'=-1+D, [ D>=1 && B>=0 && A>=D && C==0 ], cost: 1 3: cont1 -> a : C'=-1+C, [ C>=1 && D>=1 && C>=0 && B>=0 && A>=D ], cost: 1 4: a -> b : C'=free, D'=-1+D, [ A>=D && B>=0 && C>=0 && D>=1 ], cost: 1 5: b -> start : [ C>=0 && D>=0 && B>=0 && A>=1+D ], cost: 1 6: b -> stop3 : [ 0>=1+C && D>=0 && B>=0 && A>=1+D ], cost: 1 7: start0 -> start : C'=B, D'=A, [ A>=0 && B>=0 ], cost: 1 Removed unreachable and leaf rules: Start location: start0 1: start -> cont1 : [ D>=1 && A>=0 && B>=0 && C>=0 && D>=0 && A>=D ], cost: 1 3: cont1 -> a : C'=-1+C, [ C>=1 && D>=1 && C>=0 && B>=0 && A>=D ], cost: 1 4: a -> b : C'=free, D'=-1+D, [ A>=D && B>=0 && C>=0 && D>=1 ], cost: 1 5: b -> start : [ C>=0 && D>=0 && B>=0 && A>=1+D ], cost: 1 7: start0 -> start : C'=B, D'=A, [ A>=0 && B>=0 ], cost: 1 Simplified all rules, resulting in: Start location: start0 1: start -> cont1 : [ D>=1 && A>=0 && B>=0 && C>=0 && A>=D ], cost: 1 3: cont1 -> a : C'=-1+C, [ C>=1 && D>=1 && B>=0 && A>=D ], cost: 1 4: a -> b : C'=free, D'=-1+D, [ A>=D && B>=0 && C>=0 && D>=1 ], cost: 1 5: b -> start : [ C>=0 && D>=0 && B>=0 && A>=1+D ], cost: 1 7: start0 -> start : C'=B, D'=A, [ A>=0 && B>=0 ], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: start0 10: start -> start : C'=free, D'=-1+D, [ D>=1 && A>=0 && B>=0 && A>=D && C>=1 && free>=0 ], cost: 4 7: start0 -> start : C'=B, D'=A, [ A>=0 && B>=0 ], cost: 1 Accelerating simple loops of location 0. Accelerating the following rules: 10: start -> start : C'=free, D'=-1+D, [ D>=1 && A>=0 && B>=0 && A>=D && C>=1 && free>=0 ], cost: 4 Accelerated rule 10 with metering function D (after strengthening guard), yielding the new rule 11. Removing the simple loops:. Accelerated all simple loops using metering functions (where possible): Start location: start0 10: start -> start : C'=free, D'=-1+D, [ D>=1 && A>=0 && B>=0 && A>=D && C>=1 && free>=0 ], cost: 4 11: start -> start : C'=free, D'=0, [ D>=1 && A>=0 && B>=0 && A>=D && C>=1 && free>=1 ], cost: 4*D 7: start0 -> start : C'=B, D'=A, [ A>=0 && B>=0 ], cost: 1 Chained accelerated rules (with incoming rules): Start location: start0 7: start0 -> start : C'=B, D'=A, [ A>=0 && B>=0 ], cost: 1 12: start0 -> start : C'=free, D'=-1+A, [ A>=1 && B>=1 && free>=0 ], cost: 5 13: start0 -> start : C'=free, D'=0, [ A>=1 && B>=1 && free>=1 ], cost: 1+4*A Removed unreachable locations (and leaf rules with constant cost): Start location: start0 13: start0 -> start : C'=free, D'=0, [ A>=1 && B>=1 && free>=1 ], cost: 1+4*A ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: start0 13: start0 -> start : C'=free, D'=0, [ A>=1 && B>=1 && free>=1 ], cost: 1+4*A Computing asymptotic complexity for rule 13 Solved the limit problem by the following transformations: Created initial limit problem: free (+/+!), 1+4*A (+), A (+/+!), B (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {free==n,A==n,B==n} resulting limit problem: [solved] Solution: free / n A / n B / n Resulting cost 1+4*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+4*n Rule cost: 1+4*A Rule guard: [ A>=1 && B>=1 && free>=1 ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (4) BOUNDS(n^1, INF)