/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.koat /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^2), O(n^2)) 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^2, n^2). (0) CpxIntTrs (1) Koat Proof [FINISHED, 288 ms] (2) BOUNDS(1, n^2) (3) Loat Proof [FINISHED, 723 ms] (4) BOUNDS(n^2, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: evalSimpleMultipleDepstart(A, B, C, D) -> Com_1(evalSimpleMultipleDepentryin(A, B, C, D)) :|: TRUE evalSimpleMultipleDepentryin(A, B, C, D) -> Com_1(evalSimpleMultipleDepbb3in(0, 0, C, D)) :|: TRUE evalSimpleMultipleDepbb3in(A, B, C, D) -> Com_1(evalSimpleMultipleDepbbin(A, B, C, D)) :|: C >= B + 1 evalSimpleMultipleDepbb3in(A, B, C, D) -> Com_1(evalSimpleMultipleDepreturnin(A, B, C, D)) :|: B >= C evalSimpleMultipleDepbbin(A, B, C, D) -> Com_1(evalSimpleMultipleDepbb1in(A, B, C, D)) :|: D >= A + 1 evalSimpleMultipleDepbbin(A, B, C, D) -> Com_1(evalSimpleMultipleDepbb2in(A, B, C, D)) :|: A >= D evalSimpleMultipleDepbb1in(A, B, C, D) -> Com_1(evalSimpleMultipleDepbb3in(A + 1, B, C, D)) :|: TRUE evalSimpleMultipleDepbb2in(A, B, C, D) -> Com_1(evalSimpleMultipleDepbb3in(0, B + 1, C, D)) :|: TRUE evalSimpleMultipleDepreturnin(A, B, C, D) -> Com_1(evalSimpleMultipleDepstop(A, B, C, D)) :|: TRUE The start-symbols are:[evalSimpleMultipleDepstart_4] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 6*ar_2 + 6*ar_3 + 12*ar_2*ar_3 + 7) Initial complexity problem: 1: T: (Comp: ?, Cost: 1) evalSimpleMultipleDepstart(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepentryin(ar_0, ar_1, ar_2, ar_3)) (Comp: ?, Cost: 1) evalSimpleMultipleDepentryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(0, 0, ar_2, ar_3)) (Comp: ?, Cost: 1) evalSimpleMultipleDepbb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= ar_1 + 1 ] (Comp: ?, Cost: 1) evalSimpleMultipleDepbb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepreturnin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= ar_2 ] (Comp: ?, Cost: 1) evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb1in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= ar_0 + 1 ] (Comp: ?, Cost: 1) evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_3 ] (Comp: ?, Cost: 1) evalSimpleMultipleDepbb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(ar_0 + 1, ar_1, ar_2, ar_3)) (Comp: ?, Cost: 1) evalSimpleMultipleDepbb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(0, ar_1 + 1, ar_2, ar_3)) (Comp: ?, Cost: 1) evalSimpleMultipleDepreturnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepstop(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepstart(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) evalSimpleMultipleDepstart(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepentryin(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 1) evalSimpleMultipleDepentryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(0, 0, ar_2, ar_3)) (Comp: ?, Cost: 1) evalSimpleMultipleDepbb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= ar_1 + 1 ] (Comp: ?, Cost: 1) evalSimpleMultipleDepbb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepreturnin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= ar_2 ] (Comp: ?, Cost: 1) evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb1in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= ar_0 + 1 ] (Comp: ?, Cost: 1) evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_3 ] (Comp: ?, Cost: 1) evalSimpleMultipleDepbb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(ar_0 + 1, ar_1, ar_2, ar_3)) (Comp: ?, Cost: 1) evalSimpleMultipleDepbb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(0, ar_1 + 1, ar_2, ar_3)) (Comp: ?, Cost: 1) evalSimpleMultipleDepreturnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepstop(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepstart(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalSimpleMultipleDepstart) = 2 Pol(evalSimpleMultipleDepentryin) = 2 Pol(evalSimpleMultipleDepbb3in) = 2 Pol(evalSimpleMultipleDepbbin) = 2 Pol(evalSimpleMultipleDepreturnin) = 1 Pol(evalSimpleMultipleDepbb1in) = 2 Pol(evalSimpleMultipleDepbb2in) = 2 Pol(evalSimpleMultipleDepstop) = 0 Pol(koat_start) = 2 orients all transitions weakly and the transitions evalSimpleMultipleDepreturnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepstop(ar_0, ar_1, ar_2, ar_3)) evalSimpleMultipleDepbb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepreturnin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= ar_2 ] strictly and produces the following problem: 3: T: (Comp: 1, Cost: 1) evalSimpleMultipleDepstart(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepentryin(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 1) evalSimpleMultipleDepentryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(0, 0, ar_2, ar_3)) (Comp: ?, Cost: 1) evalSimpleMultipleDepbb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= ar_1 + 1 ] (Comp: 2, Cost: 1) evalSimpleMultipleDepbb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepreturnin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= ar_2 ] (Comp: ?, Cost: 1) evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb1in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= ar_0 + 1 ] (Comp: ?, Cost: 1) evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_3 ] (Comp: ?, Cost: 1) evalSimpleMultipleDepbb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(ar_0 + 1, ar_1, ar_2, ar_3)) (Comp: ?, Cost: 1) evalSimpleMultipleDepbb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(0, ar_1 + 1, ar_2, ar_3)) (Comp: 2, Cost: 1) evalSimpleMultipleDepreturnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepstop(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepstart(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Applied AI with 'oct' on problem 3 to obtain the following invariants: For symbol evalSimpleMultipleDepbb1in: X_4 - 1 >= 0 /\ X_3 + X_4 - 2 >= 0 /\ X_2 + X_4 - 1 >= 0 /\ X_1 + X_4 - 1 >= 0 /\ -X_1 + X_4 - 1 >= 0 /\ X_3 - 1 >= 0 /\ X_2 + X_3 - 1 >= 0 /\ -X_2 + X_3 - 1 >= 0 /\ X_1 + X_3 - 1 >= 0 /\ X_2 >= 0 /\ X_1 + X_2 >= 0 /\ X_1 >= 0 For symbol evalSimpleMultipleDepbb2in: X_1 - X_4 >= 0 /\ X_3 - 1 >= 0 /\ X_2 + X_3 - 1 >= 0 /\ -X_2 + X_3 - 1 >= 0 /\ X_1 + X_3 - 1 >= 0 /\ X_2 >= 0 /\ X_1 + X_2 >= 0 /\ X_1 >= 0 For symbol evalSimpleMultipleDepbb3in: X_2 >= 0 /\ X_1 + X_2 >= 0 /\ X_1 >= 0 For symbol evalSimpleMultipleDepbbin: X_3 - 1 >= 0 /\ X_2 + X_3 - 1 >= 0 /\ -X_2 + X_3 - 1 >= 0 /\ X_1 + X_3 - 1 >= 0 /\ X_2 >= 0 /\ X_1 + X_2 >= 0 /\ X_1 >= 0 For symbol evalSimpleMultipleDepreturnin: X_2 - X_3 >= 0 /\ X_2 >= 0 /\ X_1 + X_2 >= 0 /\ X_1 >= 0 This yielded the following problem: 4: T: (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepstart(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] (Comp: 2, Cost: 1) evalSimpleMultipleDepreturnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepstop(ar_0, ar_1, ar_2, ar_3)) [ ar_1 - ar_2 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 ] (Comp: ?, Cost: 1) evalSimpleMultipleDepbb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(0, ar_1 + 1, ar_2, ar_3)) [ ar_0 - ar_3 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ -ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 ] (Comp: ?, Cost: 1) evalSimpleMultipleDepbb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_3 - 1 >= 0 /\ ar_2 + ar_3 - 2 >= 0 /\ ar_1 + ar_3 - 1 >= 0 /\ ar_0 + ar_3 - 1 >= 0 /\ -ar_0 + ar_3 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ -ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 ] (Comp: ?, Cost: 1) evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ -ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_0 >= ar_3 ] (Comp: ?, Cost: 1) evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb1in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ -ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_3 >= ar_0 + 1 ] (Comp: 2, Cost: 1) evalSimpleMultipleDepbb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepreturnin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_1 >= ar_2 ] (Comp: ?, Cost: 1) evalSimpleMultipleDepbb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_2 >= ar_1 + 1 ] (Comp: 1, Cost: 1) evalSimpleMultipleDepentryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(0, 0, ar_2, ar_3)) (Comp: 1, Cost: 1) evalSimpleMultipleDepstart(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepentryin(ar_0, ar_1, ar_2, ar_3)) start location: koat_start leaf cost: 0 A polynomial rank function with Pol(koat_start) = 2*V_3 Pol(evalSimpleMultipleDepstart) = 2*V_3 Pol(evalSimpleMultipleDepreturnin) = -2*V_2 + 2*V_3 Pol(evalSimpleMultipleDepstop) = -2*V_2 + 2*V_3 Pol(evalSimpleMultipleDepbb2in) = -2*V_2 + 2*V_3 - 1 Pol(evalSimpleMultipleDepbb3in) = -2*V_2 + 2*V_3 Pol(evalSimpleMultipleDepbb1in) = -2*V_2 + 2*V_3 Pol(evalSimpleMultipleDepbbin) = -2*V_2 + 2*V_3 Pol(evalSimpleMultipleDepentryin) = 2*V_3 orients all transitions weakly and the transitions evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ -ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_0 >= ar_3 ] evalSimpleMultipleDepbb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(0, ar_1 + 1, ar_2, ar_3)) [ ar_0 - ar_3 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ -ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 ] strictly and produces the following problem: 5: T: (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepstart(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] (Comp: 2, Cost: 1) evalSimpleMultipleDepreturnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepstop(ar_0, ar_1, ar_2, ar_3)) [ ar_1 - ar_2 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 ] (Comp: 2*ar_2, Cost: 1) evalSimpleMultipleDepbb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(0, ar_1 + 1, ar_2, ar_3)) [ ar_0 - ar_3 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ -ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 ] (Comp: ?, Cost: 1) evalSimpleMultipleDepbb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_3 - 1 >= 0 /\ ar_2 + ar_3 - 2 >= 0 /\ ar_1 + ar_3 - 1 >= 0 /\ ar_0 + ar_3 - 1 >= 0 /\ -ar_0 + ar_3 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ -ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 ] (Comp: 2*ar_2, Cost: 1) evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ -ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_0 >= ar_3 ] (Comp: ?, Cost: 1) evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb1in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ -ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_3 >= ar_0 + 1 ] (Comp: 2, Cost: 1) evalSimpleMultipleDepbb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepreturnin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_1 >= ar_2 ] (Comp: ?, Cost: 1) evalSimpleMultipleDepbb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_2 >= ar_1 + 1 ] (Comp: 1, Cost: 1) evalSimpleMultipleDepentryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(0, 0, ar_2, ar_3)) (Comp: 1, Cost: 1) evalSimpleMultipleDepstart(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepentryin(ar_0, ar_1, ar_2, ar_3)) start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalSimpleMultipleDepbbin) = -2*V_1 + 2*V_4 Pol(evalSimpleMultipleDepbb1in) = -2*V_1 + 2*V_4 - 1 Pol(evalSimpleMultipleDepbb3in) = -2*V_1 + 2*V_4 and size complexities S("evalSimpleMultipleDepstart(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepentryin(ar_0, ar_1, ar_2, ar_3))", 0-0) = ar_0 S("evalSimpleMultipleDepstart(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepentryin(ar_0, ar_1, ar_2, ar_3))", 0-1) = ar_1 S("evalSimpleMultipleDepstart(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepentryin(ar_0, ar_1, ar_2, ar_3))", 0-2) = ar_2 S("evalSimpleMultipleDepstart(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepentryin(ar_0, ar_1, ar_2, ar_3))", 0-3) = ar_3 S("evalSimpleMultipleDepentryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(0, 0, ar_2, ar_3))", 0-0) = 0 S("evalSimpleMultipleDepentryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(0, 0, ar_2, ar_3))", 0-1) = 0 S("evalSimpleMultipleDepentryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(0, 0, ar_2, ar_3))", 0-2) = ar_2 S("evalSimpleMultipleDepentryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(0, 0, ar_2, ar_3))", 0-3) = ar_3 S("evalSimpleMultipleDepbb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 /\\ ar_2 >= ar_1 + 1 ]", 0-0) = ar_3 S("evalSimpleMultipleDepbb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 /\\ ar_2 >= ar_1 + 1 ]", 0-1) = ar_2 S("evalSimpleMultipleDepbb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 /\\ ar_2 >= ar_1 + 1 ]", 0-2) = ar_2 S("evalSimpleMultipleDepbb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 /\\ ar_2 >= ar_1 + 1 ]", 0-3) = ar_3 S("evalSimpleMultipleDepbb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepreturnin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 /\\ ar_1 >= ar_2 ]", 0-0) = 0 S("evalSimpleMultipleDepbb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepreturnin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 /\\ ar_1 >= ar_2 ]", 0-1) = ar_2 S("evalSimpleMultipleDepbb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepreturnin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 /\\ ar_1 >= ar_2 ]", 0-2) = ar_2 S("evalSimpleMultipleDepbb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepreturnin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 /\\ ar_1 >= ar_2 ]", 0-3) = ar_3 S("evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb1in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 1 >= 0 /\\ -ar_1 + ar_2 - 1 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 /\\ ar_3 >= ar_0 + 1 ]", 0-0) = ar_3 S("evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb1in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 1 >= 0 /\\ -ar_1 + ar_2 - 1 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 /\\ ar_3 >= ar_0 + 1 ]", 0-1) = ar_2 S("evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb1in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 1 >= 0 /\\ -ar_1 + ar_2 - 1 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 /\\ ar_3 >= ar_0 + 1 ]", 0-2) = ar_2 S("evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb1in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 1 >= 0 /\\ -ar_1 + ar_2 - 1 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 /\\ ar_3 >= ar_0 + 1 ]", 0-3) = ar_3 S("evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 1 >= 0 /\\ -ar_1 + ar_2 - 1 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 /\\ ar_0 >= ar_3 ]", 0-0) = ar_3 S("evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 1 >= 0 /\\ -ar_1 + ar_2 - 1 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 /\\ ar_0 >= ar_3 ]", 0-1) = ar_2 S("evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 1 >= 0 /\\ -ar_1 + ar_2 - 1 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 /\\ ar_0 >= ar_3 ]", 0-2) = ar_2 S("evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 1 >= 0 /\\ -ar_1 + ar_2 - 1 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 /\\ ar_0 >= ar_3 ]", 0-3) = ar_3 S("evalSimpleMultipleDepbb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_3 - 1 >= 0 /\\ ar_2 + ar_3 - 2 >= 0 /\\ ar_1 + ar_3 - 1 >= 0 /\\ ar_0 + ar_3 - 1 >= 0 /\\ -ar_0 + ar_3 - 1 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 1 >= 0 /\\ -ar_1 + ar_2 - 1 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 ]", 0-0) = ar_3 S("evalSimpleMultipleDepbb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_3 - 1 >= 0 /\\ ar_2 + ar_3 - 2 >= 0 /\\ ar_1 + ar_3 - 1 >= 0 /\\ ar_0 + ar_3 - 1 >= 0 /\\ -ar_0 + ar_3 - 1 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 1 >= 0 /\\ -ar_1 + ar_2 - 1 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 ]", 0-1) = ar_2 S("evalSimpleMultipleDepbb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_3 - 1 >= 0 /\\ ar_2 + ar_3 - 2 >= 0 /\\ ar_1 + ar_3 - 1 >= 0 /\\ ar_0 + ar_3 - 1 >= 0 /\\ -ar_0 + ar_3 - 1 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 1 >= 0 /\\ -ar_1 + ar_2 - 1 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 ]", 0-2) = ar_2 S("evalSimpleMultipleDepbb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_3 - 1 >= 0 /\\ ar_2 + ar_3 - 2 >= 0 /\\ ar_1 + ar_3 - 1 >= 0 /\\ ar_0 + ar_3 - 1 >= 0 /\\ -ar_0 + ar_3 - 1 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 1 >= 0 /\\ -ar_1 + ar_2 - 1 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 ]", 0-3) = ar_3 S("evalSimpleMultipleDepbb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(0, ar_1 + 1, ar_2, ar_3)) [ ar_0 - ar_3 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 1 >= 0 /\\ -ar_1 + ar_2 - 1 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 ]", 0-0) = 0 S("evalSimpleMultipleDepbb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(0, ar_1 + 1, ar_2, ar_3)) [ ar_0 - ar_3 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 1 >= 0 /\\ -ar_1 + ar_2 - 1 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 ]", 0-1) = ar_2 S("evalSimpleMultipleDepbb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(0, ar_1 + 1, ar_2, ar_3)) [ ar_0 - ar_3 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 1 >= 0 /\\ -ar_1 + ar_2 - 1 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 ]", 0-2) = ar_2 S("evalSimpleMultipleDepbb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(0, ar_1 + 1, ar_2, ar_3)) [ ar_0 - ar_3 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 1 >= 0 /\\ -ar_1 + ar_2 - 1 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 ]", 0-3) = ar_3 S("evalSimpleMultipleDepreturnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepstop(ar_0, ar_1, ar_2, ar_3)) [ ar_1 - ar_2 >= 0 /\\ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 ]", 0-0) = 0 S("evalSimpleMultipleDepreturnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepstop(ar_0, ar_1, ar_2, ar_3)) [ ar_1 - ar_2 >= 0 /\\ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 ]", 0-1) = ar_2 S("evalSimpleMultipleDepreturnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepstop(ar_0, ar_1, ar_2, ar_3)) [ ar_1 - ar_2 >= 0 /\\ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 ]", 0-2) = ar_2 S("evalSimpleMultipleDepreturnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepstop(ar_0, ar_1, ar_2, ar_3)) [ ar_1 - ar_2 >= 0 /\\ ar_1 >= 0 /\\ ar_0 + ar_1 >= 0 /\\ ar_0 >= 0 ]", 0-3) = ar_3 S("koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepstart(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(evalSimpleMultipleDepstart(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(evalSimpleMultipleDepstart(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(evalSimpleMultipleDepstart(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]", 0-3) = ar_3 orients the transitions evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb1in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ -ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_3 >= ar_0 + 1 ] evalSimpleMultipleDepbb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_2 >= ar_1 + 1 ] evalSimpleMultipleDepbb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_3 - 1 >= 0 /\ ar_2 + ar_3 - 2 >= 0 /\ ar_1 + ar_3 - 1 >= 0 /\ ar_0 + ar_3 - 1 >= 0 /\ -ar_0 + ar_3 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ -ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 ] weakly and the transitions evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb1in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ -ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_3 >= ar_0 + 1 ] evalSimpleMultipleDepbb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_3 - 1 >= 0 /\ ar_2 + ar_3 - 2 >= 0 /\ ar_1 + ar_3 - 1 >= 0 /\ ar_0 + ar_3 - 1 >= 0 /\ -ar_0 + ar_3 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ -ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 ] strictly and produces the following problem: 6: T: (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepstart(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] (Comp: 2, Cost: 1) evalSimpleMultipleDepreturnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepstop(ar_0, ar_1, ar_2, ar_3)) [ ar_1 - ar_2 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 ] (Comp: 2*ar_2, Cost: 1) evalSimpleMultipleDepbb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(0, ar_1 + 1, ar_2, ar_3)) [ ar_0 - ar_3 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ -ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 ] (Comp: 2*ar_3 + 4*ar_2*ar_3, Cost: 1) evalSimpleMultipleDepbb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_3 - 1 >= 0 /\ ar_2 + ar_3 - 2 >= 0 /\ ar_1 + ar_3 - 1 >= 0 /\ ar_0 + ar_3 - 1 >= 0 /\ -ar_0 + ar_3 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ -ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 ] (Comp: 2*ar_2, Cost: 1) evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ -ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_0 >= ar_3 ] (Comp: 2*ar_3 + 4*ar_2*ar_3, Cost: 1) evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb1in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ -ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_3 >= ar_0 + 1 ] (Comp: 2, Cost: 1) evalSimpleMultipleDepbb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepreturnin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_1 >= ar_2 ] (Comp: ?, Cost: 1) evalSimpleMultipleDepbb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_2 >= ar_1 + 1 ] (Comp: 1, Cost: 1) evalSimpleMultipleDepentryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(0, 0, ar_2, ar_3)) (Comp: 1, Cost: 1) evalSimpleMultipleDepstart(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepentryin(ar_0, ar_1, ar_2, ar_3)) start location: koat_start leaf cost: 0 Repeatedly propagating knowledge in problem 6 produces the following problem: 7: T: (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepstart(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] (Comp: 2, Cost: 1) evalSimpleMultipleDepreturnin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepstop(ar_0, ar_1, ar_2, ar_3)) [ ar_1 - ar_2 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 ] (Comp: 2*ar_2, Cost: 1) evalSimpleMultipleDepbb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(0, ar_1 + 1, ar_2, ar_3)) [ ar_0 - ar_3 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ -ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 ] (Comp: 2*ar_3 + 4*ar_2*ar_3, Cost: 1) evalSimpleMultipleDepbb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_3 - 1 >= 0 /\ ar_2 + ar_3 - 2 >= 0 /\ ar_1 + ar_3 - 1 >= 0 /\ ar_0 + ar_3 - 1 >= 0 /\ -ar_0 + ar_3 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ -ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 ] (Comp: 2*ar_2, Cost: 1) evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ -ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_0 >= ar_3 ] (Comp: 2*ar_3 + 4*ar_2*ar_3, Cost: 1) evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb1in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ -ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_3 >= ar_0 + 1 ] (Comp: 2, Cost: 1) evalSimpleMultipleDepbb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepreturnin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_1 >= ar_2 ] (Comp: 2*ar_3 + 4*ar_2*ar_3 + 2*ar_2 + 1, Cost: 1) evalSimpleMultipleDepbb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbbin(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= 0 /\ ar_0 + ar_1 >= 0 /\ ar_0 >= 0 /\ ar_2 >= ar_1 + 1 ] (Comp: 1, Cost: 1) evalSimpleMultipleDepentryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepbb3in(0, 0, ar_2, ar_3)) (Comp: 1, Cost: 1) evalSimpleMultipleDepstart(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalSimpleMultipleDepentryin(ar_0, ar_1, ar_2, ar_3)) start location: koat_start leaf cost: 0 Complexity upper bound 6*ar_2 + 6*ar_3 + 12*ar_2*ar_3 + 7 Time: 0.318 sec (SMT: 0.271 sec) ---------------------------------------- (2) BOUNDS(1, n^2) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalSimpleMultipleDepstart 0: evalSimpleMultipleDepstart -> evalSimpleMultipleDepentryin : [], cost: 1 1: evalSimpleMultipleDepentryin -> evalSimpleMultipleDepbb3in : A'=0, B'=0, [], cost: 1 2: evalSimpleMultipleDepbb3in -> evalSimpleMultipleDepbbin : [ C>=1+B ], cost: 1 3: evalSimpleMultipleDepbb3in -> evalSimpleMultipleDepreturnin : [ B>=C ], cost: 1 4: evalSimpleMultipleDepbbin -> evalSimpleMultipleDepbb1in : [ D>=1+A ], cost: 1 5: evalSimpleMultipleDepbbin -> evalSimpleMultipleDepbb2in : [ A>=D ], cost: 1 6: evalSimpleMultipleDepbb1in -> evalSimpleMultipleDepbb3in : A'=1+A, [], cost: 1 7: evalSimpleMultipleDepbb2in -> evalSimpleMultipleDepbb3in : A'=0, B'=1+B, [], cost: 1 8: evalSimpleMultipleDepreturnin -> evalSimpleMultipleDepstop : [], cost: 1 Removed unreachable and leaf rules: Start location: evalSimpleMultipleDepstart 0: evalSimpleMultipleDepstart -> evalSimpleMultipleDepentryin : [], cost: 1 1: evalSimpleMultipleDepentryin -> evalSimpleMultipleDepbb3in : A'=0, B'=0, [], cost: 1 2: evalSimpleMultipleDepbb3in -> evalSimpleMultipleDepbbin : [ C>=1+B ], cost: 1 4: evalSimpleMultipleDepbbin -> evalSimpleMultipleDepbb1in : [ D>=1+A ], cost: 1 5: evalSimpleMultipleDepbbin -> evalSimpleMultipleDepbb2in : [ A>=D ], cost: 1 6: evalSimpleMultipleDepbb1in -> evalSimpleMultipleDepbb3in : A'=1+A, [], cost: 1 7: evalSimpleMultipleDepbb2in -> evalSimpleMultipleDepbb3in : A'=0, B'=1+B, [], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalSimpleMultipleDepstart 9: evalSimpleMultipleDepstart -> evalSimpleMultipleDepbb3in : A'=0, B'=0, [], cost: 2 2: evalSimpleMultipleDepbb3in -> evalSimpleMultipleDepbbin : [ C>=1+B ], cost: 1 10: evalSimpleMultipleDepbbin -> evalSimpleMultipleDepbb3in : A'=1+A, [ D>=1+A ], cost: 2 11: evalSimpleMultipleDepbbin -> evalSimpleMultipleDepbb3in : A'=0, B'=1+B, [ A>=D ], cost: 2 Eliminated locations (on tree-shaped paths): Start location: evalSimpleMultipleDepstart 9: evalSimpleMultipleDepstart -> evalSimpleMultipleDepbb3in : A'=0, B'=0, [], cost: 2 12: evalSimpleMultipleDepbb3in -> evalSimpleMultipleDepbb3in : A'=1+A, [ C>=1+B && D>=1+A ], cost: 3 13: evalSimpleMultipleDepbb3in -> evalSimpleMultipleDepbb3in : A'=0, B'=1+B, [ C>=1+B && A>=D ], cost: 3 Accelerating simple loops of location 2. Accelerating the following rules: 12: evalSimpleMultipleDepbb3in -> evalSimpleMultipleDepbb3in : A'=1+A, [ C>=1+B && D>=1+A ], cost: 3 13: evalSimpleMultipleDepbb3in -> evalSimpleMultipleDepbb3in : A'=0, B'=1+B, [ C>=1+B && A>=D ], cost: 3 Accelerated rule 12 with metering function D-A, yielding the new rule 14. Accelerated rule 13 with metering function C-B (after strengthening guard), yielding the new rule 15. Nested simple loops 13 (outer loop) and 14 (inner loop) with metering function -1+C-B, resulting in the new rules: 16, 17. Removing the simple loops: 12 13. Accelerated all simple loops using metering functions (where possible): Start location: evalSimpleMultipleDepstart 9: evalSimpleMultipleDepstart -> evalSimpleMultipleDepbb3in : A'=0, B'=0, [], cost: 2 14: evalSimpleMultipleDepbb3in -> evalSimpleMultipleDepbb3in : A'=D, [ C>=1+B && D>=1+A ], cost: 3*D-3*A 15: evalSimpleMultipleDepbb3in -> evalSimpleMultipleDepbb3in : A'=0, B'=C, [ C>=1+B && A>=D && 0>=D ], cost: 3*C-3*B 16: evalSimpleMultipleDepbb3in -> evalSimpleMultipleDepbb3in : A'=D, B'=-1+C, [ A>=D && C>=2+B && D>=1 ], cost: -3+3*C+3*D*(-1+C-B)-3*B 17: evalSimpleMultipleDepbb3in -> evalSimpleMultipleDepbb3in : A'=D, B'=-1+C, [ D>=1+A && C>=2+B && D>=1 ], cost: -3+3*C+3*D-3*A+3*D*(-1+C-B)-3*B Chained accelerated rules (with incoming rules): Start location: evalSimpleMultipleDepstart 9: evalSimpleMultipleDepstart -> evalSimpleMultipleDepbb3in : A'=0, B'=0, [], cost: 2 18: evalSimpleMultipleDepstart -> evalSimpleMultipleDepbb3in : A'=D, B'=0, [ C>=1 && D>=1 ], cost: 2+3*D 19: evalSimpleMultipleDepstart -> evalSimpleMultipleDepbb3in : A'=0, B'=C, [ C>=1 && 0>=D ], cost: 2+3*C 20: evalSimpleMultipleDepstart -> evalSimpleMultipleDepbb3in : A'=D, B'=-1+C, [ D>=1 && C>=2 ], cost: -1+3*D*(-1+C)+3*C+3*D Removed unreachable locations (and leaf rules with constant cost): Start location: evalSimpleMultipleDepstart 18: evalSimpleMultipleDepstart -> evalSimpleMultipleDepbb3in : A'=D, B'=0, [ C>=1 && D>=1 ], cost: 2+3*D 19: evalSimpleMultipleDepstart -> evalSimpleMultipleDepbb3in : A'=0, B'=C, [ C>=1 && 0>=D ], cost: 2+3*C 20: evalSimpleMultipleDepstart -> evalSimpleMultipleDepbb3in : A'=D, B'=-1+C, [ D>=1 && C>=2 ], cost: -1+3*D*(-1+C)+3*C+3*D ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalSimpleMultipleDepstart 18: evalSimpleMultipleDepstart -> evalSimpleMultipleDepbb3in : A'=D, B'=0, [ C>=1 && D>=1 ], cost: 2+3*D 19: evalSimpleMultipleDepstart -> evalSimpleMultipleDepbb3in : A'=0, B'=C, [ C>=1 && 0>=D ], cost: 2+3*C 20: evalSimpleMultipleDepstart -> evalSimpleMultipleDepbb3in : A'=D, B'=-1+C, [ D>=1 && C>=2 ], cost: -1+3*D*(-1+C)+3*C+3*D Computing asymptotic complexity for rule 18 Solved the limit problem by the following transformations: Created initial limit problem: C (+/+!), D (+/+!), 2+3*D (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {C==1,D==n} resulting limit problem: [solved] Solution: C / 1 D / n Resulting cost 2+3*n has complexity: Poly(n^1) Found new complexity Poly(n^1). Computing asymptotic complexity for rule 20 Solved the limit problem by the following transformations: Created initial limit problem: -1+3*C+3*C*D (+), D (+/+!), -1+C (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {C==n,D==n} resulting limit problem: [solved] Solution: C / n D / n Resulting cost -1+3*n^2+3*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: -1+3*n^2+3*n Rule cost: -1+3*D*(-1+C)+3*C+3*D Rule guard: [ D>=1 && C>=2 ] WORST_CASE(Omega(n^2),?) ---------------------------------------- (4) BOUNDS(n^2, INF)