/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^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^1, n^2). (0) CpxIntTrs (1) Koat Proof [FINISHED, 322 ms] (2) BOUNDS(1, n^2) (3) Loat Proof [FINISHED, 1237 ms] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: evalEx7start(A, B, C) -> Com_1(evalEx7entryin(A, B, C)) :|: TRUE evalEx7entryin(A, B, C) -> Com_1(evalEx7bb3in(A, B, A + 1)) :|: A >= 1 && B >= A + 1 evalEx7bb3in(A, B, C) -> Com_1(evalEx7bbin(A, B, C)) :|: A >= C + 1 evalEx7bb3in(A, B, C) -> Com_1(evalEx7bbin(A, B, C)) :|: C >= A + 1 evalEx7bb3in(A, B, C) -> Com_1(evalEx7returnin(A, B, C)) :|: C >= A && C <= A evalEx7bbin(A, B, C) -> Com_1(evalEx7bb3in(A, B, 0)) :|: C >= B + 1 evalEx7bbin(A, B, C) -> Com_1(evalEx7bb3in(A, B, C + 1)) :|: B >= C evalEx7returnin(A, B, C) -> Com_1(evalEx7stop(A, B, C)) :|: TRUE The start-symbols are:[evalEx7start_3] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 20*ar_1^2 + 62*ar_1 + 35) Initial complexity problem: 1: T: (Comp: ?, Cost: 1) evalEx7start(ar_0, ar_1, ar_2) -> Com_1(evalEx7entryin(ar_0, ar_1, ar_2)) (Comp: ?, Cost: 1) evalEx7entryin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_0 + 1)) [ ar_0 >= 1 /\ ar_1 >= ar_0 + 1 ] (Comp: ?, Cost: 1) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bbin(ar_0, ar_1, ar_2)) [ ar_0 >= ar_2 + 1 ] (Comp: ?, Cost: 1) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bbin(ar_0, ar_1, ar_2)) [ ar_2 >= ar_0 + 1 ] (Comp: ?, Cost: 1) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7returnin(ar_0, ar_1, ar_2)) [ ar_2 = ar_0 ] (Comp: ?, Cost: 1) evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, 0)) [ ar_2 >= ar_1 + 1 ] (Comp: ?, Cost: 1) evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 >= ar_2 ] (Comp: ?, Cost: 1) evalEx7returnin(ar_0, ar_1, ar_2) -> Com_1(evalEx7stop(ar_0, ar_1, ar_2)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2) -> Com_1(evalEx7start(ar_0, ar_1, ar_2)) [ 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) evalEx7start(ar_0, ar_1, ar_2) -> Com_1(evalEx7entryin(ar_0, ar_1, ar_2)) (Comp: 1, Cost: 1) evalEx7entryin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_0 + 1)) [ ar_0 >= 1 /\ ar_1 >= ar_0 + 1 ] (Comp: ?, Cost: 1) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bbin(ar_0, ar_1, ar_2)) [ ar_0 >= ar_2 + 1 ] (Comp: ?, Cost: 1) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bbin(ar_0, ar_1, ar_2)) [ ar_2 >= ar_0 + 1 ] (Comp: ?, Cost: 1) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7returnin(ar_0, ar_1, ar_2)) [ ar_2 = ar_0 ] (Comp: ?, Cost: 1) evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, 0)) [ ar_2 >= ar_1 + 1 ] (Comp: ?, Cost: 1) evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 >= ar_2 ] (Comp: ?, Cost: 1) evalEx7returnin(ar_0, ar_1, ar_2) -> Com_1(evalEx7stop(ar_0, ar_1, ar_2)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2) -> Com_1(evalEx7start(ar_0, ar_1, ar_2)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalEx7start) = 2 Pol(evalEx7entryin) = 2 Pol(evalEx7bb3in) = 2 Pol(evalEx7bbin) = 2 Pol(evalEx7returnin) = 1 Pol(evalEx7stop) = 0 Pol(koat_start) = 2 orients all transitions weakly and the transitions evalEx7returnin(ar_0, ar_1, ar_2) -> Com_1(evalEx7stop(ar_0, ar_1, ar_2)) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7returnin(ar_0, ar_1, ar_2)) [ ar_2 = ar_0 ] strictly and produces the following problem: 3: T: (Comp: 1, Cost: 1) evalEx7start(ar_0, ar_1, ar_2) -> Com_1(evalEx7entryin(ar_0, ar_1, ar_2)) (Comp: 1, Cost: 1) evalEx7entryin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_0 + 1)) [ ar_0 >= 1 /\ ar_1 >= ar_0 + 1 ] (Comp: ?, Cost: 1) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bbin(ar_0, ar_1, ar_2)) [ ar_0 >= ar_2 + 1 ] (Comp: ?, Cost: 1) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bbin(ar_0, ar_1, ar_2)) [ ar_2 >= ar_0 + 1 ] (Comp: 2, Cost: 1) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7returnin(ar_0, ar_1, ar_2)) [ ar_2 = ar_0 ] (Comp: ?, Cost: 1) evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, 0)) [ ar_2 >= ar_1 + 1 ] (Comp: ?, Cost: 1) evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 >= ar_2 ] (Comp: 2, Cost: 1) evalEx7returnin(ar_0, ar_1, ar_2) -> Com_1(evalEx7stop(ar_0, ar_1, ar_2)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2) -> Com_1(evalEx7start(ar_0, ar_1, ar_2)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Applied AI with 'oct' on problem 3 to obtain the following invariants: For symbol evalEx7bb3in: X_2 - 2 >= 0 /\ X_1 + X_2 - 3 >= 0 /\ -X_1 + X_2 - 1 >= 0 /\ X_1 - 1 >= 0 For symbol evalEx7bbin: X_2 - 2 >= 0 /\ X_1 + X_2 - 3 >= 0 /\ -X_1 + X_2 - 1 >= 0 /\ X_1 - 1 >= 0 For symbol evalEx7returnin: X_2 - X_3 - 1 >= 0 /\ X_1 - X_3 >= 0 /\ X_3 - 1 >= 0 /\ X_2 + X_3 - 3 >= 0 /\ X_1 + X_3 - 2 >= 0 /\ -X_1 + X_3 >= 0 /\ X_2 - 2 >= 0 /\ X_1 + X_2 - 3 >= 0 /\ -X_1 + X_2 - 1 >= 0 /\ X_1 - 1 >= 0 This yielded the following problem: 4: T: (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2) -> Com_1(evalEx7start(ar_0, ar_1, ar_2)) [ 0 <= 0 ] (Comp: 2, Cost: 1) evalEx7returnin(ar_0, ar_1, ar_2) -> Com_1(evalEx7stop(ar_0, ar_1, ar_2)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_0 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ ar_0 + ar_2 - 2 >= 0 /\ -ar_0 + ar_2 >= 0 /\ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 ] (Comp: ?, Cost: 1) evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_2 ] (Comp: ?, Cost: 1) evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, 0)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_1 + 1 ] (Comp: 2, Cost: 1) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7returnin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 = ar_0 ] (Comp: ?, Cost: 1) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bbin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_0 + 1 ] (Comp: ?, Cost: 1) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bbin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_2 + 1 ] (Comp: 1, Cost: 1) evalEx7entryin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_0 + 1)) [ ar_0 >= 1 /\ ar_1 >= ar_0 + 1 ] (Comp: 1, Cost: 1) evalEx7start(ar_0, ar_1, ar_2) -> Com_1(evalEx7entryin(ar_0, ar_1, ar_2)) start location: koat_start leaf cost: 0 By chaining the transition koat_start(ar_0, ar_1, ar_2) -> Com_1(evalEx7start(ar_0, ar_1, ar_2)) [ 0 <= 0 ] with all transitions in problem 4, the following new transition is obtained: koat_start(ar_0, ar_1, ar_2) -> Com_1(evalEx7entryin(ar_0, ar_1, ar_2)) [ 0 <= 0 ] We thus obtain the following problem: 5: T: (Comp: 1, Cost: 1) koat_start(ar_0, ar_1, ar_2) -> Com_1(evalEx7entryin(ar_0, ar_1, ar_2)) [ 0 <= 0 ] (Comp: 2, Cost: 1) evalEx7returnin(ar_0, ar_1, ar_2) -> Com_1(evalEx7stop(ar_0, ar_1, ar_2)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_0 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ ar_0 + ar_2 - 2 >= 0 /\ -ar_0 + ar_2 >= 0 /\ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 ] (Comp: ?, Cost: 1) evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_2 ] (Comp: ?, Cost: 1) evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, 0)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_1 + 1 ] (Comp: 2, Cost: 1) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7returnin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 = ar_0 ] (Comp: ?, Cost: 1) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bbin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_0 + 1 ] (Comp: ?, Cost: 1) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bbin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_2 + 1 ] (Comp: 1, Cost: 1) evalEx7entryin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_0 + 1)) [ ar_0 >= 1 /\ ar_1 >= ar_0 + 1 ] (Comp: 1, Cost: 1) evalEx7start(ar_0, ar_1, ar_2) -> Com_1(evalEx7entryin(ar_0, ar_1, ar_2)) start location: koat_start leaf cost: 0 Testing for reachability in the complexity graph removes the following transition from problem 5: evalEx7start(ar_0, ar_1, ar_2) -> Com_1(evalEx7entryin(ar_0, ar_1, ar_2)) We thus obtain the following problem: 6: T: (Comp: 2, Cost: 1) evalEx7returnin(ar_0, ar_1, ar_2) -> Com_1(evalEx7stop(ar_0, ar_1, ar_2)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_0 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ ar_0 + ar_2 - 2 >= 0 /\ -ar_0 + ar_2 >= 0 /\ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 ] (Comp: ?, Cost: 1) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bbin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_2 + 1 ] (Comp: 2, Cost: 1) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7returnin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 = ar_0 ] (Comp: ?, Cost: 1) evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, 0)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_1 + 1 ] (Comp: ?, Cost: 1) evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_2 ] (Comp: ?, Cost: 1) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bbin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_0 + 1 ] (Comp: 1, Cost: 1) evalEx7entryin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_0 + 1)) [ ar_0 >= 1 /\ ar_1 >= ar_0 + 1 ] (Comp: 1, Cost: 1) koat_start(ar_0, ar_1, ar_2) -> Com_1(evalEx7entryin(ar_0, ar_1, ar_2)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 By chaining the transition evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bbin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_2 + 1 ] with all transitions in problem 6, the following new transition is obtained: evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_2 + 1 /\ ar_1 >= ar_2 ] We thus obtain the following problem: 7: T: (Comp: ?, Cost: 2) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_2 + 1 /\ ar_1 >= ar_2 ] (Comp: 2, Cost: 1) evalEx7returnin(ar_0, ar_1, ar_2) -> Com_1(evalEx7stop(ar_0, ar_1, ar_2)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_0 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ ar_0 + ar_2 - 2 >= 0 /\ -ar_0 + ar_2 >= 0 /\ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 ] (Comp: 2, Cost: 1) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7returnin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 = ar_0 ] (Comp: ?, Cost: 1) evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, 0)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_1 + 1 ] (Comp: ?, Cost: 1) evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_2 ] (Comp: ?, Cost: 1) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bbin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_0 + 1 ] (Comp: 1, Cost: 1) evalEx7entryin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_0 + 1)) [ ar_0 >= 1 /\ ar_1 >= ar_0 + 1 ] (Comp: 1, Cost: 1) koat_start(ar_0, ar_1, ar_2) -> Com_1(evalEx7entryin(ar_0, ar_1, ar_2)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalEx7bbin) = V_2 - V_3 + 1 Pol(evalEx7bb3in) = V_2 - V_3 + 1 and size complexities S("koat_start(ar_0, ar_1, ar_2) -> Com_1(evalEx7entryin(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-0) = ar_0 S("koat_start(ar_0, ar_1, ar_2) -> Com_1(evalEx7entryin(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-1) = ar_1 S("koat_start(ar_0, ar_1, ar_2) -> Com_1(evalEx7entryin(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-2) = ar_2 S("evalEx7entryin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_0 + 1)) [ ar_0 >= 1 /\\ ar_1 >= ar_0 + 1 ]", 0-0) = ar_0 S("evalEx7entryin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_0 + 1)) [ ar_0 >= 1 /\\ ar_1 >= ar_0 + 1 ]", 0-1) = ar_1 S("evalEx7entryin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_0 + 1)) [ ar_0 >= 1 /\\ ar_1 >= ar_0 + 1 ]", 0-2) = ar_1 S("evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bbin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_2 >= ar_0 + 1 ]", 0-0) = ar_0 S("evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bbin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_2 >= ar_0 + 1 ]", 0-1) = ar_1 S("evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bbin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_2 >= ar_0 + 1 ]", 0-2) = ? S("evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_1 >= ar_2 ]", 0-0) = ar_0 S("evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_1 >= ar_2 ]", 0-1) = ar_1 S("evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_1 >= ar_2 ]", 0-2) = ? S("evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, 0)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_2 >= ar_1 + 1 ]", 0-0) = ar_0 S("evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, 0)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_2 >= ar_1 + 1 ]", 0-1) = ar_1 S("evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, 0)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_2 >= ar_1 + 1 ]", 0-2) = 0 S("evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7returnin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_2 = ar_0 ]", 0-0) = ar_0 S("evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7returnin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_2 = ar_0 ]", 0-1) = ar_1 S("evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7returnin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_2 = ar_0 ]", 0-2) = ? S("evalEx7returnin(ar_0, ar_1, ar_2) -> Com_1(evalEx7stop(ar_0, ar_1, ar_2)) [ ar_1 - ar_2 - 1 >= 0 /\\ ar_0 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 3 >= 0 /\\ ar_0 + ar_2 - 2 >= 0 /\\ -ar_0 + ar_2 >= 0 /\\ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 ]", 0-0) = ar_0 S("evalEx7returnin(ar_0, ar_1, ar_2) -> Com_1(evalEx7stop(ar_0, ar_1, ar_2)) [ ar_1 - ar_2 - 1 >= 0 /\\ ar_0 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 3 >= 0 /\\ ar_0 + ar_2 - 2 >= 0 /\\ -ar_0 + ar_2 >= 0 /\\ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 ]", 0-1) = ar_1 S("evalEx7returnin(ar_0, ar_1, ar_2) -> Com_1(evalEx7stop(ar_0, ar_1, ar_2)) [ ar_1 - ar_2 - 1 >= 0 /\\ ar_0 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 3 >= 0 /\\ ar_0 + ar_2 - 2 >= 0 /\\ -ar_0 + ar_2 >= 0 /\\ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 ]", 0-2) = ? S("evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_0 >= ar_2 + 1 /\\ ar_1 >= ar_2 ]", 0-0) = ar_0 S("evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_0 >= ar_2 + 1 /\\ ar_1 >= ar_2 ]", 0-1) = ar_1 S("evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_0 >= ar_2 + 1 /\\ ar_1 >= ar_2 ]", 0-2) = ? orients the transitions evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_2 ] evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bbin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_0 + 1 ] weakly and the transition evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_2 ] strictly and produces the following problem: 8: T: (Comp: ?, Cost: 2) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_2 + 1 /\ ar_1 >= ar_2 ] (Comp: 2, Cost: 1) evalEx7returnin(ar_0, ar_1, ar_2) -> Com_1(evalEx7stop(ar_0, ar_1, ar_2)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_0 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ ar_0 + ar_2 - 2 >= 0 /\ -ar_0 + ar_2 >= 0 /\ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 ] (Comp: 2, Cost: 1) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7returnin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 = ar_0 ] (Comp: ?, Cost: 1) evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, 0)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_1 + 1 ] (Comp: 2*ar_1 + 1, Cost: 1) evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_2 ] (Comp: ?, Cost: 1) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bbin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_0 + 1 ] (Comp: 1, Cost: 1) evalEx7entryin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_0 + 1)) [ ar_0 >= 1 /\ ar_1 >= ar_0 + 1 ] (Comp: 1, Cost: 1) koat_start(ar_0, ar_1, ar_2) -> Com_1(evalEx7entryin(ar_0, ar_1, ar_2)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Repeatedly propagating knowledge in problem 8 produces the following problem: 9: T: (Comp: ?, Cost: 2) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_2 + 1 /\ ar_1 >= ar_2 ] (Comp: 2, Cost: 1) evalEx7returnin(ar_0, ar_1, ar_2) -> Com_1(evalEx7stop(ar_0, ar_1, ar_2)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_0 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ ar_0 + ar_2 - 2 >= 0 /\ -ar_0 + ar_2 >= 0 /\ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 ] (Comp: 2, Cost: 1) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7returnin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 = ar_0 ] (Comp: 2*ar_1 + 2, Cost: 1) evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, 0)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_1 + 1 ] (Comp: 2*ar_1 + 1, Cost: 1) evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_2 ] (Comp: 2*ar_1 + 2, Cost: 1) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bbin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_0 + 1 ] (Comp: 1, Cost: 1) evalEx7entryin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_0 + 1)) [ ar_0 >= 1 /\ ar_1 >= ar_0 + 1 ] (Comp: 1, Cost: 1) koat_start(ar_0, ar_1, ar_2) -> Com_1(evalEx7entryin(ar_0, ar_1, ar_2)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalEx7bb3in) = V_2 - V_3 + 1 and size complexities S("koat_start(ar_0, ar_1, ar_2) -> Com_1(evalEx7entryin(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-0) = ar_0 S("koat_start(ar_0, ar_1, ar_2) -> Com_1(evalEx7entryin(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-1) = ar_1 S("koat_start(ar_0, ar_1, ar_2) -> Com_1(evalEx7entryin(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-2) = ar_2 S("evalEx7entryin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_0 + 1)) [ ar_0 >= 1 /\\ ar_1 >= ar_0 + 1 ]", 0-0) = ar_0 S("evalEx7entryin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_0 + 1)) [ ar_0 >= 1 /\\ ar_1 >= ar_0 + 1 ]", 0-1) = ar_1 S("evalEx7entryin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_0 + 1)) [ ar_0 >= 1 /\\ ar_1 >= ar_0 + 1 ]", 0-2) = ar_1 S("evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bbin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_2 >= ar_0 + 1 ]", 0-0) = ar_0 S("evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bbin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_2 >= ar_0 + 1 ]", 0-1) = ar_1 S("evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bbin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_2 >= ar_0 + 1 ]", 0-2) = 3*ar_1 + 9 S("evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_1 >= ar_2 ]", 0-0) = ar_0 S("evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_1 >= ar_2 ]", 0-1) = ar_1 S("evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_1 >= ar_2 ]", 0-2) = 3*ar_1 + 9 S("evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, 0)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_2 >= ar_1 + 1 ]", 0-0) = ar_0 S("evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, 0)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_2 >= ar_1 + 1 ]", 0-1) = ar_1 S("evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, 0)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_2 >= ar_1 + 1 ]", 0-2) = 0 S("evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7returnin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_2 = ar_0 ]", 0-0) = ar_0 S("evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7returnin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_2 = ar_0 ]", 0-1) = ar_1 S("evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7returnin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_2 = ar_0 ]", 0-2) = ? S("evalEx7returnin(ar_0, ar_1, ar_2) -> Com_1(evalEx7stop(ar_0, ar_1, ar_2)) [ ar_1 - ar_2 - 1 >= 0 /\\ ar_0 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 3 >= 0 /\\ ar_0 + ar_2 - 2 >= 0 /\\ -ar_0 + ar_2 >= 0 /\\ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 ]", 0-0) = ar_0 S("evalEx7returnin(ar_0, ar_1, ar_2) -> Com_1(evalEx7stop(ar_0, ar_1, ar_2)) [ ar_1 - ar_2 - 1 >= 0 /\\ ar_0 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 3 >= 0 /\\ ar_0 + ar_2 - 2 >= 0 /\\ -ar_0 + ar_2 >= 0 /\\ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 ]", 0-1) = ar_1 S("evalEx7returnin(ar_0, ar_1, ar_2) -> Com_1(evalEx7stop(ar_0, ar_1, ar_2)) [ ar_1 - ar_2 - 1 >= 0 /\\ ar_0 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 3 >= 0 /\\ ar_0 + ar_2 - 2 >= 0 /\\ -ar_0 + ar_2 >= 0 /\\ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 ]", 0-2) = ? S("evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_0 >= ar_2 + 1 /\\ ar_1 >= ar_2 ]", 0-0) = ar_0 S("evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_0 >= ar_2 + 1 /\\ ar_1 >= ar_2 ]", 0-1) = ar_1 S("evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\\ ar_0 + ar_1 - 3 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_0 >= ar_2 + 1 /\\ ar_1 >= ar_2 ]", 0-2) = ? orients the transitions evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_2 + 1 /\ ar_1 >= ar_2 ] weakly and the transition evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_2 + 1 /\ ar_1 >= ar_2 ] strictly and produces the following problem: 10: T: (Comp: 10*ar_1^2 + 28*ar_1 + 12, Cost: 2) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_2 + 1 /\ ar_1 >= ar_2 ] (Comp: 2, Cost: 1) evalEx7returnin(ar_0, ar_1, ar_2) -> Com_1(evalEx7stop(ar_0, ar_1, ar_2)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_0 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ ar_0 + ar_2 - 2 >= 0 /\ -ar_0 + ar_2 >= 0 /\ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 ] (Comp: 2, Cost: 1) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7returnin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 = ar_0 ] (Comp: 2*ar_1 + 2, Cost: 1) evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, 0)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_1 + 1 ] (Comp: 2*ar_1 + 1, Cost: 1) evalEx7bbin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_2 + 1)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_2 ] (Comp: 2*ar_1 + 2, Cost: 1) evalEx7bb3in(ar_0, ar_1, ar_2) -> Com_1(evalEx7bbin(ar_0, ar_1, ar_2)) [ ar_1 - 2 >= 0 /\ ar_0 + ar_1 - 3 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_0 + 1 ] (Comp: 1, Cost: 1) evalEx7entryin(ar_0, ar_1, ar_2) -> Com_1(evalEx7bb3in(ar_0, ar_1, ar_0 + 1)) [ ar_0 >= 1 /\ ar_1 >= ar_0 + 1 ] (Comp: 1, Cost: 1) koat_start(ar_0, ar_1, ar_2) -> Com_1(evalEx7entryin(ar_0, ar_1, ar_2)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Complexity upper bound 20*ar_1^2 + 62*ar_1 + 35 Time: 0.309 sec (SMT: 0.255 sec) ---------------------------------------- (2) BOUNDS(1, n^2) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalEx7start 0: evalEx7start -> evalEx7entryin : [], cost: 1 1: evalEx7entryin -> evalEx7bb3in : C'=1+A, [ A>=1 && B>=1+A ], cost: 1 2: evalEx7bb3in -> evalEx7bbin : [ A>=1+C ], cost: 1 3: evalEx7bb3in -> evalEx7bbin : [ C>=1+A ], cost: 1 4: evalEx7bb3in -> evalEx7returnin : [ C==A ], cost: 1 5: evalEx7bbin -> evalEx7bb3in : C'=0, [ C>=1+B ], cost: 1 6: evalEx7bbin -> evalEx7bb3in : C'=1+C, [ B>=C ], cost: 1 7: evalEx7returnin -> evalEx7stop : [], cost: 1 Removed unreachable and leaf rules: Start location: evalEx7start 0: evalEx7start -> evalEx7entryin : [], cost: 1 1: evalEx7entryin -> evalEx7bb3in : C'=1+A, [ A>=1 && B>=1+A ], cost: 1 2: evalEx7bb3in -> evalEx7bbin : [ A>=1+C ], cost: 1 3: evalEx7bb3in -> evalEx7bbin : [ C>=1+A ], cost: 1 5: evalEx7bbin -> evalEx7bb3in : C'=0, [ C>=1+B ], cost: 1 6: evalEx7bbin -> evalEx7bb3in : C'=1+C, [ B>=C ], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalEx7start 8: evalEx7start -> evalEx7bb3in : C'=1+A, [ A>=1 && B>=1+A ], cost: 2 2: evalEx7bb3in -> evalEx7bbin : [ A>=1+C ], cost: 1 3: evalEx7bb3in -> evalEx7bbin : [ C>=1+A ], cost: 1 5: evalEx7bbin -> evalEx7bb3in : C'=0, [ C>=1+B ], cost: 1 6: evalEx7bbin -> evalEx7bb3in : C'=1+C, [ B>=C ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: evalEx7start 8: evalEx7start -> evalEx7bb3in : C'=1+A, [ A>=1 && B>=1+A ], cost: 2 9: evalEx7bb3in -> evalEx7bb3in : C'=0, [ A>=1+C && C>=1+B ], cost: 2 10: evalEx7bb3in -> evalEx7bb3in : C'=1+C, [ A>=1+C && B>=C ], cost: 2 11: evalEx7bb3in -> evalEx7bb3in : C'=0, [ C>=1+A && C>=1+B ], cost: 2 12: evalEx7bb3in -> evalEx7bb3in : C'=1+C, [ C>=1+A && B>=C ], cost: 2 Accelerating simple loops of location 2. Accelerating the following rules: 9: evalEx7bb3in -> evalEx7bb3in : C'=0, [ A>=1+C && C>=1+B ], cost: 2 10: evalEx7bb3in -> evalEx7bb3in : C'=1+C, [ A>=1+C && B>=C ], cost: 2 11: evalEx7bb3in -> evalEx7bb3in : C'=0, [ C>=1+A && C>=1+B ], cost: 2 12: evalEx7bb3in -> evalEx7bb3in : C'=1+C, [ C>=1+A && B>=C ], cost: 2 Accelerated rule 9 with NONTERM (after strengthening guard), yielding the new rule 13. Accelerated rule 10 with backward acceleration, yielding the new rule 14. Accelerated rule 10 with backward acceleration, yielding the new rule 15. Accelerated rule 11 with NONTERM (after strengthening guard), yielding the new rule 16. Accelerated rule 12 with metering function 1-C+B, yielding the new rule 17. Nested simple loops 9 (outer loop) and 15 (inner loop) with NONTERM, resulting in the new rules: 18, 19. Nested simple loops 11 (outer loop) and 17 (inner loop) with NONTERM, resulting in the new rules: 20, 21. Removing the simple loops: 9 10 11 12. Accelerated all simple loops using metering functions (where possible): Start location: evalEx7start 8: evalEx7start -> evalEx7bb3in : C'=1+A, [ A>=1 && B>=1+A ], cost: 2 13: evalEx7bb3in -> [6] : [ A>=1+C && C>=1+B && A>=1 && 0>=1+B ], cost: INF 14: evalEx7bb3in -> evalEx7bb3in : C'=A, [ A>=1+C && B>=C && B>=-1+A ], cost: -2*C+2*A 15: evalEx7bb3in -> evalEx7bb3in : C'=1+B, [ A>=1+C && B>=C && A>=1+B ], cost: 2-2*C+2*B 16: evalEx7bb3in -> [6] : [ C>=1+A && C>=1+B && 0>=1+A && 0>=1+B ], cost: INF 17: evalEx7bb3in -> evalEx7bb3in : C'=1+B, [ C>=1+A && B>=C ], cost: 2-2*C+2*B 18: evalEx7bb3in -> [6] : [ A>=1+C && C>=1+B && A>=1 && B>=0 && A>=1+B && 4+2*B>=1 ], cost: INF 19: evalEx7bb3in -> [6] : C'=1+B, [ A>=1+C && B>=C && A>=2+B && A>=1 && B>=0 && 4+2*B>=1 ], cost: INF 20: evalEx7bb3in -> [6] : [ C>=1+A && C>=1+B && 0>=1+A && B>=0 && 4+2*B>=1 ], cost: INF 21: evalEx7bb3in -> [6] : C'=1+B, [ C>=1+A && B>=C && 1+B>=1+A && 0>=1+A && B>=0 && 4+2*B>=1 ], cost: INF Chained accelerated rules (with incoming rules): Start location: evalEx7start 8: evalEx7start -> evalEx7bb3in : C'=1+A, [ A>=1 && B>=1+A ], cost: 2 22: evalEx7start -> evalEx7bb3in : C'=1+B, [ A>=1 && B>=1+A ], cost: 2-2*A+2*B Removed unreachable locations (and leaf rules with constant cost): Start location: evalEx7start 22: evalEx7start -> evalEx7bb3in : C'=1+B, [ A>=1 && B>=1+A ], cost: 2-2*A+2*B ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalEx7start 22: evalEx7start -> evalEx7bb3in : C'=1+B, [ A>=1 && B>=1+A ], cost: 2-2*A+2*B Computing asymptotic complexity for rule 22 Solved the limit problem by the following transformations: Created initial limit problem: 2-2*A+2*B (+), A (+/+!), -A+B (+/+!) [not solved] applying transformation rule (C) using substitution {A==1} resulting limit problem: 1 (+/+!), -1+B (+/+!), 2*B (+) [not solved] applying transformation rule (C) using substitution {B==1+A} resulting limit problem: 1 (+/+!), A (+/+!), 2+2*A (+) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: A (+/+!), 2+2*A (+) [not solved] applying transformation rule (D), replacing 2+2*A (+) by 2*A (+) resulting limit problem: 2*A (+), A (+/+!) [not solved] applying transformation rule (A), replacing 2*A (+) by A (+) and 2 (+!) using + limit vector (+,+!) resulting limit problem: 2 (+!), A (+) [not solved] applying transformation rule (B), deleting 2 (+!) resulting limit problem: A (+) [solved] Solution: A / 1 B / 1+n Resulting cost 2+2*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: 2+2*n Rule cost: 2-2*A+2*B Rule guard: [ A>=1 && B>=1+A ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (4) BOUNDS(n^1, INF)