/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, 213 ms] (2) BOUNDS(1, n^1) (3) Loat Proof [FINISHED, 919 ms] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: evalNestedMultiplestart(A, B, C, D, E) -> Com_1(evalNestedMultipleentryin(A, B, C, D, E)) :|: TRUE evalNestedMultipleentryin(A, B, C, D, E) -> Com_1(evalNestedMultiplebb5in(B, A, D, C, E)) :|: TRUE evalNestedMultiplebb5in(A, B, C, D, E) -> Com_1(evalNestedMultiplebb2in(A, B, C, D, D)) :|: A >= B + 1 evalNestedMultiplebb5in(A, B, C, D, E) -> Com_1(evalNestedMultiplereturnin(A, B, C, D, E)) :|: B >= A evalNestedMultiplebb2in(A, B, C, D, E) -> Com_1(evalNestedMultiplebb4in(A, B, C, D, E)) :|: E >= C evalNestedMultiplebb2in(A, B, C, D, E) -> Com_1(evalNestedMultiplebb3in(A, B, C, D, E)) :|: C >= E + 1 evalNestedMultiplebb3in(A, B, C, D, E) -> Com_1(evalNestedMultiplebb1in(A, B, C, D, E)) :|: 0 >= F + 1 evalNestedMultiplebb3in(A, B, C, D, E) -> Com_1(evalNestedMultiplebb1in(A, B, C, D, E)) :|: F >= 1 evalNestedMultiplebb3in(A, B, C, D, E) -> Com_1(evalNestedMultiplebb4in(A, B, C, D, E)) :|: TRUE evalNestedMultiplebb1in(A, B, C, D, E) -> Com_1(evalNestedMultiplebb2in(A, B, C, D, E + 1)) :|: TRUE evalNestedMultiplebb4in(A, B, C, D, E) -> Com_1(evalNestedMultiplebb5in(A, B + 1, C, E, E)) :|: TRUE evalNestedMultiplereturnin(A, B, C, D, E) -> Com_1(evalNestedMultiplestop(A, B, C, D, E)) :|: TRUE The start-symbols are:[evalNestedMultiplestart_5] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 11*Ar_0 + 11*Ar_1 + 12*Ar_2 + 12*Ar_3 + 17) Initial complexity problem: 1: T: (Comp: ?, Cost: 1) evalNestedMultiplestart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultipleentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: ?, Cost: 1) evalNestedMultipleentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb5in(Ar_1, Ar_0, Ar_3, Ar_2, Ar_4)) (Comp: ?, Cost: 1) evalNestedMultiplebb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_3)) [ Ar_0 >= Ar_1 + 1 ] (Comp: ?, Cost: 1) evalNestedMultiplebb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplereturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 ] (Comp: ?, Cost: 1) evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_4 >= Ar_2 ] (Comp: ?, Cost: 1) evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= Ar_4 + 1 ] (Comp: ?, Cost: 1) evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= F + 1 ] (Comp: ?, Cost: 1) evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= 1 ] (Comp: ?, Cost: 1) evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: ?, Cost: 1) evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4 + 1)) (Comp: ?, Cost: 1) evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb5in(Ar_0, Ar_1 + 1, Ar_2, Ar_4, Ar_4)) (Comp: ?, Cost: 1) evalNestedMultiplereturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplestop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplestart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 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) evalNestedMultiplestart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultipleentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalNestedMultipleentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb5in(Ar_1, Ar_0, Ar_3, Ar_2, Ar_4)) (Comp: ?, Cost: 1) evalNestedMultiplebb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_3)) [ Ar_0 >= Ar_1 + 1 ] (Comp: ?, Cost: 1) evalNestedMultiplebb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplereturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 ] (Comp: ?, Cost: 1) evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_4 >= Ar_2 ] (Comp: ?, Cost: 1) evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= Ar_4 + 1 ] (Comp: ?, Cost: 1) evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= F + 1 ] (Comp: ?, Cost: 1) evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= 1 ] (Comp: ?, Cost: 1) evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: ?, Cost: 1) evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4 + 1)) (Comp: ?, Cost: 1) evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb5in(Ar_0, Ar_1 + 1, Ar_2, Ar_4, Ar_4)) (Comp: ?, Cost: 1) evalNestedMultiplereturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplestop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplestart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalNestedMultiplestart) = 2 Pol(evalNestedMultipleentryin) = 2 Pol(evalNestedMultiplebb5in) = 2 Pol(evalNestedMultiplebb2in) = 2 Pol(evalNestedMultiplereturnin) = 1 Pol(evalNestedMultiplebb4in) = 2 Pol(evalNestedMultiplebb3in) = 2 Pol(evalNestedMultiplebb1in) = 2 Pol(evalNestedMultiplestop) = 0 Pol(koat_start) = 2 orients all transitions weakly and the transitions evalNestedMultiplereturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplestop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) evalNestedMultiplebb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplereturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 ] strictly and produces the following problem: 3: T: (Comp: 1, Cost: 1) evalNestedMultiplestart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultipleentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalNestedMultipleentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb5in(Ar_1, Ar_0, Ar_3, Ar_2, Ar_4)) (Comp: ?, Cost: 1) evalNestedMultiplebb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_3)) [ Ar_0 >= Ar_1 + 1 ] (Comp: 2, Cost: 1) evalNestedMultiplebb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplereturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 ] (Comp: ?, Cost: 1) evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_4 >= Ar_2 ] (Comp: ?, Cost: 1) evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= Ar_4 + 1 ] (Comp: ?, Cost: 1) evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= F + 1 ] (Comp: ?, Cost: 1) evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= 1 ] (Comp: ?, Cost: 1) evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: ?, Cost: 1) evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4 + 1)) (Comp: ?, Cost: 1) evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb5in(Ar_0, Ar_1 + 1, Ar_2, Ar_4, Ar_4)) (Comp: 2, Cost: 1) evalNestedMultiplereturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplestop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplestart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalNestedMultiplestart) = -V_1 + V_2 + 1 Pol(evalNestedMultipleentryin) = -V_1 + V_2 + 1 Pol(evalNestedMultiplebb5in) = V_1 - V_2 + 1 Pol(evalNestedMultiplebb2in) = V_1 - V_2 Pol(evalNestedMultiplereturnin) = V_1 - V_2 Pol(evalNestedMultiplebb4in) = V_1 - V_2 Pol(evalNestedMultiplebb3in) = V_1 - V_2 Pol(evalNestedMultiplebb1in) = V_1 - V_2 Pol(evalNestedMultiplestop) = V_1 - V_2 Pol(koat_start) = -V_1 + V_2 + 1 orients all transitions weakly and the transition evalNestedMultiplebb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_3)) [ Ar_0 >= Ar_1 + 1 ] strictly and produces the following problem: 4: T: (Comp: 1, Cost: 1) evalNestedMultiplestart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultipleentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalNestedMultipleentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb5in(Ar_1, Ar_0, Ar_3, Ar_2, Ar_4)) (Comp: Ar_0 + Ar_1 + 1, Cost: 1) evalNestedMultiplebb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_3)) [ Ar_0 >= Ar_1 + 1 ] (Comp: 2, Cost: 1) evalNestedMultiplebb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplereturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 ] (Comp: ?, Cost: 1) evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_4 >= Ar_2 ] (Comp: ?, Cost: 1) evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= Ar_4 + 1 ] (Comp: ?, Cost: 1) evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= F + 1 ] (Comp: ?, Cost: 1) evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= 1 ] (Comp: ?, Cost: 1) evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: ?, Cost: 1) evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4 + 1)) (Comp: ?, Cost: 1) evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb5in(Ar_0, Ar_1 + 1, Ar_2, Ar_4, Ar_4)) (Comp: 2, Cost: 1) evalNestedMultiplereturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplestop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplestart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalNestedMultiplebb4in) = 1 Pol(evalNestedMultiplebb5in) = 0 Pol(evalNestedMultiplebb3in) = 2 Pol(evalNestedMultiplebb1in) = 2 Pol(evalNestedMultiplebb2in) = 2 and size complexities S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplestart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 <= 0 ]", 0-0) = Ar_0 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplestart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 <= 0 ]", 0-1) = Ar_1 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplestart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 <= 0 ]", 0-2) = Ar_2 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplestart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 <= 0 ]", 0-3) = Ar_3 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplestart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 <= 0 ]", 0-4) = Ar_4 S("evalNestedMultiplereturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplestop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = Ar_1 S("evalNestedMultiplereturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplestop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = ? S("evalNestedMultiplereturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplestop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = Ar_3 S("evalNestedMultiplereturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplestop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = ? S("evalNestedMultiplereturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplestop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = ? S("evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb5in(Ar_0, Ar_1 + 1, Ar_2, Ar_4, Ar_4))", 0-0) = Ar_1 S("evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb5in(Ar_0, Ar_1 + 1, Ar_2, Ar_4, Ar_4))", 0-1) = ? S("evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb5in(Ar_0, Ar_1 + 1, Ar_2, Ar_4, Ar_4))", 0-2) = Ar_3 S("evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb5in(Ar_0, Ar_1 + 1, Ar_2, Ar_4, Ar_4))", 0-3) = ? S("evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb5in(Ar_0, Ar_1 + 1, Ar_2, Ar_4, Ar_4))", 0-4) = ? S("evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4 + 1))", 0-0) = Ar_1 S("evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4 + 1))", 0-1) = ? S("evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4 + 1))", 0-2) = Ar_3 S("evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4 + 1))", 0-3) = ? S("evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4 + 1))", 0-4) = ? S("evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = Ar_1 S("evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = ? S("evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = Ar_3 S("evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = ? S("evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = ? S("evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= 1 ]", 0-0) = Ar_1 S("evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= 1 ]", 0-1) = ? S("evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= 1 ]", 0-2) = Ar_3 S("evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= 1 ]", 0-3) = ? S("evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= 1 ]", 0-4) = ? S("evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= F + 1 ]", 0-0) = Ar_1 S("evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= F + 1 ]", 0-1) = ? S("evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= F + 1 ]", 0-2) = Ar_3 S("evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= F + 1 ]", 0-3) = ? S("evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= F + 1 ]", 0-4) = ? S("evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= Ar_4 + 1 ]", 0-0) = Ar_1 S("evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= Ar_4 + 1 ]", 0-1) = ? S("evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= Ar_4 + 1 ]", 0-2) = Ar_3 S("evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= Ar_4 + 1 ]", 0-3) = ? S("evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= Ar_4 + 1 ]", 0-4) = ? S("evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_4 >= Ar_2 ]", 0-0) = Ar_1 S("evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_4 >= Ar_2 ]", 0-1) = ? S("evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_4 >= Ar_2 ]", 0-2) = Ar_3 S("evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_4 >= Ar_2 ]", 0-3) = ? S("evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_4 >= Ar_2 ]", 0-4) = ? S("evalNestedMultiplebb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplereturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 ]", 0-0) = Ar_1 S("evalNestedMultiplebb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplereturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 ]", 0-1) = ? S("evalNestedMultiplebb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplereturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 ]", 0-2) = Ar_3 S("evalNestedMultiplebb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplereturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 ]", 0-3) = ? S("evalNestedMultiplebb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplereturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 ]", 0-4) = ? S("evalNestedMultiplebb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_3)) [ Ar_0 >= Ar_1 + 1 ]", 0-0) = Ar_1 S("evalNestedMultiplebb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_3)) [ Ar_0 >= Ar_1 + 1 ]", 0-1) = ? S("evalNestedMultiplebb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_3)) [ Ar_0 >= Ar_1 + 1 ]", 0-2) = Ar_3 S("evalNestedMultiplebb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_3)) [ Ar_0 >= Ar_1 + 1 ]", 0-3) = ? S("evalNestedMultiplebb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_3)) [ Ar_0 >= Ar_1 + 1 ]", 0-4) = ? S("evalNestedMultipleentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb5in(Ar_1, Ar_0, Ar_3, Ar_2, Ar_4))", 0-0) = Ar_1 S("evalNestedMultipleentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb5in(Ar_1, Ar_0, Ar_3, Ar_2, Ar_4))", 0-1) = Ar_0 S("evalNestedMultipleentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb5in(Ar_1, Ar_0, Ar_3, Ar_2, Ar_4))", 0-2) = Ar_3 S("evalNestedMultipleentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb5in(Ar_1, Ar_0, Ar_3, Ar_2, Ar_4))", 0-3) = Ar_2 S("evalNestedMultipleentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb5in(Ar_1, Ar_0, Ar_3, Ar_2, Ar_4))", 0-4) = Ar_4 S("evalNestedMultiplestart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultipleentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = Ar_0 S("evalNestedMultiplestart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultipleentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = Ar_1 S("evalNestedMultiplestart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultipleentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = Ar_2 S("evalNestedMultiplestart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultipleentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = Ar_3 S("evalNestedMultiplestart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultipleentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = Ar_4 orients the transitions evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb5in(Ar_0, Ar_1 + 1, Ar_2, Ar_4, Ar_4)) evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= 1 ] evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= F + 1 ] evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_4 >= Ar_2 ] evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= Ar_4 + 1 ] evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4 + 1)) weakly and the transitions evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb5in(Ar_0, Ar_1 + 1, Ar_2, Ar_4, Ar_4)) evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_4 >= Ar_2 ] strictly and produces the following problem: 5: T: (Comp: 1, Cost: 1) evalNestedMultiplestart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultipleentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalNestedMultipleentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb5in(Ar_1, Ar_0, Ar_3, Ar_2, Ar_4)) (Comp: Ar_0 + Ar_1 + 1, Cost: 1) evalNestedMultiplebb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_3)) [ Ar_0 >= Ar_1 + 1 ] (Comp: 2, Cost: 1) evalNestedMultiplebb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplereturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 ] (Comp: 2*Ar_0 + 2*Ar_1 + 2, Cost: 1) evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_4 >= Ar_2 ] (Comp: ?, Cost: 1) evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= Ar_4 + 1 ] (Comp: ?, Cost: 1) evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= F + 1 ] (Comp: ?, Cost: 1) evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= 1 ] (Comp: 2*Ar_0 + 2*Ar_1 + 2, Cost: 1) evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: ?, Cost: 1) evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4 + 1)) (Comp: 2*Ar_0 + 2*Ar_1 + 2, Cost: 1) evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb5in(Ar_0, Ar_1 + 1, Ar_2, Ar_4, Ar_4)) (Comp: 2, Cost: 1) evalNestedMultiplereturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplestop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplestart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Applied AI with 'oct' on problem 5 to obtain the following invariants: For symbol evalNestedMultiplebb1in: X_3 - X_5 - 1 >= 0 /\ -X_4 + X_5 >= 0 /\ X_3 - X_4 - 1 >= 0 /\ X_1 - X_2 - 1 >= 0 For symbol evalNestedMultiplebb2in: -X_4 + X_5 >= 0 /\ X_1 - X_2 - 1 >= 0 For symbol evalNestedMultiplebb3in: X_3 - X_5 - 1 >= 0 /\ -X_4 + X_5 >= 0 /\ X_3 - X_4 - 1 >= 0 /\ X_1 - X_2 - 1 >= 0 For symbol evalNestedMultiplebb4in: -X_4 + X_5 >= 0 /\ X_1 - X_2 - 1 >= 0 For symbol evalNestedMultiplereturnin: -X_1 + X_2 >= 0 This yielded the following problem: 6: T: (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplestart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 <= 0 ] (Comp: 2, Cost: 1) evalNestedMultiplereturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplestop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ -Ar_0 + Ar_1 >= 0 ] (Comp: 2*Ar_0 + 2*Ar_1 + 2, Cost: 1) evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb5in(Ar_0, Ar_1 + 1, Ar_2, Ar_4, Ar_4)) [ -Ar_3 + Ar_4 >= 0 /\ Ar_0 - Ar_1 - 1 >= 0 ] (Comp: ?, Cost: 1) evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4 + 1)) [ Ar_2 - Ar_4 - 1 >= 0 /\ -Ar_3 + Ar_4 >= 0 /\ Ar_2 - Ar_3 - 1 >= 0 /\ Ar_0 - Ar_1 - 1 >= 0 ] (Comp: 2*Ar_0 + 2*Ar_1 + 2, Cost: 1) evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 - Ar_4 - 1 >= 0 /\ -Ar_3 + Ar_4 >= 0 /\ Ar_2 - Ar_3 - 1 >= 0 /\ Ar_0 - Ar_1 - 1 >= 0 ] (Comp: ?, Cost: 1) evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 - Ar_4 - 1 >= 0 /\ -Ar_3 + Ar_4 >= 0 /\ Ar_2 - Ar_3 - 1 >= 0 /\ Ar_0 - Ar_1 - 1 >= 0 /\ F >= 1 ] (Comp: ?, Cost: 1) evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 - Ar_4 - 1 >= 0 /\ -Ar_3 + Ar_4 >= 0 /\ Ar_2 - Ar_3 - 1 >= 0 /\ Ar_0 - Ar_1 - 1 >= 0 /\ 0 >= F + 1 ] (Comp: ?, Cost: 1) evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ -Ar_3 + Ar_4 >= 0 /\ Ar_0 - Ar_1 - 1 >= 0 /\ Ar_2 >= Ar_4 + 1 ] (Comp: 2*Ar_0 + 2*Ar_1 + 2, Cost: 1) evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ -Ar_3 + Ar_4 >= 0 /\ Ar_0 - Ar_1 - 1 >= 0 /\ Ar_4 >= Ar_2 ] (Comp: 2, Cost: 1) evalNestedMultiplebb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplereturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 ] (Comp: Ar_0 + Ar_1 + 1, Cost: 1) evalNestedMultiplebb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_3)) [ Ar_0 >= Ar_1 + 1 ] (Comp: 1, Cost: 1) evalNestedMultipleentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb5in(Ar_1, Ar_0, Ar_3, Ar_2, Ar_4)) (Comp: 1, Cost: 1) evalNestedMultiplestart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultipleentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) start location: koat_start leaf cost: 0 A polynomial rank function with Pol(koat_start) = -V_1 + V_2 - 3*V_3 + 3*V_4 + 1 Pol(evalNestedMultiplestart) = -V_1 + V_2 - 3*V_3 + 3*V_4 + 1 Pol(evalNestedMultiplereturnin) = V_1 - V_2 + 3*V_3 - 3*V_4 Pol(evalNestedMultiplestop) = V_1 - V_2 + 3*V_3 - 3*V_4 Pol(evalNestedMultiplebb4in) = V_1 - V_2 + 3*V_3 - 3*V_5 Pol(evalNestedMultiplebb5in) = V_1 - V_2 + 3*V_3 - 3*V_4 + 1 Pol(evalNestedMultiplebb1in) = V_1 - V_2 + 3*V_3 - 3*V_5 - 1 Pol(evalNestedMultiplebb2in) = V_1 - V_2 + 3*V_3 - 3*V_5 + 1 Pol(evalNestedMultiplebb3in) = V_1 - V_2 + 3*V_3 - 3*V_5 Pol(evalNestedMultipleentryin) = -V_1 + V_2 - 3*V_3 + 3*V_4 + 1 orients all transitions weakly and the transitions evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 - Ar_4 - 1 >= 0 /\ -Ar_3 + Ar_4 >= 0 /\ Ar_2 - Ar_3 - 1 >= 0 /\ Ar_0 - Ar_1 - 1 >= 0 /\ F >= 1 ] evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 - Ar_4 - 1 >= 0 /\ -Ar_3 + Ar_4 >= 0 /\ Ar_2 - Ar_3 - 1 >= 0 /\ Ar_0 - Ar_1 - 1 >= 0 /\ 0 >= F + 1 ] evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ -Ar_3 + Ar_4 >= 0 /\ Ar_0 - Ar_1 - 1 >= 0 /\ Ar_2 >= Ar_4 + 1 ] evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4 + 1)) [ Ar_2 - Ar_4 - 1 >= 0 /\ -Ar_3 + Ar_4 >= 0 /\ Ar_2 - Ar_3 - 1 >= 0 /\ Ar_0 - Ar_1 - 1 >= 0 ] strictly and produces the following problem: 7: T: (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplestart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 <= 0 ] (Comp: 2, Cost: 1) evalNestedMultiplereturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplestop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ -Ar_0 + Ar_1 >= 0 ] (Comp: 2*Ar_0 + 2*Ar_1 + 2, Cost: 1) evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb5in(Ar_0, Ar_1 + 1, Ar_2, Ar_4, Ar_4)) [ -Ar_3 + Ar_4 >= 0 /\ Ar_0 - Ar_1 - 1 >= 0 ] (Comp: Ar_0 + Ar_1 + 3*Ar_2 + 3*Ar_3 + 1, Cost: 1) evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4 + 1)) [ Ar_2 - Ar_4 - 1 >= 0 /\ -Ar_3 + Ar_4 >= 0 /\ Ar_2 - Ar_3 - 1 >= 0 /\ Ar_0 - Ar_1 - 1 >= 0 ] (Comp: 2*Ar_0 + 2*Ar_1 + 2, Cost: 1) evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 - Ar_4 - 1 >= 0 /\ -Ar_3 + Ar_4 >= 0 /\ Ar_2 - Ar_3 - 1 >= 0 /\ Ar_0 - Ar_1 - 1 >= 0 ] (Comp: Ar_0 + Ar_1 + 3*Ar_2 + 3*Ar_3 + 1, Cost: 1) evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 - Ar_4 - 1 >= 0 /\ -Ar_3 + Ar_4 >= 0 /\ Ar_2 - Ar_3 - 1 >= 0 /\ Ar_0 - Ar_1 - 1 >= 0 /\ F >= 1 ] (Comp: Ar_0 + Ar_1 + 3*Ar_2 + 3*Ar_3 + 1, Cost: 1) evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 - Ar_4 - 1 >= 0 /\ -Ar_3 + Ar_4 >= 0 /\ Ar_2 - Ar_3 - 1 >= 0 /\ Ar_0 - Ar_1 - 1 >= 0 /\ 0 >= F + 1 ] (Comp: Ar_0 + Ar_1 + 3*Ar_2 + 3*Ar_3 + 1, Cost: 1) evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ -Ar_3 + Ar_4 >= 0 /\ Ar_0 - Ar_1 - 1 >= 0 /\ Ar_2 >= Ar_4 + 1 ] (Comp: 2*Ar_0 + 2*Ar_1 + 2, Cost: 1) evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ -Ar_3 + Ar_4 >= 0 /\ Ar_0 - Ar_1 - 1 >= 0 /\ Ar_4 >= Ar_2 ] (Comp: 2, Cost: 1) evalNestedMultiplebb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplereturnin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 ] (Comp: Ar_0 + Ar_1 + 1, Cost: 1) evalNestedMultiplebb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_3)) [ Ar_0 >= Ar_1 + 1 ] (Comp: 1, Cost: 1) evalNestedMultipleentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultiplebb5in(Ar_1, Ar_0, Ar_3, Ar_2, Ar_4)) (Comp: 1, Cost: 1) evalNestedMultiplestart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalNestedMultipleentryin(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) start location: koat_start leaf cost: 0 Complexity upper bound 11*Ar_0 + 11*Ar_1 + 12*Ar_2 + 12*Ar_3 + 17 Time: 0.265 sec (SMT: 0.196 sec) ---------------------------------------- (2) BOUNDS(1, n^1) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalNestedMultiplestart 0: evalNestedMultiplestart -> evalNestedMultipleentryin : [], cost: 1 1: evalNestedMultipleentryin -> evalNestedMultiplebb5in : A'=B, B'=A, C'=D, D'=C, [], cost: 1 2: evalNestedMultiplebb5in -> evalNestedMultiplebb2in : E'=D, [ A>=1+B ], cost: 1 3: evalNestedMultiplebb5in -> evalNestedMultiplereturnin : [ B>=A ], cost: 1 4: evalNestedMultiplebb2in -> evalNestedMultiplebb4in : [ E>=C ], cost: 1 5: evalNestedMultiplebb2in -> evalNestedMultiplebb3in : [ C>=1+E ], cost: 1 6: evalNestedMultiplebb3in -> evalNestedMultiplebb1in : [ 0>=1+free ], cost: 1 7: evalNestedMultiplebb3in -> evalNestedMultiplebb1in : [ free_1>=1 ], cost: 1 8: evalNestedMultiplebb3in -> evalNestedMultiplebb4in : [], cost: 1 9: evalNestedMultiplebb1in -> evalNestedMultiplebb2in : E'=1+E, [], cost: 1 10: evalNestedMultiplebb4in -> evalNestedMultiplebb5in : B'=1+B, D'=E, [], cost: 1 11: evalNestedMultiplereturnin -> evalNestedMultiplestop : [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: evalNestedMultiplestart -> evalNestedMultipleentryin : [], cost: 1 Removed unreachable and leaf rules: Start location: evalNestedMultiplestart 0: evalNestedMultiplestart -> evalNestedMultipleentryin : [], cost: 1 1: evalNestedMultipleentryin -> evalNestedMultiplebb5in : A'=B, B'=A, C'=D, D'=C, [], cost: 1 2: evalNestedMultiplebb5in -> evalNestedMultiplebb2in : E'=D, [ A>=1+B ], cost: 1 4: evalNestedMultiplebb2in -> evalNestedMultiplebb4in : [ E>=C ], cost: 1 5: evalNestedMultiplebb2in -> evalNestedMultiplebb3in : [ C>=1+E ], cost: 1 6: evalNestedMultiplebb3in -> evalNestedMultiplebb1in : [ 0>=1+free ], cost: 1 7: evalNestedMultiplebb3in -> evalNestedMultiplebb1in : [ free_1>=1 ], cost: 1 8: evalNestedMultiplebb3in -> evalNestedMultiplebb4in : [], cost: 1 9: evalNestedMultiplebb1in -> evalNestedMultiplebb2in : E'=1+E, [], cost: 1 10: evalNestedMultiplebb4in -> evalNestedMultiplebb5in : B'=1+B, D'=E, [], cost: 1 Simplified all rules, resulting in: Start location: evalNestedMultiplestart 0: evalNestedMultiplestart -> evalNestedMultipleentryin : [], cost: 1 1: evalNestedMultipleentryin -> evalNestedMultiplebb5in : A'=B, B'=A, C'=D, D'=C, [], cost: 1 2: evalNestedMultiplebb5in -> evalNestedMultiplebb2in : E'=D, [ A>=1+B ], cost: 1 4: evalNestedMultiplebb2in -> evalNestedMultiplebb4in : [ E>=C ], cost: 1 5: evalNestedMultiplebb2in -> evalNestedMultiplebb3in : [ C>=1+E ], cost: 1 7: evalNestedMultiplebb3in -> evalNestedMultiplebb1in : [], cost: 1 8: evalNestedMultiplebb3in -> evalNestedMultiplebb4in : [], cost: 1 9: evalNestedMultiplebb1in -> evalNestedMultiplebb2in : E'=1+E, [], cost: 1 10: evalNestedMultiplebb4in -> evalNestedMultiplebb5in : B'=1+B, D'=E, [], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalNestedMultiplestart 12: evalNestedMultiplestart -> evalNestedMultiplebb5in : A'=B, B'=A, C'=D, D'=C, [], cost: 2 2: evalNestedMultiplebb5in -> evalNestedMultiplebb2in : E'=D, [ A>=1+B ], cost: 1 4: evalNestedMultiplebb2in -> evalNestedMultiplebb4in : [ E>=C ], cost: 1 5: evalNestedMultiplebb2in -> evalNestedMultiplebb3in : [ C>=1+E ], cost: 1 8: evalNestedMultiplebb3in -> evalNestedMultiplebb4in : [], cost: 1 13: evalNestedMultiplebb3in -> evalNestedMultiplebb2in : E'=1+E, [], cost: 2 10: evalNestedMultiplebb4in -> evalNestedMultiplebb5in : B'=1+B, D'=E, [], cost: 1 Eliminated locations (on tree-shaped paths): Start location: evalNestedMultiplestart 12: evalNestedMultiplestart -> evalNestedMultiplebb5in : A'=B, B'=A, C'=D, D'=C, [], cost: 2 2: evalNestedMultiplebb5in -> evalNestedMultiplebb2in : E'=D, [ A>=1+B ], cost: 1 15: evalNestedMultiplebb2in -> evalNestedMultiplebb2in : E'=1+E, [ C>=1+E ], cost: 3 16: evalNestedMultiplebb2in -> evalNestedMultiplebb5in : B'=1+B, D'=E, [ E>=C ], cost: 2 17: evalNestedMultiplebb2in -> evalNestedMultiplebb5in : B'=1+B, D'=E, [ C>=1+E ], cost: 3 Accelerating simple loops of location 3. Accelerating the following rules: 15: evalNestedMultiplebb2in -> evalNestedMultiplebb2in : E'=1+E, [ C>=1+E ], cost: 3 Accelerated rule 15 with metering function C-E, yielding the new rule 18. Removing the simple loops: 15. Accelerated all simple loops using metering functions (where possible): Start location: evalNestedMultiplestart 12: evalNestedMultiplestart -> evalNestedMultiplebb5in : A'=B, B'=A, C'=D, D'=C, [], cost: 2 2: evalNestedMultiplebb5in -> evalNestedMultiplebb2in : E'=D, [ A>=1+B ], cost: 1 16: evalNestedMultiplebb2in -> evalNestedMultiplebb5in : B'=1+B, D'=E, [ E>=C ], cost: 2 17: evalNestedMultiplebb2in -> evalNestedMultiplebb5in : B'=1+B, D'=E, [ C>=1+E ], cost: 3 18: evalNestedMultiplebb2in -> evalNestedMultiplebb2in : E'=C, [ C>=1+E ], cost: 3*C-3*E Chained accelerated rules (with incoming rules): Start location: evalNestedMultiplestart 12: evalNestedMultiplestart -> evalNestedMultiplebb5in : A'=B, B'=A, C'=D, D'=C, [], cost: 2 2: evalNestedMultiplebb5in -> evalNestedMultiplebb2in : E'=D, [ A>=1+B ], cost: 1 19: evalNestedMultiplebb5in -> evalNestedMultiplebb2in : E'=C, [ A>=1+B && C>=1+D ], cost: 1+3*C-3*D 16: evalNestedMultiplebb2in -> evalNestedMultiplebb5in : B'=1+B, D'=E, [ E>=C ], cost: 2 17: evalNestedMultiplebb2in -> evalNestedMultiplebb5in : B'=1+B, D'=E, [ C>=1+E ], cost: 3 Eliminated locations (on tree-shaped paths): Start location: evalNestedMultiplestart 12: evalNestedMultiplestart -> evalNestedMultiplebb5in : A'=B, B'=A, C'=D, D'=C, [], cost: 2 20: evalNestedMultiplebb5in -> evalNestedMultiplebb5in : B'=1+B, D'=D, E'=D, [ A>=1+B && D>=C ], cost: 3 21: evalNestedMultiplebb5in -> evalNestedMultiplebb5in : B'=1+B, D'=D, E'=D, [ A>=1+B && C>=1+D ], cost: 4 22: evalNestedMultiplebb5in -> evalNestedMultiplebb5in : B'=1+B, D'=C, E'=C, [ A>=1+B && C>=1+D ], cost: 3+3*C-3*D 23: evalNestedMultiplebb5in -> [10] : [ A>=1+B && C>=1+D ], cost: 1+3*C-3*D Accelerating simple loops of location 2. Simplified some of the simple loops (and removed duplicate rules). Accelerating the following rules: 20: evalNestedMultiplebb5in -> evalNestedMultiplebb5in : B'=1+B, E'=D, [ A>=1+B && D>=C ], cost: 3 21: evalNestedMultiplebb5in -> evalNestedMultiplebb5in : B'=1+B, E'=D, [ A>=1+B && C>=1+D ], cost: 4 22: evalNestedMultiplebb5in -> evalNestedMultiplebb5in : B'=1+B, D'=C, E'=C, [ A>=1+B && C>=1+D ], cost: 3+3*C-3*D Accelerated rule 20 with metering function A-B, yielding the new rule 24. Accelerated rule 21 with metering function A-B, yielding the new rule 25. Found no metering function for rule 22. Removing the simple loops: 20 21. Accelerated all simple loops using metering functions (where possible): Start location: evalNestedMultiplestart 12: evalNestedMultiplestart -> evalNestedMultiplebb5in : A'=B, B'=A, C'=D, D'=C, [], cost: 2 22: evalNestedMultiplebb5in -> evalNestedMultiplebb5in : B'=1+B, D'=C, E'=C, [ A>=1+B && C>=1+D ], cost: 3+3*C-3*D 23: evalNestedMultiplebb5in -> [10] : [ A>=1+B && C>=1+D ], cost: 1+3*C-3*D 24: evalNestedMultiplebb5in -> evalNestedMultiplebb5in : B'=A, E'=D, [ A>=1+B && D>=C ], cost: 3*A-3*B 25: evalNestedMultiplebb5in -> evalNestedMultiplebb5in : B'=A, E'=D, [ A>=1+B && C>=1+D ], cost: 4*A-4*B Chained accelerated rules (with incoming rules): Start location: evalNestedMultiplestart 12: evalNestedMultiplestart -> evalNestedMultiplebb5in : A'=B, B'=A, C'=D, D'=C, [], cost: 2 26: evalNestedMultiplestart -> evalNestedMultiplebb5in : A'=B, B'=1+A, C'=D, E'=D, [ B>=1+A && D>=1+C ], cost: 5-3*C+3*D 27: evalNestedMultiplestart -> evalNestedMultiplebb5in : A'=B, C'=D, D'=C, E'=C, [ B>=1+A && C>=D ], cost: 2-3*A+3*B 28: evalNestedMultiplestart -> evalNestedMultiplebb5in : A'=B, C'=D, D'=C, E'=C, [ B>=1+A && D>=1+C ], cost: 2-4*A+4*B 23: evalNestedMultiplebb5in -> [10] : [ A>=1+B && C>=1+D ], cost: 1+3*C-3*D Eliminated locations (on tree-shaped paths): Start location: evalNestedMultiplestart 29: evalNestedMultiplestart -> [10] : A'=B, B'=A, C'=D, D'=C, [ B>=1+A && D>=1+C ], cost: 3-3*C+3*D 30: evalNestedMultiplestart -> [12] : [ B>=1+A && D>=1+C ], cost: 5-3*C+3*D 31: evalNestedMultiplestart -> [12] : [ B>=1+A && C>=D ], cost: 2-3*A+3*B 32: evalNestedMultiplestart -> [12] : [ B>=1+A && D>=1+C ], cost: 2-4*A+4*B ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalNestedMultiplestart 30: evalNestedMultiplestart -> [12] : [ B>=1+A && D>=1+C ], cost: 5-3*C+3*D 31: evalNestedMultiplestart -> [12] : [ B>=1+A && C>=D ], cost: 2-3*A+3*B 32: evalNestedMultiplestart -> [12] : [ B>=1+A && D>=1+C ], cost: 2-4*A+4*B Computing asymptotic complexity for rule 30 Solved the limit problem by the following transformations: Created initial limit problem: -C+D (+/+!), 5-3*C+3*D (+), -A+B (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {C==0,D==n,A==-n,B==0} resulting limit problem: [solved] Solution: C / 0 D / n A / -n B / 0 Resulting cost 5+3*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+3*n Rule cost: 5-3*C+3*D Rule guard: [ B>=1+A && D>=1+C ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (4) BOUNDS(n^1, INF)