3.44/1.89 WORST_CASE(Omega(n^1), O(n^1)) 3.44/1.90 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 3.44/1.90 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.44/1.90 3.44/1.90 3.44/1.90 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, n^1). 3.44/1.90 3.44/1.90 (0) CpxIntTrs 3.44/1.90 (1) Koat Proof [FINISHED, 119 ms] 3.44/1.90 (2) BOUNDS(1, n^1) 3.44/1.90 (3) Loat Proof [FINISHED, 216 ms] 3.44/1.90 (4) BOUNDS(n^1, INF) 3.44/1.90 3.44/1.90 3.44/1.90 ---------------------------------------- 3.44/1.90 3.44/1.90 (0) 3.44/1.90 Obligation: 3.44/1.90 Complexity Int TRS consisting of the following rules: 3.44/1.90 start(A, B, C, D, E, F) -> Com_1(stop(A, B, C, D, E, F)) :|: 0 >= A && B >= A && B <= A && C >= D && C <= D && E >= F && E <= F 3.44/1.90 start(A, B, C, D, E, F) -> Com_1(lbl71(A, B - 1, C - 1, D, 1 + E, F)) :|: A >= 1 && B >= A && B <= A && C >= D && C <= D && E >= F && E <= F 3.44/1.90 lbl71(A, B, C, D, E, F) -> Com_1(stop(A, B, C, D, E, F)) :|: D >= C + 1 && B >= 0 && B <= 0 && E + C >= F + D && E + C <= F + D && A + C >= D && A + C <= D 3.44/1.90 lbl71(A, B, C, D, E, F) -> Com_1(lbl71(A, B - 1, C - 1, D, 1 + E, F)) :|: A + C >= D + 1 && D >= C + 1 && A + C >= D && E + C >= D + F && E + C <= D + F && B + D >= A + C && B + D <= A + C 3.44/1.90 start0(A, B, C, D, E, F) -> Com_1(start(A, A, D, D, F, F)) :|: TRUE 3.44/1.90 3.44/1.90 The start-symbols are:[start0_6] 3.44/1.90 3.44/1.90 3.44/1.90 ---------------------------------------- 3.44/1.90 3.44/1.90 (1) Koat Proof (FINISHED) 3.44/1.90 YES(?, ar_0 + 4) 3.44/1.90 3.44/1.90 3.44/1.90 3.44/1.90 Initial complexity problem: 3.44/1.90 3.44/1.90 1: T: 3.44/1.90 3.44/1.90 (Comp: ?, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 >= ar_0 /\ ar_1 = ar_0 /\ ar_2 = ar_3 /\ ar_4 = ar_5 ] 3.44/1.90 3.44/1.90 (Comp: ?, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl71(ar_0, ar_1 - 1, ar_2 - 1, ar_3, ar_4 + 1, ar_5)) [ ar_0 >= 1 /\ ar_1 = ar_0 /\ ar_2 = ar_3 /\ ar_4 = ar_5 ] 3.44/1.90 3.44/1.90 (Comp: ?, Cost: 1) lbl71(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= ar_2 + 1 /\ ar_1 = 0 /\ ar_4 + ar_2 = ar_5 + ar_3 /\ ar_0 + ar_2 = ar_3 ] 3.44/1.90 3.44/1.90 (Comp: ?, Cost: 1) lbl71(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl71(ar_0, ar_1 - 1, ar_2 - 1, ar_3, ar_4 + 1, ar_5)) [ ar_0 + ar_2 >= ar_3 + 1 /\ ar_3 >= ar_2 + 1 /\ ar_0 + ar_2 >= ar_3 /\ ar_4 + ar_2 = ar_3 + ar_5 /\ ar_1 + ar_3 = ar_0 + ar_2 ] 3.44/1.90 3.44/1.90 (Comp: ?, Cost: 1) start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start(ar_0, ar_0, ar_3, ar_3, ar_5, ar_5)) 3.44/1.90 3.44/1.90 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ] 3.44/1.90 3.44/1.90 start location: koat_start 3.44/1.90 3.44/1.90 leaf cost: 0 3.44/1.90 3.44/1.90 3.44/1.90 3.44/1.90 Repeatedly propagating knowledge in problem 1 produces the following problem: 3.44/1.90 3.44/1.90 2: T: 3.44/1.90 3.44/1.90 (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 >= ar_0 /\ ar_1 = ar_0 /\ ar_2 = ar_3 /\ ar_4 = ar_5 ] 3.44/1.90 3.44/1.90 (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl71(ar_0, ar_1 - 1, ar_2 - 1, ar_3, ar_4 + 1, ar_5)) [ ar_0 >= 1 /\ ar_1 = ar_0 /\ ar_2 = ar_3 /\ ar_4 = ar_5 ] 3.44/1.90 3.44/1.90 (Comp: ?, Cost: 1) lbl71(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= ar_2 + 1 /\ ar_1 = 0 /\ ar_4 + ar_2 = ar_5 + ar_3 /\ ar_0 + ar_2 = ar_3 ] 3.44/1.90 3.44/1.90 (Comp: ?, Cost: 1) lbl71(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl71(ar_0, ar_1 - 1, ar_2 - 1, ar_3, ar_4 + 1, ar_5)) [ ar_0 + ar_2 >= ar_3 + 1 /\ ar_3 >= ar_2 + 1 /\ ar_0 + ar_2 >= ar_3 /\ ar_4 + ar_2 = ar_3 + ar_5 /\ ar_1 + ar_3 = ar_0 + ar_2 ] 3.44/1.90 3.44/1.90 (Comp: 1, Cost: 1) start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start(ar_0, ar_0, ar_3, ar_3, ar_5, ar_5)) 3.44/1.90 3.44/1.90 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ] 3.44/1.90 3.44/1.90 start location: koat_start 3.44/1.90 3.44/1.90 leaf cost: 0 3.44/1.90 3.44/1.90 3.44/1.90 3.44/1.90 A polynomial rank function with 3.44/1.90 3.44/1.90 Pol(start) = 1 3.44/1.90 3.44/1.90 Pol(stop) = 0 3.44/1.90 3.44/1.90 Pol(lbl71) = 1 3.44/1.90 3.44/1.90 Pol(start0) = 1 3.44/1.90 3.44/1.90 Pol(koat_start) = 1 3.44/1.90 3.44/1.90 orients all transitions weakly and the transition 3.44/1.90 3.44/1.90 lbl71(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= ar_2 + 1 /\ ar_1 = 0 /\ ar_4 + ar_2 = ar_5 + ar_3 /\ ar_0 + ar_2 = ar_3 ] 3.44/1.90 3.44/1.90 strictly and produces the following problem: 3.44/1.90 3.44/1.90 3: T: 3.44/1.90 3.44/1.90 (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 >= ar_0 /\ ar_1 = ar_0 /\ ar_2 = ar_3 /\ ar_4 = ar_5 ] 3.44/1.90 3.44/1.90 (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl71(ar_0, ar_1 - 1, ar_2 - 1, ar_3, ar_4 + 1, ar_5)) [ ar_0 >= 1 /\ ar_1 = ar_0 /\ ar_2 = ar_3 /\ ar_4 = ar_5 ] 3.44/1.90 3.44/1.90 (Comp: 1, Cost: 1) lbl71(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= ar_2 + 1 /\ ar_1 = 0 /\ ar_4 + ar_2 = ar_5 + ar_3 /\ ar_0 + ar_2 = ar_3 ] 3.44/1.90 3.44/1.90 (Comp: ?, Cost: 1) lbl71(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl71(ar_0, ar_1 - 1, ar_2 - 1, ar_3, ar_4 + 1, ar_5)) [ ar_0 + ar_2 >= ar_3 + 1 /\ ar_3 >= ar_2 + 1 /\ ar_0 + ar_2 >= ar_3 /\ ar_4 + ar_2 = ar_3 + ar_5 /\ ar_1 + ar_3 = ar_0 + ar_2 ] 3.44/1.90 3.44/1.90 (Comp: 1, Cost: 1) start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start(ar_0, ar_0, ar_3, ar_3, ar_5, ar_5)) 3.44/1.90 3.44/1.90 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ] 3.44/1.91 3.44/1.91 start location: koat_start 3.44/1.91 3.44/1.91 leaf cost: 0 3.44/1.91 3.44/1.91 3.44/1.91 3.44/1.91 A polynomial rank function with 3.44/1.91 3.44/1.91 Pol(start) = V_1 3.44/1.91 3.44/1.91 Pol(stop) = V_2 3.44/1.91 3.44/1.91 Pol(lbl71) = V_2 3.44/1.91 3.44/1.91 Pol(start0) = V_1 3.44/1.91 3.44/1.91 Pol(koat_start) = V_1 3.44/1.91 3.44/1.91 orients all transitions weakly and the transition 3.44/1.91 3.44/1.91 lbl71(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl71(ar_0, ar_1 - 1, ar_2 - 1, ar_3, ar_4 + 1, ar_5)) [ ar_0 + ar_2 >= ar_3 + 1 /\ ar_3 >= ar_2 + 1 /\ ar_0 + ar_2 >= ar_3 /\ ar_4 + ar_2 = ar_3 + ar_5 /\ ar_1 + ar_3 = ar_0 + ar_2 ] 3.44/1.91 3.44/1.91 strictly and produces the following problem: 3.44/1.91 3.44/1.91 4: T: 3.44/1.91 3.44/1.91 (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 >= ar_0 /\ ar_1 = ar_0 /\ ar_2 = ar_3 /\ ar_4 = ar_5 ] 3.44/1.91 3.44/1.91 (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl71(ar_0, ar_1 - 1, ar_2 - 1, ar_3, ar_4 + 1, ar_5)) [ ar_0 >= 1 /\ ar_1 = ar_0 /\ ar_2 = ar_3 /\ ar_4 = ar_5 ] 3.44/1.91 3.44/1.91 (Comp: 1, Cost: 1) lbl71(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= ar_2 + 1 /\ ar_1 = 0 /\ ar_4 + ar_2 = ar_5 + ar_3 /\ ar_0 + ar_2 = ar_3 ] 3.44/1.91 3.44/1.91 (Comp: ar_0, Cost: 1) lbl71(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl71(ar_0, ar_1 - 1, ar_2 - 1, ar_3, ar_4 + 1, ar_5)) [ ar_0 + ar_2 >= ar_3 + 1 /\ ar_3 >= ar_2 + 1 /\ ar_0 + ar_2 >= ar_3 /\ ar_4 + ar_2 = ar_3 + ar_5 /\ ar_1 + ar_3 = ar_0 + ar_2 ] 3.44/1.91 3.44/1.91 (Comp: 1, Cost: 1) start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start(ar_0, ar_0, ar_3, ar_3, ar_5, ar_5)) 3.44/1.91 3.44/1.91 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ] 3.44/1.91 3.44/1.91 start location: koat_start 3.44/1.91 3.44/1.91 leaf cost: 0 3.44/1.91 3.44/1.91 3.44/1.91 3.44/1.91 Complexity upper bound ar_0 + 4 3.44/1.91 3.44/1.91 3.44/1.91 3.44/1.91 Time: 0.179 sec (SMT: 0.165 sec) 3.44/1.91 3.44/1.91 3.44/1.91 ---------------------------------------- 3.44/1.91 3.44/1.91 (2) 3.44/1.91 BOUNDS(1, n^1) 3.44/1.91 3.44/1.91 ---------------------------------------- 3.44/1.91 3.44/1.91 (3) Loat Proof (FINISHED) 3.44/1.91 3.44/1.91 3.44/1.91 ### Pre-processing the ITS problem ### 3.44/1.91 3.44/1.91 3.44/1.91 3.44/1.91 Initial linear ITS problem 3.44/1.91 3.44/1.91 Start location: start0 3.44/1.91 3.44/1.91 0: start -> stop : [ 0>=A && B==A && C==D && E==F ], cost: 1 3.44/1.91 3.44/1.91 1: start -> lbl71 : B'=-1+B, C'=-1+C, E'=1+E, [ A>=1 && B==A && C==D && E==F ], cost: 1 3.44/1.91 3.44/1.91 2: lbl71 -> stop : [ D>=1+C && B==0 && C+E==F+D && C+A==D ], cost: 1 3.44/1.91 3.44/1.91 3: lbl71 -> lbl71 : B'=-1+B, C'=-1+C, E'=1+E, [ C+A>=1+D && D>=1+C && C+A>=D && C+E==F+D && D+B==C+A ], cost: 1 3.44/1.91 3.44/1.91 4: start0 -> start : B'=A, C'=D, E'=F, [], cost: 1 3.44/1.91 3.44/1.91 3.44/1.91 3.44/1.91 Removed unreachable and leaf rules: 3.44/1.91 3.44/1.91 Start location: start0 3.44/1.91 3.44/1.91 1: start -> lbl71 : B'=-1+B, C'=-1+C, E'=1+E, [ A>=1 && B==A && C==D && E==F ], cost: 1 3.44/1.91 3.44/1.91 3: lbl71 -> lbl71 : B'=-1+B, C'=-1+C, E'=1+E, [ C+A>=1+D && D>=1+C && C+A>=D && C+E==F+D && D+B==C+A ], cost: 1 3.44/1.91 3.44/1.91 4: start0 -> start : B'=A, C'=D, E'=F, [], cost: 1 3.44/1.91 3.44/1.91 3.44/1.91 3.44/1.91 Simplified all rules, resulting in: 3.44/1.91 3.44/1.91 Start location: start0 3.44/1.91 3.44/1.91 1: start -> lbl71 : B'=-1+B, C'=-1+C, E'=1+E, [ A>=1 && B==A && C==D && E==F ], cost: 1 3.44/1.91 3.44/1.91 3: lbl71 -> lbl71 : B'=-1+B, C'=-1+C, E'=1+E, [ C+A>=1+D && D>=1+C && C+E==F+D && D+B==C+A ], cost: 1 3.44/1.91 3.44/1.91 4: start0 -> start : B'=A, C'=D, E'=F, [], cost: 1 3.44/1.91 3.44/1.91 3.44/1.91 3.44/1.91 ### Simplification by acceleration and chaining ### 3.44/1.91 3.44/1.91 3.44/1.91 3.44/1.91 Accelerating simple loops of location 1. 3.44/1.91 3.44/1.91 Accelerating the following rules: 3.44/1.91 3.44/1.91 3: lbl71 -> lbl71 : B'=-1+B, C'=-1+C, E'=1+E, [ C+A>=1+D && D>=1+C && C+E==F+D && D+B==C+A ], cost: 1 3.44/1.91 3.44/1.91 3.44/1.91 3.44/1.91 Accelerated rule 3 with metering function C-D+A, yielding the new rule 5. 3.44/1.91 3.44/1.91 Removing the simple loops: 3. 3.44/1.91 3.44/1.91 3.44/1.91 3.44/1.91 Accelerated all simple loops using metering functions (where possible): 3.44/1.91 3.44/1.91 Start location: start0 3.44/1.91 3.44/1.91 1: start -> lbl71 : B'=-1+B, C'=-1+C, E'=1+E, [ A>=1 && B==A && C==D && E==F ], cost: 1 3.44/1.91 3.44/1.91 5: lbl71 -> lbl71 : B'=-C+D-A+B, C'=D-A, E'=C-D+A+E, [ C+A>=1+D && D>=1+C && C+E==F+D && D+B==C+A ], cost: C-D+A 3.44/1.91 3.44/1.91 4: start0 -> start : B'=A, C'=D, E'=F, [], cost: 1 3.44/1.91 3.44/1.91 3.44/1.91 3.44/1.91 Chained accelerated rules (with incoming rules): 3.44/1.91 3.44/1.91 Start location: start0 3.44/1.91 3.44/1.91 1: start -> lbl71 : B'=-1+B, C'=-1+C, E'=1+E, [ A>=1 && B==A && C==D && E==F ], cost: 1 3.44/1.91 3.44/1.91 6: start -> lbl71 : B'=-C+D-A+B, C'=D-A, E'=C-D+A+E, [ A>=1 && B==A && C==D && E==F && -1+C+A>=1+D && C+E==F+D && -1+D+B==-1+C+A ], cost: C-D+A 3.44/1.91 3.44/1.91 4: start0 -> start : B'=A, C'=D, E'=F, [], cost: 1 3.44/1.91 3.44/1.91 3.44/1.91 3.44/1.91 Removed unreachable locations (and leaf rules with constant cost): 3.44/1.91 3.44/1.91 Start location: start0 3.44/1.91 3.44/1.91 6: start -> lbl71 : B'=-C+D-A+B, C'=D-A, E'=C-D+A+E, [ A>=1 && B==A && C==D && E==F && -1+C+A>=1+D && C+E==F+D && -1+D+B==-1+C+A ], cost: C-D+A 3.44/1.91 3.44/1.91 4: start0 -> start : B'=A, C'=D, E'=F, [], cost: 1 3.44/1.91 3.44/1.91 3.44/1.91 3.44/1.91 Eliminated locations (on linear paths): 3.44/1.91 3.44/1.91 Start location: start0 3.44/1.91 3.44/1.91 7: start0 -> lbl71 : B'=0, C'=D-A, E'=F+A, [ -1+D+A>=1+D ], cost: 1+A 3.44/1.91 3.44/1.91 3.44/1.91 3.44/1.91 ### Computing asymptotic complexity ### 3.44/1.91 3.44/1.91 3.44/1.91 3.44/1.91 Fully simplified ITS problem 3.44/1.91 3.44/1.91 Start location: start0 3.44/1.91 3.44/1.91 7: start0 -> lbl71 : B'=0, C'=D-A, E'=F+A, [ -1+D+A>=1+D ], cost: 1+A 3.44/1.91 3.44/1.91 3.44/1.91 3.44/1.91 Computing asymptotic complexity for rule 7 3.44/1.91 3.44/1.91 Solved the limit problem by the following transformations: 3.44/1.91 3.44/1.91 Created initial limit problem: 3.44/1.91 3.44/1.91 -1+A (+/+!), 1+A (+) [not solved] 3.44/1.91 3.44/1.91 3.44/1.91 3.44/1.91 removing all constraints (solved by SMT) 3.44/1.91 3.44/1.91 resulting limit problem: [solved] 3.44/1.91 3.44/1.91 3.44/1.91 3.44/1.91 applying transformation rule (C) using substitution {A==n} 3.44/1.91 3.44/1.91 resulting limit problem: 3.44/1.91 3.44/1.91 [solved] 3.44/1.91 3.44/1.91 3.44/1.91 3.44/1.91 Solution: 3.44/1.91 3.44/1.91 D / 0 3.44/1.91 3.44/1.91 A / n 3.44/1.91 3.44/1.91 Resulting cost 1+n has complexity: Poly(n^1) 3.44/1.91 3.44/1.91 3.44/1.91 3.44/1.91 Found new complexity Poly(n^1). 3.44/1.91 3.44/1.91 3.44/1.91 3.44/1.91 Obtained the following overall complexity (w.r.t. the length of the input n): 3.44/1.91 3.44/1.91 Complexity: Poly(n^1) 3.44/1.91 3.44/1.91 Cpx degree: 1 3.44/1.91 3.44/1.91 Solved cost: 1+n 3.44/1.91 3.44/1.91 Rule cost: 1+A 3.44/1.91 3.44/1.91 Rule guard: [ -1+D+A>=1+D ] 3.44/1.91 3.44/1.91 3.44/1.91 3.44/1.91 WORST_CASE(Omega(n^1),?) 3.44/1.91 3.44/1.91 3.44/1.91 ---------------------------------------- 3.44/1.91 3.44/1.91 (4) 3.44/1.91 BOUNDS(n^1, INF) 4.21/1.92 EOF