6.71/3.04 WORST_CASE(Omega(n^2), O(n^2)) 6.71/3.05 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 6.71/3.05 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 6.71/3.05 6.71/3.05 6.71/3.05 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^2, n^2). 6.71/3.05 6.71/3.05 (0) CpxIntTrs 6.71/3.05 (1) Koat Proof [FINISHED, 418 ms] 6.71/3.05 (2) BOUNDS(1, n^2) 6.71/3.05 (3) Loat Proof [FINISHED, 1322 ms] 6.71/3.05 (4) BOUNDS(n^2, INF) 6.71/3.05 6.71/3.05 6.71/3.05 ---------------------------------------- 6.71/3.05 6.71/3.05 (0) 6.71/3.05 Obligation: 6.71/3.05 Complexity Int TRS consisting of the following rules: 6.71/3.05 f0(A, B, C, D) -> Com_1(f4(0, B, C, D)) :|: TRUE 6.71/3.05 f4(A, B, C, D) -> Com_1(f7(A, B, A + 1, D)) :|: B >= A + 1 6.71/3.05 f7(A, B, C, D) -> Com_1(f7(A, B, C + 1, 0)) :|: B >= C + 1 6.71/3.05 f7(A, B, C, D) -> Com_1(f7(A, B - 1, C, E)) :|: B >= C + 1 && 0 >= E + 1 6.71/3.05 f7(A, B, C, D) -> Com_1(f7(A, B - 1, C, E)) :|: B >= C + 1 && E >= 1 6.71/3.05 f7(A, B, C, D) -> Com_1(f4(A + 1, B, C, D)) :|: C >= B 6.71/3.05 f4(A, B, C, D) -> Com_1(f19(A, B, C, D)) :|: A >= B 6.71/3.05 6.71/3.05 The start-symbols are:[f0_4] 6.71/3.05 6.71/3.05 6.71/3.05 ---------------------------------------- 6.71/3.05 6.71/3.05 (1) Koat Proof (FINISHED) 6.71/3.05 YES(?, 9*ar_1 + 6*ar_1^2 + 5) 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 Initial complexity problem: 6.71/3.05 6.71/3.05 1: T: 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f0(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(0, ar_1, ar_2, ar_3)) 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_0 + 1, ar_3)) [ ar_1 >= ar_0 + 1 ] 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_2 + 1, 0)) [ ar_1 >= ar_2 + 1 ] 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 >= ar_2 + 1 /\ 0 >= e + 1 ] 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 >= ar_2 + 1 /\ e >= 1 ] 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_2 >= ar_1 ] 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f19(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_1 ] 6.71/3.05 6.71/3.05 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] 6.71/3.05 6.71/3.05 start location: koat_start 6.71/3.05 6.71/3.05 leaf cost: 0 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 Repeatedly propagating knowledge in problem 1 produces the following problem: 6.71/3.05 6.71/3.05 2: T: 6.71/3.05 6.71/3.05 (Comp: 1, Cost: 1) f0(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(0, ar_1, ar_2, ar_3)) 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_0 + 1, ar_3)) [ ar_1 >= ar_0 + 1 ] 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_2 + 1, 0)) [ ar_1 >= ar_2 + 1 ] 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 >= ar_2 + 1 /\ 0 >= e + 1 ] 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 >= ar_2 + 1 /\ e >= 1 ] 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_2 >= ar_1 ] 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f19(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_1 ] 6.71/3.05 6.71/3.05 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] 6.71/3.05 6.71/3.05 start location: koat_start 6.71/3.05 6.71/3.05 leaf cost: 0 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 A polynomial rank function with 6.71/3.05 6.71/3.05 Pol(f0) = 1 6.71/3.05 6.71/3.05 Pol(f4) = 1 6.71/3.05 6.71/3.05 Pol(f7) = 1 6.71/3.05 6.71/3.05 Pol(f19) = 0 6.71/3.05 6.71/3.05 Pol(koat_start) = 1 6.71/3.05 6.71/3.05 orients all transitions weakly and the transition 6.71/3.05 6.71/3.05 f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f19(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_1 ] 6.71/3.05 6.71/3.05 strictly and produces the following problem: 6.71/3.05 6.71/3.05 3: T: 6.71/3.05 6.71/3.05 (Comp: 1, Cost: 1) f0(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(0, ar_1, ar_2, ar_3)) 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_0 + 1, ar_3)) [ ar_1 >= ar_0 + 1 ] 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_2 + 1, 0)) [ ar_1 >= ar_2 + 1 ] 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 >= ar_2 + 1 /\ 0 >= e + 1 ] 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 >= ar_2 + 1 /\ e >= 1 ] 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_2 >= ar_1 ] 6.71/3.05 6.71/3.05 (Comp: 1, Cost: 1) f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f19(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_1 ] 6.71/3.05 6.71/3.05 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] 6.71/3.05 6.71/3.05 start location: koat_start 6.71/3.05 6.71/3.05 leaf cost: 0 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 A polynomial rank function with 6.71/3.05 6.71/3.05 Pol(f0) = V_2 + 1 6.71/3.05 6.71/3.05 Pol(f4) = -V_1 + V_2 + 1 6.71/3.05 6.71/3.05 Pol(f7) = -V_1 + V_2 6.71/3.05 6.71/3.05 Pol(f19) = -V_1 + V_2 6.71/3.05 6.71/3.05 Pol(koat_start) = V_2 + 1 6.71/3.05 6.71/3.05 orients all transitions weakly and the transition 6.71/3.05 6.71/3.05 f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_0 + 1, ar_3)) [ ar_1 >= ar_0 + 1 ] 6.71/3.05 6.71/3.05 strictly and produces the following problem: 6.71/3.05 6.71/3.05 4: T: 6.71/3.05 6.71/3.05 (Comp: 1, Cost: 1) f0(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(0, ar_1, ar_2, ar_3)) 6.71/3.05 6.71/3.05 (Comp: ar_1 + 1, Cost: 1) f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_0 + 1, ar_3)) [ ar_1 >= ar_0 + 1 ] 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_2 + 1, 0)) [ ar_1 >= ar_2 + 1 ] 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 >= ar_2 + 1 /\ 0 >= e + 1 ] 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 >= ar_2 + 1 /\ e >= 1 ] 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_2 >= ar_1 ] 6.71/3.05 6.71/3.05 (Comp: 1, Cost: 1) f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f19(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_1 ] 6.71/3.05 6.71/3.05 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] 6.71/3.05 6.71/3.05 start location: koat_start 6.71/3.05 6.71/3.05 leaf cost: 0 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 A polynomial rank function with 6.71/3.05 6.71/3.05 Pol(f7) = 1 6.71/3.05 6.71/3.05 Pol(f4) = 0 6.71/3.05 6.71/3.05 and size complexities 6.71/3.05 6.71/3.05 S("koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]", 0-0) = ar_0 6.71/3.05 6.71/3.05 S("koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]", 0-1) = ar_1 6.71/3.05 6.71/3.05 S("koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]", 0-2) = ar_2 6.71/3.05 6.71/3.05 S("koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]", 0-3) = ar_3 6.71/3.05 6.71/3.05 S("f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f19(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_1 ]", 0-0) = ? 6.71/3.05 6.71/3.05 S("f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f19(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_1 ]", 0-1) = ? 6.71/3.05 6.71/3.05 S("f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f19(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_1 ]", 0-2) = ? 6.71/3.05 6.71/3.05 S("f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f19(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_1 ]", 0-3) = ? 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_2 >= ar_1 ]", 0-0) = ? 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_2 >= ar_1 ]", 0-1) = ? 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_2 >= ar_1 ]", 0-2) = ? 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_2 >= ar_1 ]", 0-3) = ? 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 >= ar_2 + 1 /\\ e >= 1 ]", 0-0) = ? 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 >= ar_2 + 1 /\\ e >= 1 ]", 0-1) = ? 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 >= ar_2 + 1 /\\ e >= 1 ]", 0-2) = ? 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 >= ar_2 + 1 /\\ e >= 1 ]", 0-3) = ? 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 >= ar_2 + 1 /\\ 0 >= e + 1 ]", 0-0) = ? 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 >= ar_2 + 1 /\\ 0 >= e + 1 ]", 0-1) = ? 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 >= ar_2 + 1 /\\ 0 >= e + 1 ]", 0-2) = ? 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 >= ar_2 + 1 /\\ 0 >= e + 1 ]", 0-3) = ? 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_2 + 1, 0)) [ ar_1 >= ar_2 + 1 ]", 0-0) = ? 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_2 + 1, 0)) [ ar_1 >= ar_2 + 1 ]", 0-1) = ? 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_2 + 1, 0)) [ ar_1 >= ar_2 + 1 ]", 0-2) = ? 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_2 + 1, 0)) [ ar_1 >= ar_2 + 1 ]", 0-3) = 0 6.71/3.05 6.71/3.05 S("f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_0 + 1, ar_3)) [ ar_1 >= ar_0 + 1 ]", 0-0) = ? 6.71/3.05 6.71/3.05 S("f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_0 + 1, ar_3)) [ ar_1 >= ar_0 + 1 ]", 0-1) = ? 6.71/3.05 6.71/3.05 S("f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_0 + 1, ar_3)) [ ar_1 >= ar_0 + 1 ]", 0-2) = ? 6.71/3.05 6.71/3.05 S("f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_0 + 1, ar_3)) [ ar_1 >= ar_0 + 1 ]", 0-3) = ? 6.71/3.05 6.71/3.05 S("f0(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(0, ar_1, ar_2, ar_3))", 0-0) = 0 6.71/3.05 6.71/3.05 S("f0(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(0, ar_1, ar_2, ar_3))", 0-1) = ar_1 6.71/3.05 6.71/3.05 S("f0(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(0, ar_1, ar_2, ar_3))", 0-2) = ar_2 6.71/3.05 6.71/3.05 S("f0(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(0, ar_1, ar_2, ar_3))", 0-3) = ar_3 6.71/3.05 6.71/3.05 orients the transitions 6.71/3.05 6.71/3.05 f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_2 + 1, 0)) [ ar_1 >= ar_2 + 1 ] 6.71/3.05 6.71/3.05 f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 >= ar_2 + 1 /\ e >= 1 ] 6.71/3.05 6.71/3.05 f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 >= ar_2 + 1 /\ 0 >= e + 1 ] 6.71/3.05 6.71/3.05 f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_2 >= ar_1 ] 6.71/3.05 6.71/3.05 weakly and the transition 6.71/3.05 6.71/3.05 f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_2 >= ar_1 ] 6.71/3.05 6.71/3.05 strictly and produces the following problem: 6.71/3.05 6.71/3.05 5: T: 6.71/3.05 6.71/3.05 (Comp: 1, Cost: 1) f0(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(0, ar_1, ar_2, ar_3)) 6.71/3.05 6.71/3.05 (Comp: ar_1 + 1, Cost: 1) f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_0 + 1, ar_3)) [ ar_1 >= ar_0 + 1 ] 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_2 + 1, 0)) [ ar_1 >= ar_2 + 1 ] 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 >= ar_2 + 1 /\ 0 >= e + 1 ] 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 >= ar_2 + 1 /\ e >= 1 ] 6.71/3.05 6.71/3.05 (Comp: ar_1 + 1, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_2 >= ar_1 ] 6.71/3.05 6.71/3.05 (Comp: 1, Cost: 1) f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f19(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_1 ] 6.71/3.05 6.71/3.05 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] 6.71/3.05 6.71/3.05 start location: koat_start 6.71/3.05 6.71/3.05 leaf cost: 0 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 Applied AI with 'oct' on problem 5 to obtain the following invariants: 6.71/3.05 6.71/3.05 For symbol f4: X_1 >= 0 6.71/3.05 6.71/3.05 For symbol f7: X_2 - X_3 >= 0 /\ X_3 - 1 >= 0 /\ X_2 + X_3 - 2 >= 0 /\ X_1 + X_3 - 1 >= 0 /\ -X_1 + X_3 - 1 >= 0 /\ X_2 - 1 >= 0 /\ X_1 + X_2 - 1 >= 0 /\ -X_1 + X_2 - 1 >= 0 /\ X_1 >= 0 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 This yielded the following problem: 6.71/3.05 6.71/3.05 6: T: 6.71/3.05 6.71/3.05 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] 6.71/3.05 6.71/3.05 (Comp: 1, Cost: 1) f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f19(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= 0 /\ ar_0 >= ar_1 ] 6.71/3.05 6.71/3.05 (Comp: ar_1 + 1, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_1 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ -ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 /\ ar_2 >= ar_1 ] 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ -ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 /\ ar_1 >= ar_2 + 1 /\ e >= 1 ] 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ -ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 /\ ar_1 >= ar_2 + 1 /\ 0 >= e + 1 ] 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_2 + 1, 0)) [ ar_1 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ -ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 /\ ar_1 >= ar_2 + 1 ] 6.71/3.05 6.71/3.05 (Comp: ar_1 + 1, Cost: 1) f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_0 + 1, ar_3)) [ ar_0 >= 0 /\ ar_1 >= ar_0 + 1 ] 6.71/3.05 6.71/3.05 (Comp: 1, Cost: 1) f0(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(0, ar_1, ar_2, ar_3)) 6.71/3.05 6.71/3.05 start location: koat_start 6.71/3.05 6.71/3.05 leaf cost: 0 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 A polynomial rank function with 6.71/3.05 6.71/3.05 Pol(koat_start) = V_2 6.71/3.05 6.71/3.05 Pol(f0) = V_2 6.71/3.05 6.71/3.05 Pol(f4) = V_2 6.71/3.05 6.71/3.05 Pol(f19) = V_2 6.71/3.05 6.71/3.05 Pol(f7) = V_2 6.71/3.05 6.71/3.05 orients all transitions weakly and the transitions 6.71/3.05 6.71/3.05 f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ -ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 /\ ar_1 >= ar_2 + 1 /\ e >= 1 ] 6.71/3.05 6.71/3.05 f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ -ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 /\ ar_1 >= ar_2 + 1 /\ 0 >= e + 1 ] 6.71/3.05 6.71/3.05 strictly and produces the following problem: 6.71/3.05 6.71/3.05 7: T: 6.71/3.05 6.71/3.05 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] 6.71/3.05 6.71/3.05 (Comp: 1, Cost: 1) f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f19(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= 0 /\ ar_0 >= ar_1 ] 6.71/3.05 6.71/3.05 (Comp: ar_1 + 1, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_1 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ -ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 /\ ar_2 >= ar_1 ] 6.71/3.05 6.71/3.05 (Comp: ar_1, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ -ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 /\ ar_1 >= ar_2 + 1 /\ e >= 1 ] 6.71/3.05 6.71/3.05 (Comp: ar_1, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ -ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 /\ ar_1 >= ar_2 + 1 /\ 0 >= e + 1 ] 6.71/3.05 6.71/3.05 (Comp: ?, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_2 + 1, 0)) [ ar_1 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ -ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 /\ ar_1 >= ar_2 + 1 ] 6.71/3.05 6.71/3.05 (Comp: ar_1 + 1, Cost: 1) f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_0 + 1, ar_3)) [ ar_0 >= 0 /\ ar_1 >= ar_0 + 1 ] 6.71/3.05 6.71/3.05 (Comp: 1, Cost: 1) f0(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(0, ar_1, ar_2, ar_3)) 6.71/3.05 6.71/3.05 start location: koat_start 6.71/3.05 6.71/3.05 leaf cost: 0 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 A polynomial rank function with 6.71/3.05 6.71/3.05 Pol(f7) = V_2 - V_3 + 1 6.71/3.05 6.71/3.05 and size complexities 6.71/3.05 6.71/3.05 S("f0(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(0, ar_1, ar_2, ar_3))", 0-0) = 0 6.71/3.05 6.71/3.05 S("f0(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(0, ar_1, ar_2, ar_3))", 0-1) = ar_1 6.71/3.05 6.71/3.05 S("f0(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(0, ar_1, ar_2, ar_3))", 0-2) = ar_2 6.71/3.05 6.71/3.05 S("f0(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(0, ar_1, ar_2, ar_3))", 0-3) = ar_3 6.71/3.05 6.71/3.05 S("f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_0 + 1, ar_3)) [ ar_0 >= 0 /\\ ar_1 >= ar_0 + 1 ]", 0-0) = ar_1 6.71/3.05 6.71/3.05 S("f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_0 + 1, ar_3)) [ ar_0 >= 0 /\\ ar_1 >= ar_0 + 1 ]", 0-1) = ar_1 6.71/3.05 6.71/3.05 S("f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_0 + 1, ar_3)) [ ar_0 >= 0 /\\ ar_1 >= ar_0 + 1 ]", 0-2) = ar_1 6.71/3.05 6.71/3.05 S("f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_0 + 1, ar_3)) [ ar_0 >= 0 /\\ ar_1 >= ar_0 + 1 ]", 0-3) = ? 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_2 + 1, 0)) [ ar_1 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ -ar_0 + ar_2 - 1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 1 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 >= 0 /\\ ar_1 >= ar_2 + 1 ]", 0-0) = ar_1 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_2 + 1, 0)) [ ar_1 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ -ar_0 + ar_2 - 1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 1 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 >= 0 /\\ ar_1 >= ar_2 + 1 ]", 0-1) = ar_1 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_2 + 1, 0)) [ ar_1 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ -ar_0 + ar_2 - 1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 1 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 >= 0 /\\ ar_1 >= ar_2 + 1 ]", 0-2) = ar_1 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_2 + 1, 0)) [ ar_1 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ -ar_0 + ar_2 - 1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 1 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 >= 0 /\\ ar_1 >= ar_2 + 1 ]", 0-3) = 0 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ -ar_0 + ar_2 - 1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 1 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 >= 0 /\\ ar_1 >= ar_2 + 1 /\\ 0 >= e + 1 ]", 0-0) = ar_1 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ -ar_0 + ar_2 - 1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 1 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 >= 0 /\\ ar_1 >= ar_2 + 1 /\\ 0 >= e + 1 ]", 0-1) = ar_1 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ -ar_0 + ar_2 - 1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 1 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 >= 0 /\\ ar_1 >= ar_2 + 1 /\\ 0 >= e + 1 ]", 0-2) = ar_1 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ -ar_0 + ar_2 - 1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 1 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 >= 0 /\\ ar_1 >= ar_2 + 1 /\\ 0 >= e + 1 ]", 0-3) = ? 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ -ar_0 + ar_2 - 1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 1 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 >= 0 /\\ ar_1 >= ar_2 + 1 /\\ e >= 1 ]", 0-0) = ar_1 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ -ar_0 + ar_2 - 1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 1 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 >= 0 /\\ ar_1 >= ar_2 + 1 /\\ e >= 1 ]", 0-1) = ar_1 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ -ar_0 + ar_2 - 1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 1 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 >= 0 /\\ ar_1 >= ar_2 + 1 /\\ e >= 1 ]", 0-2) = ar_1 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ -ar_0 + ar_2 - 1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 1 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 >= 0 /\\ ar_1 >= ar_2 + 1 /\\ e >= 1 ]", 0-3) = ? 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_1 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ -ar_0 + ar_2 - 1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 1 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 >= 0 /\\ ar_2 >= ar_1 ]", 0-0) = ar_1 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_1 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ -ar_0 + ar_2 - 1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 1 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 >= 0 /\\ ar_2 >= ar_1 ]", 0-1) = ar_1 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_1 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ -ar_0 + ar_2 - 1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 1 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 >= 0 /\\ ar_2 >= ar_1 ]", 0-2) = ar_1 6.71/3.05 6.71/3.05 S("f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_1 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 1 >= 0 /\\ -ar_0 + ar_2 - 1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 1 >= 0 /\\ -ar_0 + ar_1 - 1 >= 0 /\\ ar_0 >= 0 /\\ ar_2 >= ar_1 ]", 0-3) = ? 6.71/3.05 6.71/3.05 S("f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f19(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= 0 /\\ ar_0 >= ar_1 ]", 0-0) = ar_1 6.71/3.05 6.71/3.05 S("f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f19(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= 0 /\\ ar_0 >= ar_1 ]", 0-1) = ar_1 6.71/3.05 6.71/3.05 S("f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f19(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= 0 /\\ ar_0 >= ar_1 ]", 0-2) = ar_1 + ar_2 6.71/3.05 6.71/3.05 S("f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f19(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= 0 /\\ ar_0 >= ar_1 ]", 0-3) = ? 6.71/3.05 6.71/3.05 S("koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]", 0-0) = ar_0 6.71/3.05 6.71/3.05 S("koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]", 0-1) = ar_1 6.71/3.05 6.71/3.05 S("koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]", 0-2) = ar_2 6.71/3.05 6.71/3.05 S("koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]", 0-3) = ar_3 6.71/3.05 6.71/3.05 orients the transitions 6.71/3.05 6.71/3.05 f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_2 + 1, 0)) [ ar_1 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ -ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 /\ ar_1 >= ar_2 + 1 ] 6.71/3.05 6.71/3.05 weakly and the transition 6.71/3.05 6.71/3.05 f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_2 + 1, 0)) [ ar_1 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ -ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 /\ ar_1 >= ar_2 + 1 ] 6.71/3.05 6.71/3.05 strictly and produces the following problem: 6.71/3.05 6.71/3.05 8: T: 6.71/3.05 6.71/3.05 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] 6.71/3.05 6.71/3.05 (Comp: 1, Cost: 1) f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f19(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= 0 /\ ar_0 >= ar_1 ] 6.71/3.05 6.71/3.05 (Comp: ar_1 + 1, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(ar_0 + 1, ar_1, ar_2, ar_3)) [ ar_1 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ -ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 /\ ar_2 >= ar_1 ] 6.71/3.05 6.71/3.05 (Comp: ar_1, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ -ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 /\ ar_1 >= ar_2 + 1 /\ e >= 1 ] 6.71/3.05 6.71/3.05 (Comp: ar_1, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1 - 1, ar_2, e)) [ ar_1 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ -ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 /\ ar_1 >= ar_2 + 1 /\ 0 >= e + 1 ] 6.71/3.05 6.71/3.05 (Comp: 6*ar_1^2 + 5*ar_1 + 1, Cost: 1) f7(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_2 + 1, 0)) [ ar_1 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ -ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 /\ ar_1 >= ar_2 + 1 ] 6.71/3.05 6.71/3.05 (Comp: ar_1 + 1, Cost: 1) f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f7(ar_0, ar_1, ar_0 + 1, ar_3)) [ ar_0 >= 0 /\ ar_1 >= ar_0 + 1 ] 6.71/3.05 6.71/3.05 (Comp: 1, Cost: 1) f0(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(0, ar_1, ar_2, ar_3)) 6.71/3.05 6.71/3.05 start location: koat_start 6.71/3.05 6.71/3.05 leaf cost: 0 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 Complexity upper bound 9*ar_1 + 6*ar_1^2 + 5 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 Time: 0.418 sec (SMT: 0.359 sec) 6.71/3.05 6.71/3.05 6.71/3.05 ---------------------------------------- 6.71/3.05 6.71/3.05 (2) 6.71/3.05 BOUNDS(1, n^2) 6.71/3.05 6.71/3.05 ---------------------------------------- 6.71/3.05 6.71/3.05 (3) Loat Proof (FINISHED) 6.71/3.05 6.71/3.05 6.71/3.05 ### Pre-processing the ITS problem ### 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 Initial linear ITS problem 6.71/3.05 6.71/3.05 Start location: f0 6.71/3.05 6.71/3.05 0: f0 -> f4 : A'=0, [], cost: 1 6.71/3.05 6.71/3.05 1: f4 -> f7 : C'=1+A, [ B>=1+A ], cost: 1 6.71/3.05 6.71/3.05 6: f4 -> f19 : [ A>=B ], cost: 1 6.71/3.05 6.71/3.05 2: f7 -> f7 : C'=1+C, D'=0, [ B>=1+C ], cost: 1 6.71/3.05 6.71/3.05 3: f7 -> f7 : B'=-1+B, D'=free, [ B>=1+C && 0>=1+free ], cost: 1 6.71/3.05 6.71/3.05 4: f7 -> f7 : B'=-1+B, D'=free_1, [ B>=1+C && free_1>=1 ], cost: 1 6.71/3.05 6.71/3.05 5: f7 -> f4 : A'=1+A, [ C>=B ], cost: 1 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 Removed unreachable and leaf rules: 6.71/3.05 6.71/3.05 Start location: f0 6.71/3.05 6.71/3.05 0: f0 -> f4 : A'=0, [], cost: 1 6.71/3.05 6.71/3.05 1: f4 -> f7 : C'=1+A, [ B>=1+A ], cost: 1 6.71/3.05 6.71/3.05 2: f7 -> f7 : C'=1+C, D'=0, [ B>=1+C ], cost: 1 6.71/3.05 6.71/3.05 3: f7 -> f7 : B'=-1+B, D'=free, [ B>=1+C && 0>=1+free ], cost: 1 6.71/3.05 6.71/3.05 4: f7 -> f7 : B'=-1+B, D'=free_1, [ B>=1+C && free_1>=1 ], cost: 1 6.71/3.05 6.71/3.05 5: f7 -> f4 : A'=1+A, [ C>=B ], cost: 1 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 ### Simplification by acceleration and chaining ### 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 Accelerating simple loops of location 2. 6.71/3.05 6.71/3.05 Accelerating the following rules: 6.71/3.05 6.71/3.05 2: f7 -> f7 : C'=1+C, D'=0, [ B>=1+C ], cost: 1 6.71/3.05 6.71/3.05 3: f7 -> f7 : B'=-1+B, D'=free, [ B>=1+C && 0>=1+free ], cost: 1 6.71/3.05 6.71/3.05 4: f7 -> f7 : B'=-1+B, D'=free_1, [ B>=1+C && free_1>=1 ], cost: 1 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 Accelerated rule 2 with metering function -C+B, yielding the new rule 7. 6.71/3.05 6.71/3.05 Accelerated rule 3 with metering function -C+B, yielding the new rule 8. 6.71/3.05 6.71/3.05 Accelerated rule 4 with metering function -C+B, yielding the new rule 9. 6.71/3.05 6.71/3.05 Removing the simple loops: 2 3 4. 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 Accelerated all simple loops using metering functions (where possible): 6.71/3.05 6.71/3.05 Start location: f0 6.71/3.05 6.71/3.05 0: f0 -> f4 : A'=0, [], cost: 1 6.71/3.05 6.71/3.05 1: f4 -> f7 : C'=1+A, [ B>=1+A ], cost: 1 6.71/3.05 6.71/3.05 5: f7 -> f4 : A'=1+A, [ C>=B ], cost: 1 6.71/3.05 6.71/3.05 7: f7 -> f7 : C'=B, D'=0, [ B>=1+C ], cost: -C+B 6.71/3.05 6.71/3.05 8: f7 -> f7 : B'=C, D'=free, [ B>=1+C && 0>=1+free ], cost: -C+B 6.71/3.05 6.71/3.05 9: f7 -> f7 : B'=C, D'=free_1, [ B>=1+C && free_1>=1 ], cost: -C+B 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 Chained accelerated rules (with incoming rules): 6.71/3.05 6.71/3.05 Start location: f0 6.71/3.05 6.71/3.05 0: f0 -> f4 : A'=0, [], cost: 1 6.71/3.05 6.71/3.05 1: f4 -> f7 : C'=1+A, [ B>=1+A ], cost: 1 6.71/3.05 6.71/3.05 10: f4 -> f7 : C'=B, D'=0, [ B>=2+A ], cost: -A+B 6.71/3.05 6.71/3.05 11: f4 -> f7 : B'=1+A, C'=1+A, D'=free, [ B>=2+A && 0>=1+free ], cost: -A+B 6.71/3.05 6.71/3.05 12: f4 -> f7 : B'=1+A, C'=1+A, D'=free_1, [ B>=2+A && free_1>=1 ], cost: -A+B 6.71/3.05 6.71/3.05 5: f7 -> f4 : A'=1+A, [ C>=B ], cost: 1 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 Eliminated locations (on tree-shaped paths): 6.71/3.05 6.71/3.05 Start location: f0 6.71/3.05 6.71/3.05 0: f0 -> f4 : A'=0, [], cost: 1 6.71/3.05 6.71/3.05 13: f4 -> f4 : A'=1+A, C'=1+A, [ B>=1+A && 1+A>=B ], cost: 2 6.71/3.05 6.71/3.05 14: f4 -> f4 : A'=1+A, C'=B, D'=0, [ B>=2+A ], cost: 1-A+B 6.71/3.05 6.71/3.05 15: f4 -> f4 : A'=1+A, B'=1+A, C'=1+A, D'=free, [ B>=2+A && 0>=1+free ], cost: 1-A+B 6.71/3.05 6.71/3.05 16: f4 -> f4 : A'=1+A, B'=1+A, C'=1+A, D'=free_1, [ B>=2+A && free_1>=1 ], cost: 1-A+B 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 Accelerating simple loops of location 1. 6.71/3.05 6.71/3.05 Simplified some of the simple loops (and removed duplicate rules). 6.71/3.05 6.71/3.05 Accelerating the following rules: 6.71/3.05 6.71/3.05 13: f4 -> f4 : A'=1+A, C'=1+A, [ 1+A-B==0 ], cost: 2 6.71/3.05 6.71/3.05 14: f4 -> f4 : A'=1+A, C'=B, D'=0, [ B>=2+A ], cost: 1-A+B 6.71/3.05 6.71/3.05 15: f4 -> f4 : A'=1+A, B'=1+A, C'=1+A, D'=free, [ B>=2+A && 0>=1+free ], cost: 1-A+B 6.71/3.05 6.71/3.05 16: f4 -> f4 : A'=1+A, B'=1+A, C'=1+A, D'=free_1, [ B>=2+A && free_1>=1 ], cost: 1-A+B 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 Accelerated rule 13 with metering function -A+B, yielding the new rule 17. 6.71/3.05 6.71/3.05 Accelerated rule 14 with metering function -1-A+B, yielding the new rule 18. 6.71/3.05 6.71/3.05 Found no metering function for rule 15. 6.71/3.05 6.71/3.05 Found no metering function for rule 16. 6.71/3.05 6.71/3.05 Removing the simple loops: 13 14. 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 Accelerated all simple loops using metering functions (where possible): 6.71/3.05 6.71/3.05 Start location: f0 6.71/3.05 6.71/3.05 0: f0 -> f4 : A'=0, [], cost: 1 6.71/3.05 6.71/3.05 15: f4 -> f4 : A'=1+A, B'=1+A, C'=1+A, D'=free, [ B>=2+A && 0>=1+free ], cost: 1-A+B 6.71/3.05 6.71/3.05 16: f4 -> f4 : A'=1+A, B'=1+A, C'=1+A, D'=free_1, [ B>=2+A && free_1>=1 ], cost: 1-A+B 6.71/3.05 6.71/3.05 17: f4 -> f4 : A'=B, C'=B, [ 1+A-B==0 ], cost: -2*A+2*B 6.71/3.05 6.71/3.05 18: f4 -> f4 : A'=-1+B, C'=B, D'=0, [ B>=2+A ], cost: -3/2-1/2*(1+A-B)^2-3/2*A-(1+A-B)*B+A*(1+A-B)+3/2*B 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 Chained accelerated rules (with incoming rules): 6.71/3.05 6.71/3.05 Start location: f0 6.71/3.05 6.71/3.05 0: f0 -> f4 : A'=0, [], cost: 1 6.71/3.05 6.71/3.05 19: f0 -> f4 : A'=1, B'=1, C'=1, D'=free, [ B>=2 && 0>=1+free ], cost: 2+B 6.71/3.05 6.71/3.05 20: f0 -> f4 : A'=1, B'=1, C'=1, D'=free_1, [ B>=2 && free_1>=1 ], cost: 2+B 6.71/3.05 6.71/3.05 21: f0 -> f4 : A'=B, C'=B, [ 1-B==0 ], cost: 1+2*B 6.71/3.05 6.71/3.05 22: f0 -> f4 : A'=-1+B, C'=B, D'=0, [ B>=2 ], cost: -1/2+(-1+B)*B-1/2*(-1+B)^2+3/2*B 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 Removed unreachable locations (and leaf rules with constant cost): 6.71/3.05 6.71/3.05 Start location: f0 6.71/3.05 6.71/3.05 19: f0 -> f4 : A'=1, B'=1, C'=1, D'=free, [ B>=2 && 0>=1+free ], cost: 2+B 6.71/3.05 6.71/3.05 20: f0 -> f4 : A'=1, B'=1, C'=1, D'=free_1, [ B>=2 && free_1>=1 ], cost: 2+B 6.71/3.05 6.71/3.05 21: f0 -> f4 : A'=B, C'=B, [ 1-B==0 ], cost: 1+2*B 6.71/3.05 6.71/3.05 22: f0 -> f4 : A'=-1+B, C'=B, D'=0, [ B>=2 ], cost: -1/2+(-1+B)*B-1/2*(-1+B)^2+3/2*B 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 ### Computing asymptotic complexity ### 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 Fully simplified ITS problem 6.71/3.05 6.71/3.05 Start location: f0 6.71/3.05 6.71/3.05 19: f0 -> f4 : A'=1, B'=1, C'=1, D'=free, [ B>=2 && 0>=1+free ], cost: 2+B 6.71/3.05 6.71/3.05 20: f0 -> f4 : A'=1, B'=1, C'=1, D'=free_1, [ B>=2 && free_1>=1 ], cost: 2+B 6.71/3.05 6.71/3.05 21: f0 -> f4 : A'=B, C'=B, [ 1-B==0 ], cost: 1+2*B 6.71/3.05 6.71/3.05 22: f0 -> f4 : A'=-1+B, C'=B, D'=0, [ B>=2 ], cost: -1/2+(-1+B)*B-1/2*(-1+B)^2+3/2*B 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 Computing asymptotic complexity for rule 19 6.71/3.05 6.71/3.05 Solved the limit problem by the following transformations: 6.71/3.05 6.71/3.05 Created initial limit problem: 6.71/3.05 6.71/3.05 2+B (+), -1+B (+/+!), -free (+/+!) [not solved] 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 removing all constraints (solved by SMT) 6.71/3.05 6.71/3.05 resulting limit problem: [solved] 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 applying transformation rule (C) using substitution {free==-n,B==n} 6.71/3.05 6.71/3.05 resulting limit problem: 6.71/3.05 6.71/3.05 [solved] 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 Solution: 6.71/3.05 6.71/3.05 free / -n 6.71/3.05 6.71/3.05 B / n 6.71/3.05 6.71/3.05 Resulting cost 2+n has complexity: Poly(n^1) 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 Found new complexity Poly(n^1). 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 Computing asymptotic complexity for rule 22 6.71/3.05 6.71/3.05 Solved the limit problem by the following transformations: 6.71/3.05 6.71/3.05 Created initial limit problem: 6.71/3.05 6.71/3.05 -1+B (+/+!), -1+1/2*B^2+3/2*B (+) [not solved] 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 removing all constraints (solved by SMT) 6.71/3.05 6.71/3.05 resulting limit problem: [solved] 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 applying transformation rule (C) using substitution {B==n} 6.71/3.05 6.71/3.05 resulting limit problem: 6.71/3.05 6.71/3.05 [solved] 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 Solution: 6.71/3.05 6.71/3.05 B / n 6.71/3.05 6.71/3.05 Resulting cost -1+3/2*n+1/2*n^2 has complexity: Poly(n^2) 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 Found new complexity Poly(n^2). 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 Obtained the following overall complexity (w.r.t. the length of the input n): 6.71/3.05 6.71/3.05 Complexity: Poly(n^2) 6.71/3.05 6.71/3.05 Cpx degree: 2 6.71/3.05 6.71/3.05 Solved cost: -1+3/2*n+1/2*n^2 6.71/3.05 6.71/3.05 Rule cost: -1/2+(-1+B)*B-1/2*(-1+B)^2+3/2*B 6.71/3.05 6.71/3.05 Rule guard: [ B>=2 ] 6.71/3.05 6.71/3.05 6.71/3.05 6.71/3.05 WORST_CASE(Omega(n^2),?) 6.71/3.05 6.71/3.05 6.71/3.05 ---------------------------------------- 6.71/3.05 6.71/3.05 (4) 6.71/3.05 BOUNDS(n^2, INF) 6.71/3.07 EOF