/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: 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, 120 ms] (2) BOUNDS(1, n^1) (3) Loat Proof [FINISHED, 2001 ms] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: evalwcet1start(A, B, C, D) -> Com_1(evalwcet1entryin(A, B, C, D)) :|: TRUE evalwcet1entryin(A, B, C, D) -> Com_1(evalwcet1bbin(A, 0, A, D)) :|: A >= 1 evalwcet1entryin(A, B, C, D) -> Com_1(evalwcet1returnin(A, B, C, D)) :|: 0 >= A evalwcet1bbin(A, B, C, D) -> Com_1(evalwcet1bb1in(A, B, C, D)) :|: 0 >= E + 1 evalwcet1bbin(A, B, C, D) -> Com_1(evalwcet1bb1in(A, B, C, D)) :|: E >= 1 evalwcet1bbin(A, B, C, D) -> Com_1(evalwcet1bb4in(A, B, C, D)) :|: TRUE evalwcet1bb1in(A, B, C, D) -> Com_1(evalwcet1bb6in(A, B, C, 0)) :|: B + 1 >= A evalwcet1bb1in(A, B, C, D) -> Com_1(evalwcet1bb6in(A, B, C, B + 1)) :|: A >= B + 2 evalwcet1bb4in(A, B, C, D) -> Com_1(evalwcet1bb5in(A, B, C, D)) :|: 1 >= B evalwcet1bb4in(A, B, C, D) -> Com_1(evalwcet1bb6in(A, B, C, B - 1)) :|: B >= 2 evalwcet1bb5in(A, B, C, D) -> Com_1(evalwcet1bb6in(A, B, C, 0)) :|: TRUE evalwcet1bb6in(A, B, C, D) -> Com_1(evalwcet1bbin(A, D, C - 1, D)) :|: C >= 2 evalwcet1bb6in(A, B, C, D) -> Com_1(evalwcet1returnin(A, B, C, D)) :|: 1 >= C evalwcet1returnin(A, B, C, D) -> Com_1(evalwcet1stop(A, B, C, D)) :|: TRUE The start-symbols are:[evalwcet1start_4] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 11*ar_0 + 17) Initial complexity problem: 1: T: (Comp: ?, Cost: 1) evalwcet1start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1entryin(ar_0, ar_1, ar_2, ar_3)) (Comp: ?, Cost: 1) evalwcet1entryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bbin(ar_0, 0, ar_0, ar_3)) [ ar_0 >= 1 ] (Comp: ?, Cost: 1) evalwcet1entryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1returnin(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_0 ] (Comp: ?, Cost: 1) evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= e + 1 ] (Comp: ?, Cost: 1) evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3)) [ e >= 1 ] (Comp: ?, Cost: 1) evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3)) (Comp: ?, Cost: 1) evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, 0)) [ ar_1 + 1 >= ar_0 ] (Comp: ?, Cost: 1) evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, ar_1 + 1)) [ ar_0 >= ar_1 + 2 ] (Comp: ?, Cost: 1) evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3)) [ 1 >= ar_1 ] (Comp: ?, Cost: 1) evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, ar_1 - 1)) [ ar_1 >= 2 ] (Comp: ?, Cost: 1) evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, 0)) (Comp: ?, Cost: 1) evalwcet1bb6in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bbin(ar_0, ar_3, ar_2 - 1, ar_3)) [ ar_2 >= 2 ] (Comp: ?, Cost: 1) evalwcet1bb6in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1returnin(ar_0, ar_1, ar_2, ar_3)) [ 1 >= ar_2 ] (Comp: ?, Cost: 1) evalwcet1returnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1stop(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1start(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) evalwcet1start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1entryin(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 1) evalwcet1entryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bbin(ar_0, 0, ar_0, ar_3)) [ ar_0 >= 1 ] (Comp: 1, Cost: 1) evalwcet1entryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1returnin(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_0 ] (Comp: ?, Cost: 1) evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= e + 1 ] (Comp: ?, Cost: 1) evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3)) [ e >= 1 ] (Comp: ?, Cost: 1) evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3)) (Comp: ?, Cost: 1) evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, 0)) [ ar_1 + 1 >= ar_0 ] (Comp: ?, Cost: 1) evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, ar_1 + 1)) [ ar_0 >= ar_1 + 2 ] (Comp: ?, Cost: 1) evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3)) [ 1 >= ar_1 ] (Comp: ?, Cost: 1) evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, ar_1 - 1)) [ ar_1 >= 2 ] (Comp: ?, Cost: 1) evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, 0)) (Comp: ?, Cost: 1) evalwcet1bb6in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bbin(ar_0, ar_3, ar_2 - 1, ar_3)) [ ar_2 >= 2 ] (Comp: ?, Cost: 1) evalwcet1bb6in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1returnin(ar_0, ar_1, ar_2, ar_3)) [ 1 >= ar_2 ] (Comp: ?, Cost: 1) evalwcet1returnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1stop(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalwcet1start) = 2 Pol(evalwcet1entryin) = 2 Pol(evalwcet1bbin) = 2 Pol(evalwcet1returnin) = 1 Pol(evalwcet1bb1in) = 2 Pol(evalwcet1bb4in) = 2 Pol(evalwcet1bb6in) = 2 Pol(evalwcet1bb5in) = 2 Pol(evalwcet1stop) = 0 Pol(koat_start) = 2 orients all transitions weakly and the transitions evalwcet1returnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1stop(ar_0, ar_1, ar_2, ar_3)) evalwcet1bb6in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1returnin(ar_0, ar_1, ar_2, ar_3)) [ 1 >= ar_2 ] strictly and produces the following problem: 3: T: (Comp: 1, Cost: 1) evalwcet1start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1entryin(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 1) evalwcet1entryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bbin(ar_0, 0, ar_0, ar_3)) [ ar_0 >= 1 ] (Comp: 1, Cost: 1) evalwcet1entryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1returnin(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_0 ] (Comp: ?, Cost: 1) evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= e + 1 ] (Comp: ?, Cost: 1) evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3)) [ e >= 1 ] (Comp: ?, Cost: 1) evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3)) (Comp: ?, Cost: 1) evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, 0)) [ ar_1 + 1 >= ar_0 ] (Comp: ?, Cost: 1) evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, ar_1 + 1)) [ ar_0 >= ar_1 + 2 ] (Comp: ?, Cost: 1) evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3)) [ 1 >= ar_1 ] (Comp: ?, Cost: 1) evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, ar_1 - 1)) [ ar_1 >= 2 ] (Comp: ?, Cost: 1) evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, 0)) (Comp: ?, Cost: 1) evalwcet1bb6in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bbin(ar_0, ar_3, ar_2 - 1, ar_3)) [ ar_2 >= 2 ] (Comp: 2, Cost: 1) evalwcet1bb6in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1returnin(ar_0, ar_1, ar_2, ar_3)) [ 1 >= ar_2 ] (Comp: 2, Cost: 1) evalwcet1returnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1stop(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalwcet1bbin) = V_3 Pol(evalwcet1bb4in) = V_3 Pol(evalwcet1bb1in) = V_3 Pol(evalwcet1bb6in) = V_3 Pol(evalwcet1bb5in) = V_3 and size complexities S("koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1start(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(evalwcet1start(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(evalwcet1start(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(evalwcet1start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]", 0-3) = ar_3 S("evalwcet1returnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1stop(ar_0, ar_1, ar_2, ar_3))", 0-0) = ar_0 S("evalwcet1returnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1stop(ar_0, ar_1, ar_2, ar_3))", 0-1) = ? S("evalwcet1returnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1stop(ar_0, ar_1, ar_2, ar_3))", 0-2) = ar_0 + ar_2 S("evalwcet1returnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1stop(ar_0, ar_1, ar_2, ar_3))", 0-3) = ? S("evalwcet1bb6in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1returnin(ar_0, ar_1, ar_2, ar_3)) [ 1 >= ar_2 ]", 0-0) = ar_0 S("evalwcet1bb6in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1returnin(ar_0, ar_1, ar_2, ar_3)) [ 1 >= ar_2 ]", 0-1) = ? S("evalwcet1bb6in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1returnin(ar_0, ar_1, ar_2, ar_3)) [ 1 >= ar_2 ]", 0-2) = ar_0 S("evalwcet1bb6in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1returnin(ar_0, ar_1, ar_2, ar_3)) [ 1 >= ar_2 ]", 0-3) = ? S("evalwcet1bb6in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bbin(ar_0, ar_3, ar_2 - 1, ar_3)) [ ar_2 >= 2 ]", 0-0) = ar_0 S("evalwcet1bb6in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bbin(ar_0, ar_3, ar_2 - 1, ar_3)) [ ar_2 >= 2 ]", 0-1) = ? S("evalwcet1bb6in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bbin(ar_0, ar_3, ar_2 - 1, ar_3)) [ ar_2 >= 2 ]", 0-2) = ar_0 S("evalwcet1bb6in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bbin(ar_0, ar_3, ar_2 - 1, ar_3)) [ ar_2 >= 2 ]", 0-3) = ? S("evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, 0))", 0-0) = ar_0 S("evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, 0))", 0-1) = ? S("evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, 0))", 0-2) = ar_0 S("evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, 0))", 0-3) = 0 S("evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, ar_1 - 1)) [ ar_1 >= 2 ]", 0-0) = ar_0 S("evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, ar_1 - 1)) [ ar_1 >= 2 ]", 0-1) = ? S("evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, ar_1 - 1)) [ ar_1 >= 2 ]", 0-2) = ar_0 S("evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, ar_1 - 1)) [ ar_1 >= 2 ]", 0-3) = ? S("evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3)) [ 1 >= ar_1 ]", 0-0) = ar_0 S("evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3)) [ 1 >= ar_1 ]", 0-1) = ? S("evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3)) [ 1 >= ar_1 ]", 0-2) = ar_0 S("evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3)) [ 1 >= ar_1 ]", 0-3) = ? S("evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, ar_1 + 1)) [ ar_0 >= ar_1 + 2 ]", 0-0) = ar_0 S("evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, ar_1 + 1)) [ ar_0 >= ar_1 + 2 ]", 0-1) = ? S("evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, ar_1 + 1)) [ ar_0 >= ar_1 + 2 ]", 0-2) = ar_0 S("evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, ar_1 + 1)) [ ar_0 >= ar_1 + 2 ]", 0-3) = ? S("evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, 0)) [ ar_1 + 1 >= ar_0 ]", 0-0) = ar_0 S("evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, 0)) [ ar_1 + 1 >= ar_0 ]", 0-1) = ? S("evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, 0)) [ ar_1 + 1 >= ar_0 ]", 0-2) = ar_0 S("evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, 0)) [ ar_1 + 1 >= ar_0 ]", 0-3) = 0 S("evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3))", 0-0) = ar_0 S("evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3))", 0-1) = ? S("evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3))", 0-2) = ar_0 S("evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3))", 0-3) = ? S("evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3)) [ e >= 1 ]", 0-0) = ar_0 S("evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3)) [ e >= 1 ]", 0-1) = ? S("evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3)) [ e >= 1 ]", 0-2) = ar_0 S("evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3)) [ e >= 1 ]", 0-3) = ? S("evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= e + 1 ]", 0-0) = ar_0 S("evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= e + 1 ]", 0-1) = ? S("evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= e + 1 ]", 0-2) = ar_0 S("evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= e + 1 ]", 0-3) = ? S("evalwcet1entryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1returnin(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_0 ]", 0-0) = ar_0 S("evalwcet1entryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1returnin(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_0 ]", 0-1) = ar_1 S("evalwcet1entryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1returnin(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_0 ]", 0-2) = ar_2 S("evalwcet1entryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1returnin(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_0 ]", 0-3) = ar_3 S("evalwcet1entryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bbin(ar_0, 0, ar_0, ar_3)) [ ar_0 >= 1 ]", 0-0) = ar_0 S("evalwcet1entryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bbin(ar_0, 0, ar_0, ar_3)) [ ar_0 >= 1 ]", 0-1) = 0 S("evalwcet1entryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bbin(ar_0, 0, ar_0, ar_3)) [ ar_0 >= 1 ]", 0-2) = ar_0 S("evalwcet1entryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bbin(ar_0, 0, ar_0, ar_3)) [ ar_0 >= 1 ]", 0-3) = ar_3 S("evalwcet1start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1entryin(ar_0, ar_1, ar_2, ar_3))", 0-0) = ar_0 S("evalwcet1start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1entryin(ar_0, ar_1, ar_2, ar_3))", 0-1) = ar_1 S("evalwcet1start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1entryin(ar_0, ar_1, ar_2, ar_3))", 0-2) = ar_2 S("evalwcet1start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1entryin(ar_0, ar_1, ar_2, ar_3))", 0-3) = ar_3 orients the transitions evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3)) evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3)) [ e >= 1 ] evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= e + 1 ] evalwcet1bb6in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bbin(ar_0, ar_3, ar_2 - 1, ar_3)) [ ar_2 >= 2 ] evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, 0)) evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, ar_1 - 1)) [ ar_1 >= 2 ] evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3)) [ 1 >= ar_1 ] evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, ar_1 + 1)) [ ar_0 >= ar_1 + 2 ] evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, 0)) [ ar_1 + 1 >= ar_0 ] weakly and the transition evalwcet1bb6in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bbin(ar_0, ar_3, ar_2 - 1, ar_3)) [ ar_2 >= 2 ] strictly and produces the following problem: 4: T: (Comp: 1, Cost: 1) evalwcet1start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1entryin(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 1) evalwcet1entryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bbin(ar_0, 0, ar_0, ar_3)) [ ar_0 >= 1 ] (Comp: 1, Cost: 1) evalwcet1entryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1returnin(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_0 ] (Comp: ?, Cost: 1) evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= e + 1 ] (Comp: ?, Cost: 1) evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3)) [ e >= 1 ] (Comp: ?, Cost: 1) evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3)) (Comp: ?, Cost: 1) evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, 0)) [ ar_1 + 1 >= ar_0 ] (Comp: ?, Cost: 1) evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, ar_1 + 1)) [ ar_0 >= ar_1 + 2 ] (Comp: ?, Cost: 1) evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3)) [ 1 >= ar_1 ] (Comp: ?, Cost: 1) evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, ar_1 - 1)) [ ar_1 >= 2 ] (Comp: ?, Cost: 1) evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, 0)) (Comp: ar_0, Cost: 1) evalwcet1bb6in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bbin(ar_0, ar_3, ar_2 - 1, ar_3)) [ ar_2 >= 2 ] (Comp: 2, Cost: 1) evalwcet1bb6in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1returnin(ar_0, ar_1, ar_2, ar_3)) [ 1 >= ar_2 ] (Comp: 2, Cost: 1) evalwcet1returnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1stop(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Repeatedly propagating knowledge in problem 4 produces the following problem: 5: T: (Comp: 1, Cost: 1) evalwcet1start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1entryin(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 1) evalwcet1entryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bbin(ar_0, 0, ar_0, ar_3)) [ ar_0 >= 1 ] (Comp: 1, Cost: 1) evalwcet1entryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1returnin(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_0 ] (Comp: ar_0 + 1, Cost: 1) evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= e + 1 ] (Comp: ar_0 + 1, Cost: 1) evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3)) [ e >= 1 ] (Comp: ar_0 + 1, Cost: 1) evalwcet1bbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3)) (Comp: 2*ar_0 + 2, Cost: 1) evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, 0)) [ ar_1 + 1 >= ar_0 ] (Comp: 2*ar_0 + 2, Cost: 1) evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, ar_1 + 1)) [ ar_0 >= ar_1 + 2 ] (Comp: ar_0 + 1, Cost: 1) evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3)) [ 1 >= ar_1 ] (Comp: ar_0 + 1, Cost: 1) evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, ar_1 - 1)) [ ar_1 >= 2 ] (Comp: ar_0 + 1, Cost: 1) evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bb6in(ar_0, ar_1, ar_2, 0)) (Comp: ar_0, Cost: 1) evalwcet1bb6in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1bbin(ar_0, ar_3, ar_2 - 1, ar_3)) [ ar_2 >= 2 ] (Comp: 2, Cost: 1) evalwcet1bb6in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1returnin(ar_0, ar_1, ar_2, ar_3)) [ 1 >= ar_2 ] (Comp: 2, Cost: 1) evalwcet1returnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1stop(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalwcet1start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Complexity upper bound 11*ar_0 + 17 Time: 0.171 sec (SMT: 0.148 sec) ---------------------------------------- (2) BOUNDS(1, n^1) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalwcet1start 0: evalwcet1start -> evalwcet1entryin : [], cost: 1 1: evalwcet1entryin -> evalwcet1bbin : B'=0, C'=A, [ A>=1 ], cost: 1 2: evalwcet1entryin -> evalwcet1returnin : [ 0>=A ], cost: 1 3: evalwcet1bbin -> evalwcet1bb1in : [ 0>=1+free ], cost: 1 4: evalwcet1bbin -> evalwcet1bb1in : [ free_1>=1 ], cost: 1 5: evalwcet1bbin -> evalwcet1bb4in : [], cost: 1 6: evalwcet1bb1in -> evalwcet1bb6in : D'=0, [ 1+B>=A ], cost: 1 7: evalwcet1bb1in -> evalwcet1bb6in : D'=1+B, [ A>=2+B ], cost: 1 8: evalwcet1bb4in -> evalwcet1bb5in : [ 1>=B ], cost: 1 9: evalwcet1bb4in -> evalwcet1bb6in : D'=-1+B, [ B>=2 ], cost: 1 10: evalwcet1bb5in -> evalwcet1bb6in : D'=0, [], cost: 1 11: evalwcet1bb6in -> evalwcet1bbin : B'=D, C'=-1+C, [ C>=2 ], cost: 1 12: evalwcet1bb6in -> evalwcet1returnin : [ 1>=C ], cost: 1 13: evalwcet1returnin -> evalwcet1stop : [], cost: 1 Removed unreachable and leaf rules: Start location: evalwcet1start 0: evalwcet1start -> evalwcet1entryin : [], cost: 1 1: evalwcet1entryin -> evalwcet1bbin : B'=0, C'=A, [ A>=1 ], cost: 1 3: evalwcet1bbin -> evalwcet1bb1in : [ 0>=1+free ], cost: 1 4: evalwcet1bbin -> evalwcet1bb1in : [ free_1>=1 ], cost: 1 5: evalwcet1bbin -> evalwcet1bb4in : [], cost: 1 6: evalwcet1bb1in -> evalwcet1bb6in : D'=0, [ 1+B>=A ], cost: 1 7: evalwcet1bb1in -> evalwcet1bb6in : D'=1+B, [ A>=2+B ], cost: 1 8: evalwcet1bb4in -> evalwcet1bb5in : [ 1>=B ], cost: 1 9: evalwcet1bb4in -> evalwcet1bb6in : D'=-1+B, [ B>=2 ], cost: 1 10: evalwcet1bb5in -> evalwcet1bb6in : D'=0, [], cost: 1 11: evalwcet1bb6in -> evalwcet1bbin : B'=D, C'=-1+C, [ C>=2 ], cost: 1 Simplified all rules, resulting in: Start location: evalwcet1start 0: evalwcet1start -> evalwcet1entryin : [], cost: 1 1: evalwcet1entryin -> evalwcet1bbin : B'=0, C'=A, [ A>=1 ], cost: 1 4: evalwcet1bbin -> evalwcet1bb1in : [], cost: 1 5: evalwcet1bbin -> evalwcet1bb4in : [], cost: 1 6: evalwcet1bb1in -> evalwcet1bb6in : D'=0, [ 1+B>=A ], cost: 1 7: evalwcet1bb1in -> evalwcet1bb6in : D'=1+B, [ A>=2+B ], cost: 1 8: evalwcet1bb4in -> evalwcet1bb5in : [ 1>=B ], cost: 1 9: evalwcet1bb4in -> evalwcet1bb6in : D'=-1+B, [ B>=2 ], cost: 1 10: evalwcet1bb5in -> evalwcet1bb6in : D'=0, [], cost: 1 11: evalwcet1bb6in -> evalwcet1bbin : B'=D, C'=-1+C, [ C>=2 ], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalwcet1start 14: evalwcet1start -> evalwcet1bbin : B'=0, C'=A, [ A>=1 ], cost: 2 4: evalwcet1bbin -> evalwcet1bb1in : [], cost: 1 5: evalwcet1bbin -> evalwcet1bb4in : [], cost: 1 6: evalwcet1bb1in -> evalwcet1bb6in : D'=0, [ 1+B>=A ], cost: 1 7: evalwcet1bb1in -> evalwcet1bb6in : D'=1+B, [ A>=2+B ], cost: 1 9: evalwcet1bb4in -> evalwcet1bb6in : D'=-1+B, [ B>=2 ], cost: 1 15: evalwcet1bb4in -> evalwcet1bb6in : D'=0, [ 1>=B ], cost: 2 11: evalwcet1bb6in -> evalwcet1bbin : B'=D, C'=-1+C, [ C>=2 ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: evalwcet1start 14: evalwcet1start -> evalwcet1bbin : B'=0, C'=A, [ A>=1 ], cost: 2 16: evalwcet1bbin -> evalwcet1bb6in : D'=0, [ 1+B>=A ], cost: 2 17: evalwcet1bbin -> evalwcet1bb6in : D'=1+B, [ A>=2+B ], cost: 2 18: evalwcet1bbin -> evalwcet1bb6in : D'=-1+B, [ B>=2 ], cost: 2 19: evalwcet1bbin -> evalwcet1bb6in : D'=0, [ 1>=B ], cost: 3 11: evalwcet1bb6in -> evalwcet1bbin : B'=D, C'=-1+C, [ C>=2 ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: evalwcet1start 14: evalwcet1start -> evalwcet1bbin : B'=0, C'=A, [ A>=1 ], cost: 2 20: evalwcet1bbin -> evalwcet1bbin : B'=0, C'=-1+C, D'=0, [ 1+B>=A && C>=2 ], cost: 3 21: evalwcet1bbin -> evalwcet1bbin : B'=1+B, C'=-1+C, D'=1+B, [ A>=2+B && C>=2 ], cost: 3 22: evalwcet1bbin -> evalwcet1bbin : B'=-1+B, C'=-1+C, D'=-1+B, [ B>=2 && C>=2 ], cost: 3 23: evalwcet1bbin -> evalwcet1bbin : B'=0, C'=-1+C, D'=0, [ 1>=B && C>=2 ], cost: 4 Accelerating simple loops of location 2. Accelerating the following rules: 20: evalwcet1bbin -> evalwcet1bbin : B'=0, C'=-1+C, D'=0, [ 1+B>=A && C>=2 ], cost: 3 21: evalwcet1bbin -> evalwcet1bbin : B'=1+B, C'=-1+C, D'=1+B, [ A>=2+B && C>=2 ], cost: 3 22: evalwcet1bbin -> evalwcet1bbin : B'=-1+B, C'=-1+C, D'=-1+B, [ B>=2 && C>=2 ], cost: 3 23: evalwcet1bbin -> evalwcet1bbin : B'=0, C'=-1+C, D'=0, [ 1>=B && C>=2 ], cost: 4 Accelerated rule 20 with metering function -1+C (after strengthening guard), yielding the new rule 24. Accelerated rule 21 with backward acceleration, yielding the new rule 25. Accelerated rule 21 with backward acceleration, yielding the new rule 26. Accelerated rule 22 with metering function -1+C (after adding B>=C), yielding the new rule 27. Accelerated rule 22 with metering function -1+B (after adding B<=C), yielding the new rule 28. Accelerated rule 23 with metering function -1+C, yielding the new rule 29. Removing the simple loops: 21 22 23. Accelerated all simple loops using metering functions (where possible): Start location: evalwcet1start 14: evalwcet1start -> evalwcet1bbin : B'=0, C'=A, [ A>=1 ], cost: 2 20: evalwcet1bbin -> evalwcet1bbin : B'=0, C'=-1+C, D'=0, [ 1+B>=A && C>=2 ], cost: 3 24: evalwcet1bbin -> evalwcet1bbin : B'=0, C'=1, D'=0, [ 1+B>=A && C>=2 && 1>=A ], cost: -3+3*C 25: evalwcet1bbin -> evalwcet1bbin : B'=-1+A, C'=1+C-A+B, D'=-1+A, [ A>=2+B && C>=2 && 2+C-A+B>=2 ], cost: -3+3*A-3*B 26: evalwcet1bbin -> evalwcet1bbin : B'=-1+C+B, C'=1, D'=-1+C+B, [ A>=2+B && C>=2 && A>=C+B ], cost: -3+3*C 27: evalwcet1bbin -> evalwcet1bbin : B'=1-C+B, C'=1, D'=1-C+B, [ B>=2 && C>=2 && B>=C ], cost: -3+3*C 28: evalwcet1bbin -> evalwcet1bbin : B'=1, C'=1+C-B, D'=1, [ B>=2 && C>=2 && B<=C ], cost: -3+3*B 29: evalwcet1bbin -> evalwcet1bbin : B'=0, C'=1, D'=0, [ 1>=B && C>=2 ], cost: -4+4*C Chained accelerated rules (with incoming rules): Start location: evalwcet1start 14: evalwcet1start -> evalwcet1bbin : B'=0, C'=A, [ A>=1 ], cost: 2 30: evalwcet1start -> evalwcet1bbin : B'=-1+A, C'=1, D'=-1+A, [ A>=2 ], cost: -1+3*A 31: evalwcet1start -> evalwcet1bbin : B'=-1+A, C'=1, D'=-1+A, [ A>=2 ], cost: -1+3*A 32: evalwcet1start -> evalwcet1bbin : B'=0, C'=1, D'=0, [ A>=2 ], cost: -2+4*A Removed unreachable locations (and leaf rules with constant cost): Start location: evalwcet1start 30: evalwcet1start -> evalwcet1bbin : B'=-1+A, C'=1, D'=-1+A, [ A>=2 ], cost: -1+3*A 31: evalwcet1start -> evalwcet1bbin : B'=-1+A, C'=1, D'=-1+A, [ A>=2 ], cost: -1+3*A 32: evalwcet1start -> evalwcet1bbin : B'=0, C'=1, D'=0, [ A>=2 ], cost: -2+4*A ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalwcet1start 31: evalwcet1start -> evalwcet1bbin : B'=-1+A, C'=1, D'=-1+A, [ A>=2 ], cost: -1+3*A 32: evalwcet1start -> evalwcet1bbin : B'=0, C'=1, D'=0, [ A>=2 ], cost: -2+4*A Computing asymptotic complexity for rule 31 Solved the limit problem by the following transformations: Created initial limit problem: -1+A (+/+!), -1+3*A (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {A==n} resulting limit problem: [solved] Solution: A / n Resulting cost -1+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: -1+3*n Rule cost: -1+3*A Rule guard: [ A>=2 ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (4) BOUNDS(n^1, INF)