5.00/2.23 WORST_CASE(Omega(n^2), O(n^2)) 5.00/2.24 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 5.00/2.24 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.00/2.24 5.00/2.24 5.00/2.24 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^2, n^2). 5.00/2.24 5.00/2.24 (0) CpxIntTrs 5.00/2.24 (1) Koat Proof [FINISHED, 313 ms] 5.00/2.24 (2) BOUNDS(1, n^2) 5.00/2.24 (3) Loat Proof [FINISHED, 601 ms] 5.00/2.24 (4) BOUNDS(n^2, INF) 5.00/2.24 5.00/2.24 5.00/2.24 ---------------------------------------- 5.00/2.24 5.00/2.24 (0) 5.00/2.24 Obligation: 5.00/2.24 Complexity Int TRS consisting of the following rules: 5.00/2.24 start(A, B, C, D, E, F) -> Com_1(stop(A, B, C, F, E, F)) :|: 0 >= A && B >= C && B <= C && D >= E && D <= E && F >= A && F <= A 5.00/2.24 start(A, B, C, D, E, F) -> Com_1(lbl52(A, B - 1, C, F, E, F)) :|: A >= 1 && C >= 1 && B >= C && B <= C && D >= E && D <= E && F >= A && F <= A 5.00/2.24 start(A, B, C, D, E, F) -> Com_1(lbl72(A, F, C, F - 1, E, F)) :|: A >= 1 && 0 >= C && B >= C && B <= C && D >= E && D <= E && F >= A && F <= A 5.00/2.24 lbl52(A, B, C, D, E, F) -> Com_1(stop(A, B, C, D, E, F)) :|: 0 >= D && B >= 0 && D >= 1 && A >= D && F >= A && F <= A 5.00/2.24 lbl52(A, B, C, D, E, F) -> Com_1(lbl52(A, B - 1, C, D, E, F)) :|: D >= 1 && B >= 1 && B >= 0 && A >= D && F >= A && F <= A 5.00/2.24 lbl52(A, B, C, D, E, F) -> Com_1(lbl72(A, F, C, D - 1, E, F)) :|: D >= 1 && A >= D && B >= 0 && B <= 0 && F >= A && F <= A 5.00/2.24 lbl72(A, B, C, D, E, F) -> Com_1(stop(A, B, C, D, E, F)) :|: A >= 1 && D >= 0 && D <= 0 && F >= A && F <= A && B >= A && B <= A 5.00/2.24 lbl72(A, B, C, D, E, F) -> Com_1(lbl52(A, B - 1, C, D, E, F)) :|: D >= 1 && A >= 1 && D >= 0 && A >= D + 1 && F >= A && F <= A && B >= A && B <= A 5.00/2.24 lbl72(A, B, C, D, E, F) -> Com_1(lbl72(A, F, C, D - 1, E, F)) :|: D >= 1 && 0 >= A && D >= 0 && A >= D + 1 && F >= A && F <= A && B >= A && B <= A 5.00/2.24 start0(A, B, C, D, E, F) -> Com_1(start(A, C, C, E, E, A)) :|: TRUE 5.00/2.24 5.00/2.24 The start-symbols are:[start0_6] 5.00/2.24 5.00/2.24 5.00/2.24 ---------------------------------------- 5.00/2.24 5.00/2.24 (1) Koat Proof (FINISHED) 5.00/2.24 YES(?, 6*ar_0 + 2*ar_0^2 + ar_2 + 6) 5.00/2.24 5.00/2.24 5.00/2.24 5.00/2.24 Initial complexity problem: 5.00/2.24 5.00/2.24 1: T: 5.00/2.24 5.00/2.24 (Comp: ?, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_5, ar_4, ar_5)) [ 0 >= ar_0 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: ?, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_5, ar_4, ar_5)) [ ar_0 >= 1 /\ ar_2 >= 1 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: ?, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_5 - 1, ar_4, ar_5)) [ ar_0 >= 1 /\ 0 >= ar_2 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: ?, Cost: 1) lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 >= ar_3 /\ ar_1 >= 0 /\ ar_3 >= 1 /\ ar_0 >= ar_3 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: ?, Cost: 1) lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\ ar_1 >= 1 /\ ar_1 >= 0 /\ ar_0 >= ar_3 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: ?, Cost: 1) lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_3 - 1, ar_4, ar_5)) [ ar_3 >= 1 /\ ar_0 >= ar_3 /\ ar_1 = 0 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: ?, Cost: 1) lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_0 >= 1 /\ ar_3 = 0 /\ ar_5 = ar_0 /\ ar_1 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: ?, Cost: 1) lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\ ar_0 >= 1 /\ ar_3 >= 0 /\ ar_0 >= ar_3 + 1 /\ ar_5 = ar_0 /\ ar_1 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: ?, Cost: 1) lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_3 - 1, ar_4, ar_5)) [ ar_3 >= 1 /\ 0 >= ar_0 /\ ar_3 >= 0 /\ ar_0 >= ar_3 + 1 /\ ar_5 = ar_0 /\ ar_1 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: ?, Cost: 1) start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start(ar_0, ar_2, ar_2, ar_4, ar_4, ar_0)) 5.00/2.24 5.00/2.24 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ] 5.00/2.24 5.00/2.24 start location: koat_start 5.00/2.24 5.00/2.24 leaf cost: 0 5.00/2.24 5.00/2.24 5.00/2.24 5.00/2.24 Testing for reachability in the complexity graph removes the following transitions from problem 1: 5.00/2.24 5.00/2.24 lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 >= ar_3 /\ ar_1 >= 0 /\ ar_3 >= 1 /\ ar_0 >= ar_3 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_3 - 1, ar_4, ar_5)) [ ar_3 >= 1 /\ 0 >= ar_0 /\ ar_3 >= 0 /\ ar_0 >= ar_3 + 1 /\ ar_5 = ar_0 /\ ar_1 = ar_0 ] 5.00/2.24 5.00/2.24 We thus obtain the following problem: 5.00/2.24 5.00/2.24 2: T: 5.00/2.24 5.00/2.24 (Comp: ?, Cost: 1) lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\ ar_0 >= 1 /\ ar_3 >= 0 /\ ar_0 >= ar_3 + 1 /\ ar_5 = ar_0 /\ ar_1 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: ?, Cost: 1) lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_0 >= 1 /\ ar_3 = 0 /\ ar_5 = ar_0 /\ ar_1 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: ?, Cost: 1) lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_3 - 1, ar_4, ar_5)) [ ar_3 >= 1 /\ ar_0 >= ar_3 /\ ar_1 = 0 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: ?, Cost: 1) lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\ ar_1 >= 1 /\ ar_1 >= 0 /\ ar_0 >= ar_3 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: ?, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_5 - 1, ar_4, ar_5)) [ ar_0 >= 1 /\ 0 >= ar_2 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: ?, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_5, ar_4, ar_5)) [ ar_0 >= 1 /\ ar_2 >= 1 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: ?, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_5, ar_4, ar_5)) [ 0 >= ar_0 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: ?, Cost: 1) start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start(ar_0, ar_2, ar_2, ar_4, ar_4, ar_0)) 5.00/2.24 5.00/2.24 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ] 5.00/2.24 5.00/2.24 start location: koat_start 5.00/2.24 5.00/2.24 leaf cost: 0 5.00/2.24 5.00/2.24 5.00/2.24 5.00/2.24 Repeatedly propagating knowledge in problem 2 produces the following problem: 5.00/2.24 5.00/2.24 3: T: 5.00/2.24 5.00/2.24 (Comp: ?, Cost: 1) lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\ ar_0 >= 1 /\ ar_3 >= 0 /\ ar_0 >= ar_3 + 1 /\ ar_5 = ar_0 /\ ar_1 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: ?, Cost: 1) lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_0 >= 1 /\ ar_3 = 0 /\ ar_5 = ar_0 /\ ar_1 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: ?, Cost: 1) lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_3 - 1, ar_4, ar_5)) [ ar_3 >= 1 /\ ar_0 >= ar_3 /\ ar_1 = 0 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: ?, Cost: 1) lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\ ar_1 >= 1 /\ ar_1 >= 0 /\ ar_0 >= ar_3 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_5 - 1, ar_4, ar_5)) [ ar_0 >= 1 /\ 0 >= ar_2 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_5, ar_4, ar_5)) [ ar_0 >= 1 /\ ar_2 >= 1 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_5, ar_4, ar_5)) [ 0 >= ar_0 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: 1, Cost: 1) start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start(ar_0, ar_2, ar_2, ar_4, ar_4, ar_0)) 5.00/2.24 5.00/2.24 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ] 5.00/2.24 5.00/2.24 start location: koat_start 5.00/2.24 5.00/2.24 leaf cost: 0 5.00/2.24 5.00/2.24 5.00/2.24 5.00/2.24 A polynomial rank function with 5.00/2.24 5.00/2.24 Pol(lbl72) = 1 5.00/2.24 5.00/2.24 Pol(lbl52) = 1 5.00/2.24 5.00/2.24 Pol(stop) = 0 5.00/2.24 5.00/2.24 Pol(start) = 1 5.00/2.24 5.00/2.24 Pol(start0) = 1 5.00/2.24 5.00/2.24 Pol(koat_start) = 1 5.00/2.24 5.00/2.24 orients all transitions weakly and the transition 5.00/2.24 5.00/2.24 lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_0 >= 1 /\ ar_3 = 0 /\ ar_5 = ar_0 /\ ar_1 = ar_0 ] 5.00/2.24 5.00/2.24 strictly and produces the following problem: 5.00/2.24 5.00/2.24 4: T: 5.00/2.24 5.00/2.24 (Comp: ?, Cost: 1) lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\ ar_0 >= 1 /\ ar_3 >= 0 /\ ar_0 >= ar_3 + 1 /\ ar_5 = ar_0 /\ ar_1 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: 1, Cost: 1) lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_0 >= 1 /\ ar_3 = 0 /\ ar_5 = ar_0 /\ ar_1 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: ?, Cost: 1) lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_3 - 1, ar_4, ar_5)) [ ar_3 >= 1 /\ ar_0 >= ar_3 /\ ar_1 = 0 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: ?, Cost: 1) lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\ ar_1 >= 1 /\ ar_1 >= 0 /\ ar_0 >= ar_3 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_5 - 1, ar_4, ar_5)) [ ar_0 >= 1 /\ 0 >= ar_2 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_5, ar_4, ar_5)) [ ar_0 >= 1 /\ ar_2 >= 1 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_5, ar_4, ar_5)) [ 0 >= ar_0 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: 1, Cost: 1) start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start(ar_0, ar_2, ar_2, ar_4, ar_4, ar_0)) 5.00/2.24 5.00/2.24 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ] 5.00/2.24 5.00/2.24 start location: koat_start 5.00/2.24 5.00/2.24 leaf cost: 0 5.00/2.24 5.00/2.24 5.00/2.24 5.00/2.24 A polynomial rank function with 5.00/2.24 5.00/2.24 Pol(lbl72) = 2*V_4 5.00/2.24 5.00/2.24 Pol(lbl52) = 2*V_4 - 1 5.00/2.24 5.00/2.24 Pol(stop) = 2*V_1 + 2*V_4 - 2*V_6 5.00/2.24 5.00/2.24 Pol(start) = 2*V_1 5.00/2.24 5.00/2.24 Pol(start0) = 2*V_1 5.00/2.24 5.00/2.24 Pol(koat_start) = 2*V_1 5.00/2.24 5.00/2.24 orients all transitions weakly and the transitions 5.00/2.24 5.00/2.24 lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\ ar_0 >= 1 /\ ar_3 >= 0 /\ ar_0 >= ar_3 + 1 /\ ar_5 = ar_0 /\ ar_1 = ar_0 ] 5.00/2.24 5.00/2.24 lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_3 - 1, ar_4, ar_5)) [ ar_3 >= 1 /\ ar_0 >= ar_3 /\ ar_1 = 0 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 strictly and produces the following problem: 5.00/2.24 5.00/2.24 5: T: 5.00/2.24 5.00/2.24 (Comp: 2*ar_0, Cost: 1) lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\ ar_0 >= 1 /\ ar_3 >= 0 /\ ar_0 >= ar_3 + 1 /\ ar_5 = ar_0 /\ ar_1 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: 1, Cost: 1) lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_0 >= 1 /\ ar_3 = 0 /\ ar_5 = ar_0 /\ ar_1 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: 2*ar_0, Cost: 1) lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_3 - 1, ar_4, ar_5)) [ ar_3 >= 1 /\ ar_0 >= ar_3 /\ ar_1 = 0 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: ?, Cost: 1) lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\ ar_1 >= 1 /\ ar_1 >= 0 /\ ar_0 >= ar_3 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_5 - 1, ar_4, ar_5)) [ ar_0 >= 1 /\ 0 >= ar_2 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_5, ar_4, ar_5)) [ ar_0 >= 1 /\ ar_2 >= 1 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_5, ar_4, ar_5)) [ 0 >= ar_0 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: 1, Cost: 1) start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start(ar_0, ar_2, ar_2, ar_4, ar_4, ar_0)) 5.00/2.24 5.00/2.24 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ] 5.00/2.24 5.00/2.24 start location: koat_start 5.00/2.24 5.00/2.24 leaf cost: 0 5.00/2.24 5.00/2.24 5.00/2.24 5.00/2.24 A polynomial rank function with 5.00/2.24 5.00/2.24 Pol(lbl52) = V_2 + 1 5.00/2.24 5.00/2.24 and size complexities 5.00/2.24 5.00/2.24 S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ]", 0-0) = ar_0 5.00/2.24 5.00/2.24 S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ]", 0-1) = ar_1 5.00/2.24 5.00/2.24 S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ]", 0-2) = ar_2 5.00/2.24 5.00/2.24 S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ]", 0-3) = ar_3 5.00/2.24 5.00/2.24 S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ]", 0-4) = ar_4 5.00/2.24 5.00/2.24 S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ]", 0-5) = ar_5 5.00/2.24 5.00/2.24 S("start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start(ar_0, ar_2, ar_2, ar_4, ar_4, ar_0))", 0-0) = ar_0 5.00/2.24 5.00/2.24 S("start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start(ar_0, ar_2, ar_2, ar_4, ar_4, ar_0))", 0-1) = ar_2 5.00/2.24 5.00/2.24 S("start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start(ar_0, ar_2, ar_2, ar_4, ar_4, ar_0))", 0-2) = ar_2 5.00/2.24 5.00/2.24 S("start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start(ar_0, ar_2, ar_2, ar_4, ar_4, ar_0))", 0-3) = ar_4 5.00/2.24 5.00/2.24 S("start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start(ar_0, ar_2, ar_2, ar_4, ar_4, ar_0))", 0-4) = ar_4 5.00/2.24 5.00/2.24 S("start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start(ar_0, ar_2, ar_2, ar_4, ar_4, ar_0))", 0-5) = ar_0 5.00/2.24 5.00/2.24 S("start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_5, ar_4, ar_5)) [ 0 >= ar_0 /\\ ar_1 = ar_2 /\\ ar_3 = ar_4 /\\ ar_5 = ar_0 ]", 0-0) = ar_0 5.00/2.24 5.00/2.24 S("start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_5, ar_4, ar_5)) [ 0 >= ar_0 /\\ ar_1 = ar_2 /\\ ar_3 = ar_4 /\\ ar_5 = ar_0 ]", 0-1) = ar_2 5.00/2.24 5.00/2.24 S("start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_5, ar_4, ar_5)) [ 0 >= ar_0 /\\ ar_1 = ar_2 /\\ ar_3 = ar_4 /\\ ar_5 = ar_0 ]", 0-2) = ar_2 5.00/2.24 5.00/2.24 S("start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_5, ar_4, ar_5)) [ 0 >= ar_0 /\\ ar_1 = ar_2 /\\ ar_3 = ar_4 /\\ ar_5 = ar_0 ]", 0-3) = ar_0 5.00/2.24 5.00/2.24 S("start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_5, ar_4, ar_5)) [ 0 >= ar_0 /\\ ar_1 = ar_2 /\\ ar_3 = ar_4 /\\ ar_5 = ar_0 ]", 0-4) = ar_4 5.00/2.24 5.00/2.24 S("start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_5, ar_4, ar_5)) [ 0 >= ar_0 /\\ ar_1 = ar_2 /\\ ar_3 = ar_4 /\\ ar_5 = ar_0 ]", 0-5) = ar_0 5.00/2.24 5.00/2.24 S("start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_5, ar_4, ar_5)) [ ar_0 >= 1 /\\ ar_2 >= 1 /\\ ar_1 = ar_2 /\\ ar_3 = ar_4 /\\ ar_5 = ar_0 ]", 0-0) = ar_0 5.00/2.24 5.00/2.24 S("start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_5, ar_4, ar_5)) [ ar_0 >= 1 /\\ ar_2 >= 1 /\\ ar_1 = ar_2 /\\ ar_3 = ar_4 /\\ ar_5 = ar_0 ]", 0-1) = ar_2 5.00/2.24 5.00/2.24 S("start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_5, ar_4, ar_5)) [ ar_0 >= 1 /\\ ar_2 >= 1 /\\ ar_1 = ar_2 /\\ ar_3 = ar_4 /\\ ar_5 = ar_0 ]", 0-2) = ar_2 5.00/2.24 5.00/2.24 S("start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_5, ar_4, ar_5)) [ ar_0 >= 1 /\\ ar_2 >= 1 /\\ ar_1 = ar_2 /\\ ar_3 = ar_4 /\\ ar_5 = ar_0 ]", 0-3) = ar_0 5.00/2.24 5.00/2.24 S("start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_5, ar_4, ar_5)) [ ar_0 >= 1 /\\ ar_2 >= 1 /\\ ar_1 = ar_2 /\\ ar_3 = ar_4 /\\ ar_5 = ar_0 ]", 0-4) = ar_4 5.00/2.24 5.00/2.24 S("start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_5, ar_4, ar_5)) [ ar_0 >= 1 /\\ ar_2 >= 1 /\\ ar_1 = ar_2 /\\ ar_3 = ar_4 /\\ ar_5 = ar_0 ]", 0-5) = ar_0 5.00/2.24 5.00/2.24 S("start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_5 - 1, ar_4, ar_5)) [ ar_0 >= 1 /\\ 0 >= ar_2 /\\ ar_1 = ar_2 /\\ ar_3 = ar_4 /\\ ar_5 = ar_0 ]", 0-0) = ar_0 5.00/2.24 5.00/2.24 S("start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_5 - 1, ar_4, ar_5)) [ ar_0 >= 1 /\\ 0 >= ar_2 /\\ ar_1 = ar_2 /\\ ar_3 = ar_4 /\\ ar_5 = ar_0 ]", 0-1) = ar_0 5.00/2.24 5.00/2.24 S("start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_5 - 1, ar_4, ar_5)) [ ar_0 >= 1 /\\ 0 >= ar_2 /\\ ar_1 = ar_2 /\\ ar_3 = ar_4 /\\ ar_5 = ar_0 ]", 0-2) = ar_2 5.00/2.24 5.00/2.24 S("start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_5 - 1, ar_4, ar_5)) [ ar_0 >= 1 /\\ 0 >= ar_2 /\\ ar_1 = ar_2 /\\ ar_3 = ar_4 /\\ ar_5 = ar_0 ]", 0-3) = ar_0 5.00/2.24 5.00/2.24 S("start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_5 - 1, ar_4, ar_5)) [ ar_0 >= 1 /\\ 0 >= ar_2 /\\ ar_1 = ar_2 /\\ ar_3 = ar_4 /\\ ar_5 = ar_0 ]", 0-4) = ar_4 5.00/2.24 5.00/2.24 S("start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_5 - 1, ar_4, ar_5)) [ ar_0 >= 1 /\\ 0 >= ar_2 /\\ ar_1 = ar_2 /\\ ar_3 = ar_4 /\\ ar_5 = ar_0 ]", 0-5) = ar_0 5.00/2.24 5.00/2.24 S("lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\\ ar_1 >= 1 /\\ ar_1 >= 0 /\\ ar_0 >= ar_3 /\\ ar_5 = ar_0 ]", 0-0) = ar_0 5.00/2.24 5.00/2.24 S("lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\\ ar_1 >= 1 /\\ ar_1 >= 0 /\\ ar_0 >= ar_3 /\\ ar_5 = ar_0 ]", 0-1) = ar_0 + ar_2 5.00/2.24 5.00/2.24 S("lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\\ ar_1 >= 1 /\\ ar_1 >= 0 /\\ ar_0 >= ar_3 /\\ ar_5 = ar_0 ]", 0-2) = ar_2 5.00/2.24 5.00/2.24 S("lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\\ ar_1 >= 1 /\\ ar_1 >= 0 /\\ ar_0 >= ar_3 /\\ ar_5 = ar_0 ]", 0-3) = ar_0 5.00/2.24 5.00/2.24 S("lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\\ ar_1 >= 1 /\\ ar_1 >= 0 /\\ ar_0 >= ar_3 /\\ ar_5 = ar_0 ]", 0-4) = ar_4 5.00/2.24 5.00/2.24 S("lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\\ ar_1 >= 1 /\\ ar_1 >= 0 /\\ ar_0 >= ar_3 /\\ ar_5 = ar_0 ]", 0-5) = ar_0 5.00/2.24 5.00/2.24 S("lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_3 - 1, ar_4, ar_5)) [ ar_3 >= 1 /\\ ar_0 >= ar_3 /\\ ar_1 = 0 /\\ ar_5 = ar_0 ]", 0-0) = ar_0 5.00/2.24 5.00/2.24 S("lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_3 - 1, ar_4, ar_5)) [ ar_3 >= 1 /\\ ar_0 >= ar_3 /\\ ar_1 = 0 /\\ ar_5 = ar_0 ]", 0-1) = ar_0 5.00/2.24 5.00/2.24 S("lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_3 - 1, ar_4, ar_5)) [ ar_3 >= 1 /\\ ar_0 >= ar_3 /\\ ar_1 = 0 /\\ ar_5 = ar_0 ]", 0-2) = ar_2 5.00/2.24 5.00/2.24 S("lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_3 - 1, ar_4, ar_5)) [ ar_3 >= 1 /\\ ar_0 >= ar_3 /\\ ar_1 = 0 /\\ ar_5 = ar_0 ]", 0-3) = ar_0 5.00/2.24 5.00/2.24 S("lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_3 - 1, ar_4, ar_5)) [ ar_3 >= 1 /\\ ar_0 >= ar_3 /\\ ar_1 = 0 /\\ ar_5 = ar_0 ]", 0-4) = ar_4 5.00/2.24 5.00/2.24 S("lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_3 - 1, ar_4, ar_5)) [ ar_3 >= 1 /\\ ar_0 >= ar_3 /\\ ar_1 = 0 /\\ ar_5 = ar_0 ]", 0-5) = ar_0 5.00/2.24 5.00/2.24 S("lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_0 >= 1 /\\ ar_3 = 0 /\\ ar_5 = ar_0 /\\ ar_1 = ar_0 ]", 0-0) = ar_0 5.00/2.24 5.00/2.24 S("lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_0 >= 1 /\\ ar_3 = 0 /\\ ar_5 = ar_0 /\\ ar_1 = ar_0 ]", 0-1) = ar_0 5.00/2.24 5.00/2.24 S("lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_0 >= 1 /\\ ar_3 = 0 /\\ ar_5 = ar_0 /\\ ar_1 = ar_0 ]", 0-2) = ar_2 5.00/2.24 5.00/2.24 S("lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_0 >= 1 /\\ ar_3 = 0 /\\ ar_5 = ar_0 /\\ ar_1 = ar_0 ]", 0-3) = 0 5.00/2.24 5.00/2.24 S("lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_0 >= 1 /\\ ar_3 = 0 /\\ ar_5 = ar_0 /\\ ar_1 = ar_0 ]", 0-4) = ar_4 5.00/2.24 5.00/2.24 S("lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_0 >= 1 /\\ ar_3 = 0 /\\ ar_5 = ar_0 /\\ ar_1 = ar_0 ]", 0-5) = ar_0 5.00/2.24 5.00/2.24 S("lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\\ ar_0 >= 1 /\\ ar_3 >= 0 /\\ ar_0 >= ar_3 + 1 /\\ ar_5 = ar_0 /\\ ar_1 = ar_0 ]", 0-0) = ar_0 5.00/2.24 5.00/2.24 S("lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\\ ar_0 >= 1 /\\ ar_3 >= 0 /\\ ar_0 >= ar_3 + 1 /\\ ar_5 = ar_0 /\\ ar_1 = ar_0 ]", 0-1) = ar_0 5.00/2.24 5.00/2.24 S("lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\\ ar_0 >= 1 /\\ ar_3 >= 0 /\\ ar_0 >= ar_3 + 1 /\\ ar_5 = ar_0 /\\ ar_1 = ar_0 ]", 0-2) = ar_2 5.00/2.24 5.00/2.24 S("lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\\ ar_0 >= 1 /\\ ar_3 >= 0 /\\ ar_0 >= ar_3 + 1 /\\ ar_5 = ar_0 /\\ ar_1 = ar_0 ]", 0-3) = ar_0 5.00/2.24 5.00/2.24 S("lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\\ ar_0 >= 1 /\\ ar_3 >= 0 /\\ ar_0 >= ar_3 + 1 /\\ ar_5 = ar_0 /\\ ar_1 = ar_0 ]", 0-4) = ar_4 5.00/2.24 5.00/2.24 S("lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\\ ar_0 >= 1 /\\ ar_3 >= 0 /\\ ar_0 >= ar_3 + 1 /\\ ar_5 = ar_0 /\\ ar_1 = ar_0 ]", 0-5) = ar_0 5.00/2.24 5.00/2.24 orients the transitions 5.00/2.24 5.00/2.24 lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\ ar_1 >= 1 /\ ar_1 >= 0 /\ ar_0 >= ar_3 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 weakly and the transition 5.00/2.24 5.00/2.24 lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\ ar_1 >= 1 /\ ar_1 >= 0 /\ ar_0 >= ar_3 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 strictly and produces the following problem: 5.00/2.24 5.00/2.24 6: T: 5.00/2.24 5.00/2.24 (Comp: 2*ar_0, Cost: 1) lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\ ar_0 >= 1 /\ ar_3 >= 0 /\ ar_0 >= ar_3 + 1 /\ ar_5 = ar_0 /\ ar_1 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: 1, Cost: 1) lbl72(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_0 >= 1 /\ ar_3 = 0 /\ ar_5 = ar_0 /\ ar_1 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: 2*ar_0, Cost: 1) lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_3 - 1, ar_4, ar_5)) [ ar_3 >= 1 /\ ar_0 >= ar_3 /\ ar_1 = 0 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: 2*ar_0^2 + 2*ar_0 + ar_2 + 1, Cost: 1) lbl52(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= 1 /\ ar_1 >= 1 /\ ar_1 >= 0 /\ ar_0 >= ar_3 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl72(ar_0, ar_5, ar_2, ar_5 - 1, ar_4, ar_5)) [ ar_0 >= 1 /\ 0 >= ar_2 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(lbl52(ar_0, ar_1 - 1, ar_2, ar_5, ar_4, ar_5)) [ ar_0 >= 1 /\ ar_2 >= 1 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(stop(ar_0, ar_1, ar_2, ar_5, ar_4, ar_5)) [ 0 >= ar_0 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_0 ] 5.00/2.24 5.00/2.24 (Comp: 1, Cost: 1) start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start(ar_0, ar_2, ar_2, ar_4, ar_4, ar_0)) 5.00/2.24 5.00/2.24 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ] 5.00/2.24 5.00/2.24 start location: koat_start 5.00/2.24 5.00/2.24 leaf cost: 0 5.00/2.24 5.00/2.24 5.00/2.24 5.00/2.24 Complexity upper bound 6*ar_0 + 2*ar_0^2 + ar_2 + 6 5.00/2.24 5.00/2.24 5.00/2.24 5.00/2.24 Time: 0.269 sec (SMT: 0.227 sec) 5.00/2.24 5.00/2.24 5.00/2.24 ---------------------------------------- 5.00/2.24 5.00/2.24 (2) 5.00/2.24 BOUNDS(1, n^2) 5.00/2.24 5.00/2.24 ---------------------------------------- 5.00/2.24 5.00/2.24 (3) Loat Proof (FINISHED) 5.00/2.24 5.00/2.24 5.00/2.24 ### Pre-processing the ITS problem ### 5.00/2.24 5.00/2.24 5.00/2.24 5.00/2.24 Initial linear ITS problem 5.00/2.24 5.00/2.24 Start location: start0 5.00/2.24 5.00/2.24 0: start -> stop : D'=F, [ 0>=A && B==C && D==E && F==A ], cost: 1 5.00/2.24 5.00/2.24 1: start -> lbl52 : B'=-1+B, D'=F, [ A>=1 && C>=1 && B==C && D==E && F==A ], cost: 1 5.00/2.24 5.00/2.24 2: start -> lbl72 : B'=F, D'=-1+F, [ A>=1 && 0>=C && B==C && D==E && F==A ], cost: 1 5.00/2.24 5.00/2.24 3: lbl52 -> stop : [ 0>=D && B>=0 && D>=1 && A>=D && F==A ], cost: 1 5.00/2.24 5.00/2.24 4: lbl52 -> lbl52 : B'=-1+B, [ D>=1 && B>=1 && B>=0 && A>=D && F==A ], cost: 1 5.00/2.24 5.00/2.24 5: lbl52 -> lbl72 : B'=F, D'=-1+D, [ D>=1 && A>=D && B==0 && F==A ], cost: 1 5.00/2.24 5.00/2.24 6: lbl72 -> stop : [ A>=1 && D==0 && F==A && B==A ], cost: 1 5.00/2.24 5.00/2.24 7: lbl72 -> lbl52 : B'=-1+B, [ D>=1 && A>=1 && D>=0 && A>=1+D && F==A && B==A ], cost: 1 5.00/2.24 5.00/2.24 8: lbl72 -> lbl72 : B'=F, D'=-1+D, [ D>=1 && 0>=A && D>=0 && A>=1+D && F==A && B==A ], cost: 1 5.00/2.24 5.00/2.24 9: start0 -> start : B'=C, D'=E, F'=A, [], cost: 1 5.00/2.24 5.00/2.24 5.00/2.24 5.00/2.24 Removed unreachable and leaf rules: 5.00/2.24 5.00/2.24 Start location: start0 5.00/2.24 5.00/2.24 1: start -> lbl52 : B'=-1+B, D'=F, [ A>=1 && C>=1 && B==C && D==E && F==A ], cost: 1 5.00/2.24 5.00/2.24 2: start -> lbl72 : B'=F, D'=-1+F, [ A>=1 && 0>=C && B==C && D==E && F==A ], cost: 1 5.00/2.24 5.00/2.24 4: lbl52 -> lbl52 : B'=-1+B, [ D>=1 && B>=1 && B>=0 && A>=D && F==A ], cost: 1 5.00/2.24 5.00/2.24 5: lbl52 -> lbl72 : B'=F, D'=-1+D, [ D>=1 && A>=D && B==0 && F==A ], cost: 1 5.00/2.24 5.00/2.24 7: lbl72 -> lbl52 : B'=-1+B, [ D>=1 && A>=1 && D>=0 && A>=1+D && F==A && B==A ], cost: 1 5.00/2.24 5.00/2.24 8: lbl72 -> lbl72 : B'=F, D'=-1+D, [ D>=1 && 0>=A && D>=0 && A>=1+D && F==A && B==A ], cost: 1 5.00/2.24 5.00/2.24 9: start0 -> start : B'=C, D'=E, F'=A, [], cost: 1 5.00/2.24 5.00/2.24 5.00/2.24 5.00/2.24 Removed rules with unsatisfiable guard: 5.00/2.24 5.00/2.24 Start location: start0 5.00/2.24 5.00/2.24 1: start -> lbl52 : B'=-1+B, D'=F, [ A>=1 && C>=1 && B==C && D==E && F==A ], cost: 1 5.00/2.24 5.00/2.24 2: start -> lbl72 : B'=F, D'=-1+F, [ A>=1 && 0>=C && B==C && D==E && F==A ], cost: 1 5.00/2.24 5.00/2.24 4: lbl52 -> lbl52 : B'=-1+B, [ D>=1 && B>=1 && B>=0 && A>=D && F==A ], cost: 1 5.00/2.24 5.00/2.24 5: lbl52 -> lbl72 : B'=F, D'=-1+D, [ D>=1 && A>=D && B==0 && F==A ], cost: 1 5.00/2.24 5.00/2.24 7: lbl72 -> lbl52 : B'=-1+B, [ D>=1 && A>=1 && D>=0 && A>=1+D && F==A && B==A ], cost: 1 5.00/2.24 5.00/2.24 9: start0 -> start : B'=C, D'=E, F'=A, [], cost: 1 5.00/2.24 5.00/2.24 5.00/2.24 5.00/2.24 Simplified all rules, resulting in: 5.00/2.24 5.00/2.24 Start location: start0 5.00/2.24 5.00/2.24 1: start -> lbl52 : B'=-1+B, D'=F, [ A>=1 && C>=1 && B==C && D==E && F==A ], cost: 1 5.00/2.24 5.00/2.24 2: start -> lbl72 : B'=F, D'=-1+F, [ A>=1 && 0>=C && B==C && D==E && F==A ], cost: 1 5.00/2.24 5.00/2.24 4: lbl52 -> lbl52 : B'=-1+B, [ D>=1 && B>=1 && A>=D && F==A ], cost: 1 5.00/2.24 5.00/2.24 5: lbl52 -> lbl72 : B'=F, D'=-1+D, [ D>=1 && A>=D && B==0 && F==A ], cost: 1 5.19/2.24 5.19/2.24 7: lbl72 -> lbl52 : B'=-1+B, [ D>=1 && A>=1 && A>=1+D && F==A && B==A ], cost: 1 5.19/2.24 5.19/2.24 9: start0 -> start : B'=C, D'=E, F'=A, [], cost: 1 5.19/2.24 5.19/2.24 5.19/2.24 5.19/2.24 ### Simplification by acceleration and chaining ### 5.19/2.24 5.19/2.24 5.19/2.24 5.19/2.24 Accelerating simple loops of location 1. 5.19/2.24 5.19/2.24 Accelerating the following rules: 5.19/2.24 5.19/2.24 4: lbl52 -> lbl52 : B'=-1+B, [ D>=1 && B>=1 && A>=D && F==A ], cost: 1 5.19/2.24 5.19/2.24 5.19/2.24 5.19/2.24 Accelerated rule 4 with metering function B, yielding the new rule 10. 5.19/2.24 5.19/2.24 Removing the simple loops: 4. 5.19/2.24 5.19/2.24 5.19/2.24 5.19/2.24 Accelerated all simple loops using metering functions (where possible): 5.19/2.24 5.19/2.24 Start location: start0 5.19/2.24 5.19/2.24 1: start -> lbl52 : B'=-1+B, D'=F, [ A>=1 && C>=1 && B==C && D==E && F==A ], cost: 1 5.19/2.24 5.19/2.24 2: start -> lbl72 : B'=F, D'=-1+F, [ A>=1 && 0>=C && B==C && D==E && F==A ], cost: 1 5.19/2.24 5.19/2.24 5: lbl52 -> lbl72 : B'=F, D'=-1+D, [ D>=1 && A>=D && B==0 && F==A ], cost: 1 5.19/2.24 5.19/2.24 10: lbl52 -> lbl52 : B'=0, [ D>=1 && B>=1 && A>=D && F==A ], cost: B 5.19/2.24 5.19/2.24 7: lbl72 -> lbl52 : B'=-1+B, [ D>=1 && A>=1 && A>=1+D && F==A && B==A ], cost: 1 5.19/2.24 5.19/2.24 9: start0 -> start : B'=C, D'=E, F'=A, [], cost: 1 5.19/2.24 5.19/2.24 5.19/2.24 5.19/2.24 Chained accelerated rules (with incoming rules): 5.19/2.24 5.19/2.24 Start location: start0 5.19/2.24 5.19/2.24 1: start -> lbl52 : B'=-1+B, D'=F, [ A>=1 && C>=1 && B==C && D==E && F==A ], cost: 1 5.19/2.24 5.19/2.24 2: start -> lbl72 : B'=F, D'=-1+F, [ A>=1 && 0>=C && B==C && D==E && F==A ], cost: 1 5.19/2.24 5.19/2.24 11: start -> lbl52 : B'=0, D'=F, [ A>=1 && C>=1 && B==C && D==E && F==A && F>=1 && -1+B>=1 ], cost: B 5.19/2.24 5.19/2.24 5: lbl52 -> lbl72 : B'=F, D'=-1+D, [ D>=1 && A>=D && B==0 && F==A ], cost: 1 5.19/2.24 5.19/2.24 7: lbl72 -> lbl52 : B'=-1+B, [ D>=1 && A>=1 && A>=1+D && F==A && B==A ], cost: 1 5.19/2.24 5.19/2.24 12: lbl72 -> lbl52 : B'=0, [ D>=1 && A>=1 && A>=1+D && F==A && B==A && -1+B>=1 ], cost: B 5.19/2.24 5.19/2.24 9: start0 -> start : B'=C, D'=E, F'=A, [], cost: 1 5.19/2.24 5.19/2.24 5.19/2.24 5.19/2.24 Eliminated locations (on tree-shaped paths): 5.19/2.24 5.19/2.24 Start location: start0 5.19/2.24 5.19/2.24 5: lbl52 -> lbl72 : B'=F, D'=-1+D, [ D>=1 && A>=D && B==0 && F==A ], cost: 1 5.19/2.24 5.19/2.24 7: lbl72 -> lbl52 : B'=-1+B, [ D>=1 && A>=1 && A>=1+D && F==A && B==A ], cost: 1 5.19/2.24 5.19/2.24 12: lbl72 -> lbl52 : B'=0, [ D>=1 && A>=1 && A>=1+D && F==A && B==A && -1+B>=1 ], cost: B 5.19/2.24 5.19/2.24 13: start0 -> lbl52 : B'=-1+C, D'=A, F'=A, [ A>=1 && C>=1 ], cost: 2 5.19/2.24 5.19/2.24 14: start0 -> lbl72 : B'=A, D'=-1+A, F'=A, [ A>=1 && 0>=C ], cost: 2 5.19/2.24 5.19/2.24 15: start0 -> lbl52 : B'=0, D'=A, F'=A, [ A>=1 && -1+C>=1 ], cost: 1+C 5.19/2.24 5.19/2.24 5.19/2.24 5.19/2.24 Eliminated location lbl52 (as a last resort): 5.19/2.24 5.19/2.24 Start location: start0 5.19/2.24 5.19/2.24 16: lbl72 -> lbl72 : B'=F, D'=-1+D, [ D>=1 && A>=1 && A>=1+D && F==A && B==A && -1+B>=1 ], cost: 1+B 5.19/2.24 5.19/2.24 14: start0 -> lbl72 : B'=A, D'=-1+A, F'=A, [ A>=1 && 0>=C ], cost: 2 5.19/2.24 5.19/2.24 17: start0 -> lbl72 : B'=A, D'=-1+A, F'=A, [ A>=1 && -1+C==0 ], cost: 3 5.19/2.24 5.19/2.24 18: start0 -> lbl72 : B'=A, D'=-1+A, F'=A, [ A>=1 && -1+C>=1 ], cost: 2+C 5.19/2.24 5.19/2.24 5.19/2.24 5.19/2.24 Accelerating simple loops of location 2. 5.19/2.24 5.19/2.24 Accelerating the following rules: 5.19/2.24 5.19/2.24 16: lbl72 -> lbl72 : B'=F, D'=-1+D, [ D>=1 && A>=1 && A>=1+D && F==A && B==A && -1+B>=1 ], cost: 1+B 5.19/2.24 5.19/2.24 5.19/2.24 5.19/2.24 Accelerated rule 16 with metering function D, yielding the new rule 19. 5.19/2.25 5.19/2.25 Removing the simple loops: 16. 5.19/2.25 5.19/2.25 5.19/2.25 5.19/2.25 Accelerated all simple loops using metering functions (where possible): 5.19/2.25 5.19/2.25 Start location: start0 5.19/2.25 5.19/2.25 19: lbl72 -> lbl72 : B'=F, D'=0, [ D>=1 && A>=1 && A>=1+D && F==A && B==A && -1+B>=1 ], cost: F*D+D 5.19/2.25 5.19/2.25 14: start0 -> lbl72 : B'=A, D'=-1+A, F'=A, [ A>=1 && 0>=C ], cost: 2 5.19/2.25 5.19/2.25 17: start0 -> lbl72 : B'=A, D'=-1+A, F'=A, [ A>=1 && -1+C==0 ], cost: 3 5.19/2.25 5.19/2.25 18: start0 -> lbl72 : B'=A, D'=-1+A, F'=A, [ A>=1 && -1+C>=1 ], cost: 2+C 5.19/2.25 5.19/2.25 5.19/2.25 5.19/2.25 Chained accelerated rules (with incoming rules): 5.19/2.25 5.19/2.25 Start location: start0 5.19/2.25 5.19/2.25 14: start0 -> lbl72 : B'=A, D'=-1+A, F'=A, [ A>=1 && 0>=C ], cost: 2 5.19/2.25 5.19/2.25 17: start0 -> lbl72 : B'=A, D'=-1+A, F'=A, [ A>=1 && -1+C==0 ], cost: 3 5.19/2.25 5.19/2.25 18: start0 -> lbl72 : B'=A, D'=-1+A, F'=A, [ A>=1 && -1+C>=1 ], cost: 2+C 5.19/2.25 5.19/2.25 20: start0 -> lbl72 : B'=A, D'=0, F'=A, [ 0>=C && -1+A>=1 ], cost: 1+(-1+A)*A+A 5.19/2.25 5.19/2.25 21: start0 -> lbl72 : B'=A, D'=0, F'=A, [ -1+C==0 && -1+A>=1 ], cost: 2+(-1+A)*A+A 5.19/2.25 5.19/2.25 22: start0 -> lbl72 : B'=A, D'=0, F'=A, [ -1+C>=1 && -1+A>=1 ], cost: 1+(-1+A)*A+C+A 5.19/2.25 5.19/2.25 5.19/2.25 5.19/2.25 Removed unreachable locations (and leaf rules with constant cost): 5.19/2.25 5.19/2.25 Start location: start0 5.19/2.25 5.19/2.25 18: start0 -> lbl72 : B'=A, D'=-1+A, F'=A, [ A>=1 && -1+C>=1 ], cost: 2+C 5.19/2.25 5.19/2.25 20: start0 -> lbl72 : B'=A, D'=0, F'=A, [ 0>=C && -1+A>=1 ], cost: 1+(-1+A)*A+A 5.19/2.25 5.19/2.25 21: start0 -> lbl72 : B'=A, D'=0, F'=A, [ -1+C==0 && -1+A>=1 ], cost: 2+(-1+A)*A+A 5.19/2.25 5.19/2.25 22: start0 -> lbl72 : B'=A, D'=0, F'=A, [ -1+C>=1 && -1+A>=1 ], cost: 1+(-1+A)*A+C+A 5.19/2.25 5.19/2.25 5.19/2.25 5.19/2.25 ### Computing asymptotic complexity ### 5.19/2.25 5.19/2.25 5.19/2.25 5.19/2.25 Fully simplified ITS problem 5.19/2.25 5.19/2.25 Start location: start0 5.19/2.25 5.19/2.25 18: start0 -> lbl72 : B'=A, D'=-1+A, F'=A, [ A>=1 && -1+C>=1 ], cost: 2+C 5.19/2.25 5.19/2.25 20: start0 -> lbl72 : B'=A, D'=0, F'=A, [ 0>=C && -1+A>=1 ], cost: 1+(-1+A)*A+A 5.19/2.25 5.19/2.25 21: start0 -> lbl72 : B'=A, D'=0, F'=A, [ -1+C==0 && -1+A>=1 ], cost: 2+(-1+A)*A+A 5.19/2.25 5.19/2.25 22: start0 -> lbl72 : B'=A, D'=0, F'=A, [ -1+C>=1 && -1+A>=1 ], cost: 1+(-1+A)*A+C+A 5.19/2.25 5.19/2.25 5.19/2.25 5.19/2.25 Computing asymptotic complexity for rule 18 5.19/2.25 5.19/2.25 Solved the limit problem by the following transformations: 5.19/2.25 5.19/2.25 Created initial limit problem: 5.19/2.25 5.19/2.25 2+C (+), A (+/+!), -1+C (+/+!) [not solved] 5.19/2.25 5.19/2.25 5.19/2.25 5.19/2.25 applying transformation rule (C) using substitution {A==1} 5.19/2.25 5.19/2.25 resulting limit problem: 5.19/2.25 5.19/2.25 1 (+/+!), 2+C (+), -1+C (+/+!) [not solved] 5.19/2.25 5.19/2.25 5.19/2.25 5.19/2.25 applying transformation rule (B), deleting 1 (+/+!) 5.19/2.25 5.19/2.25 resulting limit problem: 5.19/2.25 5.19/2.25 2+C (+), -1+C (+/+!) [not solved] 5.19/2.25 5.19/2.25 5.19/2.25 5.19/2.25 removing all constraints (solved by SMT) 5.19/2.25 5.19/2.25 resulting limit problem: [solved] 5.19/2.25 5.19/2.25 5.19/2.25 5.19/2.25 applying transformation rule (C) using substitution {C==n} 5.19/2.25 5.19/2.25 resulting limit problem: 5.19/2.25 5.19/2.25 [solved] 5.19/2.25 5.19/2.25 5.19/2.25 5.19/2.25 Solution: 5.19/2.25 5.19/2.25 C / n 5.19/2.25 5.19/2.25 A / 1 5.19/2.25 5.19/2.25 Resulting cost 2+n has complexity: Poly(n^1) 5.19/2.25 5.19/2.25 5.19/2.25 5.19/2.25 Found new complexity Poly(n^1). 5.19/2.25 5.19/2.25 5.19/2.25 5.19/2.25 Computing asymptotic complexity for rule 20 5.19/2.25 5.19/2.25 Solved the limit problem by the following transformations: 5.19/2.25 5.19/2.25 Created initial limit problem: 5.19/2.25 5.19/2.25 1+A^2 (+), -1+A (+/+!), 1-C (+/+!) [not solved] 5.19/2.25 5.19/2.25 5.19/2.25 5.19/2.25 applying transformation rule (C) using substitution {C==0} 5.19/2.25 5.19/2.25 resulting limit problem: 5.19/2.25 5.19/2.25 1+A^2 (+), 1 (+/+!), -1+A (+/+!) [not solved] 5.19/2.25 5.19/2.25 5.19/2.25 5.19/2.25 applying transformation rule (B), deleting 1 (+/+!) 5.19/2.25 5.19/2.25 resulting limit problem: 5.19/2.25 5.19/2.25 1+A^2 (+), -1+A (+/+!) [not solved] 5.19/2.25 5.19/2.25 5.19/2.25 5.19/2.25 removing all constraints (solved by SMT) 5.19/2.25 5.19/2.25 resulting limit problem: [solved] 5.19/2.25 5.19/2.25 5.19/2.25 5.19/2.25 applying transformation rule (C) using substitution {A==n} 5.19/2.25 5.19/2.25 resulting limit problem: 5.19/2.25 5.19/2.25 [solved] 5.19/2.25 5.19/2.25 5.19/2.25 5.19/2.25 Solution: 5.19/2.25 5.19/2.25 C / 0 5.19/2.25 5.19/2.25 A / n 5.19/2.25 5.19/2.25 Resulting cost 1+n^2 has complexity: Poly(n^2) 5.19/2.25 5.19/2.25 5.19/2.25 5.19/2.25 Found new complexity Poly(n^2). 5.19/2.25 5.19/2.25 5.19/2.25 5.19/2.25 Obtained the following overall complexity (w.r.t. the length of the input n): 5.19/2.25 5.19/2.25 Complexity: Poly(n^2) 5.19/2.25 5.19/2.25 Cpx degree: 2 5.19/2.25 5.19/2.25 Solved cost: 1+n^2 5.19/2.25 5.19/2.25 Rule cost: 1+(-1+A)*A+A 5.19/2.25 5.19/2.25 Rule guard: [ 0>=C && -1+A>=1 ] 5.19/2.25 5.19/2.25 5.19/2.25 5.19/2.25 WORST_CASE(Omega(n^2),?) 5.19/2.25 5.19/2.25 5.19/2.25 ---------------------------------------- 5.19/2.25 5.19/2.25 (4) 5.19/2.25 BOUNDS(n^2, INF) 5.19/2.27 EOF