/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^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^1, n^2). (0) CpxIntTrs (1) Koat Proof [FINISHED, 175 ms] (2) BOUNDS(1, n^2) (3) Loat Proof [FINISHED, 2619 ms] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: eval1(A, B, C, D) -> Com_1(eval2(A - 1, B, C, D)) :|: A >= 2 eval1(A, B, C, D) -> Com_1(eval2(A, B - 1, C, D)) :|: 1 >= A eval2(A, B, C, D) -> Com_1(eval3(A, B, A, 2 * A)) :|: B >= 2 eval3(A, B, C, D) -> Com_1(eval4(A, B, C, D)) :|: B >= D && B >= 1 + D eval3(A, B, C, D) -> Com_1(eval4(A, B, C, D + 1)) :|: B >= D && B >= 1 + D eval3(A, B, C, D) -> Com_1(eval3(A, B, D, 2 * D)) :|: B >= D && B >= 1 + D && D >= 1 eval3(A, B, C, D) -> Com_1(eval3(A, B, D + 1, 2 * D + 2)) :|: B >= D && B >= 1 + D && D >= 1 eval3(A, B, C, D) -> Com_1(eval4(A, B, C, D)) :|: B >= D && B <= D eval3(A, B, C, D) -> Com_1(eval3(A, B, D, 2 * D)) :|: D >= 1 && B >= D && B <= D eval4(A, B, C, D) -> Com_1(eval2(A - 1, B, C, D)) :|: A >= 2 && A >= 1 && B >= 2 eval4(A, B, C, D) -> Com_1(eval2(A, B - 1, C, D)) :|: B >= 2 && A >= 1 && A <= 1 The start-symbols are:[eval1_4] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 82*Ar_0 + 76*Ar_1 + 18*Ar_0*Ar_1 + 6*Ar_1^2 + 12*Ar_0^2 + 70) Initial complexity problem: 1: T: (Comp: ?, Cost: 1) eval1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 2 ] (Comp: ?, Cost: 1) eval1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_2, Ar_3)) [ 1 >= Ar_0 ] (Comp: ?, Cost: 1) eval2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, Ar_0, 2*Ar_0)) [ Ar_1 >= 2 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_2, Ar_3 + 1)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, Ar_3, 2*Ar_3)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 /\ Ar_3 >= 1 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, Ar_3 + 1, 2*Ar_3 + 2)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 /\ Ar_3 >= 1 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 = Ar_3 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, Ar_3, 2*Ar_3)) [ Ar_3 >= 1 /\ Ar_1 = Ar_3 ] (Comp: ?, Cost: 1) eval4(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 2 /\ Ar_0 >= 1 /\ Ar_1 >= 2 ] (Comp: ?, Cost: 1) eval4(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_2, Ar_3)) [ Ar_1 >= 2 /\ Ar_0 = 1 ] (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(eval1(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Slicing away variables that do not contribute to conditions from problem 1 leaves variables [Ar_0, Ar_1, Ar_3]. We thus obtain the following problem: 2: T: (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_3) -> Com_1(eval1(Ar_0, Ar_1, Ar_3)) [ 0 <= 0 ] (Comp: ?, Cost: 1) eval4(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_3)) [ Ar_1 >= 2 /\ Ar_0 = 1 ] (Comp: ?, Cost: 1) eval4(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_3)) [ Ar_0 >= 2 /\ Ar_0 >= 1 /\ Ar_1 >= 2 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_3 >= 1 /\ Ar_1 = Ar_3 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 = Ar_3 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3 + 2)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 /\ Ar_3 >= 1 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 /\ Ar_3 >= 1 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3 + 1)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 ] (Comp: ?, Cost: 1) eval2(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_0)) [ Ar_1 >= 2 ] (Comp: ?, Cost: 1) eval1(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_3)) [ 1 >= Ar_0 ] (Comp: ?, Cost: 1) eval1(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_3)) [ Ar_0 >= 2 ] start location: koat_start leaf cost: 0 Repeatedly propagating knowledge in problem 2 produces the following problem: 3: T: (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_3) -> Com_1(eval1(Ar_0, Ar_1, Ar_3)) [ 0 <= 0 ] (Comp: ?, Cost: 1) eval4(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_3)) [ Ar_1 >= 2 /\ Ar_0 = 1 ] (Comp: ?, Cost: 1) eval4(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_3)) [ Ar_0 >= 2 /\ Ar_0 >= 1 /\ Ar_1 >= 2 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_3 >= 1 /\ Ar_1 = Ar_3 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 = Ar_3 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3 + 2)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 /\ Ar_3 >= 1 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 /\ Ar_3 >= 1 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3 + 1)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 ] (Comp: ?, Cost: 1) eval2(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_0)) [ Ar_1 >= 2 ] (Comp: 1, Cost: 1) eval1(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_3)) [ 1 >= Ar_0 ] (Comp: 1, Cost: 1) eval1(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_3)) [ Ar_0 >= 2 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(koat_start) = V_1 + V_2 Pol(eval1) = V_1 + V_2 Pol(eval4) = V_1 + V_2 Pol(eval2) = V_1 + V_2 Pol(eval3) = V_1 + V_2 orients all transitions weakly and the transitions eval4(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_3)) [ Ar_1 >= 2 /\ Ar_0 = 1 ] eval4(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_3)) [ Ar_0 >= 2 /\ Ar_0 >= 1 /\ Ar_1 >= 2 ] strictly and produces the following problem: 4: T: (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_3) -> Com_1(eval1(Ar_0, Ar_1, Ar_3)) [ 0 <= 0 ] (Comp: Ar_0 + Ar_1, Cost: 1) eval4(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_3)) [ Ar_1 >= 2 /\ Ar_0 = 1 ] (Comp: Ar_0 + Ar_1, Cost: 1) eval4(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_3)) [ Ar_0 >= 2 /\ Ar_0 >= 1 /\ Ar_1 >= 2 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_3 >= 1 /\ Ar_1 = Ar_3 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 = Ar_3 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3 + 2)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 /\ Ar_3 >= 1 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 /\ Ar_3 >= 1 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3 + 1)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 ] (Comp: ?, Cost: 1) eval2(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_0)) [ Ar_1 >= 2 ] (Comp: 1, Cost: 1) eval1(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_3)) [ 1 >= Ar_0 ] (Comp: 1, Cost: 1) eval1(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_3)) [ Ar_0 >= 2 ] start location: koat_start leaf cost: 0 Repeatedly propagating knowledge in problem 4 produces the following problem: 5: T: (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_3) -> Com_1(eval1(Ar_0, Ar_1, Ar_3)) [ 0 <= 0 ] (Comp: Ar_0 + Ar_1, Cost: 1) eval4(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_3)) [ Ar_1 >= 2 /\ Ar_0 = 1 ] (Comp: Ar_0 + Ar_1, Cost: 1) eval4(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_3)) [ Ar_0 >= 2 /\ Ar_0 >= 1 /\ Ar_1 >= 2 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_3 >= 1 /\ Ar_1 = Ar_3 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 = Ar_3 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3 + 2)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 /\ Ar_3 >= 1 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 /\ Ar_3 >= 1 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3 + 1)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 ] (Comp: 2*Ar_0 + 2*Ar_1 + 2, Cost: 1) eval2(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_0)) [ Ar_1 >= 2 ] (Comp: 1, Cost: 1) eval1(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_3)) [ 1 >= Ar_0 ] (Comp: 1, Cost: 1) eval1(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_3)) [ Ar_0 >= 2 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(eval3) = 1 Pol(eval4) = 0 and size complexities S("eval1(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_3)) [ Ar_0 >= 2 ]", 0-0) = Ar_0 S("eval1(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_3)) [ Ar_0 >= 2 ]", 0-1) = Ar_1 S("eval1(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_3)) [ Ar_0 >= 2 ]", 0-2) = Ar_3 S("eval1(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_3)) [ 1 >= Ar_0 ]", 0-0) = Ar_0 S("eval1(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_3)) [ 1 >= Ar_0 ]", 0-1) = Ar_1 + 1 S("eval1(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_3)) [ 1 >= Ar_0 ]", 0-2) = Ar_3 S("eval2(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_0)) [ Ar_1 >= 2 ]", 0-0) = Ar_0 + 1 S("eval2(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_0)) [ Ar_1 >= 2 ]", 0-1) = Ar_1 + 1 S("eval2(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_0)) [ Ar_1 >= 2 ]", 0-2) = 2*Ar_0 + 8 S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 >= Ar_3 /\\ Ar_1 >= Ar_3 + 1 ]", 0-0) = Ar_0 + 1 S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 >= Ar_3 /\\ Ar_1 >= Ar_3 + 1 ]", 0-1) = Ar_1 + 1 S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 >= Ar_3 /\\ Ar_1 >= Ar_3 + 1 ]", 0-2) = ? S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3 + 1)) [ Ar_1 >= Ar_3 /\\ Ar_1 >= Ar_3 + 1 ]", 0-0) = Ar_0 + 1 S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3 + 1)) [ Ar_1 >= Ar_3 /\\ Ar_1 >= Ar_3 + 1 ]", 0-1) = Ar_1 + 1 S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3 + 1)) [ Ar_1 >= Ar_3 /\\ Ar_1 >= Ar_3 + 1 ]", 0-2) = ? S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_1 >= Ar_3 /\\ Ar_1 >= Ar_3 + 1 /\\ Ar_3 >= 1 ]", 0-0) = Ar_0 + 1 S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_1 >= Ar_3 /\\ Ar_1 >= Ar_3 + 1 /\\ Ar_3 >= 1 ]", 0-1) = Ar_1 + 1 S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_1 >= Ar_3 /\\ Ar_1 >= Ar_3 + 1 /\\ Ar_3 >= 1 ]", 0-2) = ? S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3 + 2)) [ Ar_1 >= Ar_3 /\\ Ar_1 >= Ar_3 + 1 /\\ Ar_3 >= 1 ]", 0-0) = Ar_0 + 1 S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3 + 2)) [ Ar_1 >= Ar_3 /\\ Ar_1 >= Ar_3 + 1 /\\ Ar_3 >= 1 ]", 0-1) = Ar_1 + 1 S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3 + 2)) [ Ar_1 >= Ar_3 /\\ Ar_1 >= Ar_3 + 1 /\\ Ar_3 >= 1 ]", 0-2) = ? S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 = Ar_3 ]", 0-0) = Ar_0 + 1 S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 = Ar_3 ]", 0-1) = Ar_1 + 1 S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 = Ar_3 ]", 0-2) = ? S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_3 >= 1 /\\ Ar_1 = Ar_3 ]", 0-0) = Ar_0 + 1 S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_3 >= 1 /\\ Ar_1 = Ar_3 ]", 0-1) = Ar_1 + 1 S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_3 >= 1 /\\ Ar_1 = Ar_3 ]", 0-2) = ? S("eval4(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_3)) [ Ar_0 >= 2 /\\ Ar_0 >= 1 /\\ Ar_1 >= 2 ]", 0-0) = Ar_0 + 1 S("eval4(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_3)) [ Ar_0 >= 2 /\\ Ar_0 >= 1 /\\ Ar_1 >= 2 ]", 0-1) = Ar_1 + 1 S("eval4(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_3)) [ Ar_0 >= 2 /\\ Ar_0 >= 1 /\\ Ar_1 >= 2 ]", 0-2) = ? S("eval4(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_3)) [ Ar_1 >= 2 /\\ Ar_0 = 1 ]", 0-0) = 1 S("eval4(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_3)) [ Ar_1 >= 2 /\\ Ar_0 = 1 ]", 0-1) = Ar_1 + 1 S("eval4(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_3)) [ Ar_1 >= 2 /\\ Ar_0 = 1 ]", 0-2) = ? S("koat_start(Ar_0, Ar_1, Ar_3) -> Com_1(eval1(Ar_0, Ar_1, Ar_3)) [ 0 <= 0 ]", 0-0) = Ar_0 S("koat_start(Ar_0, Ar_1, Ar_3) -> Com_1(eval1(Ar_0, Ar_1, Ar_3)) [ 0 <= 0 ]", 0-1) = Ar_1 S("koat_start(Ar_0, Ar_1, Ar_3) -> Com_1(eval1(Ar_0, Ar_1, Ar_3)) [ 0 <= 0 ]", 0-2) = Ar_3 orients the transitions eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3 + 1)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 ] eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 ] eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 = Ar_3 ] eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3 + 2)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 /\ Ar_3 >= 1 ] eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 /\ Ar_3 >= 1 ] eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_3 >= 1 /\ Ar_1 = Ar_3 ] weakly and the transitions eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3 + 1)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 ] eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 ] eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 = Ar_3 ] strictly and produces the following problem: 6: T: (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_3) -> Com_1(eval1(Ar_0, Ar_1, Ar_3)) [ 0 <= 0 ] (Comp: Ar_0 + Ar_1, Cost: 1) eval4(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_3)) [ Ar_1 >= 2 /\ Ar_0 = 1 ] (Comp: Ar_0 + Ar_1, Cost: 1) eval4(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_3)) [ Ar_0 >= 2 /\ Ar_0 >= 1 /\ Ar_1 >= 2 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_3 >= 1 /\ Ar_1 = Ar_3 ] (Comp: 2*Ar_0 + 2*Ar_1 + 2, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 = Ar_3 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3 + 2)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 /\ Ar_3 >= 1 ] (Comp: ?, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 /\ Ar_3 >= 1 ] (Comp: 2*Ar_0 + 2*Ar_1 + 2, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3 + 1)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 ] (Comp: 2*Ar_0 + 2*Ar_1 + 2, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 ] (Comp: 2*Ar_0 + 2*Ar_1 + 2, Cost: 1) eval2(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_0)) [ Ar_1 >= 2 ] (Comp: 1, Cost: 1) eval1(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_3)) [ 1 >= Ar_0 ] (Comp: 1, Cost: 1) eval1(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_3)) [ Ar_0 >= 2 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(eval3) = V_2 - V_3 + 1 and size complexities S("eval1(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_3)) [ Ar_0 >= 2 ]", 0-0) = Ar_0 S("eval1(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_3)) [ Ar_0 >= 2 ]", 0-1) = Ar_1 S("eval1(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_3)) [ Ar_0 >= 2 ]", 0-2) = Ar_3 S("eval1(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_3)) [ 1 >= Ar_0 ]", 0-0) = Ar_0 S("eval1(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_3)) [ 1 >= Ar_0 ]", 0-1) = Ar_1 + 1 S("eval1(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_3)) [ 1 >= Ar_0 ]", 0-2) = Ar_3 S("eval2(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_0)) [ Ar_1 >= 2 ]", 0-0) = Ar_0 + 1 S("eval2(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_0)) [ Ar_1 >= 2 ]", 0-1) = Ar_1 + 1 S("eval2(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_0)) [ Ar_1 >= 2 ]", 0-2) = 2*Ar_0 + 8 S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 >= Ar_3 /\\ Ar_1 >= Ar_3 + 1 ]", 0-0) = Ar_0 + 1 S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 >= Ar_3 /\\ Ar_1 >= Ar_3 + 1 ]", 0-1) = Ar_1 + 1 S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 >= Ar_3 /\\ Ar_1 >= Ar_3 + 1 ]", 0-2) = ? S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3 + 1)) [ Ar_1 >= Ar_3 /\\ Ar_1 >= Ar_3 + 1 ]", 0-0) = Ar_0 + 1 S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3 + 1)) [ Ar_1 >= Ar_3 /\\ Ar_1 >= Ar_3 + 1 ]", 0-1) = Ar_1 + 1 S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3 + 1)) [ Ar_1 >= Ar_3 /\\ Ar_1 >= Ar_3 + 1 ]", 0-2) = ? S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_1 >= Ar_3 /\\ Ar_1 >= Ar_3 + 1 /\\ Ar_3 >= 1 ]", 0-0) = Ar_0 + 1 S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_1 >= Ar_3 /\\ Ar_1 >= Ar_3 + 1 /\\ Ar_3 >= 1 ]", 0-1) = Ar_1 + 1 S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_1 >= Ar_3 /\\ Ar_1 >= Ar_3 + 1 /\\ Ar_3 >= 1 ]", 0-2) = ? S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3 + 2)) [ Ar_1 >= Ar_3 /\\ Ar_1 >= Ar_3 + 1 /\\ Ar_3 >= 1 ]", 0-0) = Ar_0 + 1 S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3 + 2)) [ Ar_1 >= Ar_3 /\\ Ar_1 >= Ar_3 + 1 /\\ Ar_3 >= 1 ]", 0-1) = Ar_1 + 1 S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3 + 2)) [ Ar_1 >= Ar_3 /\\ Ar_1 >= Ar_3 + 1 /\\ Ar_3 >= 1 ]", 0-2) = ? S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 = Ar_3 ]", 0-0) = Ar_0 + 1 S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 = Ar_3 ]", 0-1) = Ar_1 + 1 S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 = Ar_3 ]", 0-2) = ? S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_3 >= 1 /\\ Ar_1 = Ar_3 ]", 0-0) = Ar_0 + 1 S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_3 >= 1 /\\ Ar_1 = Ar_3 ]", 0-1) = Ar_1 + 1 S("eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_3 >= 1 /\\ Ar_1 = Ar_3 ]", 0-2) = ? S("eval4(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_3)) [ Ar_0 >= 2 /\\ Ar_0 >= 1 /\\ Ar_1 >= 2 ]", 0-0) = Ar_0 + 1 S("eval4(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_3)) [ Ar_0 >= 2 /\\ Ar_0 >= 1 /\\ Ar_1 >= 2 ]", 0-1) = Ar_1 + 1 S("eval4(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_3)) [ Ar_0 >= 2 /\\ Ar_0 >= 1 /\\ Ar_1 >= 2 ]", 0-2) = ? S("eval4(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_3)) [ Ar_1 >= 2 /\\ Ar_0 = 1 ]", 0-0) = 1 S("eval4(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_3)) [ Ar_1 >= 2 /\\ Ar_0 = 1 ]", 0-1) = Ar_1 + 1 S("eval4(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_3)) [ Ar_1 >= 2 /\\ Ar_0 = 1 ]", 0-2) = ? S("koat_start(Ar_0, Ar_1, Ar_3) -> Com_1(eval1(Ar_0, Ar_1, Ar_3)) [ 0 <= 0 ]", 0-0) = Ar_0 S("koat_start(Ar_0, Ar_1, Ar_3) -> Com_1(eval1(Ar_0, Ar_1, Ar_3)) [ 0 <= 0 ]", 0-1) = Ar_1 S("koat_start(Ar_0, Ar_1, Ar_3) -> Com_1(eval1(Ar_0, Ar_1, Ar_3)) [ 0 <= 0 ]", 0-2) = Ar_3 orients the transitions eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3 + 2)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 /\ Ar_3 >= 1 ] eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 /\ Ar_3 >= 1 ] eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_3 >= 1 /\ Ar_1 = Ar_3 ] weakly and the transitions eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3 + 2)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 /\ Ar_3 >= 1 ] eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 /\ Ar_3 >= 1 ] eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_3 >= 1 /\ Ar_1 = Ar_3 ] strictly and produces the following problem: 7: T: (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_3) -> Com_1(eval1(Ar_0, Ar_1, Ar_3)) [ 0 <= 0 ] (Comp: Ar_0 + Ar_1, Cost: 1) eval4(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_3)) [ Ar_1 >= 2 /\ Ar_0 = 1 ] (Comp: Ar_0 + Ar_1, Cost: 1) eval4(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_3)) [ Ar_0 >= 2 /\ Ar_0 >= 1 /\ Ar_1 >= 2 ] (Comp: 6*Ar_0*Ar_1 + 2*Ar_1^2 + 4*Ar_0^2 + 22*Ar_1 + 24*Ar_0 + 20, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_3 >= 1 /\ Ar_1 = Ar_3 ] (Comp: 2*Ar_0 + 2*Ar_1 + 2, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 = Ar_3 ] (Comp: 6*Ar_0*Ar_1 + 2*Ar_1^2 + 4*Ar_0^2 + 22*Ar_1 + 24*Ar_0 + 20, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3 + 2)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 /\ Ar_3 >= 1 ] (Comp: 6*Ar_0*Ar_1 + 2*Ar_1^2 + 4*Ar_0^2 + 22*Ar_1 + 24*Ar_0 + 20, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_3)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 /\ Ar_3 >= 1 ] (Comp: 2*Ar_0 + 2*Ar_1 + 2, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3 + 1)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 ] (Comp: 2*Ar_0 + 2*Ar_1 + 2, Cost: 1) eval3(Ar_0, Ar_1, Ar_3) -> Com_1(eval4(Ar_0, Ar_1, Ar_3)) [ Ar_1 >= Ar_3 /\ Ar_1 >= Ar_3 + 1 ] (Comp: 2*Ar_0 + 2*Ar_1 + 2, Cost: 1) eval2(Ar_0, Ar_1, Ar_3) -> Com_1(eval3(Ar_0, Ar_1, 2*Ar_0)) [ Ar_1 >= 2 ] (Comp: 1, Cost: 1) eval1(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0, Ar_1 - 1, Ar_3)) [ 1 >= Ar_0 ] (Comp: 1, Cost: 1) eval1(Ar_0, Ar_1, Ar_3) -> Com_1(eval2(Ar_0 - 1, Ar_1, Ar_3)) [ Ar_0 >= 2 ] start location: koat_start leaf cost: 0 Complexity upper bound 82*Ar_0 + 76*Ar_1 + 18*Ar_0*Ar_1 + 6*Ar_1^2 + 12*Ar_0^2 + 70 Time: 0.286 sec (SMT: 0.240 sec) ---------------------------------------- (2) BOUNDS(1, n^2) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: eval1 0: eval1 -> eval2 : A'=-1+A, [ A>=2 ], cost: 1 1: eval1 -> eval2 : B'=-1+B, [ 1>=A ], cost: 1 2: eval2 -> eval3 : C'=A, D'=2*A, [ B>=2 ], cost: 1 3: eval3 -> eval4 : [ B>=D && B>=1+D ], cost: 1 4: eval3 -> eval4 : D'=1+D, [ B>=D && B>=1+D ], cost: 1 5: eval3 -> eval3 : C'=D, D'=2*D, [ B>=D && B>=1+D && D>=1 ], cost: 1 6: eval3 -> eval3 : C'=1+D, D'=2+2*D, [ B>=D && B>=1+D && D>=1 ], cost: 1 7: eval3 -> eval4 : [ B==D ], cost: 1 8: eval3 -> eval3 : C'=D, D'=2*D, [ D>=1 && B==D ], cost: 1 9: eval4 -> eval2 : A'=-1+A, [ A>=2 && A>=1 && B>=2 ], cost: 1 10: eval4 -> eval2 : B'=-1+B, [ B>=2 && A==1 ], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: eval1 -> eval2 : A'=-1+A, [ A>=2 ], cost: 1 Simplified all rules, resulting in: Start location: eval1 0: eval1 -> eval2 : A'=-1+A, [ A>=2 ], cost: 1 1: eval1 -> eval2 : B'=-1+B, [ 1>=A ], cost: 1 2: eval2 -> eval3 : C'=A, D'=2*A, [ B>=2 ], cost: 1 3: eval3 -> eval4 : [ B>=1+D ], cost: 1 4: eval3 -> eval4 : D'=1+D, [ B>=1+D ], cost: 1 5: eval3 -> eval3 : C'=D, D'=2*D, [ B>=1+D && D>=1 ], cost: 1 6: eval3 -> eval3 : C'=1+D, D'=2+2*D, [ B>=1+D && D>=1 ], cost: 1 7: eval3 -> eval4 : [ B==D ], cost: 1 8: eval3 -> eval3 : C'=D, D'=2*D, [ D>=1 && B==D ], cost: 1 9: eval4 -> eval2 : A'=-1+A, [ A>=2 && B>=2 ], cost: 1 10: eval4 -> eval2 : B'=-1+B, [ B>=2 && A==1 ], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 2. Accelerating the following rules: 5: eval3 -> eval3 : C'=D, D'=2*D, [ B>=1+D && D>=1 ], cost: 1 6: eval3 -> eval3 : C'=1+D, D'=2+2*D, [ B>=1+D && D>=1 ], cost: 1 8: eval3 -> eval3 : C'=D, D'=2*D, [ D>=1 && B==D ], cost: 1 Found no metering function for rule 5. Found no metering function for rule 6. Found no metering function for rule 8. Removing the simple loops:. Accelerated all simple loops using metering functions (where possible): Start location: eval1 0: eval1 -> eval2 : A'=-1+A, [ A>=2 ], cost: 1 1: eval1 -> eval2 : B'=-1+B, [ 1>=A ], cost: 1 2: eval2 -> eval3 : C'=A, D'=2*A, [ B>=2 ], cost: 1 3: eval3 -> eval4 : [ B>=1+D ], cost: 1 4: eval3 -> eval4 : D'=1+D, [ B>=1+D ], cost: 1 5: eval3 -> eval3 : C'=D, D'=2*D, [ B>=1+D && D>=1 ], cost: 1 6: eval3 -> eval3 : C'=1+D, D'=2+2*D, [ B>=1+D && D>=1 ], cost: 1 7: eval3 -> eval4 : [ B==D ], cost: 1 8: eval3 -> eval3 : C'=D, D'=2*D, [ D>=1 && B==D ], cost: 1 9: eval4 -> eval2 : A'=-1+A, [ A>=2 && B>=2 ], cost: 1 10: eval4 -> eval2 : B'=-1+B, [ B>=2 && A==1 ], cost: 1 Chained accelerated rules (with incoming rules): Start location: eval1 0: eval1 -> eval2 : A'=-1+A, [ A>=2 ], cost: 1 1: eval1 -> eval2 : B'=-1+B, [ 1>=A ], cost: 1 2: eval2 -> eval3 : C'=A, D'=2*A, [ B>=2 ], cost: 1 11: eval2 -> eval3 : C'=2*A, D'=4*A, [ B>=2 && B>=1+2*A && 2*A>=1 ], cost: 2 12: eval2 -> eval3 : C'=1+2*A, D'=2+4*A, [ B>=2 && B>=1+2*A && 2*A>=1 ], cost: 2 13: eval2 -> eval3 : C'=2*A, D'=4*A, [ B>=2 && 2*A>=1 && B==2*A ], cost: 2 3: eval3 -> eval4 : [ B>=1+D ], cost: 1 4: eval3 -> eval4 : D'=1+D, [ B>=1+D ], cost: 1 7: eval3 -> eval4 : [ B==D ], cost: 1 9: eval4 -> eval2 : A'=-1+A, [ A>=2 && B>=2 ], cost: 1 10: eval4 -> eval2 : B'=-1+B, [ B>=2 && A==1 ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: eval1 0: eval1 -> eval2 : A'=-1+A, [ A>=2 ], cost: 1 1: eval1 -> eval2 : B'=-1+B, [ 1>=A ], cost: 1 14: eval2 -> eval4 : C'=A, D'=2*A, [ B>=2 && B>=1+2*A ], cost: 2 15: eval2 -> eval4 : C'=A, D'=1+2*A, [ B>=2 && B>=1+2*A ], cost: 2 16: eval2 -> eval4 : C'=A, D'=2*A, [ B>=2 && B==2*A ], cost: 2 17: eval2 -> eval4 : C'=2*A, D'=4*A, [ B>=2 && B>=1+2*A && 2*A>=1 && B>=1+4*A ], cost: 3 18: eval2 -> eval4 : C'=2*A, D'=1+4*A, [ B>=2 && B>=1+2*A && 2*A>=1 && B>=1+4*A ], cost: 3 19: eval2 -> eval4 : C'=2*A, D'=4*A, [ B>=2 && B>=1+2*A && 2*A>=1 && B==4*A ], cost: 3 20: eval2 -> eval4 : C'=1+2*A, D'=2+4*A, [ B>=2 && B>=1+2*A && 2*A>=1 && B>=3+4*A ], cost: 3 21: eval2 -> eval4 : C'=1+2*A, D'=3+4*A, [ B>=2 && B>=1+2*A && 2*A>=1 && B>=3+4*A ], cost: 3 22: eval2 -> eval4 : C'=1+2*A, D'=2+4*A, [ B>=2 && B>=1+2*A && 2*A>=1 && B==2+4*A ], cost: 3 9: eval4 -> eval2 : A'=-1+A, [ A>=2 && B>=2 ], cost: 1 10: eval4 -> eval2 : B'=-1+B, [ B>=2 && A==1 ], cost: 1 Applied pruning (of leafs and parallel rules): Start location: eval1 0: eval1 -> eval2 : A'=-1+A, [ A>=2 ], cost: 1 1: eval1 -> eval2 : B'=-1+B, [ 1>=A ], cost: 1 14: eval2 -> eval4 : C'=A, D'=2*A, [ B>=2 && B>=1+2*A ], cost: 2 15: eval2 -> eval4 : C'=A, D'=1+2*A, [ B>=2 && B>=1+2*A ], cost: 2 17: eval2 -> eval4 : C'=2*A, D'=4*A, [ B>=2 && B>=1+2*A && 2*A>=1 && B>=1+4*A ], cost: 3 18: eval2 -> eval4 : C'=2*A, D'=1+4*A, [ B>=2 && B>=1+2*A && 2*A>=1 && B>=1+4*A ], cost: 3 20: eval2 -> eval4 : C'=1+2*A, D'=2+4*A, [ B>=2 && B>=1+2*A && 2*A>=1 && B>=3+4*A ], cost: 3 9: eval4 -> eval2 : A'=-1+A, [ A>=2 && B>=2 ], cost: 1 10: eval4 -> eval2 : B'=-1+B, [ B>=2 && A==1 ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: eval1 0: eval1 -> eval2 : A'=-1+A, [ A>=2 ], cost: 1 1: eval1 -> eval2 : B'=-1+B, [ 1>=A ], cost: 1 23: eval2 -> eval2 : A'=-1+A, C'=A, D'=2*A, [ B>=2 && B>=1+2*A && A>=2 ], cost: 3 24: eval2 -> eval2 : B'=-1+B, C'=A, D'=2*A, [ B>=2 && B>=1+2*A && A==1 ], cost: 3 25: eval2 -> eval2 : A'=-1+A, C'=A, D'=1+2*A, [ B>=2 && B>=1+2*A && A>=2 ], cost: 3 26: eval2 -> eval2 : B'=-1+B, C'=A, D'=1+2*A, [ B>=2 && B>=1+2*A && A==1 ], cost: 3 27: eval2 -> eval2 : A'=-1+A, C'=2*A, D'=4*A, [ B>=2 && B>=1+2*A && 2*A>=1 && B>=1+4*A && A>=2 ], cost: 4 28: eval2 -> eval2 : B'=-1+B, C'=2*A, D'=4*A, [ B>=2 && B>=1+2*A && 2*A>=1 && B>=1+4*A && A==1 ], cost: 4 29: eval2 -> eval2 : A'=-1+A, C'=2*A, D'=1+4*A, [ B>=2 && B>=1+2*A && 2*A>=1 && B>=1+4*A && A>=2 ], cost: 4 30: eval2 -> eval2 : B'=-1+B, C'=2*A, D'=1+4*A, [ B>=2 && B>=1+2*A && 2*A>=1 && B>=1+4*A && A==1 ], cost: 4 31: eval2 -> eval2 : A'=-1+A, C'=1+2*A, D'=2+4*A, [ B>=2 && B>=1+2*A && 2*A>=1 && B>=3+4*A && A>=2 ], cost: 4 32: eval2 -> eval2 : B'=-1+B, C'=1+2*A, D'=2+4*A, [ B>=2 && B>=1+2*A && 2*A>=1 && B>=3+4*A && A==1 ], cost: 4 Applied pruning (of leafs and parallel rules): Start location: eval1 0: eval1 -> eval2 : A'=-1+A, [ A>=2 ], cost: 1 1: eval1 -> eval2 : B'=-1+B, [ 1>=A ], cost: 1 23: eval2 -> eval2 : A'=-1+A, C'=A, D'=2*A, [ B>=2 && B>=1+2*A && A>=2 ], cost: 3 24: eval2 -> eval2 : B'=-1+B, C'=A, D'=2*A, [ B>=2 && B>=1+2*A && A==1 ], cost: 3 26: eval2 -> eval2 : B'=-1+B, C'=A, D'=1+2*A, [ B>=2 && B>=1+2*A && A==1 ], cost: 3 27: eval2 -> eval2 : A'=-1+A, C'=2*A, D'=4*A, [ B>=2 && B>=1+2*A && 2*A>=1 && B>=1+4*A && A>=2 ], cost: 4 28: eval2 -> eval2 : B'=-1+B, C'=2*A, D'=4*A, [ B>=2 && B>=1+2*A && 2*A>=1 && B>=1+4*A && A==1 ], cost: 4 Accelerating simple loops of location 1. Accelerating the following rules: 23: eval2 -> eval2 : A'=-1+A, C'=A, D'=2*A, [ B>=2 && B>=1+2*A && A>=2 ], cost: 3 24: eval2 -> eval2 : B'=-1+B, C'=A, D'=2*A, [ B>=2 && B>=1+2*A && A==1 ], cost: 3 26: eval2 -> eval2 : B'=-1+B, C'=A, D'=1+2*A, [ B>=2 && B>=1+2*A && A==1 ], cost: 3 27: eval2 -> eval2 : A'=-1+A, C'=2*A, D'=4*A, [ B>=2 && B>=1+2*A && 2*A>=1 && B>=1+4*A && A>=2 ], cost: 4 28: eval2 -> eval2 : B'=-1+B, C'=2*A, D'=4*A, [ B>=2 && B>=1+2*A && 2*A>=1 && B>=1+4*A && A==1 ], cost: 4 Accelerated rule 23 with metering function -1+A, yielding the new rule 33. Accelerated rule 24 with metering function -2*A+B, yielding the new rule 34. Accelerated rule 26 with metering function -2*A+B, yielding the new rule 35. Accelerated rule 27 with metering function -1+A, yielding the new rule 36. Accelerated rule 28 with metering function -4*A+B, yielding the new rule 37. Removing the simple loops: 23 24 26 27 28. Accelerated all simple loops using metering functions (where possible): Start location: eval1 0: eval1 -> eval2 : A'=-1+A, [ A>=2 ], cost: 1 1: eval1 -> eval2 : B'=-1+B, [ 1>=A ], cost: 1 33: eval2 -> eval2 : A'=1, C'=2, D'=4, [ B>=2 && B>=1+2*A && A>=2 ], cost: -3+3*A 34: eval2 -> eval2 : B'=2*A, C'=A, D'=2*A, [ B>=2 && B>=1+2*A && A==1 ], cost: -6*A+3*B 35: eval2 -> eval2 : B'=2*A, C'=A, D'=1+2*A, [ B>=2 && B>=1+2*A && A==1 ], cost: -6*A+3*B 36: eval2 -> eval2 : A'=1, C'=4, D'=8, [ B>=2 && B>=1+2*A && 2*A>=1 && B>=1+4*A && A>=2 ], cost: -4+4*A 37: eval2 -> eval2 : B'=4*A, C'=2*A, D'=4*A, [ B>=2 && B>=1+2*A && 2*A>=1 && B>=1+4*A && A==1 ], cost: -16*A+4*B Chained accelerated rules (with incoming rules): Start location: eval1 0: eval1 -> eval2 : A'=-1+A, [ A>=2 ], cost: 1 1: eval1 -> eval2 : B'=-1+B, [ 1>=A ], cost: 1 38: eval1 -> eval2 : A'=1, C'=2, D'=4, [ B>=2 && B>=-1+2*A && -1+A>=2 ], cost: -5+3*A 39: eval1 -> eval2 : A'=-1+A, B'=-2+2*A, C'=-1+A, D'=-2+2*A, [ B>=2 && B>=-1+2*A && -1+A==1 ], cost: 7-6*A+3*B 40: eval1 -> eval2 : B'=2*A, C'=A, D'=2*A, [ -1+B>=2 && -1+B>=1+2*A && A==1 ], cost: -2-6*A+3*B 41: eval1 -> eval2 : A'=-1+A, B'=-2+2*A, C'=-1+A, D'=-1+2*A, [ B>=2 && B>=-1+2*A && -1+A==1 ], cost: 7-6*A+3*B 42: eval1 -> eval2 : B'=2*A, C'=A, D'=1+2*A, [ -1+B>=2 && -1+B>=1+2*A && A==1 ], cost: -2-6*A+3*B 43: eval1 -> eval2 : A'=1, C'=4, D'=8, [ B>=2 && B>=-1+2*A && -2+2*A>=1 && B>=-3+4*A && -1+A>=2 ], cost: -7+4*A 44: eval1 -> eval2 : A'=-1+A, B'=-4+4*A, C'=-2+2*A, D'=-4+4*A, [ B>=2 && B>=-1+2*A && -2+2*A>=1 && B>=-3+4*A && -1+A==1 ], cost: 17-16*A+4*B 45: eval1 -> eval2 : B'=4*A, C'=2*A, D'=4*A, [ -1+B>=2 && -1+B>=1+2*A && 2*A>=1 && -1+B>=1+4*A && A==1 ], cost: -3-16*A+4*B Removed unreachable locations (and leaf rules with constant cost): Start location: eval1 38: eval1 -> eval2 : A'=1, C'=2, D'=4, [ B>=2 && B>=-1+2*A && -1+A>=2 ], cost: -5+3*A 39: eval1 -> eval2 : A'=-1+A, B'=-2+2*A, C'=-1+A, D'=-2+2*A, [ B>=2 && B>=-1+2*A && -1+A==1 ], cost: 7-6*A+3*B 40: eval1 -> eval2 : B'=2*A, C'=A, D'=2*A, [ -1+B>=2 && -1+B>=1+2*A && A==1 ], cost: -2-6*A+3*B 41: eval1 -> eval2 : A'=-1+A, B'=-2+2*A, C'=-1+A, D'=-1+2*A, [ B>=2 && B>=-1+2*A && -1+A==1 ], cost: 7-6*A+3*B 42: eval1 -> eval2 : B'=2*A, C'=A, D'=1+2*A, [ -1+B>=2 && -1+B>=1+2*A && A==1 ], cost: -2-6*A+3*B 43: eval1 -> eval2 : A'=1, C'=4, D'=8, [ B>=2 && B>=-1+2*A && -2+2*A>=1 && B>=-3+4*A && -1+A>=2 ], cost: -7+4*A 44: eval1 -> eval2 : A'=-1+A, B'=-4+4*A, C'=-2+2*A, D'=-4+4*A, [ B>=2 && B>=-1+2*A && -2+2*A>=1 && B>=-3+4*A && -1+A==1 ], cost: 17-16*A+4*B 45: eval1 -> eval2 : B'=4*A, C'=2*A, D'=4*A, [ -1+B>=2 && -1+B>=1+2*A && 2*A>=1 && -1+B>=1+4*A && A==1 ], cost: -3-16*A+4*B ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: eval1 38: eval1 -> eval2 : A'=1, C'=2, D'=4, [ B>=2 && B>=-1+2*A && -1+A>=2 ], cost: -5+3*A 41: eval1 -> eval2 : A'=-1+A, B'=-2+2*A, C'=-1+A, D'=-1+2*A, [ B>=2 && B>=-1+2*A && -1+A==1 ], cost: 7-6*A+3*B 42: eval1 -> eval2 : B'=2*A, C'=A, D'=1+2*A, [ -1+B>=2 && -1+B>=1+2*A && A==1 ], cost: -2-6*A+3*B 43: eval1 -> eval2 : A'=1, C'=4, D'=8, [ B>=2 && B>=-1+2*A && -2+2*A>=1 && B>=-3+4*A && -1+A>=2 ], cost: -7+4*A 44: eval1 -> eval2 : A'=-1+A, B'=-4+4*A, C'=-2+2*A, D'=-4+4*A, [ B>=2 && B>=-1+2*A && -2+2*A>=1 && B>=-3+4*A && -1+A==1 ], cost: 17-16*A+4*B 45: eval1 -> eval2 : B'=4*A, C'=2*A, D'=4*A, [ -1+B>=2 && -1+B>=1+2*A && 2*A>=1 && -1+B>=1+4*A && A==1 ], cost: -3-16*A+4*B Computing asymptotic complexity for rule 38 Simplified the guard: 38: eval1 -> eval2 : A'=1, C'=2, D'=4, [ B>=-1+2*A && -1+A>=2 ], cost: -5+3*A Solved the limit problem by the following transformations: Created initial limit problem: 2-2*A+B (+/+!), -2+A (+/+!), -5+3*A (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {A==n,B==2*n} resulting limit problem: [solved] Solution: A / n B / 2*n Resulting cost -5+3*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: -5+3*n Rule cost: -5+3*A Rule guard: [ B>=-1+2*A && -1+A>=2 ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (4) BOUNDS(n^1, INF)