7.11/3.16 WORST_CASE(Omega(n^1), O(n^1)) 7.11/3.17 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 7.11/3.17 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 7.11/3.17 7.11/3.17 7.11/3.17 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, n^1). 7.11/3.17 7.11/3.17 (0) CpxIntTrs 7.11/3.17 (1) Koat Proof [FINISHED, 823 ms] 7.11/3.17 (2) BOUNDS(1, n^1) 7.11/3.17 (3) Loat Proof [FINISHED, 1410 ms] 7.11/3.17 (4) BOUNDS(n^1, INF) 7.11/3.17 7.11/3.17 7.11/3.17 ---------------------------------------- 7.11/3.17 7.11/3.17 (0) 7.11/3.17 Obligation: 7.11/3.17 Complexity Int TRS consisting of the following rules: 7.11/3.17 evalfstart(A, B, C, D, E, F) -> Com_1(evalfentryin(A, B, C, D, E, F)) :|: TRUE 7.11/3.17 evalfentryin(A, B, C, D, E, F) -> Com_1(evalfbb9in(B, B, C, D, E, F)) :|: TRUE 7.11/3.17 evalfbb9in(A, B, C, D, E, F) -> Com_1(evalfbbin(A, B, C, D, E, F)) :|: B >= 2 7.11/3.17 evalfbb9in(A, B, C, D, E, F) -> Com_1(evalfreturnin(A, B, C, D, E, F)) :|: 1 >= B 7.11/3.17 evalfbbin(A, B, C, D, E, F) -> Com_1(evalfbb6in(A, B, B - 1, A + B - 1, E, F)) :|: TRUE 7.11/3.17 evalfbb6in(A, B, C, D, E, F) -> Com_1(evalfbb8in(A, B, C, D, E, F)) :|: C >= D 7.11/3.17 evalfbb6in(A, B, C, D, E, F) -> Com_1(evalfbb7in(A, B, C, D, E, F)) :|: D >= C + 1 7.11/3.17 evalfbb7in(A, B, C, D, E, F) -> Com_1(evalfbb1in(A, B, C, D, E, F)) :|: 0 >= G + 1 7.11/3.17 evalfbb7in(A, B, C, D, E, F) -> Com_1(evalfbb1in(A, B, C, D, E, F)) :|: G >= 1 7.11/3.17 evalfbb7in(A, B, C, D, E, F) -> Com_1(evalfbb8in(A, B, C, D, E, F)) :|: TRUE 7.11/3.17 evalfbb1in(A, B, C, D, E, F) -> Com_1(evalfbb3in(A, B, C, D, C, D - 1)) :|: TRUE 7.11/3.17 evalfbb3in(A, B, C, D, E, F) -> Com_1(evalfbb5in(A, B, C, D, E, F)) :|: TRUE 7.11/3.17 evalfbb3in(A, B, C, D, E, F) -> Com_1(evalfbb4in(A, B, C, D, E, F)) :|: 0 >= 3 7.11/3.17 evalfbb4in(A, B, C, D, E, F) -> Com_1(evalfbb2in(A, B, C, D, E, F)) :|: 0 >= G + 1 7.11/3.17 evalfbb4in(A, B, C, D, E, F) -> Com_1(evalfbb2in(A, B, C, D, E, F)) :|: G >= 1 7.11/3.17 evalfbb4in(A, B, C, D, E, F) -> Com_1(evalfbb5in(A, B, C, D, E, F)) :|: TRUE 7.11/3.17 evalfbb2in(A, B, C, D, E, F) -> Com_1(evalfbb3in(A, B, C, D, E + 1, F - 2)) :|: TRUE 7.11/3.17 evalfbb5in(A, B, C, D, E, F) -> Com_1(evalfbb6in(A, B, E, F - 1, E, F)) :|: TRUE 7.11/3.17 evalfbb8in(A, B, C, D, E, F) -> Com_1(evalfbb9in(D - C + 1, C - 1, C, D, E, F)) :|: TRUE 7.11/3.17 evalfreturnin(A, B, C, D, E, F) -> Com_1(evalfstop(A, B, C, D, E, F)) :|: TRUE 7.11/3.17 7.11/3.17 The start-symbols are:[evalfstart_6] 7.11/3.17 7.11/3.17 7.11/3.17 ---------------------------------------- 7.11/3.17 7.11/3.17 (1) Koat Proof (FINISHED) 7.11/3.17 YES(?, 110*ar_1 + 14) 7.11/3.17 7.11/3.17 7.11/3.17 7.11/3.17 Initial complexity problem: 7.11/3.17 7.11/3.17 1: T: 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_1, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_1 >= 2 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 1 >= ar_1 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_1 - 1, ar_0 + ar_1 - 1, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_2 >= ar_3 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= ar_2 + 1 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 >= g + 1 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ g >= 1 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_2, ar_3 - 1)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb4in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 >= 3 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb4in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb2in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 >= g + 1 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb4in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb2in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ g >= 1 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb4in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb2in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_4 + 1, ar_5 - 2)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_4, ar_5 - 1, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_3 - ar_2 + 1, ar_2 - 1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ] 7.11/3.17 7.11/3.17 start location: koat_start 7.11/3.17 7.11/3.17 leaf cost: 0 7.11/3.17 7.11/3.17 7.11/3.17 7.11/3.17 Testing for reachability in the complexity graph removes the following transitions from problem 1: 7.11/3.17 7.11/3.17 evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb4in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 >= 3 ] 7.11/3.17 7.11/3.17 evalfbb4in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb2in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 >= g + 1 ] 7.11/3.17 7.11/3.17 evalfbb4in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb2in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ g >= 1 ] 7.11/3.17 7.11/3.17 evalfbb4in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 evalfbb2in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_4 + 1, ar_5 - 2)) 7.11/3.17 7.11/3.17 We thus obtain the following problem: 7.11/3.17 7.11/3.17 2: T: 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_4, ar_5 - 1, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_2, ar_3 - 1)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ g >= 1 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 >= g + 1 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_3 - ar_2 + 1, ar_2 - 1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= ar_2 + 1 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_2 >= ar_3 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_1 - 1, ar_0 + ar_1 - 1, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 1 >= ar_1 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_1 >= 2 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_1, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ] 7.11/3.17 7.11/3.17 start location: koat_start 7.11/3.17 7.11/3.17 leaf cost: 0 7.11/3.17 7.11/3.17 7.11/3.17 7.11/3.17 Repeatedly propagating knowledge in problem 2 produces the following problem: 7.11/3.17 7.11/3.17 3: T: 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_4, ar_5 - 1, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_2, ar_3 - 1)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ g >= 1 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 >= g + 1 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_3 - ar_2 + 1, ar_2 - 1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= ar_2 + 1 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_2 >= ar_3 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_1 - 1, ar_0 + ar_1 - 1, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 1 >= ar_1 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_1 >= 2 ] 7.11/3.17 7.11/3.17 (Comp: 1, Cost: 1) evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_1, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: 1, Cost: 1) evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ] 7.11/3.17 7.11/3.17 start location: koat_start 7.11/3.17 7.11/3.17 leaf cost: 0 7.11/3.17 7.11/3.17 7.11/3.17 7.11/3.17 A polynomial rank function with 7.11/3.17 7.11/3.17 Pol(evalfbb5in) = 2 7.11/3.17 7.11/3.17 Pol(evalfbb6in) = 2 7.11/3.17 7.11/3.17 Pol(evalfbb3in) = 2 7.11/3.17 7.11/3.17 Pol(evalfbb1in) = 2 7.11/3.17 7.11/3.17 Pol(evalfbb7in) = 2 7.11/3.17 7.11/3.17 Pol(evalfbb8in) = 2 7.11/3.17 7.11/3.17 Pol(evalfbb9in) = 2 7.11/3.17 7.11/3.17 Pol(evalfreturnin) = 1 7.11/3.17 7.11/3.17 Pol(evalfstop) = 0 7.11/3.17 7.11/3.17 Pol(evalfbbin) = 2 7.11/3.17 7.11/3.17 Pol(evalfentryin) = 2 7.11/3.17 7.11/3.17 Pol(evalfstart) = 2 7.11/3.17 7.11/3.17 Pol(koat_start) = 2 7.11/3.17 7.11/3.17 orients all transitions weakly and the transitions 7.11/3.17 7.11/3.17 evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 1 >= ar_1 ] 7.11/3.17 7.11/3.17 strictly and produces the following problem: 7.11/3.17 7.11/3.17 4: T: 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_4, ar_5 - 1, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_2, ar_3 - 1)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ g >= 1 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 >= g + 1 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_3 - ar_2 + 1, ar_2 - 1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= ar_2 + 1 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_2 >= ar_3 ] 7.11/3.17 7.11/3.17 (Comp: 2, Cost: 1) evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_1 - 1, ar_0 + ar_1 - 1, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: 2, Cost: 1) evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 1 >= ar_1 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_1 >= 2 ] 7.11/3.17 7.11/3.17 (Comp: 1, Cost: 1) evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_1, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: 1, Cost: 1) evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ] 7.11/3.17 7.11/3.17 start location: koat_start 7.11/3.17 7.11/3.17 leaf cost: 0 7.11/3.17 7.11/3.17 7.11/3.17 7.11/3.17 A polynomial rank function with 7.11/3.17 7.11/3.17 Pol(evalfbb5in) = V_5 7.11/3.17 7.11/3.17 Pol(evalfbb6in) = V_3 7.11/3.17 7.11/3.17 Pol(evalfbb3in) = V_5 7.11/3.17 7.11/3.17 Pol(evalfbb1in) = V_3 7.11/3.17 7.11/3.17 Pol(evalfbb7in) = V_3 7.11/3.17 7.11/3.17 Pol(evalfbb8in) = V_3 7.11/3.17 7.11/3.17 Pol(evalfbb9in) = V_2 + 1 7.11/3.17 7.11/3.17 Pol(evalfreturnin) = V_2 + 1 7.11/3.17 7.11/3.17 Pol(evalfstop) = V_2 + 1 7.11/3.17 7.11/3.17 Pol(evalfbbin) = V_2 - 1 7.11/3.17 7.11/3.17 Pol(evalfentryin) = V_2 + 1 7.11/3.17 7.11/3.17 Pol(evalfstart) = V_2 + 1 7.11/3.17 7.11/3.17 Pol(koat_start) = V_2 + 1 7.11/3.17 7.11/3.17 orients all transitions weakly and the transition 7.11/3.17 7.11/3.17 evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_1 >= 2 ] 7.11/3.17 7.11/3.17 strictly and produces the following problem: 7.11/3.17 7.11/3.17 5: T: 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_4, ar_5 - 1, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_2, ar_3 - 1)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ g >= 1 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 >= g + 1 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_3 - ar_2 + 1, ar_2 - 1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= ar_2 + 1 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_2 >= ar_3 ] 7.11/3.17 7.11/3.17 (Comp: 2, Cost: 1) evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_1 - 1, ar_0 + ar_1 - 1, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: 2, Cost: 1) evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 1 >= ar_1 ] 7.11/3.17 7.11/3.17 (Comp: ar_1 + 1, Cost: 1) evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_1 >= 2 ] 7.11/3.17 7.11/3.17 (Comp: 1, Cost: 1) evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_1, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: 1, Cost: 1) evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ] 7.11/3.17 7.11/3.17 start location: koat_start 7.11/3.17 7.11/3.17 leaf cost: 0 7.11/3.17 7.11/3.17 7.11/3.17 7.11/3.17 Repeatedly propagating knowledge in problem 5 produces the following problem: 7.11/3.17 7.11/3.17 6: T: 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_4, ar_5 - 1, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_2, ar_3 - 1)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ g >= 1 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 >= g + 1 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_3 - ar_2 + 1, ar_2 - 1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= ar_2 + 1 ] 7.11/3.17 7.11/3.17 (Comp: ?, Cost: 1) evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_2 >= ar_3 ] 7.11/3.17 7.11/3.17 (Comp: 2, Cost: 1) evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: ar_1 + 1, Cost: 1) evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_1 - 1, ar_0 + ar_1 - 1, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: 2, Cost: 1) evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 1 >= ar_1 ] 7.11/3.17 7.11/3.17 (Comp: ar_1 + 1, Cost: 1) evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_1 >= 2 ] 7.11/3.17 7.11/3.17 (Comp: 1, Cost: 1) evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_1, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: 1, Cost: 1) evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.17 7.11/3.17 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ] 7.11/3.17 7.11/3.17 start location: koat_start 7.11/3.17 7.11/3.17 leaf cost: 0 7.11/3.17 7.11/3.17 7.11/3.17 7.11/3.17 A polynomial rank function with 7.11/3.17 7.11/3.17 Pol(evalfbb8in) = 1 7.11/3.17 7.11/3.17 Pol(evalfbb9in) = 0 7.11/3.17 7.11/3.17 Pol(evalfbb7in) = 2 7.11/3.17 7.11/3.17 Pol(evalfbb1in) = 2 7.11/3.17 7.11/3.17 Pol(evalfbb6in) = 2 7.11/3.17 7.11/3.17 Pol(evalfbb5in) = 2 7.11/3.17 7.11/3.17 Pol(evalfbb3in) = 2 7.11/3.17 7.11/3.17 and size complexities 7.11/3.17 7.11/3.17 S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ]", 0-0) = ar_0 7.11/3.17 7.11/3.17 S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ]", 0-1) = ar_1 7.11/3.17 7.11/3.17 S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ]", 0-2) = ar_2 7.11/3.17 7.11/3.17 S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ]", 0-3) = ar_3 7.11/3.17 7.11/3.17 S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ]", 0-4) = ar_4 7.11/3.17 7.11/3.17 S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ]", 0-5) = ar_5 7.11/3.17 7.11/3.17 S("evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-0) = ar_0 7.11/3.17 7.11/3.17 S("evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-1) = ar_1 7.11/3.17 7.11/3.17 S("evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-2) = ar_2 7.11/3.17 7.11/3.17 S("evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-3) = ar_3 7.11/3.17 7.11/3.17 S("evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-4) = ar_4 7.11/3.18 7.11/3.18 S("evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-5) = ar_5 7.11/3.18 7.11/3.18 S("evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_1, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-0) = ar_1 7.11/3.18 7.11/3.18 S("evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_1, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-1) = ar_1 7.11/3.18 7.11/3.18 S("evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_1, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-2) = ar_2 7.11/3.18 7.11/3.18 S("evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_1, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-3) = ar_3 7.11/3.18 7.11/3.18 S("evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_1, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-4) = ar_4 7.11/3.18 7.11/3.18 S("evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_1, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-5) = ar_5 7.11/3.18 7.11/3.18 S("evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_1 >= 2 ]", 0-0) = ? 7.11/3.18 7.11/3.18 S("evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_1 >= 2 ]", 0-1) = ? 7.11/3.18 7.11/3.18 S("evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_1 >= 2 ]", 0-2) = ? 7.11/3.18 7.11/3.18 S("evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_1 >= 2 ]", 0-3) = ? 7.11/3.18 7.11/3.18 S("evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_1 >= 2 ]", 0-4) = ? 7.11/3.18 7.11/3.18 S("evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_1 >= 2 ]", 0-5) = ? 7.11/3.18 7.11/3.18 S("evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 1 >= ar_1 ]", 0-0) = ? 7.11/3.18 7.11/3.18 S("evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 1 >= ar_1 ]", 0-1) = ? 7.11/3.18 7.11/3.18 S("evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 1 >= ar_1 ]", 0-2) = ? 7.11/3.18 7.11/3.18 S("evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 1 >= ar_1 ]", 0-3) = ? 7.11/3.18 7.11/3.18 S("evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 1 >= ar_1 ]", 0-4) = ? 7.11/3.18 7.11/3.18 S("evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 1 >= ar_1 ]", 0-5) = ? 7.11/3.18 7.11/3.18 S("evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_1 - 1, ar_0 + ar_1 - 1, ar_4, ar_5))", 0-0) = ? 7.11/3.18 7.11/3.18 S("evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_1 - 1, ar_0 + ar_1 - 1, ar_4, ar_5))", 0-1) = ? 7.11/3.18 7.11/3.18 S("evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_1 - 1, ar_0 + ar_1 - 1, ar_4, ar_5))", 0-2) = ? 7.11/3.18 7.11/3.18 S("evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_1 - 1, ar_0 + ar_1 - 1, ar_4, ar_5))", 0-3) = ? 7.11/3.18 7.11/3.18 S("evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_1 - 1, ar_0 + ar_1 - 1, ar_4, ar_5))", 0-4) = ? 7.11/3.18 7.11/3.18 S("evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_1 - 1, ar_0 + ar_1 - 1, ar_4, ar_5))", 0-5) = ? 7.11/3.18 7.11/3.18 S("evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-0) = ? 7.11/3.18 7.11/3.18 S("evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-1) = ? 7.11/3.18 7.11/3.18 S("evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-2) = ? 7.11/3.18 7.11/3.18 S("evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-3) = ? 7.11/3.18 7.11/3.18 S("evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-4) = ? 7.11/3.18 7.11/3.18 S("evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-5) = ? 7.11/3.18 7.11/3.18 S("evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_2 >= ar_3 ]", 0-0) = ? 7.11/3.18 7.11/3.18 S("evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_2 >= ar_3 ]", 0-1) = ? 7.11/3.18 7.11/3.18 S("evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_2 >= ar_3 ]", 0-2) = ? 7.11/3.18 7.11/3.18 S("evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_2 >= ar_3 ]", 0-3) = ? 7.11/3.18 7.11/3.18 S("evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_2 >= ar_3 ]", 0-4) = ? 7.11/3.18 7.11/3.18 S("evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_2 >= ar_3 ]", 0-5) = ? 7.11/3.18 7.11/3.18 S("evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= ar_2 + 1 ]", 0-0) = ? 7.11/3.18 7.11/3.18 S("evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= ar_2 + 1 ]", 0-1) = ? 7.11/3.18 7.11/3.18 S("evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= ar_2 + 1 ]", 0-2) = ? 7.11/3.18 7.11/3.18 S("evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= ar_2 + 1 ]", 0-3) = ? 7.11/3.18 7.11/3.18 S("evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= ar_2 + 1 ]", 0-4) = ? 7.11/3.18 7.11/3.18 S("evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= ar_2 + 1 ]", 0-5) = ? 7.11/3.18 7.11/3.18 S("evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_3 - ar_2 + 1, ar_2 - 1, ar_2, ar_3, ar_4, ar_5))", 0-0) = ? 7.11/3.18 7.11/3.18 S("evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_3 - ar_2 + 1, ar_2 - 1, ar_2, ar_3, ar_4, ar_5))", 0-1) = ? 7.11/3.18 7.11/3.18 S("evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_3 - ar_2 + 1, ar_2 - 1, ar_2, ar_3, ar_4, ar_5))", 0-2) = ? 7.11/3.18 7.11/3.18 S("evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_3 - ar_2 + 1, ar_2 - 1, ar_2, ar_3, ar_4, ar_5))", 0-3) = ? 7.11/3.18 7.11/3.18 S("evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_3 - ar_2 + 1, ar_2 - 1, ar_2, ar_3, ar_4, ar_5))", 0-4) = ? 7.11/3.18 7.11/3.18 S("evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_3 - ar_2 + 1, ar_2 - 1, ar_2, ar_3, ar_4, ar_5))", 0-5) = ? 7.11/3.18 7.11/3.18 S("evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 >= g + 1 ]", 0-0) = ? 7.11/3.18 7.11/3.18 S("evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 >= g + 1 ]", 0-1) = ? 7.11/3.18 7.11/3.18 S("evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 >= g + 1 ]", 0-2) = ? 7.11/3.18 7.11/3.18 S("evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 >= g + 1 ]", 0-3) = ? 7.11/3.18 7.11/3.18 S("evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 >= g + 1 ]", 0-4) = ? 7.11/3.18 7.11/3.18 S("evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 >= g + 1 ]", 0-5) = ? 7.11/3.18 7.11/3.18 S("evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ g >= 1 ]", 0-0) = ? 7.11/3.18 7.11/3.18 S("evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ g >= 1 ]", 0-1) = ? 7.11/3.18 7.11/3.18 S("evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ g >= 1 ]", 0-2) = ? 7.11/3.18 7.11/3.18 S("evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ g >= 1 ]", 0-3) = ? 7.11/3.18 7.11/3.18 S("evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ g >= 1 ]", 0-4) = ? 7.11/3.18 7.11/3.18 S("evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ g >= 1 ]", 0-5) = ? 7.11/3.18 7.11/3.18 S("evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-0) = ? 7.11/3.18 7.11/3.18 S("evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-1) = ? 7.11/3.18 7.11/3.18 S("evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-2) = ? 7.11/3.18 7.11/3.18 S("evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-3) = ? 7.11/3.18 7.11/3.18 S("evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-4) = ? 7.11/3.18 7.11/3.18 S("evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-5) = ? 7.11/3.18 7.11/3.18 S("evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_2, ar_3 - 1))", 0-0) = ? 7.11/3.18 7.11/3.18 S("evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_2, ar_3 - 1))", 0-1) = ? 7.11/3.18 7.11/3.18 S("evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_2, ar_3 - 1))", 0-2) = ? 7.11/3.18 7.11/3.18 S("evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_2, ar_3 - 1))", 0-3) = ? 7.11/3.18 7.11/3.18 S("evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_2, ar_3 - 1))", 0-4) = ? 7.11/3.18 7.11/3.18 S("evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_2, ar_3 - 1))", 0-5) = ? 7.11/3.18 7.11/3.18 S("evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-0) = ? 7.11/3.18 7.11/3.18 S("evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-1) = ? 7.11/3.18 7.11/3.18 S("evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-2) = ? 7.11/3.18 7.11/3.18 S("evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-3) = ? 7.11/3.18 7.11/3.18 S("evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-4) = ? 7.11/3.18 7.11/3.18 S("evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5))", 0-5) = ? 7.11/3.18 7.11/3.18 S("evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_4, ar_5 - 1, ar_4, ar_5))", 0-0) = ? 7.11/3.18 7.11/3.18 S("evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_4, ar_5 - 1, ar_4, ar_5))", 0-1) = ? 7.11/3.18 7.11/3.18 S("evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_4, ar_5 - 1, ar_4, ar_5))", 0-2) = ? 7.11/3.18 7.11/3.18 S("evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_4, ar_5 - 1, ar_4, ar_5))", 0-3) = ? 7.11/3.18 7.11/3.18 S("evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_4, ar_5 - 1, ar_4, ar_5))", 0-4) = ? 7.11/3.18 7.11/3.18 S("evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_4, ar_5 - 1, ar_4, ar_5))", 0-5) = ? 7.11/3.18 7.11/3.18 orients the transitions 7.11/3.18 7.11/3.18 evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_3 - ar_2 + 1, ar_2 - 1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.18 7.11/3.18 evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.18 7.11/3.18 evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ g >= 1 ] 7.11/3.18 7.11/3.18 evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 >= g + 1 ] 7.11/3.18 7.11/3.18 evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_2 >= ar_3 ] 7.11/3.18 7.11/3.18 evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= ar_2 + 1 ] 7.11/3.18 7.11/3.18 evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_4, ar_5 - 1, ar_4, ar_5)) 7.11/3.18 7.11/3.18 evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.18 7.11/3.18 evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_2, ar_3 - 1)) 7.11/3.18 7.11/3.18 weakly and the transitions 7.11/3.18 7.11/3.18 evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_3 - ar_2 + 1, ar_2 - 1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.18 7.11/3.18 evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.18 7.11/3.18 evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_2 >= ar_3 ] 7.11/3.18 7.11/3.18 strictly and produces the following problem: 7.11/3.18 7.11/3.18 7: T: 7.11/3.18 7.11/3.18 (Comp: ?, Cost: 1) evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_4, ar_5 - 1, ar_4, ar_5)) 7.11/3.18 7.11/3.18 (Comp: ?, Cost: 1) evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.18 7.11/3.18 (Comp: ?, Cost: 1) evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_2, ar_3 - 1)) 7.11/3.18 7.11/3.18 (Comp: 2*ar_1 + 2, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.18 7.11/3.18 (Comp: ?, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ g >= 1 ] 7.11/3.18 7.11/3.18 (Comp: ?, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 >= g + 1 ] 7.11/3.18 7.11/3.18 (Comp: 2*ar_1 + 2, Cost: 1) evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_3 - ar_2 + 1, ar_2 - 1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.18 7.11/3.18 (Comp: ?, Cost: 1) evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 >= ar_2 + 1 ] 7.11/3.18 7.11/3.18 (Comp: 2*ar_1 + 2, Cost: 1) evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_2 >= ar_3 ] 7.11/3.18 7.11/3.18 (Comp: 2, Cost: 1) evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.18 7.11/3.18 (Comp: ar_1 + 1, Cost: 1) evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_1 - 1, ar_0 + ar_1 - 1, ar_4, ar_5)) 7.11/3.18 7.11/3.18 (Comp: 2, Cost: 1) evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 1 >= ar_1 ] 7.11/3.18 7.11/3.18 (Comp: ar_1 + 1, Cost: 1) evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_1 >= 2 ] 7.11/3.18 7.11/3.18 (Comp: 1, Cost: 1) evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_1, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.18 7.11/3.18 (Comp: 1, Cost: 1) evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.18 7.11/3.18 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ] 7.11/3.18 7.11/3.18 start location: koat_start 7.11/3.18 7.11/3.18 leaf cost: 0 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Applied AI with 'oct' on problem 7 to obtain the following invariants: 7.11/3.18 7.11/3.18 For symbol evalfbb1in: X_4 - 2 >= 0 /\ X_3 + X_4 - 3 >= 0 /\ -X_3 + X_4 - 1 >= 0 /\ X_2 + X_4 - 4 >= 0 /\ -X_2 + X_4 >= 0 /\ X_2 - X_3 - 1 >= 0 /\ X_3 - 1 >= 0 /\ X_2 + X_3 - 3 >= 0 /\ -X_2 + X_3 + 1 >= 0 /\ X_2 - 2 >= 0 7.11/3.18 7.11/3.18 For symbol evalfbb3in: X_4 - X_6 - 1 >= 0 /\ X_6 - 1 >= 0 /\ X_5 + X_6 - 2 >= 0 /\ -X_5 + X_6 >= 0 /\ X_4 + X_6 - 3 >= 0 /\ -X_4 + X_6 + 1 >= 0 /\ X_3 + X_6 - 2 >= 0 /\ -X_3 + X_6 >= 0 /\ X_2 + X_6 - 3 >= 0 /\ -X_2 + X_6 + 1 >= 0 /\ X_4 - X_5 - 1 >= 0 /\ X_3 - X_5 >= 0 /\ X_2 - X_5 - 1 >= 0 /\ X_5 - 1 >= 0 /\ X_4 + X_5 - 3 >= 0 /\ X_3 + X_5 - 2 >= 0 /\ -X_3 + X_5 >= 0 /\ X_2 + X_5 - 3 >= 0 /\ -X_2 + X_5 + 1 >= 0 /\ X_4 - 2 >= 0 /\ X_3 + X_4 - 3 >= 0 /\ -X_3 + X_4 - 1 >= 0 /\ X_2 + X_4 - 4 >= 0 /\ -X_2 + X_4 >= 0 /\ X_2 - X_3 - 1 >= 0 /\ X_3 - 1 >= 0 /\ X_2 + X_3 - 3 >= 0 /\ -X_2 + X_3 + 1 >= 0 /\ X_2 - 2 >= 0 7.11/3.18 7.11/3.18 For symbol evalfbb5in: X_4 - X_6 - 1 >= 0 /\ X_6 - 1 >= 0 /\ X_5 + X_6 - 2 >= 0 /\ -X_5 + X_6 >= 0 /\ X_4 + X_6 - 3 >= 0 /\ -X_4 + X_6 + 1 >= 0 /\ X_3 + X_6 - 2 >= 0 /\ -X_3 + X_6 >= 0 /\ X_2 + X_6 - 3 >= 0 /\ -X_2 + X_6 + 1 >= 0 /\ X_4 - X_5 - 1 >= 0 /\ X_3 - X_5 >= 0 /\ X_2 - X_5 - 1 >= 0 /\ X_5 - 1 >= 0 /\ X_4 + X_5 - 3 >= 0 /\ X_3 + X_5 - 2 >= 0 /\ -X_3 + X_5 >= 0 /\ X_2 + X_5 - 3 >= 0 /\ -X_2 + X_5 + 1 >= 0 /\ X_4 - 2 >= 0 /\ X_3 + X_4 - 3 >= 0 /\ -X_3 + X_4 - 1 >= 0 /\ X_2 + X_4 - 4 >= 0 /\ -X_2 + X_4 >= 0 /\ X_2 - X_3 - 1 >= 0 /\ X_3 - 1 >= 0 /\ X_2 + X_3 - 3 >= 0 /\ -X_2 + X_3 + 1 >= 0 /\ X_2 - 2 >= 0 7.11/3.18 7.11/3.18 For symbol evalfbb6in: X_2 - X_3 - 1 >= 0 /\ X_3 - 1 >= 0 /\ X_2 + X_3 - 3 >= 0 /\ -X_2 + X_3 + 1 >= 0 /\ X_2 - 2 >= 0 7.11/3.18 7.11/3.18 For symbol evalfbb7in: X_4 - 2 >= 0 /\ X_3 + X_4 - 3 >= 0 /\ -X_3 + X_4 - 1 >= 0 /\ X_2 + X_4 - 4 >= 0 /\ -X_2 + X_4 >= 0 /\ X_2 - X_3 - 1 >= 0 /\ X_3 - 1 >= 0 /\ X_2 + X_3 - 3 >= 0 /\ -X_2 + X_3 + 1 >= 0 /\ X_2 - 2 >= 0 7.11/3.18 7.11/3.18 For symbol evalfbb8in: X_2 - X_3 - 1 >= 0 /\ X_3 - 1 >= 0 /\ X_2 + X_3 - 3 >= 0 /\ -X_2 + X_3 + 1 >= 0 /\ X_2 - 2 >= 0 7.11/3.18 7.11/3.18 For symbol evalfbbin: X_2 - 2 >= 0 7.11/3.18 7.11/3.18 For symbol evalfreturnin: -X_2 + 1 >= 0 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 This yielded the following problem: 7.11/3.18 7.11/3.18 8: T: 7.11/3.18 7.11/3.18 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ] 7.11/3.18 7.11/3.18 (Comp: 1, Cost: 1) evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.18 7.11/3.18 (Comp: 1, Cost: 1) evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_1, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.18 7.11/3.18 (Comp: ar_1 + 1, Cost: 1) evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_1 >= 2 ] 7.11/3.18 7.11/3.18 (Comp: 2, Cost: 1) evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 1 >= ar_1 ] 7.11/3.18 7.11/3.18 (Comp: ar_1 + 1, Cost: 1) evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_1 - 1, ar_0 + ar_1 - 1, ar_4, ar_5)) [ ar_1 - 2 >= 0 ] 7.11/3.18 7.11/3.18 (Comp: 2, Cost: 1) evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ -ar_1 + 1 >= 0 ] 7.11/3.18 7.11/3.18 (Comp: 2*ar_1 + 2, Cost: 1) evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ -ar_1 + ar_2 + 1 >= 0 /\ ar_1 - 2 >= 0 /\ ar_2 >= ar_3 ] 7.11/3.18 7.11/3.18 (Comp: ?, Cost: 1) evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ -ar_1 + ar_2 + 1 >= 0 /\ ar_1 - 2 >= 0 /\ ar_3 >= ar_2 + 1 ] 7.11/3.18 7.11/3.18 (Comp: 2*ar_1 + 2, Cost: 1) evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_3 - ar_2 + 1, ar_2 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ -ar_1 + ar_2 + 1 >= 0 /\ ar_1 - 2 >= 0 ] 7.11/3.18 7.11/3.18 (Comp: ?, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 - 2 >= 0 /\ ar_2 + ar_3 - 3 >= 0 /\ -ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 4 >= 0 /\ -ar_1 + ar_3 >= 0 /\ ar_1 - ar_2 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ -ar_1 + ar_2 + 1 >= 0 /\ ar_1 - 2 >= 0 /\ 0 >= g + 1 ] 7.11/3.18 7.11/3.18 (Comp: ?, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 - 2 >= 0 /\ ar_2 + ar_3 - 3 >= 0 /\ -ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 4 >= 0 /\ -ar_1 + ar_3 >= 0 /\ ar_1 - ar_2 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ -ar_1 + ar_2 + 1 >= 0 /\ ar_1 - 2 >= 0 /\ g >= 1 ] 7.11/3.18 7.11/3.18 (Comp: 2*ar_1 + 2, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 - 2 >= 0 /\ ar_2 + ar_3 - 3 >= 0 /\ -ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 4 >= 0 /\ -ar_1 + ar_3 >= 0 /\ ar_1 - ar_2 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ -ar_1 + ar_2 + 1 >= 0 /\ ar_1 - 2 >= 0 ] 7.11/3.18 7.11/3.18 (Comp: ?, Cost: 1) evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_2, ar_3 - 1)) [ ar_3 - 2 >= 0 /\ ar_2 + ar_3 - 3 >= 0 /\ -ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 4 >= 0 /\ -ar_1 + ar_3 >= 0 /\ ar_1 - ar_2 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ -ar_1 + ar_2 + 1 >= 0 /\ ar_1 - 2 >= 0 ] 7.11/3.18 7.11/3.18 (Comp: ?, Cost: 1) evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 - ar_5 - 1 >= 0 /\ ar_5 - 1 >= 0 /\ ar_4 + ar_5 - 2 >= 0 /\ -ar_4 + ar_5 >= 0 /\ ar_3 + ar_5 - 3 >= 0 /\ -ar_3 + ar_5 + 1 >= 0 /\ ar_2 + ar_5 - 2 >= 0 /\ -ar_2 + ar_5 >= 0 /\ ar_1 + ar_5 - 3 >= 0 /\ -ar_1 + ar_5 + 1 >= 0 /\ ar_3 - ar_4 - 1 >= 0 /\ ar_2 - ar_4 >= 0 /\ ar_1 - ar_4 - 1 >= 0 /\ ar_4 - 1 >= 0 /\ ar_3 + ar_4 - 3 >= 0 /\ ar_2 + ar_4 - 2 >= 0 /\ -ar_2 + ar_4 >= 0 /\ ar_1 + ar_4 - 3 >= 0 /\ -ar_1 + ar_4 + 1 >= 0 /\ ar_3 - 2 >= 0 /\ ar_2 + ar_3 - 3 >= 0 /\ -ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 4 >= 0 /\ -ar_1 + ar_3 >= 0 /\ ar_1 - ar_2 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ -ar_1 + ar_2 + 1 >= 0 /\ ar_1 - 2 >= 0 ] 7.11/3.18 7.11/3.18 (Comp: ?, Cost: 1) evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_4, ar_5 - 1, ar_4, ar_5)) [ ar_3 - ar_5 - 1 >= 0 /\ ar_5 - 1 >= 0 /\ ar_4 + ar_5 - 2 >= 0 /\ -ar_4 + ar_5 >= 0 /\ ar_3 + ar_5 - 3 >= 0 /\ -ar_3 + ar_5 + 1 >= 0 /\ ar_2 + ar_5 - 2 >= 0 /\ -ar_2 + ar_5 >= 0 /\ ar_1 + ar_5 - 3 >= 0 /\ -ar_1 + ar_5 + 1 >= 0 /\ ar_3 - ar_4 - 1 >= 0 /\ ar_2 - ar_4 >= 0 /\ ar_1 - ar_4 - 1 >= 0 /\ ar_4 - 1 >= 0 /\ ar_3 + ar_4 - 3 >= 0 /\ ar_2 + ar_4 - 2 >= 0 /\ -ar_2 + ar_4 >= 0 /\ ar_1 + ar_4 - 3 >= 0 /\ -ar_1 + ar_4 + 1 >= 0 /\ ar_3 - 2 >= 0 /\ ar_2 + ar_3 - 3 >= 0 /\ -ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 4 >= 0 /\ -ar_1 + ar_3 >= 0 /\ ar_1 - ar_2 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ -ar_1 + ar_2 + 1 >= 0 /\ ar_1 - 2 >= 0 ] 7.11/3.18 7.11/3.18 start location: koat_start 7.11/3.18 7.11/3.18 leaf cost: 0 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 A polynomial rank function with 7.11/3.18 7.11/3.18 Pol(koat_start) = 17*V_2 7.11/3.18 7.11/3.18 Pol(evalfstart) = 17*V_2 7.11/3.18 7.11/3.18 Pol(evalfentryin) = 17*V_2 7.11/3.18 7.11/3.18 Pol(evalfbb9in) = 10*V_1 + 7*V_2 7.11/3.18 7.11/3.18 Pol(evalfbbin) = 10*V_1 + 7*V_2 7.11/3.18 7.11/3.18 Pol(evalfreturnin) = 10*V_1 + 7*V_2 7.11/3.18 7.11/3.18 Pol(evalfbb6in) = -3*V_3 + 10*V_4 + 7 7.11/3.18 7.11/3.18 Pol(evalfstop) = 10*V_1 + 7*V_2 7.11/3.18 7.11/3.18 Pol(evalfbb8in) = -3*V_3 + 10*V_4 + 3 7.11/3.18 7.11/3.18 Pol(evalfbb7in) = -3*V_3 + 10*V_4 + 3 7.11/3.18 7.11/3.18 Pol(evalfbb1in) = -3*V_3 + 10*V_4 - 1 7.11/3.18 7.11/3.18 Pol(evalfbb3in) = -3*V_5 + 10*V_6 + 5 7.11/3.18 7.11/3.18 Pol(evalfbb5in) = -3*V_5 + 10*V_6 + 1 7.11/3.18 7.11/3.18 orients all transitions weakly and the transitions 7.11/3.18 7.11/3.18 evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 - 2 >= 0 /\ ar_2 + ar_3 - 3 >= 0 /\ -ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 4 >= 0 /\ -ar_1 + ar_3 >= 0 /\ ar_1 - ar_2 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ -ar_1 + ar_2 + 1 >= 0 /\ ar_1 - 2 >= 0 /\ g >= 1 ] 7.11/3.18 7.11/3.18 evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 - 2 >= 0 /\ ar_2 + ar_3 - 3 >= 0 /\ -ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 4 >= 0 /\ -ar_1 + ar_3 >= 0 /\ ar_1 - ar_2 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ -ar_1 + ar_2 + 1 >= 0 /\ ar_1 - 2 >= 0 /\ 0 >= g + 1 ] 7.11/3.18 7.11/3.18 evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ -ar_1 + ar_2 + 1 >= 0 /\ ar_1 - 2 >= 0 /\ ar_3 >= ar_2 + 1 ] 7.11/3.18 7.11/3.18 evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_4, ar_5 - 1, ar_4, ar_5)) [ ar_3 - ar_5 - 1 >= 0 /\ ar_5 - 1 >= 0 /\ ar_4 + ar_5 - 2 >= 0 /\ -ar_4 + ar_5 >= 0 /\ ar_3 + ar_5 - 3 >= 0 /\ -ar_3 + ar_5 + 1 >= 0 /\ ar_2 + ar_5 - 2 >= 0 /\ -ar_2 + ar_5 >= 0 /\ ar_1 + ar_5 - 3 >= 0 /\ -ar_1 + ar_5 + 1 >= 0 /\ ar_3 - ar_4 - 1 >= 0 /\ ar_2 - ar_4 >= 0 /\ ar_1 - ar_4 - 1 >= 0 /\ ar_4 - 1 >= 0 /\ ar_3 + ar_4 - 3 >= 0 /\ ar_2 + ar_4 - 2 >= 0 /\ -ar_2 + ar_4 >= 0 /\ ar_1 + ar_4 - 3 >= 0 /\ -ar_1 + ar_4 + 1 >= 0 /\ ar_3 - 2 >= 0 /\ ar_2 + ar_3 - 3 >= 0 /\ -ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 4 >= 0 /\ -ar_1 + ar_3 >= 0 /\ ar_1 - ar_2 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ -ar_1 + ar_2 + 1 >= 0 /\ ar_1 - 2 >= 0 ] 7.11/3.18 7.11/3.18 evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 - ar_5 - 1 >= 0 /\ ar_5 - 1 >= 0 /\ ar_4 + ar_5 - 2 >= 0 /\ -ar_4 + ar_5 >= 0 /\ ar_3 + ar_5 - 3 >= 0 /\ -ar_3 + ar_5 + 1 >= 0 /\ ar_2 + ar_5 - 2 >= 0 /\ -ar_2 + ar_5 >= 0 /\ ar_1 + ar_5 - 3 >= 0 /\ -ar_1 + ar_5 + 1 >= 0 /\ ar_3 - ar_4 - 1 >= 0 /\ ar_2 - ar_4 >= 0 /\ ar_1 - ar_4 - 1 >= 0 /\ ar_4 - 1 >= 0 /\ ar_3 + ar_4 - 3 >= 0 /\ ar_2 + ar_4 - 2 >= 0 /\ -ar_2 + ar_4 >= 0 /\ ar_1 + ar_4 - 3 >= 0 /\ -ar_1 + ar_4 + 1 >= 0 /\ ar_3 - 2 >= 0 /\ ar_2 + ar_3 - 3 >= 0 /\ -ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 4 >= 0 /\ -ar_1 + ar_3 >= 0 /\ ar_1 - ar_2 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ -ar_1 + ar_2 + 1 >= 0 /\ ar_1 - 2 >= 0 ] 7.11/3.18 7.11/3.18 evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_2, ar_3 - 1)) [ ar_3 - 2 >= 0 /\ ar_2 + ar_3 - 3 >= 0 /\ -ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 4 >= 0 /\ -ar_1 + ar_3 >= 0 /\ ar_1 - ar_2 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ -ar_1 + ar_2 + 1 >= 0 /\ ar_1 - 2 >= 0 ] 7.11/3.18 7.11/3.18 strictly and produces the following problem: 7.11/3.18 7.11/3.18 9: T: 7.11/3.18 7.11/3.18 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ] 7.11/3.18 7.11/3.18 (Comp: 1, Cost: 1) evalfstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.18 7.11/3.18 (Comp: 1, Cost: 1) evalfentryin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_1, ar_1, ar_2, ar_3, ar_4, ar_5)) 7.11/3.18 7.11/3.18 (Comp: ar_1 + 1, Cost: 1) evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_1 >= 2 ] 7.11/3.18 7.11/3.18 (Comp: 2, Cost: 1) evalfbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 1 >= ar_1 ] 7.11/3.18 7.11/3.18 (Comp: ar_1 + 1, Cost: 1) evalfbbin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_1 - 1, ar_0 + ar_1 - 1, ar_4, ar_5)) [ ar_1 - 2 >= 0 ] 7.11/3.18 7.11/3.18 (Comp: 2, Cost: 1) evalfreturnin(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfstop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ -ar_1 + 1 >= 0 ] 7.11/3.18 7.11/3.18 (Comp: 2*ar_1 + 2, Cost: 1) evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ -ar_1 + ar_2 + 1 >= 0 /\ ar_1 - 2 >= 0 /\ ar_2 >= ar_3 ] 7.11/3.18 7.11/3.18 (Comp: 17*ar_1, Cost: 1) evalfbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ -ar_1 + ar_2 + 1 >= 0 /\ ar_1 - 2 >= 0 /\ ar_3 >= ar_2 + 1 ] 7.11/3.18 7.11/3.18 (Comp: 2*ar_1 + 2, Cost: 1) evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb9in(ar_3 - ar_2 + 1, ar_2 - 1, ar_2, ar_3, ar_4, ar_5)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ -ar_1 + ar_2 + 1 >= 0 /\ ar_1 - 2 >= 0 ] 7.11/3.18 7.11/3.18 (Comp: 17*ar_1, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 - 2 >= 0 /\ ar_2 + ar_3 - 3 >= 0 /\ -ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 4 >= 0 /\ -ar_1 + ar_3 >= 0 /\ ar_1 - ar_2 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ -ar_1 + ar_2 + 1 >= 0 /\ ar_1 - 2 >= 0 /\ 0 >= g + 1 ] 7.11/3.18 7.11/3.18 (Comp: 17*ar_1, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 - 2 >= 0 /\ ar_2 + ar_3 - 3 >= 0 /\ -ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 4 >= 0 /\ -ar_1 + ar_3 >= 0 /\ ar_1 - ar_2 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ -ar_1 + ar_2 + 1 >= 0 /\ ar_1 - 2 >= 0 /\ g >= 1 ] 7.11/3.18 7.11/3.18 (Comp: 2*ar_1 + 2, Cost: 1) evalfbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 - 2 >= 0 /\ ar_2 + ar_3 - 3 >= 0 /\ -ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 4 >= 0 /\ -ar_1 + ar_3 >= 0 /\ ar_1 - ar_2 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ -ar_1 + ar_2 + 1 >= 0 /\ ar_1 - 2 >= 0 ] 7.11/3.18 7.11/3.18 (Comp: 17*ar_1, Cost: 1) evalfbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_2, ar_3 - 1)) [ ar_3 - 2 >= 0 /\ ar_2 + ar_3 - 3 >= 0 /\ -ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 4 >= 0 /\ -ar_1 + ar_3 >= 0 /\ ar_1 - ar_2 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ -ar_1 + ar_2 + 1 >= 0 /\ ar_1 - 2 >= 0 ] 7.11/3.18 7.11/3.18 (Comp: 17*ar_1, Cost: 1) evalfbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_3 - ar_5 - 1 >= 0 /\ ar_5 - 1 >= 0 /\ ar_4 + ar_5 - 2 >= 0 /\ -ar_4 + ar_5 >= 0 /\ ar_3 + ar_5 - 3 >= 0 /\ -ar_3 + ar_5 + 1 >= 0 /\ ar_2 + ar_5 - 2 >= 0 /\ -ar_2 + ar_5 >= 0 /\ ar_1 + ar_5 - 3 >= 0 /\ -ar_1 + ar_5 + 1 >= 0 /\ ar_3 - ar_4 - 1 >= 0 /\ ar_2 - ar_4 >= 0 /\ ar_1 - ar_4 - 1 >= 0 /\ ar_4 - 1 >= 0 /\ ar_3 + ar_4 - 3 >= 0 /\ ar_2 + ar_4 - 2 >= 0 /\ -ar_2 + ar_4 >= 0 /\ ar_1 + ar_4 - 3 >= 0 /\ -ar_1 + ar_4 + 1 >= 0 /\ ar_3 - 2 >= 0 /\ ar_2 + ar_3 - 3 >= 0 /\ -ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 4 >= 0 /\ -ar_1 + ar_3 >= 0 /\ ar_1 - ar_2 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ -ar_1 + ar_2 + 1 >= 0 /\ ar_1 - 2 >= 0 ] 7.11/3.18 7.11/3.18 (Comp: 17*ar_1, Cost: 1) evalfbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(evalfbb6in(ar_0, ar_1, ar_4, ar_5 - 1, ar_4, ar_5)) [ ar_3 - ar_5 - 1 >= 0 /\ ar_5 - 1 >= 0 /\ ar_4 + ar_5 - 2 >= 0 /\ -ar_4 + ar_5 >= 0 /\ ar_3 + ar_5 - 3 >= 0 /\ -ar_3 + ar_5 + 1 >= 0 /\ ar_2 + ar_5 - 2 >= 0 /\ -ar_2 + ar_5 >= 0 /\ ar_1 + ar_5 - 3 >= 0 /\ -ar_1 + ar_5 + 1 >= 0 /\ ar_3 - ar_4 - 1 >= 0 /\ ar_2 - ar_4 >= 0 /\ ar_1 - ar_4 - 1 >= 0 /\ ar_4 - 1 >= 0 /\ ar_3 + ar_4 - 3 >= 0 /\ ar_2 + ar_4 - 2 >= 0 /\ -ar_2 + ar_4 >= 0 /\ ar_1 + ar_4 - 3 >= 0 /\ -ar_1 + ar_4 + 1 >= 0 /\ ar_3 - 2 >= 0 /\ ar_2 + ar_3 - 3 >= 0 /\ -ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 4 >= 0 /\ -ar_1 + ar_3 >= 0 /\ ar_1 - ar_2 - 1 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 3 >= 0 /\ -ar_1 + ar_2 + 1 >= 0 /\ ar_1 - 2 >= 0 ] 7.11/3.18 7.11/3.18 start location: koat_start 7.11/3.18 7.11/3.18 leaf cost: 0 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Complexity upper bound 110*ar_1 + 14 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Time: 0.772 sec (SMT: 0.596 sec) 7.11/3.18 7.11/3.18 7.11/3.18 ---------------------------------------- 7.11/3.18 7.11/3.18 (2) 7.11/3.18 BOUNDS(1, n^1) 7.11/3.18 7.11/3.18 ---------------------------------------- 7.11/3.18 7.11/3.18 (3) Loat Proof (FINISHED) 7.11/3.18 7.11/3.18 7.11/3.18 ### Pre-processing the ITS problem ### 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Initial linear ITS problem 7.11/3.18 7.11/3.18 Start location: evalfstart 7.11/3.18 7.11/3.18 0: evalfstart -> evalfentryin : [], cost: 1 7.11/3.18 7.11/3.18 1: evalfentryin -> evalfbb9in : A'=B, [], cost: 1 7.11/3.18 7.11/3.18 2: evalfbb9in -> evalfbbin : [ B>=2 ], cost: 1 7.11/3.18 7.11/3.18 3: evalfbb9in -> evalfreturnin : [ 1>=B ], cost: 1 7.11/3.18 7.11/3.18 4: evalfbbin -> evalfbb6in : C'=-1+B, D'=-1+A+B, [], cost: 1 7.11/3.18 7.11/3.18 5: evalfbb6in -> evalfbb8in : [ C>=D ], cost: 1 7.11/3.18 7.11/3.18 6: evalfbb6in -> evalfbb7in : [ D>=1+C ], cost: 1 7.11/3.18 7.11/3.18 7: evalfbb7in -> evalfbb1in : [ 0>=1+free ], cost: 1 7.11/3.18 7.11/3.18 8: evalfbb7in -> evalfbb1in : [ free_1>=1 ], cost: 1 7.11/3.18 7.11/3.18 9: evalfbb7in -> evalfbb8in : [], cost: 1 7.11/3.18 7.11/3.18 10: evalfbb1in -> evalfbb3in : E'=C, F'=-1+D, [], cost: 1 7.11/3.18 7.11/3.18 11: evalfbb3in -> evalfbb5in : [], cost: 1 7.11/3.18 7.11/3.18 12: evalfbb3in -> evalfbb4in : [ 0>=3 ], cost: 1 7.11/3.18 7.11/3.18 13: evalfbb4in -> evalfbb2in : [ 0>=1+free_2 ], cost: 1 7.11/3.18 7.11/3.18 14: evalfbb4in -> evalfbb2in : [ free_3>=1 ], cost: 1 7.11/3.18 7.11/3.18 15: evalfbb4in -> evalfbb5in : [], cost: 1 7.11/3.18 7.11/3.18 16: evalfbb2in -> evalfbb3in : E'=1+E, F'=-2+F, [], cost: 1 7.11/3.18 7.11/3.18 17: evalfbb5in -> evalfbb6in : C'=E, D'=-1+F, [], cost: 1 7.11/3.18 7.11/3.18 18: evalfbb8in -> evalfbb9in : A'=1-C+D, B'=-1+C, [], cost: 1 7.11/3.18 7.11/3.18 19: evalfreturnin -> evalfstop : [], cost: 1 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Removed unreachable and leaf rules: 7.11/3.18 7.11/3.18 Start location: evalfstart 7.11/3.18 7.11/3.18 0: evalfstart -> evalfentryin : [], cost: 1 7.11/3.18 7.11/3.18 1: evalfentryin -> evalfbb9in : A'=B, [], cost: 1 7.11/3.18 7.11/3.18 2: evalfbb9in -> evalfbbin : [ B>=2 ], cost: 1 7.11/3.18 7.11/3.18 4: evalfbbin -> evalfbb6in : C'=-1+B, D'=-1+A+B, [], cost: 1 7.11/3.18 7.11/3.18 5: evalfbb6in -> evalfbb8in : [ C>=D ], cost: 1 7.11/3.18 7.11/3.18 6: evalfbb6in -> evalfbb7in : [ D>=1+C ], cost: 1 7.11/3.18 7.11/3.18 7: evalfbb7in -> evalfbb1in : [ 0>=1+free ], cost: 1 7.11/3.18 7.11/3.18 8: evalfbb7in -> evalfbb1in : [ free_1>=1 ], cost: 1 7.11/3.18 7.11/3.18 9: evalfbb7in -> evalfbb8in : [], cost: 1 7.11/3.18 7.11/3.18 10: evalfbb1in -> evalfbb3in : E'=C, F'=-1+D, [], cost: 1 7.11/3.18 7.11/3.18 11: evalfbb3in -> evalfbb5in : [], cost: 1 7.11/3.18 7.11/3.18 12: evalfbb3in -> evalfbb4in : [ 0>=3 ], cost: 1 7.11/3.18 7.11/3.18 13: evalfbb4in -> evalfbb2in : [ 0>=1+free_2 ], cost: 1 7.11/3.18 7.11/3.18 14: evalfbb4in -> evalfbb2in : [ free_3>=1 ], cost: 1 7.11/3.18 7.11/3.18 15: evalfbb4in -> evalfbb5in : [], cost: 1 7.11/3.18 7.11/3.18 16: evalfbb2in -> evalfbb3in : E'=1+E, F'=-2+F, [], cost: 1 7.11/3.18 7.11/3.18 17: evalfbb5in -> evalfbb6in : C'=E, D'=-1+F, [], cost: 1 7.11/3.18 7.11/3.18 18: evalfbb8in -> evalfbb9in : A'=1-C+D, B'=-1+C, [], cost: 1 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Removed rules with unsatisfiable guard: 7.11/3.18 7.11/3.18 Start location: evalfstart 7.11/3.18 7.11/3.18 0: evalfstart -> evalfentryin : [], cost: 1 7.11/3.18 7.11/3.18 1: evalfentryin -> evalfbb9in : A'=B, [], cost: 1 7.11/3.18 7.11/3.18 2: evalfbb9in -> evalfbbin : [ B>=2 ], cost: 1 7.11/3.18 7.11/3.18 4: evalfbbin -> evalfbb6in : C'=-1+B, D'=-1+A+B, [], cost: 1 7.11/3.18 7.11/3.18 5: evalfbb6in -> evalfbb8in : [ C>=D ], cost: 1 7.11/3.18 7.11/3.18 6: evalfbb6in -> evalfbb7in : [ D>=1+C ], cost: 1 7.11/3.18 7.11/3.18 7: evalfbb7in -> evalfbb1in : [ 0>=1+free ], cost: 1 7.11/3.18 7.11/3.18 8: evalfbb7in -> evalfbb1in : [ free_1>=1 ], cost: 1 7.11/3.18 7.11/3.18 9: evalfbb7in -> evalfbb8in : [], cost: 1 7.11/3.18 7.11/3.18 10: evalfbb1in -> evalfbb3in : E'=C, F'=-1+D, [], cost: 1 7.11/3.18 7.11/3.18 11: evalfbb3in -> evalfbb5in : [], cost: 1 7.11/3.18 7.11/3.18 13: evalfbb4in -> evalfbb2in : [ 0>=1+free_2 ], cost: 1 7.11/3.18 7.11/3.18 14: evalfbb4in -> evalfbb2in : [ free_3>=1 ], cost: 1 7.11/3.18 7.11/3.18 15: evalfbb4in -> evalfbb5in : [], cost: 1 7.11/3.18 7.11/3.18 16: evalfbb2in -> evalfbb3in : E'=1+E, F'=-2+F, [], cost: 1 7.11/3.18 7.11/3.18 17: evalfbb5in -> evalfbb6in : C'=E, D'=-1+F, [], cost: 1 7.11/3.18 7.11/3.18 18: evalfbb8in -> evalfbb9in : A'=1-C+D, B'=-1+C, [], cost: 1 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Simplified all rules, resulting in: 7.11/3.18 7.11/3.18 Start location: evalfstart 7.11/3.18 7.11/3.18 0: evalfstart -> evalfentryin : [], cost: 1 7.11/3.18 7.11/3.18 1: evalfentryin -> evalfbb9in : A'=B, [], cost: 1 7.11/3.18 7.11/3.18 2: evalfbb9in -> evalfbbin : [ B>=2 ], cost: 1 7.11/3.18 7.11/3.18 4: evalfbbin -> evalfbb6in : C'=-1+B, D'=-1+A+B, [], cost: 1 7.11/3.18 7.11/3.18 5: evalfbb6in -> evalfbb8in : [ C>=D ], cost: 1 7.11/3.18 7.11/3.18 6: evalfbb6in -> evalfbb7in : [ D>=1+C ], cost: 1 7.11/3.18 7.11/3.18 8: evalfbb7in -> evalfbb1in : [], cost: 1 7.11/3.18 7.11/3.18 9: evalfbb7in -> evalfbb8in : [], cost: 1 7.11/3.18 7.11/3.18 10: evalfbb1in -> evalfbb3in : E'=C, F'=-1+D, [], cost: 1 7.11/3.18 7.11/3.18 11: evalfbb3in -> evalfbb5in : [], cost: 1 7.11/3.18 7.11/3.18 14: evalfbb4in -> evalfbb2in : [], cost: 1 7.11/3.18 7.11/3.18 15: evalfbb4in -> evalfbb5in : [], cost: 1 7.11/3.18 7.11/3.18 16: evalfbb2in -> evalfbb3in : E'=1+E, F'=-2+F, [], cost: 1 7.11/3.18 7.11/3.18 17: evalfbb5in -> evalfbb6in : C'=E, D'=-1+F, [], cost: 1 7.11/3.18 7.11/3.18 18: evalfbb8in -> evalfbb9in : A'=1-C+D, B'=-1+C, [], cost: 1 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 ### Simplification by acceleration and chaining ### 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Removed unreachable locations (and leaf rules with constant cost): 7.11/3.18 7.11/3.18 Start location: evalfstart 7.11/3.18 7.11/3.18 0: evalfstart -> evalfentryin : [], cost: 1 7.11/3.18 7.11/3.18 1: evalfentryin -> evalfbb9in : A'=B, [], cost: 1 7.11/3.18 7.11/3.18 2: evalfbb9in -> evalfbbin : [ B>=2 ], cost: 1 7.11/3.18 7.11/3.18 4: evalfbbin -> evalfbb6in : C'=-1+B, D'=-1+A+B, [], cost: 1 7.11/3.18 7.11/3.18 5: evalfbb6in -> evalfbb8in : [ C>=D ], cost: 1 7.11/3.18 7.11/3.18 6: evalfbb6in -> evalfbb7in : [ D>=1+C ], cost: 1 7.11/3.18 7.11/3.18 8: evalfbb7in -> evalfbb1in : [], cost: 1 7.11/3.18 7.11/3.18 9: evalfbb7in -> evalfbb8in : [], cost: 1 7.11/3.18 7.11/3.18 10: evalfbb1in -> evalfbb3in : E'=C, F'=-1+D, [], cost: 1 7.11/3.18 7.11/3.18 11: evalfbb3in -> evalfbb5in : [], cost: 1 7.11/3.18 7.11/3.18 17: evalfbb5in -> evalfbb6in : C'=E, D'=-1+F, [], cost: 1 7.11/3.18 7.11/3.18 18: evalfbb8in -> evalfbb9in : A'=1-C+D, B'=-1+C, [], cost: 1 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Eliminated locations (on linear paths): 7.11/3.18 7.11/3.18 Start location: evalfstart 7.11/3.18 7.11/3.18 20: evalfstart -> evalfbb9in : A'=B, [], cost: 2 7.11/3.18 7.11/3.18 21: evalfbb9in -> evalfbb6in : C'=-1+B, D'=-1+A+B, [ B>=2 ], cost: 2 7.11/3.18 7.11/3.18 5: evalfbb6in -> evalfbb8in : [ C>=D ], cost: 1 7.11/3.18 7.11/3.18 6: evalfbb6in -> evalfbb7in : [ D>=1+C ], cost: 1 7.11/3.18 7.11/3.18 9: evalfbb7in -> evalfbb8in : [], cost: 1 7.11/3.18 7.11/3.18 24: evalfbb7in -> evalfbb6in : C'=C, D'=-2+D, E'=C, F'=-1+D, [], cost: 4 7.11/3.18 7.11/3.18 18: evalfbb8in -> evalfbb9in : A'=1-C+D, B'=-1+C, [], cost: 1 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Eliminated locations (on tree-shaped paths): 7.11/3.18 7.11/3.18 Start location: evalfstart 7.11/3.18 7.11/3.18 20: evalfstart -> evalfbb9in : A'=B, [], cost: 2 7.11/3.18 7.11/3.18 21: evalfbb9in -> evalfbb6in : C'=-1+B, D'=-1+A+B, [ B>=2 ], cost: 2 7.11/3.18 7.11/3.18 26: evalfbb6in -> evalfbb6in : C'=C, D'=-2+D, E'=C, F'=-1+D, [ D>=1+C ], cost: 5 7.11/3.18 7.11/3.18 27: evalfbb6in -> evalfbb9in : A'=1-C+D, B'=-1+C, [ C>=D ], cost: 2 7.11/3.18 7.11/3.18 28: evalfbb6in -> evalfbb9in : A'=1-C+D, B'=-1+C, [ D>=1+C ], cost: 3 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Accelerating simple loops of location 4. 7.11/3.18 7.11/3.18 Simplified some of the simple loops (and removed duplicate rules). 7.11/3.18 7.11/3.18 Accelerating the following rules: 7.11/3.18 7.11/3.18 26: evalfbb6in -> evalfbb6in : D'=-2+D, E'=C, F'=-1+D, [ D>=1+C ], cost: 5 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Accelerated rule 26 with metering function meter (where 2*meter==-C+D), yielding the new rule 29. 7.11/3.18 7.11/3.18 Removing the simple loops: 26. 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Accelerated all simple loops using metering functions (where possible): 7.11/3.18 7.11/3.18 Start location: evalfstart 7.11/3.18 7.11/3.18 20: evalfstart -> evalfbb9in : A'=B, [], cost: 2 7.11/3.18 7.11/3.18 21: evalfbb9in -> evalfbb6in : C'=-1+B, D'=-1+A+B, [ B>=2 ], cost: 2 7.11/3.18 7.11/3.18 27: evalfbb6in -> evalfbb9in : A'=1-C+D, B'=-1+C, [ C>=D ], cost: 2 7.11/3.18 7.11/3.18 28: evalfbb6in -> evalfbb9in : A'=1-C+D, B'=-1+C, [ D>=1+C ], cost: 3 7.11/3.18 7.11/3.18 29: evalfbb6in -> evalfbb6in : D'=-2*meter+D, E'=C, F'=1-2*meter+D, [ D>=1+C && 2*meter==-C+D && meter>=1 ], cost: 5*meter 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Chained accelerated rules (with incoming rules): 7.11/3.18 7.11/3.18 Start location: evalfstart 7.11/3.18 7.11/3.18 20: evalfstart -> evalfbb9in : A'=B, [], cost: 2 7.11/3.18 7.11/3.18 21: evalfbb9in -> evalfbb6in : C'=-1+B, D'=-1+A+B, [ B>=2 ], cost: 2 7.11/3.18 7.11/3.18 30: evalfbb9in -> evalfbb6in : C'=-1+B, D'=-1-2*meter+A+B, E'=-1+B, F'=-2*meter+A+B, [ B>=2 && -1+A+B>=B && 2*meter==A && meter>=1 ], cost: 2+5*meter 7.11/3.18 7.11/3.18 27: evalfbb6in -> evalfbb9in : A'=1-C+D, B'=-1+C, [ C>=D ], cost: 2 7.11/3.18 7.11/3.18 28: evalfbb6in -> evalfbb9in : A'=1-C+D, B'=-1+C, [ D>=1+C ], cost: 3 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Eliminated locations (on tree-shaped paths): 7.11/3.18 7.11/3.18 Start location: evalfstart 7.11/3.18 7.11/3.18 20: evalfstart -> evalfbb9in : A'=B, [], cost: 2 7.11/3.18 7.11/3.18 31: evalfbb9in -> evalfbb9in : A'=1+A, B'=-2+B, C'=-1+B, D'=-1+A+B, [ B>=2 && -1+B>=-1+A+B ], cost: 4 7.11/3.18 7.11/3.18 32: evalfbb9in -> evalfbb9in : A'=1+A, B'=-2+B, C'=-1+B, D'=-1+A+B, [ B>=2 && -1+A+B>=B ], cost: 5 7.11/3.18 7.11/3.18 33: evalfbb9in -> evalfbb9in : A'=1-2*meter+A, B'=-2+B, C'=-1+B, D'=-1-2*meter+A+B, E'=-1+B, F'=-2*meter+A+B, [ B>=2 && -1+A+B>=B && 2*meter==A && meter>=1 ], cost: 4+5*meter 7.11/3.18 7.11/3.18 34: evalfbb9in -> [15] : [ B>=2 && -1+A+B>=B && 2*meter==A && meter>=1 ], cost: 2+5*meter 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Accelerating simple loops of location 2. 7.11/3.18 7.11/3.18 Accelerating the following rules: 7.11/3.18 7.11/3.18 31: evalfbb9in -> evalfbb9in : A'=1+A, B'=-2+B, C'=-1+B, D'=-1+A+B, [ B>=2 && -1+B>=-1+A+B ], cost: 4 7.11/3.18 7.11/3.18 32: evalfbb9in -> evalfbb9in : A'=1+A, B'=-2+B, C'=-1+B, D'=-1+A+B, [ B>=2 && -1+A+B>=B ], cost: 5 7.11/3.18 7.11/3.18 33: evalfbb9in -> evalfbb9in : A'=1-2*meter+A, B'=-2+B, C'=-1+B, D'=-1-2*meter+A+B, E'=-1+B, F'=-2*meter+A+B, [ B>=2 && -1+A+B>=B && 2*meter==A && meter>=1 ], cost: 4+5*meter 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Accelerated rule 31 with NONTERM (after adding A>=B), yielding the new rule 35. 7.11/3.18 7.11/3.18 Accelerated rule 31 with backward acceleration, yielding the new rule 36. 7.11/3.18 7.11/3.18 Accelerated rule 32 with metering function meter_1 (where 2*meter_1==-1+B), yielding the new rule 37. 7.11/3.18 7.11/3.18 During metering: Instantiating temporary variables by {meter==1} 7.11/3.18 7.11/3.18 Accelerated rule 33 with metering function -2+A, yielding the new rule 38. 7.11/3.18 7.11/3.18 During metering: Instantiating temporary variables by {meter==1,meter_1==1} 7.11/3.18 7.11/3.18 Removing the simple loops: 31 32 33. 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Accelerated all simple loops using metering functions (where possible): 7.11/3.18 7.11/3.18 Start location: evalfstart 7.11/3.18 7.11/3.18 20: evalfstart -> evalfbb9in : A'=B, [], cost: 2 7.11/3.18 7.11/3.18 34: evalfbb9in -> [15] : [ B>=2 && -1+A+B>=B && 2*meter==A && meter>=1 ], cost: 2+5*meter 7.11/3.18 7.11/3.18 35: evalfbb9in -> [16] : [ B>=2 && -1+B>=-1+A+B && A>=B ], cost: INF 7.11/3.18 7.11/3.18 36: evalfbb9in -> evalfbb9in : A'=k+A, B'=-2*k+B, C'=1-2*k+B, D'=-k+A+B, [ B>=2 && -1+B>=-1+A+B && k>0 && 2-2*k+B>=2 && 1-2*k+B>=-k+A+B ], cost: 4*k 7.11/3.18 7.11/3.18 37: evalfbb9in -> evalfbb9in : A'=A+meter_1, B'=-2*meter_1+B, C'=1-2*meter_1+B, D'=A-meter_1+B, [ B>=2 && -1+A+B>=B && 2*meter_1==-1+B && meter_1>=1 ], cost: 5*meter_1 7.11/3.18 7.11/3.18 38: evalfbb9in -> evalfbb9in : A'=2, B'=4-2*A+B, C'=5-2*A+B, D'=6-2*A+B, E'=5-2*A+B, F'=7-2*A+B, [ B>=2 && 2==A && -2+A>=1 ], cost: -18+9*A 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Chained accelerated rules (with incoming rules): 7.11/3.18 7.11/3.18 Start location: evalfstart 7.11/3.18 7.11/3.18 20: evalfstart -> evalfbb9in : A'=B, [], cost: 2 7.11/3.18 7.11/3.18 39: evalfstart -> evalfbb9in : A'=meter_1+B, B'=-2*meter_1+B, C'=1-2*meter_1+B, D'=-meter_1+2*B, [ B>=2 && 2*meter_1==-1+B && meter_1>=1 ], cost: 2+5*meter_1 7.11/3.18 7.11/3.18 34: evalfbb9in -> [15] : [ B>=2 && -1+A+B>=B && 2*meter==A && meter>=1 ], cost: 2+5*meter 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Removed unreachable locations (and leaf rules with constant cost): 7.11/3.18 7.11/3.18 Start location: evalfstart 7.11/3.18 7.11/3.18 20: evalfstart -> evalfbb9in : A'=B, [], cost: 2 7.11/3.18 7.11/3.18 39: evalfstart -> evalfbb9in : A'=meter_1+B, B'=-2*meter_1+B, C'=1-2*meter_1+B, D'=-meter_1+2*B, [ B>=2 && 2*meter_1==-1+B && meter_1>=1 ], cost: 2+5*meter_1 7.11/3.18 7.11/3.18 34: evalfbb9in -> [15] : [ B>=2 && -1+A+B>=B && 2*meter==A && meter>=1 ], cost: 2+5*meter 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Eliminated locations (on tree-shaped paths): 7.11/3.18 7.11/3.18 Start location: evalfstart 7.11/3.18 7.11/3.18 40: evalfstart -> [15] : A'=B, [ B>=2 && 2*meter==B && meter>=1 ], cost: 4+5*meter 7.11/3.18 7.11/3.18 41: evalfstart -> [17] : [ B>=2 && 2*meter_1==-1+B && meter_1>=1 ], cost: 2+5*meter_1 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 ### Computing asymptotic complexity ### 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Fully simplified ITS problem 7.11/3.18 7.11/3.18 Start location: evalfstart 7.11/3.18 7.11/3.18 40: evalfstart -> [15] : A'=B, [ B>=2 && 2*meter==B && meter>=1 ], cost: 4+5*meter 7.11/3.18 7.11/3.18 41: evalfstart -> [17] : [ B>=2 && 2*meter_1==-1+B && meter_1>=1 ], cost: 2+5*meter_1 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Computing asymptotic complexity for rule 40 7.11/3.18 7.11/3.18 Solved the limit problem by the following transformations: 7.11/3.18 7.11/3.18 Created initial limit problem: 7.11/3.18 7.11/3.18 1+2*meter-B (+/+!), 1-2*meter+B (+/+!), 4+5*meter (+), -1+B (+/+!) [not solved] 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 applying transformation rule (C) using substitution {B==2*meter} 7.11/3.18 7.11/3.18 resulting limit problem: 7.11/3.18 7.11/3.18 1 (+/+!), 4+5*meter (+), -1+2*meter (+/+!) [not solved] 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 applying transformation rule (B), deleting 1 (+/+!) 7.11/3.18 7.11/3.18 resulting limit problem: 7.11/3.18 7.11/3.18 4+5*meter (+), -1+2*meter (+/+!) [not solved] 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 removing all constraints (solved by SMT) 7.11/3.18 7.11/3.18 resulting limit problem: [solved] 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 applying transformation rule (C) using substitution {meter==n} 7.11/3.18 7.11/3.18 resulting limit problem: 7.11/3.18 7.11/3.18 [solved] 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Solved the limit problem by the following transformations: 7.11/3.18 7.11/3.18 Created initial limit problem: 7.11/3.18 7.11/3.18 1+2*meter-B (+/+!), 1-2*meter+B (+/+!), 4+5*meter (+), -1+B (+/+!) [not solved] 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 applying transformation rule (C) using substitution {B==2*meter} 7.11/3.18 7.11/3.18 resulting limit problem: 7.11/3.18 7.11/3.18 1 (+/+!), 4+5*meter (+), -1+2*meter (+/+!) [not solved] 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 applying transformation rule (B), deleting 1 (+/+!) 7.11/3.18 7.11/3.18 resulting limit problem: 7.11/3.18 7.11/3.18 4+5*meter (+), -1+2*meter (+/+!) [not solved] 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 removing all constraints (solved by SMT) 7.11/3.18 7.11/3.18 resulting limit problem: [solved] 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 applying transformation rule (C) using substitution {meter==n} 7.11/3.18 7.11/3.18 resulting limit problem: 7.11/3.18 7.11/3.18 [solved] 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Solution: 7.11/3.18 7.11/3.18 meter / n 7.11/3.18 7.11/3.18 B / 2*n 7.11/3.18 7.11/3.18 Resulting cost 4+5*n has complexity: Poly(n^1) 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Found new complexity Poly(n^1). 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Computing asymptotic complexity for rule 41 7.11/3.18 7.11/3.18 Solved the limit problem by the following transformations: 7.11/3.18 7.11/3.18 Created initial limit problem: 7.11/3.18 7.11/3.18 -2*meter_1+B (+/+!), 2+5*meter_1 (+), 2+2*meter_1-B (+/+!), -1+B (+/+!) [not solved] 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 applying transformation rule (C) using substitution {B==1+2*meter_1} 7.11/3.18 7.11/3.18 resulting limit problem: 7.11/3.18 7.11/3.18 2+5*meter_1 (+), 1 (+/+!), 2*meter_1 (+/+!) [not solved] 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 applying transformation rule (B), deleting 1 (+/+!) 7.11/3.18 7.11/3.18 resulting limit problem: 7.11/3.18 7.11/3.18 2+5*meter_1 (+), 2*meter_1 (+/+!) [not solved] 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 removing all constraints (solved by SMT) 7.11/3.18 7.11/3.18 resulting limit problem: [solved] 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 applying transformation rule (C) using substitution {meter_1==n} 7.11/3.18 7.11/3.18 resulting limit problem: 7.11/3.18 7.11/3.18 [solved] 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Solved the limit problem by the following transformations: 7.11/3.18 7.11/3.18 Created initial limit problem: 7.11/3.18 7.11/3.18 -2*meter_1+B (+/+!), 2+5*meter_1 (+), 2+2*meter_1-B (+/+!), -1+B (+/+!) [not solved] 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 applying transformation rule (C) using substitution {B==1+2*meter_1} 7.11/3.18 7.11/3.18 resulting limit problem: 7.11/3.18 7.11/3.18 2+5*meter_1 (+), 1 (+/+!), 2*meter_1 (+/+!) [not solved] 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 applying transformation rule (B), deleting 1 (+/+!) 7.11/3.18 7.11/3.18 resulting limit problem: 7.11/3.18 7.11/3.18 2+5*meter_1 (+), 2*meter_1 (+/+!) [not solved] 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 removing all constraints (solved by SMT) 7.11/3.18 7.11/3.18 resulting limit problem: [solved] 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 applying transformation rule (C) using substitution {meter_1==n} 7.11/3.18 7.11/3.18 resulting limit problem: 7.11/3.18 7.11/3.18 [solved] 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Solution: 7.11/3.18 7.11/3.18 meter_1 / n 7.11/3.18 7.11/3.18 B / 1+2*n 7.11/3.18 7.11/3.18 Resulting cost 2+5*n has complexity: Poly(n^1) 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 Obtained the following overall complexity (w.r.t. the length of the input n): 7.11/3.18 7.11/3.18 Complexity: Poly(n^1) 7.11/3.18 7.11/3.18 Cpx degree: 1 7.11/3.18 7.11/3.18 Solved cost: 4+5*n 7.11/3.18 7.11/3.18 Rule cost: 4+5*meter 7.11/3.18 7.11/3.18 Rule guard: [ B>=2 && 2*meter==B ] 7.11/3.18 7.11/3.18 7.11/3.18 7.11/3.18 WORST_CASE(Omega(n^1),?) 7.11/3.18 7.11/3.18 7.11/3.18 ---------------------------------------- 7.11/3.18 7.11/3.18 (4) 7.11/3.18 BOUNDS(n^1, INF) 7.25/3.21 EOF