/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.koat /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^2), O(n^2)) proof of /export/starexec/sandbox/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^2, n^2). (0) CpxIntTrs (1) Koat Proof [FINISHED, 48 ms] (2) BOUNDS(1, n^2) (3) Loat Proof [FINISHED, 489 ms] (4) BOUNDS(n^2, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: l0(A, B, C, D) -> Com_1(l1(0, B, C, D)) :|: TRUE l1(A, B, C, D) -> Com_1(l1(A + 1, B - 1, C, D)) :|: B >= 1 l1(A, B, C, D) -> Com_1(l2(A, B, A, D)) :|: 0 >= B l2(A, B, C, D) -> Com_1(l3(A, B, C, C)) :|: C >= 1 l3(A, B, C, D) -> Com_1(l3(A, B, C, D - 1)) :|: D >= 1 && C >= 1 l3(A, B, C, D) -> Com_1(l2(A, B, C - 1, D)) :|: 0 >= D && C >= 1 The start-symbols are:[l0_4] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 5*Ar_1 + 2*Ar_1^2 + 2) Initial complexity problem: 1: T: (Comp: ?, Cost: 1) l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + 1, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_1 >= 1 ] (Comp: ?, Cost: 1) l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_0, Ar_3)) [ 0 >= Ar_1 ] (Comp: ?, Cost: 1) l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_2)) [ Ar_2 >= 1 ] (Comp: ?, Cost: 1) l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_3 - 1)) [ Ar_3 >= 1 /\ Ar_2 >= 1 ] (Comp: ?, Cost: 1) l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 - 1, Ar_3)) [ 0 >= Ar_3 /\ Ar_2 >= 1 ] (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(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: 1, Cost: 1) l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + 1, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_1 >= 1 ] (Comp: ?, Cost: 1) l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_0, Ar_3)) [ 0 >= Ar_1 ] (Comp: ?, Cost: 1) l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_2)) [ Ar_2 >= 1 ] (Comp: ?, Cost: 1) l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_3 - 1)) [ Ar_3 >= 1 /\ Ar_2 >= 1 ] (Comp: ?, Cost: 1) l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 - 1, Ar_3)) [ 0 >= Ar_3 /\ Ar_2 >= 1 ] (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(l0) = 1 Pol(l1) = 1 Pol(l2) = 0 Pol(l3) = 0 Pol(koat_start) = 1 orients all transitions weakly and the transition l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_0, Ar_3)) [ 0 >= Ar_1 ] strictly and produces the following problem: 3: T: (Comp: 1, Cost: 1) l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + 1, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_1 >= 1 ] (Comp: 1, Cost: 1) l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_0, Ar_3)) [ 0 >= Ar_1 ] (Comp: ?, Cost: 1) l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_2)) [ Ar_2 >= 1 ] (Comp: ?, Cost: 1) l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_3 - 1)) [ Ar_3 >= 1 /\ Ar_2 >= 1 ] (Comp: ?, Cost: 1) l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 - 1, Ar_3)) [ 0 >= Ar_3 /\ Ar_2 >= 1 ] (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(l0) = V_2 Pol(l1) = V_2 Pol(l2) = V_2 Pol(l3) = V_2 Pol(koat_start) = V_2 orients all transitions weakly and the transition l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + 1, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_1 >= 1 ] strictly and produces the following problem: 4: T: (Comp: 1, Cost: 1) l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3)) (Comp: Ar_1, Cost: 1) l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + 1, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_1 >= 1 ] (Comp: 1, Cost: 1) l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_0, Ar_3)) [ 0 >= Ar_1 ] (Comp: ?, Cost: 1) l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_2)) [ Ar_2 >= 1 ] (Comp: ?, Cost: 1) l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_3 - 1)) [ Ar_3 >= 1 /\ Ar_2 >= 1 ] (Comp: ?, Cost: 1) l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 - 1, Ar_3)) [ 0 >= Ar_3 /\ Ar_2 >= 1 ] (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(l3) = 2*V_3 - 1 Pol(l2) = 2*V_3 and size complexities S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-0) = Ar_0 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-1) = Ar_1 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-2) = Ar_2 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-3) = Ar_3 S("l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 - 1, Ar_3)) [ 0 >= Ar_3 /\\ Ar_2 >= 1 ]", 0-0) = Ar_1 S("l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 - 1, Ar_3)) [ 0 >= Ar_3 /\\ Ar_2 >= 1 ]", 0-1) = Ar_1 S("l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 - 1, Ar_3)) [ 0 >= Ar_3 /\\ Ar_2 >= 1 ]", 0-2) = Ar_1 S("l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 - 1, Ar_3)) [ 0 >= Ar_3 /\\ Ar_2 >= 1 ]", 0-3) = Ar_1 S("l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_3 - 1)) [ Ar_3 >= 1 /\\ Ar_2 >= 1 ]", 0-0) = Ar_1 S("l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_3 - 1)) [ Ar_3 >= 1 /\\ Ar_2 >= 1 ]", 0-1) = Ar_1 S("l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_3 - 1)) [ Ar_3 >= 1 /\\ Ar_2 >= 1 ]", 0-2) = Ar_1 S("l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_3 - 1)) [ Ar_3 >= 1 /\\ Ar_2 >= 1 ]", 0-3) = Ar_1 S("l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_2)) [ Ar_2 >= 1 ]", 0-0) = Ar_1 S("l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_2)) [ Ar_2 >= 1 ]", 0-1) = Ar_1 S("l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_2)) [ Ar_2 >= 1 ]", 0-2) = Ar_1 S("l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_2)) [ Ar_2 >= 1 ]", 0-3) = Ar_1 S("l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_0, Ar_3)) [ 0 >= Ar_1 ]", 0-0) = Ar_1 S("l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_0, Ar_3)) [ 0 >= Ar_1 ]", 0-1) = Ar_1 S("l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_0, Ar_3)) [ 0 >= Ar_1 ]", 0-2) = Ar_1 S("l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_0, Ar_3)) [ 0 >= Ar_1 ]", 0-3) = Ar_3 S("l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + 1, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_1 >= 1 ]", 0-0) = Ar_1 S("l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + 1, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_1 >= 1 ]", 0-1) = Ar_1 S("l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + 1, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_1 >= 1 ]", 0-2) = Ar_2 S("l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + 1, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_1 >= 1 ]", 0-3) = Ar_3 S("l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3))", 0-0) = 0 S("l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3))", 0-1) = Ar_1 S("l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3))", 0-2) = Ar_2 S("l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3))", 0-3) = Ar_3 orients the transitions l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_3 - 1)) [ Ar_3 >= 1 /\ Ar_2 >= 1 ] l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 - 1, Ar_3)) [ 0 >= Ar_3 /\ Ar_2 >= 1 ] l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_2)) [ Ar_2 >= 1 ] weakly and the transitions l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 - 1, Ar_3)) [ 0 >= Ar_3 /\ Ar_2 >= 1 ] l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_2)) [ Ar_2 >= 1 ] strictly and produces the following problem: 5: T: (Comp: 1, Cost: 1) l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3)) (Comp: Ar_1, Cost: 1) l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + 1, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_1 >= 1 ] (Comp: 1, Cost: 1) l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_0, Ar_3)) [ 0 >= Ar_1 ] (Comp: 2*Ar_1, Cost: 1) l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_2)) [ Ar_2 >= 1 ] (Comp: ?, Cost: 1) l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_3 - 1)) [ Ar_3 >= 1 /\ Ar_2 >= 1 ] (Comp: 2*Ar_1, Cost: 1) l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 - 1, Ar_3)) [ 0 >= Ar_3 /\ Ar_2 >= 1 ] (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(l3) = V_4 and size complexities S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-0) = Ar_0 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-1) = Ar_1 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-2) = Ar_2 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-3) = Ar_3 S("l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 - 1, Ar_3)) [ 0 >= Ar_3 /\\ Ar_2 >= 1 ]", 0-0) = Ar_1 S("l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 - 1, Ar_3)) [ 0 >= Ar_3 /\\ Ar_2 >= 1 ]", 0-1) = Ar_1 S("l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 - 1, Ar_3)) [ 0 >= Ar_3 /\\ Ar_2 >= 1 ]", 0-2) = Ar_1 S("l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 - 1, Ar_3)) [ 0 >= Ar_3 /\\ Ar_2 >= 1 ]", 0-3) = Ar_1 S("l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_3 - 1)) [ Ar_3 >= 1 /\\ Ar_2 >= 1 ]", 0-0) = Ar_1 S("l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_3 - 1)) [ Ar_3 >= 1 /\\ Ar_2 >= 1 ]", 0-1) = Ar_1 S("l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_3 - 1)) [ Ar_3 >= 1 /\\ Ar_2 >= 1 ]", 0-2) = Ar_1 S("l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_3 - 1)) [ Ar_3 >= 1 /\\ Ar_2 >= 1 ]", 0-3) = Ar_1 S("l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_2)) [ Ar_2 >= 1 ]", 0-0) = Ar_1 S("l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_2)) [ Ar_2 >= 1 ]", 0-1) = Ar_1 S("l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_2)) [ Ar_2 >= 1 ]", 0-2) = Ar_1 S("l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_2)) [ Ar_2 >= 1 ]", 0-3) = Ar_1 S("l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_0, Ar_3)) [ 0 >= Ar_1 ]", 0-0) = Ar_1 S("l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_0, Ar_3)) [ 0 >= Ar_1 ]", 0-1) = Ar_1 S("l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_0, Ar_3)) [ 0 >= Ar_1 ]", 0-2) = Ar_1 S("l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_0, Ar_3)) [ 0 >= Ar_1 ]", 0-3) = Ar_3 S("l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + 1, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_1 >= 1 ]", 0-0) = Ar_1 S("l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + 1, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_1 >= 1 ]", 0-1) = Ar_1 S("l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + 1, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_1 >= 1 ]", 0-2) = Ar_2 S("l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + 1, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_1 >= 1 ]", 0-3) = Ar_3 S("l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3))", 0-0) = 0 S("l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3))", 0-1) = Ar_1 S("l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3))", 0-2) = Ar_2 S("l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3))", 0-3) = Ar_3 orients the transitions l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_3 - 1)) [ Ar_3 >= 1 /\ Ar_2 >= 1 ] weakly and the transition l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_3 - 1)) [ Ar_3 >= 1 /\ Ar_2 >= 1 ] strictly and produces the following problem: 6: T: (Comp: 1, Cost: 1) l0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(0, Ar_1, Ar_2, Ar_3)) (Comp: Ar_1, Cost: 1) l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l1(Ar_0 + 1, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_1 >= 1 ] (Comp: 1, Cost: 1) l1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_0, Ar_3)) [ 0 >= Ar_1 ] (Comp: 2*Ar_1, Cost: 1) l2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_2)) [ Ar_2 >= 1 ] (Comp: 2*Ar_1^2, Cost: 1) l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l3(Ar_0, Ar_1, Ar_2, Ar_3 - 1)) [ Ar_3 >= 1 /\ Ar_2 >= 1 ] (Comp: 2*Ar_1, Cost: 1) l3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l2(Ar_0, Ar_1, Ar_2 - 1, Ar_3)) [ 0 >= Ar_3 /\ Ar_2 >= 1 ] (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(l0(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Complexity upper bound 5*Ar_1 + 2*Ar_1^2 + 2 Time: 0.107 sec (SMT: 0.088 sec) ---------------------------------------- (2) BOUNDS(1, n^2) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: l0 0: l0 -> l1 : A'=0, [], cost: 1 1: l1 -> l1 : A'=1+A, B'=-1+B, [ B>=1 ], cost: 1 2: l1 -> l2 : C'=A, [ 0>=B ], cost: 1 3: l2 -> l3 : D'=C, [ C>=1 ], cost: 1 4: l3 -> l3 : D'=-1+D, [ D>=1 && C>=1 ], cost: 1 5: l3 -> l2 : C'=-1+C, [ 0>=D && C>=1 ], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: l0 -> l1 : A'=0, [], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 1. Accelerating the following rules: 1: l1 -> l1 : A'=1+A, B'=-1+B, [ B>=1 ], cost: 1 Accelerated rule 1 with metering function B, yielding the new rule 6. Removing the simple loops: 1. Accelerating simple loops of location 3. Accelerating the following rules: 4: l3 -> l3 : D'=-1+D, [ D>=1 && C>=1 ], cost: 1 Accelerated rule 4 with metering function D, yielding the new rule 7. Removing the simple loops: 4. Accelerated all simple loops using metering functions (where possible): Start location: l0 0: l0 -> l1 : A'=0, [], cost: 1 2: l1 -> l2 : C'=A, [ 0>=B ], cost: 1 6: l1 -> l1 : A'=A+B, B'=0, [ B>=1 ], cost: B 3: l2 -> l3 : D'=C, [ C>=1 ], cost: 1 5: l3 -> l2 : C'=-1+C, [ 0>=D && C>=1 ], cost: 1 7: l3 -> l3 : D'=0, [ D>=1 && C>=1 ], cost: D Chained accelerated rules (with incoming rules): Start location: l0 0: l0 -> l1 : A'=0, [], cost: 1 8: l0 -> l1 : A'=B, B'=0, [ B>=1 ], cost: 1+B 2: l1 -> l2 : C'=A, [ 0>=B ], cost: 1 3: l2 -> l3 : D'=C, [ C>=1 ], cost: 1 9: l2 -> l3 : D'=0, [ C>=1 ], cost: 1+C 5: l3 -> l2 : C'=-1+C, [ 0>=D && C>=1 ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: l0 10: l0 -> l2 : A'=0, C'=0, [ 0>=B ], cost: 2 11: l0 -> l2 : A'=B, B'=0, C'=B, [ B>=1 ], cost: 2+B 12: l2 -> l2 : C'=-1+C, D'=0, [ C>=1 ], cost: 2+C Accelerating simple loops of location 2. Accelerating the following rules: 12: l2 -> l2 : C'=-1+C, D'=0, [ C>=1 ], cost: 2+C Accelerated rule 12 with metering function C, yielding the new rule 13. Removing the simple loops: 12. Accelerated all simple loops using metering functions (where possible): Start location: l0 10: l0 -> l2 : A'=0, C'=0, [ 0>=B ], cost: 2 11: l0 -> l2 : A'=B, B'=0, C'=B, [ B>=1 ], cost: 2+B 13: l2 -> l2 : C'=0, D'=0, [ C>=1 ], cost: 5/2*C+1/2*C^2 Chained accelerated rules (with incoming rules): Start location: l0 10: l0 -> l2 : A'=0, C'=0, [ 0>=B ], cost: 2 11: l0 -> l2 : A'=B, B'=0, C'=B, [ B>=1 ], cost: 2+B 14: l0 -> l2 : A'=B, B'=0, C'=0, D'=0, [ B>=1 ], cost: 2+7/2*B+1/2*B^2 Removed unreachable locations (and leaf rules with constant cost): Start location: l0 11: l0 -> l2 : A'=B, B'=0, C'=B, [ B>=1 ], cost: 2+B 14: l0 -> l2 : A'=B, B'=0, C'=0, D'=0, [ B>=1 ], cost: 2+7/2*B+1/2*B^2 ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: l0 11: l0 -> l2 : A'=B, B'=0, C'=B, [ B>=1 ], cost: 2+B 14: l0 -> l2 : A'=B, B'=0, C'=0, D'=0, [ B>=1 ], cost: 2+7/2*B+1/2*B^2 Computing asymptotic complexity for rule 11 Solved the limit problem by the following transformations: Created initial limit problem: B (+/+!), 2+B (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {B==n} resulting limit problem: [solved] Solution: B / n Resulting cost 2+n has complexity: Poly(n^1) Found new complexity Poly(n^1). Computing asymptotic complexity for rule 14 Solved the limit problem by the following transformations: Created initial limit problem: 2+7/2*B+1/2*B^2 (+), B (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {B==n} resulting limit problem: [solved] Solution: B / n Resulting cost 2+1/2*n^2+7/2*n has complexity: Poly(n^2) Found new complexity Poly(n^2). Obtained the following overall complexity (w.r.t. the length of the input n): Complexity: Poly(n^2) Cpx degree: 2 Solved cost: 2+1/2*n^2+7/2*n Rule cost: 2+7/2*B+1/2*B^2 Rule guard: [ B>=1 ] WORST_CASE(Omega(n^2),?) ---------------------------------------- (4) BOUNDS(n^2, INF)