/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, 23 ms] (2) BOUNDS(1, n^1) (3) Loat Proof [FINISHED, 443 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, Fresh_0, 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, Fresh_0, 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, Fresh_0, 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, Fresh_0, 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, Fresh_0, 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.111 sec (SMT: 0.092 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 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 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)