/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.koat /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^1)) proof of /export/starexec/sandbox/benchmark/theBenchmark.koat # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, n^1). (0) CpxIntTrs (1) Koat Proof [FINISHED, 190 ms] (2) BOUNDS(1, n^1) (3) Loat Proof [FINISHED, 1108 ms] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: evalfstart(A, B, C, D, E, F, G) -> Com_1(evalfentryin(A, B, C, D, E, F, G)) :|: TRUE evalfentryin(A, B, C, D, E, F, G) -> Com_1(evalfbb5in(0, 0, 0, D, E, F, G)) :|: TRUE evalfbb5in(A, B, C, D, E, F, G) -> Com_1(evalfreturnin(A, B, C, D, E, F, G)) :|: C >= D evalfbb5in(A, B, C, D, E, F, G) -> Com_1(evalfbbin(A, B, C, D, C + 1, F, G)) :|: D >= C + 1 evalfbbin(A, B, C, D, E, F, G) -> Com_1(evalfbb1in(A, B, C, D, E, B, G)) :|: 0 >= H + 1 evalfbbin(A, B, C, D, E, F, G) -> Com_1(evalfbb1in(A, B, C, D, E, B, G)) :|: H >= 1 evalfbbin(A, B, C, D, E, F, G) -> Com_1(evalfbb3in(A, B, C, D, E, A, G)) :|: TRUE evalfbb1in(A, B, C, D, E, F, G) -> Com_1(evalfbb5in(A, F + 1, E, D, E, F, G)) :|: F >= G evalfbb1in(A, B, C, D, E, F, G) -> Com_1(evalfbb1in(A, B, C, D, E, F + 1, G)) :|: G >= F + 1 evalfbb3in(A, B, C, D, E, F, G) -> Com_1(evalfbb5in(F + 1, B, E, D, E, F, G)) :|: F >= G evalfbb3in(A, B, C, D, E, F, G) -> Com_1(evalfbb3in(A, B, C, D, E, F + 1, G)) :|: G >= F + 1 evalfreturnin(A, B, C, D, E, F, G) -> Com_1(evalfstop(A, B, C, D, E, F, G)) :|: TRUE The start-symbols are:[evalfstart_7] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 10*Ar_3 + 2*Ar_6 + 6) Initial complexity problem: 1: T: (Comp: ?, Cost: 1) evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) (Comp: ?, Cost: 1) evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(0, 0, 0, Ar_3, Ar_4, Ar_5, Ar_6)) (Comp: ?, Cost: 1) evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_2 >= Ar_3 ] (Comp: ?, Cost: 1) evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_2 + 1, Ar_5, Ar_6)) [ Ar_3 >= Ar_2 + 1 ] (Comp: ?, Cost: 1) evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ 0 >= H + 1 ] (Comp: ?, Cost: 1) evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ H >= 1 ] (Comp: ?, Cost: 1) evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_0, Ar_6)) (Comp: ?, Cost: 1) evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_0, Ar_5 + 1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ] (Comp: ?, Cost: 1) evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ] (Comp: ?, Cost: 1) evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_5 + 1, Ar_1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ] (Comp: ?, Cost: 1) evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ] (Comp: ?, Cost: 1) evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Repeatedly propagating knowledge in problem 1 produces the following problem: 2: T: (Comp: 1, Cost: 1) evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) (Comp: 1, Cost: 1) evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(0, 0, 0, Ar_3, Ar_4, Ar_5, Ar_6)) (Comp: ?, Cost: 1) evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_2 >= Ar_3 ] (Comp: ?, Cost: 1) evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_2 + 1, Ar_5, Ar_6)) [ Ar_3 >= Ar_2 + 1 ] (Comp: ?, Cost: 1) evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ 0 >= H + 1 ] (Comp: ?, Cost: 1) evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ H >= 1 ] (Comp: ?, Cost: 1) evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_0, Ar_6)) (Comp: ?, Cost: 1) evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_0, Ar_5 + 1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ] (Comp: ?, Cost: 1) evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ] (Comp: ?, Cost: 1) evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_5 + 1, Ar_1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ] (Comp: ?, Cost: 1) evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ] (Comp: ?, Cost: 1) evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalfstart) = 2 Pol(evalfentryin) = 2 Pol(evalfbb5in) = 2 Pol(evalfreturnin) = 1 Pol(evalfbbin) = 2 Pol(evalfbb1in) = 2 Pol(evalfbb3in) = 2 Pol(evalfstop) = 0 Pol(koat_start) = 2 orients all transitions weakly and the transitions evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_2 >= Ar_3 ] strictly and produces the following problem: 3: T: (Comp: 1, Cost: 1) evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) (Comp: 1, Cost: 1) evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(0, 0, 0, Ar_3, Ar_4, Ar_5, Ar_6)) (Comp: 2, Cost: 1) evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_2 >= Ar_3 ] (Comp: ?, Cost: 1) evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_2 + 1, Ar_5, Ar_6)) [ Ar_3 >= Ar_2 + 1 ] (Comp: ?, Cost: 1) evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ 0 >= H + 1 ] (Comp: ?, Cost: 1) evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ H >= 1 ] (Comp: ?, Cost: 1) evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_0, Ar_6)) (Comp: ?, Cost: 1) evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_0, Ar_5 + 1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ] (Comp: ?, Cost: 1) evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ] (Comp: ?, Cost: 1) evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_5 + 1, Ar_1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ] (Comp: ?, Cost: 1) evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ] (Comp: 2, Cost: 1) evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalfstart) = V_4 Pol(evalfentryin) = V_4 Pol(evalfbb5in) = -V_3 + V_4 Pol(evalfreturnin) = -V_3 + V_4 Pol(evalfbbin) = V_4 - V_5 Pol(evalfbb1in) = V_4 - V_5 Pol(evalfbb3in) = V_4 - V_5 Pol(evalfstop) = -V_3 + V_4 Pol(koat_start) = V_4 orients all transitions weakly and the transition evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_2 + 1, Ar_5, Ar_6)) [ Ar_3 >= Ar_2 + 1 ] strictly and produces the following problem: 4: T: (Comp: 1, Cost: 1) evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) (Comp: 1, Cost: 1) evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(0, 0, 0, Ar_3, Ar_4, Ar_5, Ar_6)) (Comp: 2, Cost: 1) evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_2 >= Ar_3 ] (Comp: Ar_3, Cost: 1) evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_2 + 1, Ar_5, Ar_6)) [ Ar_3 >= Ar_2 + 1 ] (Comp: ?, Cost: 1) evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ 0 >= H + 1 ] (Comp: ?, Cost: 1) evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ H >= 1 ] (Comp: ?, Cost: 1) evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_0, Ar_6)) (Comp: ?, Cost: 1) evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_0, Ar_5 + 1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ] (Comp: ?, Cost: 1) evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ] (Comp: ?, Cost: 1) evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_5 + 1, Ar_1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ] (Comp: ?, Cost: 1) evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ] (Comp: 2, Cost: 1) evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Repeatedly propagating knowledge in problem 4 produces the following problem: 5: T: (Comp: 1, Cost: 1) evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) (Comp: 1, Cost: 1) evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(0, 0, 0, Ar_3, Ar_4, Ar_5, Ar_6)) (Comp: 2, Cost: 1) evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_2 >= Ar_3 ] (Comp: Ar_3, Cost: 1) evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_2 + 1, Ar_5, Ar_6)) [ Ar_3 >= Ar_2 + 1 ] (Comp: Ar_3, Cost: 1) evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ 0 >= H + 1 ] (Comp: Ar_3, Cost: 1) evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ H >= 1 ] (Comp: Ar_3, Cost: 1) evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_0, Ar_6)) (Comp: ?, Cost: 1) evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_0, Ar_5 + 1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ] (Comp: ?, Cost: 1) evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ] (Comp: ?, Cost: 1) evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_5 + 1, Ar_1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ] (Comp: ?, Cost: 1) evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ] (Comp: 2, Cost: 1) evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalfbb3in) = 1 Pol(evalfbb5in) = 0 Pol(evalfbb1in) = 1 and size complexities S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ 0 <= 0 ]", 0-0) = Ar_0 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ 0 <= 0 ]", 0-1) = Ar_1 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ 0 <= 0 ]", 0-2) = Ar_2 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ 0 <= 0 ]", 0-3) = Ar_3 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ 0 <= 0 ]", 0-4) = Ar_4 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ 0 <= 0 ]", 0-5) = Ar_5 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ 0 <= 0 ]", 0-6) = Ar_6 S("evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6))", 0-0) = ? S("evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6))", 0-1) = ? S("evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6))", 0-2) = Ar_3 S("evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6))", 0-3) = Ar_3 S("evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6))", 0-4) = Ar_3 + Ar_4 S("evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6))", 0-5) = ? S("evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6))", 0-6) = Ar_6 S("evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ]", 0-0) = ? S("evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ]", 0-1) = ? S("evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ]", 0-2) = Ar_3 S("evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ]", 0-3) = Ar_3 S("evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ]", 0-4) = Ar_3 S("evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ]", 0-5) = ? S("evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ]", 0-6) = Ar_6 S("evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_5 + 1, Ar_1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ]", 0-0) = ? S("evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_5 + 1, Ar_1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ]", 0-1) = ? S("evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_5 + 1, Ar_1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ]", 0-2) = Ar_3 S("evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_5 + 1, Ar_1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ]", 0-3) = Ar_3 S("evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_5 + 1, Ar_1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ]", 0-4) = Ar_3 S("evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_5 + 1, Ar_1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ]", 0-5) = ? S("evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_5 + 1, Ar_1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ]", 0-6) = Ar_6 S("evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ]", 0-0) = ? S("evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ]", 0-1) = ? S("evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ]", 0-2) = Ar_3 S("evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ]", 0-3) = Ar_3 S("evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ]", 0-4) = Ar_3 S("evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ]", 0-5) = ? S("evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ]", 0-6) = Ar_6 S("evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_0, Ar_5 + 1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ]", 0-0) = ? S("evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_0, Ar_5 + 1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ]", 0-1) = ? S("evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_0, Ar_5 + 1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ]", 0-2) = Ar_3 S("evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_0, Ar_5 + 1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ]", 0-3) = Ar_3 S("evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_0, Ar_5 + 1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ]", 0-4) = Ar_3 S("evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_0, Ar_5 + 1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ]", 0-5) = ? S("evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_0, Ar_5 + 1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ]", 0-6) = Ar_6 S("evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_0, Ar_6))", 0-0) = ? S("evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_0, Ar_6))", 0-1) = ? S("evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_0, Ar_6))", 0-2) = Ar_3 S("evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_0, Ar_6))", 0-3) = Ar_3 S("evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_0, Ar_6))", 0-4) = Ar_3 S("evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_0, Ar_6))", 0-5) = ? S("evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_0, Ar_6))", 0-6) = Ar_6 S("evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ H >= 1 ]", 0-0) = ? S("evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ H >= 1 ]", 0-1) = ? S("evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ H >= 1 ]", 0-2) = Ar_3 S("evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ H >= 1 ]", 0-3) = Ar_3 S("evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ H >= 1 ]", 0-4) = Ar_3 S("evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ H >= 1 ]", 0-5) = ? S("evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ H >= 1 ]", 0-6) = Ar_6 S("evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ 0 >= H + 1 ]", 0-0) = ? S("evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ 0 >= H + 1 ]", 0-1) = ? S("evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ 0 >= H + 1 ]", 0-2) = Ar_3 S("evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ 0 >= H + 1 ]", 0-3) = Ar_3 S("evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ 0 >= H + 1 ]", 0-4) = Ar_3 S("evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ 0 >= H + 1 ]", 0-5) = ? S("evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ 0 >= H + 1 ]", 0-6) = Ar_6 S("evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_2 + 1, Ar_5, Ar_6)) [ Ar_3 >= Ar_2 + 1 ]", 0-0) = ? S("evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_2 + 1, Ar_5, Ar_6)) [ Ar_3 >= Ar_2 + 1 ]", 0-1) = ? S("evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_2 + 1, Ar_5, Ar_6)) [ Ar_3 >= Ar_2 + 1 ]", 0-2) = Ar_3 S("evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_2 + 1, Ar_5, Ar_6)) [ Ar_3 >= Ar_2 + 1 ]", 0-3) = Ar_3 S("evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_2 + 1, Ar_5, Ar_6)) [ Ar_3 >= Ar_2 + 1 ]", 0-4) = Ar_3 S("evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_2 + 1, Ar_5, Ar_6)) [ Ar_3 >= Ar_2 + 1 ]", 0-5) = ? S("evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_2 + 1, Ar_5, Ar_6)) [ Ar_3 >= Ar_2 + 1 ]", 0-6) = Ar_6 S("evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_2 >= Ar_3 ]", 0-0) = ? S("evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_2 >= Ar_3 ]", 0-1) = ? S("evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_2 >= Ar_3 ]", 0-2) = Ar_3 S("evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_2 >= Ar_3 ]", 0-3) = Ar_3 S("evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_2 >= Ar_3 ]", 0-4) = Ar_3 + Ar_4 S("evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_2 >= Ar_3 ]", 0-5) = ? S("evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_2 >= Ar_3 ]", 0-6) = Ar_6 S("evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(0, 0, 0, Ar_3, Ar_4, Ar_5, Ar_6))", 0-0) = 0 S("evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(0, 0, 0, Ar_3, Ar_4, Ar_5, Ar_6))", 0-1) = 0 S("evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(0, 0, 0, Ar_3, Ar_4, Ar_5, Ar_6))", 0-2) = 0 S("evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(0, 0, 0, Ar_3, Ar_4, Ar_5, Ar_6))", 0-3) = Ar_3 S("evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(0, 0, 0, Ar_3, Ar_4, Ar_5, Ar_6))", 0-4) = Ar_4 S("evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(0, 0, 0, Ar_3, Ar_4, Ar_5, Ar_6))", 0-5) = Ar_5 S("evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(0, 0, 0, Ar_3, Ar_4, Ar_5, Ar_6))", 0-6) = Ar_6 S("evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6))", 0-0) = Ar_0 S("evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6))", 0-1) = Ar_1 S("evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6))", 0-2) = Ar_2 S("evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6))", 0-3) = Ar_3 S("evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6))", 0-4) = Ar_4 S("evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6))", 0-5) = Ar_5 S("evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6))", 0-6) = Ar_6 orients the transitions evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_5 + 1, Ar_1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ] evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ] evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_0, Ar_5 + 1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ] evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ] weakly and the transitions evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_5 + 1, Ar_1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ] evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_0, Ar_5 + 1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ] strictly and produces the following problem: 6: T: (Comp: 1, Cost: 1) evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) (Comp: 1, Cost: 1) evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(0, 0, 0, Ar_3, Ar_4, Ar_5, Ar_6)) (Comp: 2, Cost: 1) evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_2 >= Ar_3 ] (Comp: Ar_3, Cost: 1) evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_2 + 1, Ar_5, Ar_6)) [ Ar_3 >= Ar_2 + 1 ] (Comp: Ar_3, Cost: 1) evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ 0 >= H + 1 ] (Comp: Ar_3, Cost: 1) evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ H >= 1 ] (Comp: Ar_3, Cost: 1) evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_0, Ar_6)) (Comp: 3*Ar_3, Cost: 1) evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_0, Ar_5 + 1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ] (Comp: ?, Cost: 1) evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ] (Comp: 3*Ar_3, Cost: 1) evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_5 + 1, Ar_1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ] (Comp: ?, Cost: 1) evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ] (Comp: 2, Cost: 1) evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalfstart) = V_7 Pol(evalfentryin) = V_7 Pol(evalfbb5in) = -V_2 + V_7 Pol(evalfreturnin) = -V_2 + V_7 Pol(evalfbbin) = -V_2 + V_7 Pol(evalfbb1in) = -V_6 + V_7 Pol(evalfbb3in) = -V_2 + V_7 Pol(evalfstop) = -V_2 + V_7 Pol(koat_start) = V_7 orients all transitions weakly and the transition evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ] strictly and produces the following problem: 7: T: (Comp: 1, Cost: 1) evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) (Comp: 1, Cost: 1) evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(0, 0, 0, Ar_3, Ar_4, Ar_5, Ar_6)) (Comp: 2, Cost: 1) evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_2 >= Ar_3 ] (Comp: Ar_3, Cost: 1) evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_2 + 1, Ar_5, Ar_6)) [ Ar_3 >= Ar_2 + 1 ] (Comp: Ar_3, Cost: 1) evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ 0 >= H + 1 ] (Comp: Ar_3, Cost: 1) evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ H >= 1 ] (Comp: Ar_3, Cost: 1) evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_0, Ar_6)) (Comp: 3*Ar_3, Cost: 1) evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_0, Ar_5 + 1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ] (Comp: Ar_6, Cost: 1) evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ] (Comp: 3*Ar_3, Cost: 1) evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_5 + 1, Ar_1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ] (Comp: ?, Cost: 1) evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ] (Comp: 2, Cost: 1) evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalfstart) = V_7 Pol(evalfentryin) = V_7 Pol(evalfbb5in) = -V_1 + V_7 Pol(evalfreturnin) = -V_1 + V_7 Pol(evalfbbin) = -V_1 + V_7 Pol(evalfbb1in) = -V_1 + V_7 Pol(evalfbb3in) = -V_6 + V_7 Pol(evalfstop) = -V_1 + V_7 Pol(koat_start) = V_7 orients all transitions weakly and the transition evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ] strictly and produces the following problem: 8: T: (Comp: 1, Cost: 1) evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) (Comp: 1, Cost: 1) evalfentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(0, 0, 0, Ar_3, Ar_4, Ar_5, Ar_6)) (Comp: 2, Cost: 1) evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_2 >= Ar_3 ] (Comp: Ar_3, Cost: 1) evalfbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_2 + 1, Ar_5, Ar_6)) [ Ar_3 >= Ar_2 + 1 ] (Comp: Ar_3, Cost: 1) evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ 0 >= H + 1 ] (Comp: Ar_3, Cost: 1) evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_1, Ar_6)) [ H >= 1 ] (Comp: Ar_3, Cost: 1) evalfbbin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_0, Ar_6)) (Comp: 3*Ar_3, Cost: 1) evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_0, Ar_5 + 1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ] (Comp: Ar_6, Cost: 1) evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ] (Comp: 3*Ar_3, Cost: 1) evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb5in(Ar_5 + 1, Ar_1, Ar_4, Ar_3, Ar_4, Ar_5, Ar_6)) [ Ar_5 >= Ar_6 ] (Comp: Ar_6, Cost: 1) evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6)) [ Ar_6 >= Ar_5 + 1 ] (Comp: 2, Cost: 1) evalfreturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6) -> Com_1(evalfstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Complexity upper bound 10*Ar_3 + 2*Ar_6 + 6 Time: 0.216 sec (SMT: 0.143 sec) ---------------------------------------- (2) BOUNDS(1, n^1) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalfstart 0: evalfstart -> evalfentryin : [], cost: 1 1: evalfentryin -> evalfbb5in : A'=0, B'=0, C'=0, [], cost: 1 2: evalfbb5in -> evalfreturnin : [ C>=D ], cost: 1 3: evalfbb5in -> evalfbbin : E'=1+C, [ D>=1+C ], cost: 1 4: evalfbbin -> evalfbb1in : F'=B, [ 0>=1+free ], cost: 1 5: evalfbbin -> evalfbb1in : F'=B, [ free_1>=1 ], cost: 1 6: evalfbbin -> evalfbb3in : F'=A, [], cost: 1 7: evalfbb1in -> evalfbb5in : B'=1+F, C'=E, [ F>=G ], cost: 1 8: evalfbb1in -> evalfbb1in : F'=1+F, [ G>=1+F ], cost: 1 9: evalfbb3in -> evalfbb5in : A'=1+F, C'=E, [ F>=G ], cost: 1 10: evalfbb3in -> evalfbb3in : F'=1+F, [ G>=1+F ], cost: 1 11: evalfreturnin -> evalfstop : [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: evalfstart -> evalfentryin : [], cost: 1 Removed unreachable and leaf rules: Start location: evalfstart 0: evalfstart -> evalfentryin : [], cost: 1 1: evalfentryin -> evalfbb5in : A'=0, B'=0, C'=0, [], cost: 1 3: evalfbb5in -> evalfbbin : E'=1+C, [ D>=1+C ], cost: 1 4: evalfbbin -> evalfbb1in : F'=B, [ 0>=1+free ], cost: 1 5: evalfbbin -> evalfbb1in : F'=B, [ free_1>=1 ], cost: 1 6: evalfbbin -> evalfbb3in : F'=A, [], cost: 1 7: evalfbb1in -> evalfbb5in : B'=1+F, C'=E, [ F>=G ], cost: 1 8: evalfbb1in -> evalfbb1in : F'=1+F, [ G>=1+F ], cost: 1 9: evalfbb3in -> evalfbb5in : A'=1+F, C'=E, [ F>=G ], cost: 1 10: evalfbb3in -> evalfbb3in : F'=1+F, [ G>=1+F ], cost: 1 Simplified all rules, resulting in: Start location: evalfstart 0: evalfstart -> evalfentryin : [], cost: 1 1: evalfentryin -> evalfbb5in : A'=0, B'=0, C'=0, [], cost: 1 3: evalfbb5in -> evalfbbin : E'=1+C, [ D>=1+C ], cost: 1 5: evalfbbin -> evalfbb1in : F'=B, [], cost: 1 6: evalfbbin -> evalfbb3in : F'=A, [], cost: 1 7: evalfbb1in -> evalfbb5in : B'=1+F, C'=E, [ F>=G ], cost: 1 8: evalfbb1in -> evalfbb1in : F'=1+F, [ G>=1+F ], cost: 1 9: evalfbb3in -> evalfbb5in : A'=1+F, C'=E, [ F>=G ], cost: 1 10: evalfbb3in -> evalfbb3in : F'=1+F, [ G>=1+F ], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 4. Accelerating the following rules: 8: evalfbb1in -> evalfbb1in : F'=1+F, [ G>=1+F ], cost: 1 Accelerated rule 8 with metering function -F+G, yielding the new rule 12. Removing the simple loops: 8. Accelerating simple loops of location 5. Accelerating the following rules: 10: evalfbb3in -> evalfbb3in : F'=1+F, [ G>=1+F ], cost: 1 Accelerated rule 10 with metering function -F+G, yielding the new rule 13. Removing the simple loops: 10. Accelerated all simple loops using metering functions (where possible): Start location: evalfstart 0: evalfstart -> evalfentryin : [], cost: 1 1: evalfentryin -> evalfbb5in : A'=0, B'=0, C'=0, [], cost: 1 3: evalfbb5in -> evalfbbin : E'=1+C, [ D>=1+C ], cost: 1 5: evalfbbin -> evalfbb1in : F'=B, [], cost: 1 6: evalfbbin -> evalfbb3in : F'=A, [], cost: 1 7: evalfbb1in -> evalfbb5in : B'=1+F, C'=E, [ F>=G ], cost: 1 12: evalfbb1in -> evalfbb1in : F'=G, [ G>=1+F ], cost: -F+G 9: evalfbb3in -> evalfbb5in : A'=1+F, C'=E, [ F>=G ], cost: 1 13: evalfbb3in -> evalfbb3in : F'=G, [ G>=1+F ], cost: -F+G Chained accelerated rules (with incoming rules): Start location: evalfstart 0: evalfstart -> evalfentryin : [], cost: 1 1: evalfentryin -> evalfbb5in : A'=0, B'=0, C'=0, [], cost: 1 3: evalfbb5in -> evalfbbin : E'=1+C, [ D>=1+C ], cost: 1 5: evalfbbin -> evalfbb1in : F'=B, [], cost: 1 6: evalfbbin -> evalfbb3in : F'=A, [], cost: 1 14: evalfbbin -> evalfbb1in : F'=G, [ G>=1+B ], cost: 1+G-B 15: evalfbbin -> evalfbb3in : F'=G, [ G>=1+A ], cost: 1+G-A 7: evalfbb1in -> evalfbb5in : B'=1+F, C'=E, [ F>=G ], cost: 1 9: evalfbb3in -> evalfbb5in : A'=1+F, C'=E, [ F>=G ], cost: 1 Eliminated locations (on linear paths): Start location: evalfstart 16: evalfstart -> evalfbb5in : A'=0, B'=0, C'=0, [], cost: 2 3: evalfbb5in -> evalfbbin : E'=1+C, [ D>=1+C ], cost: 1 5: evalfbbin -> evalfbb1in : F'=B, [], cost: 1 6: evalfbbin -> evalfbb3in : F'=A, [], cost: 1 14: evalfbbin -> evalfbb1in : F'=G, [ G>=1+B ], cost: 1+G-B 15: evalfbbin -> evalfbb3in : F'=G, [ G>=1+A ], cost: 1+G-A 7: evalfbb1in -> evalfbb5in : B'=1+F, C'=E, [ F>=G ], cost: 1 9: evalfbb3in -> evalfbb5in : A'=1+F, C'=E, [ F>=G ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: evalfstart 16: evalfstart -> evalfbb5in : A'=0, B'=0, C'=0, [], cost: 2 17: evalfbb5in -> evalfbb1in : E'=1+C, F'=B, [ D>=1+C ], cost: 2 18: evalfbb5in -> evalfbb3in : E'=1+C, F'=A, [ D>=1+C ], cost: 2 19: evalfbb5in -> evalfbb1in : E'=1+C, F'=G, [ D>=1+C && G>=1+B ], cost: 2+G-B 20: evalfbb5in -> evalfbb3in : E'=1+C, F'=G, [ D>=1+C && G>=1+A ], cost: 2+G-A 7: evalfbb1in -> evalfbb5in : B'=1+F, C'=E, [ F>=G ], cost: 1 9: evalfbb3in -> evalfbb5in : A'=1+F, C'=E, [ F>=G ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: evalfstart 16: evalfstart -> evalfbb5in : A'=0, B'=0, C'=0, [], cost: 2 21: evalfbb5in -> evalfbb5in : B'=1+B, C'=1+C, E'=1+C, F'=B, [ D>=1+C && B>=G ], cost: 3 22: evalfbb5in -> evalfbb5in : B'=1+G, C'=1+C, E'=1+C, F'=G, [ D>=1+C && G>=1+B ], cost: 3+G-B 23: evalfbb5in -> evalfbb5in : A'=1+A, C'=1+C, E'=1+C, F'=A, [ D>=1+C && A>=G ], cost: 3 24: evalfbb5in -> evalfbb5in : A'=1+G, C'=1+C, E'=1+C, F'=G, [ D>=1+C && G>=1+A ], cost: 3+G-A Accelerating simple loops of location 2. Accelerating the following rules: 21: evalfbb5in -> evalfbb5in : B'=1+B, C'=1+C, E'=1+C, F'=B, [ D>=1+C && B>=G ], cost: 3 22: evalfbb5in -> evalfbb5in : B'=1+G, C'=1+C, E'=1+C, F'=G, [ D>=1+C && G>=1+B ], cost: 3+G-B 23: evalfbb5in -> evalfbb5in : A'=1+A, C'=1+C, E'=1+C, F'=A, [ D>=1+C && A>=G ], cost: 3 24: evalfbb5in -> evalfbb5in : A'=1+G, C'=1+C, E'=1+C, F'=G, [ D>=1+C && G>=1+A ], cost: 3+G-A Accelerated rule 21 with metering function -C+D, yielding the new rule 25. Found no metering function for rule 22. Accelerated rule 23 with metering function -C+D, yielding the new rule 26. Found no metering function for rule 24. Removing the simple loops: 21 23. Accelerated all simple loops using metering functions (where possible): Start location: evalfstart 16: evalfstart -> evalfbb5in : A'=0, B'=0, C'=0, [], cost: 2 22: evalfbb5in -> evalfbb5in : B'=1+G, C'=1+C, E'=1+C, F'=G, [ D>=1+C && G>=1+B ], cost: 3+G-B 24: evalfbb5in -> evalfbb5in : A'=1+G, C'=1+C, E'=1+C, F'=G, [ D>=1+C && G>=1+A ], cost: 3+G-A 25: evalfbb5in -> evalfbb5in : B'=-C+D+B, C'=D, E'=D, F'=-1-C+D+B, [ D>=1+C && B>=G ], cost: -3*C+3*D 26: evalfbb5in -> evalfbb5in : A'=-C+D+A, C'=D, E'=D, F'=-1-C+D+A, [ D>=1+C && A>=G ], cost: -3*C+3*D Chained accelerated rules (with incoming rules): Start location: evalfstart 16: evalfstart -> evalfbb5in : A'=0, B'=0, C'=0, [], cost: 2 27: evalfstart -> evalfbb5in : A'=0, B'=1+G, C'=1, E'=1, F'=G, [ D>=1 && G>=1 ], cost: 5+G 28: evalfstart -> evalfbb5in : A'=1+G, B'=0, C'=1, E'=1, F'=G, [ D>=1 && G>=1 ], cost: 5+G 29: evalfstart -> evalfbb5in : A'=0, B'=D, C'=D, E'=D, F'=-1+D, [ D>=1 && 0>=G ], cost: 2+3*D 30: evalfstart -> evalfbb5in : A'=D, B'=0, C'=D, E'=D, F'=-1+D, [ D>=1 && 0>=G ], cost: 2+3*D Removed unreachable locations (and leaf rules with constant cost): Start location: evalfstart 27: evalfstart -> evalfbb5in : A'=0, B'=1+G, C'=1, E'=1, F'=G, [ D>=1 && G>=1 ], cost: 5+G 28: evalfstart -> evalfbb5in : A'=1+G, B'=0, C'=1, E'=1, F'=G, [ D>=1 && G>=1 ], cost: 5+G 29: evalfstart -> evalfbb5in : A'=0, B'=D, C'=D, E'=D, F'=-1+D, [ D>=1 && 0>=G ], cost: 2+3*D 30: evalfstart -> evalfbb5in : A'=D, B'=0, C'=D, E'=D, F'=-1+D, [ D>=1 && 0>=G ], cost: 2+3*D ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalfstart 28: evalfstart -> evalfbb5in : A'=1+G, B'=0, C'=1, E'=1, F'=G, [ D>=1 && G>=1 ], cost: 5+G 30: evalfstart -> evalfbb5in : A'=D, B'=0, C'=D, E'=D, F'=-1+D, [ D>=1 && 0>=G ], cost: 2+3*D Computing asymptotic complexity for rule 28 Solved the limit problem by the following transformations: Created initial limit problem: 5+G (+), G (+/+!), D (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {G==n,D==n} resulting limit problem: [solved] Solution: G / n D / n Resulting cost 5+n has complexity: Poly(n^1) Found new complexity Poly(n^1). Obtained the following overall complexity (w.r.t. the length of the input n): Complexity: Poly(n^1) Cpx degree: 1 Solved cost: 5+n Rule cost: 5+G Rule guard: [ D>=1 && G>=1 ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (4) BOUNDS(n^1, INF)