/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, 299 ms] (2) BOUNDS(1, n^1) (3) Loat Proof [FINISHED, 2080 ms] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: evalrandom2dstart(A, B, C, D) -> Com_1(evalrandom2dentryin(A, B, C, D)) :|: TRUE evalrandom2dentryin(A, B, C, D) -> Com_1(evalrandom2dbb10in(0, B, C, D)) :|: TRUE evalrandom2dbb10in(A, B, C, D) -> Com_1(evalrandom2dbbin(A, B, C, D)) :|: B >= A + 1 evalrandom2dbb10in(A, B, C, D) -> Com_1(evalrandom2dreturnin(A, B, C, D)) :|: A >= B evalrandom2dbbin(A, B, C, D) -> Com_1(evalrandom2dbb2in(A, B, A + 1, E)) :|: E >= 0 && 3 >= E evalrandom2dbbin(A, B, C, D) -> Com_1(evalrandom2dbb10in(A + 1, B, C, D)) :|: 0 >= E + 1 evalrandom2dbbin(A, B, C, D) -> Com_1(evalrandom2dbb10in(A + 1, B, C, D)) :|: E >= 4 evalrandom2dbb2in(A, B, C, D) -> Com_1(evalrandom2dNodeBlock9in(A, B, C, D)) :|: TRUE evalrandom2dNodeBlock9in(A, B, C, D) -> Com_1(evalrandom2dNodeBlockin(A, B, C, D)) :|: 1 >= D evalrandom2dNodeBlock9in(A, B, C, D) -> Com_1(evalrandom2dNodeBlock7in(A, B, C, D)) :|: D >= 2 evalrandom2dNodeBlockin(A, B, C, D) -> Com_1(evalrandom2dLeafBlockin(A, B, C, D)) :|: 0 >= D evalrandom2dNodeBlockin(A, B, C, D) -> Com_1(evalrandom2dLeafBlock1in(A, B, C, D)) :|: D >= 1 evalrandom2dLeafBlockin(A, B, C, D) -> Com_1(evalrandom2dbb3in(A, B, C, D)) :|: D >= 0 && D <= 0 evalrandom2dLeafBlockin(A, B, C, D) -> Com_1(evalrandom2dNewDefaultin(A, B, C, D)) :|: 0 >= D + 1 evalrandom2dLeafBlockin(A, B, C, D) -> Com_1(evalrandom2dNewDefaultin(A, B, C, D)) :|: D >= 1 evalrandom2dbb3in(A, B, C, D) -> Com_1(evalrandom2dbb10in(C, B, C, D)) :|: TRUE evalrandom2dLeafBlock1in(A, B, C, D) -> Com_1(evalrandom2dbb5in(A, B, C, D)) :|: D >= 1 && D <= 1 evalrandom2dLeafBlock1in(A, B, C, D) -> Com_1(evalrandom2dNewDefaultin(A, B, C, D)) :|: 0 >= D evalrandom2dLeafBlock1in(A, B, C, D) -> Com_1(evalrandom2dNewDefaultin(A, B, C, D)) :|: D >= 2 evalrandom2dbb5in(A, B, C, D) -> Com_1(evalrandom2dbb10in(C, B, C, D)) :|: TRUE evalrandom2dNodeBlock7in(A, B, C, D) -> Com_1(evalrandom2dLeafBlock3in(A, B, C, D)) :|: 2 >= D evalrandom2dNodeBlock7in(A, B, C, D) -> Com_1(evalrandom2dLeafBlock5in(A, B, C, D)) :|: D >= 3 evalrandom2dLeafBlock3in(A, B, C, D) -> Com_1(evalrandom2dbb7in(A, B, C, D)) :|: D >= 2 && D <= 2 evalrandom2dLeafBlock3in(A, B, C, D) -> Com_1(evalrandom2dNewDefaultin(A, B, C, D)) :|: 1 >= D evalrandom2dLeafBlock3in(A, B, C, D) -> Com_1(evalrandom2dNewDefaultin(A, B, C, D)) :|: D >= 3 evalrandom2dbb7in(A, B, C, D) -> Com_1(evalrandom2dbb10in(C, B, C, D)) :|: TRUE evalrandom2dLeafBlock5in(A, B, C, D) -> Com_1(evalrandom2dbb9in(A, B, C, D)) :|: D >= 3 && D <= 3 evalrandom2dLeafBlock5in(A, B, C, D) -> Com_1(evalrandom2dNewDefaultin(A, B, C, D)) :|: 2 >= D evalrandom2dLeafBlock5in(A, B, C, D) -> Com_1(evalrandom2dNewDefaultin(A, B, C, D)) :|: D >= 4 evalrandom2dbb9in(A, B, C, D) -> Com_1(evalrandom2dbb10in(C, B, C, D)) :|: TRUE evalrandom2dNewDefaultin(A, B, C, D) -> Com_1(evalrandom2dbb10in(C, B, C, D)) :|: TRUE evalrandom2dreturnin(A, B, C, D) -> Com_1(evalrandom2dstop(A, B, C, D)) :|: TRUE The start-symbols are:[evalrandom2dstart_4] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 27*Ar_1 + 6) Initial complexity problem: 1: T: (Comp: ?, Cost: 1) evalrandom2dstart(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dentryin(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dentryin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb10in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbbin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 >= Ar_0 + 1 ] (Comp: ?, Cost: 1) evalrandom2dbb10in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dreturnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= Ar_1 ] (Comp: ?, Cost: 1) evalrandom2dbbin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb2in(Ar_0, Ar_1, Ar_0 + 1, Fresh_0)) [ Fresh_0 >= 0 /\ 3 >= Fresh_0 ] (Comp: ?, Cost: 1) evalrandom2dbbin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_0 + 1, Ar_1, Ar_2, Ar_3)) [ 0 >= E + 1 ] (Comp: ?, Cost: 1) evalrandom2dbbin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_0 + 1, Ar_1, Ar_2, Ar_3)) [ E >= 4 ] (Comp: ?, Cost: 1) evalrandom2dbb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNodeBlock9in(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dNodeBlock9in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNodeBlockin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 1 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlock9in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNodeBlock7in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 2 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlockin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dLeafBlockin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlockin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dLeafBlock1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 1 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlockin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 = 0 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlockin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_3 + 1 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlockin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 1 ] (Comp: ?, Cost: 1) evalrandom2dbb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dLeafBlock1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 = 1 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 2 ] (Comp: ?, Cost: 1) evalrandom2dbb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dNodeBlock7in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dLeafBlock3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ 2 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlock7in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dLeafBlock5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 3 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb7in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 = 2 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 1 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 3 ] (Comp: ?, Cost: 1) evalrandom2dbb7in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dLeafBlock5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb9in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 = 3 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 2 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 4 ] (Comp: ?, Cost: 1) evalrandom2dbb9in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dreturnin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dstop(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dstart(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Testing for reachability in the complexity graph removes the following transitions from problem 1: evalrandom2dLeafBlockin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 1 ] evalrandom2dLeafBlock1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_3 ] evalrandom2dLeafBlock3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 3 ] evalrandom2dLeafBlock5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 2 >= Ar_3 ] We thus obtain the following problem: 2: T: (Comp: ?, Cost: 1) evalrandom2dbb9in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb7in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dLeafBlock5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 4 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb9in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 = 3 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 1 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb7in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 = 2 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 2 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 = 1 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlockin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_3 + 1 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlockin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 = 0 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlock7in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dLeafBlock5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 3 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlock7in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dLeafBlock3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ 2 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlockin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dLeafBlock1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 1 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlockin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dLeafBlockin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlock9in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNodeBlock7in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 2 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlock9in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNodeBlockin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 1 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2dbb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNodeBlock9in(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dreturnin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dstop(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbbin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_0 + 1, Ar_1, Ar_2, Ar_3)) [ E >= 4 ] (Comp: ?, Cost: 1) evalrandom2dbbin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_0 + 1, Ar_1, Ar_2, Ar_3)) [ 0 >= E + 1 ] (Comp: ?, Cost: 1) evalrandom2dbbin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb2in(Ar_0, Ar_1, Ar_0 + 1, Fresh_0)) [ Fresh_0 >= 0 /\ 3 >= Fresh_0 ] (Comp: ?, Cost: 1) evalrandom2dbb10in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dreturnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= Ar_1 ] (Comp: ?, Cost: 1) evalrandom2dbb10in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbbin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 >= Ar_0 + 1 ] (Comp: ?, Cost: 1) evalrandom2dentryin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dstart(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dentryin(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dstart(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Repeatedly propagating knowledge in problem 2 produces the following problem: 3: T: (Comp: ?, Cost: 1) evalrandom2dbb9in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb7in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dLeafBlock5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 4 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb9in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 = 3 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 1 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb7in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 = 2 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 2 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 = 1 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlockin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_3 + 1 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlockin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 = 0 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlock7in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dLeafBlock5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 3 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlock7in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dLeafBlock3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ 2 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlockin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dLeafBlock1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 1 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlockin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dLeafBlockin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlock9in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNodeBlock7in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 2 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlock9in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNodeBlockin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 1 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2dbb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNodeBlock9in(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dreturnin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dstop(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbbin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_0 + 1, Ar_1, Ar_2, Ar_3)) [ E >= 4 ] (Comp: ?, Cost: 1) evalrandom2dbbin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_0 + 1, Ar_1, Ar_2, Ar_3)) [ 0 >= E + 1 ] (Comp: ?, Cost: 1) evalrandom2dbbin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb2in(Ar_0, Ar_1, Ar_0 + 1, Fresh_0)) [ Fresh_0 >= 0 /\ 3 >= Fresh_0 ] (Comp: ?, Cost: 1) evalrandom2dbb10in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dreturnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= Ar_1 ] (Comp: ?, Cost: 1) evalrandom2dbb10in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbbin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 >= Ar_0 + 1 ] (Comp: 1, Cost: 1) evalrandom2dentryin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2dstart(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dentryin(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dstart(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalrandom2dbb9in) = 2 Pol(evalrandom2dbb10in) = 2 Pol(evalrandom2dbb7in) = 2 Pol(evalrandom2dbb5in) = 2 Pol(evalrandom2dNewDefaultin) = 2 Pol(evalrandom2dbb3in) = 2 Pol(evalrandom2dLeafBlock5in) = 2 Pol(evalrandom2dLeafBlock3in) = 2 Pol(evalrandom2dLeafBlock1in) = 2 Pol(evalrandom2dLeafBlockin) = 2 Pol(evalrandom2dNodeBlock7in) = 2 Pol(evalrandom2dNodeBlockin) = 2 Pol(evalrandom2dNodeBlock9in) = 2 Pol(evalrandom2dbb2in) = 2 Pol(evalrandom2dreturnin) = 1 Pol(evalrandom2dstop) = 0 Pol(evalrandom2dbbin) = 2 Pol(evalrandom2dentryin) = 2 Pol(evalrandom2dstart) = 2 Pol(koat_start) = 2 orients all transitions weakly and the transitions evalrandom2dreturnin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dstop(Ar_0, Ar_1, Ar_2, Ar_3)) evalrandom2dbb10in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dreturnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= Ar_1 ] strictly and produces the following problem: 4: T: (Comp: ?, Cost: 1) evalrandom2dbb9in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb7in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dLeafBlock5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 4 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb9in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 = 3 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 1 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb7in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 = 2 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 2 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 = 1 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlockin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_3 + 1 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlockin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 = 0 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlock7in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dLeafBlock5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 3 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlock7in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dLeafBlock3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ 2 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlockin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dLeafBlock1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 1 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlockin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dLeafBlockin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlock9in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNodeBlock7in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 2 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlock9in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNodeBlockin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 1 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2dbb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNodeBlock9in(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 2, Cost: 1) evalrandom2dreturnin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dstop(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbbin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_0 + 1, Ar_1, Ar_2, Ar_3)) [ E >= 4 ] (Comp: ?, Cost: 1) evalrandom2dbbin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_0 + 1, Ar_1, Ar_2, Ar_3)) [ 0 >= E + 1 ] (Comp: ?, Cost: 1) evalrandom2dbbin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb2in(Ar_0, Ar_1, Ar_0 + 1, Fresh_0)) [ Fresh_0 >= 0 /\ 3 >= Fresh_0 ] (Comp: 2, Cost: 1) evalrandom2dbb10in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dreturnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= Ar_1 ] (Comp: ?, Cost: 1) evalrandom2dbb10in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbbin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 >= Ar_0 + 1 ] (Comp: 1, Cost: 1) evalrandom2dentryin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2dstart(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dentryin(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dstart(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalrandom2dbb9in) = V_2 - V_3 Pol(evalrandom2dbb10in) = -V_1 + V_2 Pol(evalrandom2dbb7in) = V_2 - V_3 Pol(evalrandom2dbb5in) = V_2 - V_3 Pol(evalrandom2dNewDefaultin) = V_2 - V_3 Pol(evalrandom2dbb3in) = V_2 - V_3 Pol(evalrandom2dLeafBlock5in) = V_2 - V_3 Pol(evalrandom2dLeafBlock3in) = V_2 - V_3 Pol(evalrandom2dLeafBlock1in) = V_2 - V_3 Pol(evalrandom2dLeafBlockin) = V_2 - V_3 Pol(evalrandom2dNodeBlock7in) = V_2 - V_3 Pol(evalrandom2dNodeBlockin) = V_2 - V_3 Pol(evalrandom2dNodeBlock9in) = V_2 - V_3 Pol(evalrandom2dbb2in) = V_2 - V_3 Pol(evalrandom2dreturnin) = -V_1 + V_2 Pol(evalrandom2dstop) = -V_1 + V_2 Pol(evalrandom2dbbin) = -V_1 + V_2 - 1 Pol(evalrandom2dentryin) = V_2 Pol(evalrandom2dstart) = V_2 Pol(koat_start) = V_2 orients all transitions weakly and the transition evalrandom2dbb10in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbbin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 >= Ar_0 + 1 ] strictly and produces the following problem: 5: T: (Comp: ?, Cost: 1) evalrandom2dbb9in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb7in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dLeafBlock5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 4 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb9in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 = 3 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 1 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb7in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 = 2 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 2 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlock1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 = 1 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlockin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_3 + 1 ] (Comp: ?, Cost: 1) evalrandom2dLeafBlockin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 = 0 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlock7in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dLeafBlock5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 3 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlock7in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dLeafBlock3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ 2 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlockin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dLeafBlock1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 1 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlockin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dLeafBlockin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlock9in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNodeBlock7in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 2 ] (Comp: ?, Cost: 1) evalrandom2dNodeBlock9in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNodeBlockin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 1 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2dbb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNodeBlock9in(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 2, Cost: 1) evalrandom2dreturnin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dstop(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbbin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_0 + 1, Ar_1, Ar_2, Ar_3)) [ E >= 4 ] (Comp: ?, Cost: 1) evalrandom2dbbin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_0 + 1, Ar_1, Ar_2, Ar_3)) [ 0 >= E + 1 ] (Comp: ?, Cost: 1) evalrandom2dbbin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb2in(Ar_0, Ar_1, Ar_0 + 1, Fresh_0)) [ Fresh_0 >= 0 /\ 3 >= Fresh_0 ] (Comp: 2, Cost: 1) evalrandom2dbb10in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dreturnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= Ar_1 ] (Comp: Ar_1, Cost: 1) evalrandom2dbb10in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbbin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 >= Ar_0 + 1 ] (Comp: 1, Cost: 1) evalrandom2dentryin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2dstart(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dentryin(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dstart(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Repeatedly propagating knowledge in problem 5 produces the following problem: 6: T: (Comp: Ar_1, Cost: 1) evalrandom2dbb9in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: Ar_1, Cost: 1) evalrandom2dbb7in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: Ar_1, Cost: 1) evalrandom2dbb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: 4*Ar_1, Cost: 1) evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: Ar_1, Cost: 1) evalrandom2dbb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: Ar_1, Cost: 1) evalrandom2dLeafBlock5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 4 ] (Comp: Ar_1, Cost: 1) evalrandom2dLeafBlock5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb9in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 = 3 ] (Comp: Ar_1, Cost: 1) evalrandom2dLeafBlock3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 1 >= Ar_3 ] (Comp: Ar_1, Cost: 1) evalrandom2dLeafBlock3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb7in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 = 2 ] (Comp: Ar_1, Cost: 1) evalrandom2dLeafBlock1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 2 ] (Comp: Ar_1, Cost: 1) evalrandom2dLeafBlock1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 = 1 ] (Comp: Ar_1, Cost: 1) evalrandom2dLeafBlockin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_3 + 1 ] (Comp: Ar_1, Cost: 1) evalrandom2dLeafBlockin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 = 0 ] (Comp: Ar_1, Cost: 1) evalrandom2dNodeBlock7in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dLeafBlock5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 3 ] (Comp: Ar_1, Cost: 1) evalrandom2dNodeBlock7in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dLeafBlock3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ 2 >= Ar_3 ] (Comp: Ar_1, Cost: 1) evalrandom2dNodeBlockin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dLeafBlock1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 1 ] (Comp: Ar_1, Cost: 1) evalrandom2dNodeBlockin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dLeafBlockin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_3 ] (Comp: Ar_1, Cost: 1) evalrandom2dNodeBlock9in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNodeBlock7in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 2 ] (Comp: Ar_1, Cost: 1) evalrandom2dNodeBlock9in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNodeBlockin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 1 >= Ar_3 ] (Comp: Ar_1, Cost: 1) evalrandom2dbb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNodeBlock9in(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 2, Cost: 1) evalrandom2dreturnin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dstop(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: Ar_1, Cost: 1) evalrandom2dbbin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_0 + 1, Ar_1, Ar_2, Ar_3)) [ E >= 4 ] (Comp: Ar_1, Cost: 1) evalrandom2dbbin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(Ar_0 + 1, Ar_1, Ar_2, Ar_3)) [ 0 >= E + 1 ] (Comp: Ar_1, Cost: 1) evalrandom2dbbin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb2in(Ar_0, Ar_1, Ar_0 + 1, Fresh_0)) [ Fresh_0 >= 0 /\ 3 >= Fresh_0 ] (Comp: 2, Cost: 1) evalrandom2dbb10in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dreturnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= Ar_1 ] (Comp: Ar_1, Cost: 1) evalrandom2dbb10in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbbin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 >= Ar_0 + 1 ] (Comp: 1, Cost: 1) evalrandom2dentryin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb10in(0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2dstart(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dentryin(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dstart(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Complexity upper bound 27*Ar_1 + 6 Time: 0.274 sec (SMT: 0.198 sec) ---------------------------------------- (2) BOUNDS(1, n^1) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalrandom2dstart 0: evalrandom2dstart -> evalrandom2dentryin : [], cost: 1 1: evalrandom2dentryin -> evalrandom2dbb10in : A'=0, [], cost: 1 2: evalrandom2dbb10in -> evalrandom2dbbin : [ B>=1+A ], cost: 1 3: evalrandom2dbb10in -> evalrandom2dreturnin : [ A>=B ], cost: 1 4: evalrandom2dbbin -> evalrandom2dbb2in : C'=1+A, D'=free, [ free>=0 && 3>=free ], cost: 1 5: evalrandom2dbbin -> evalrandom2dbb10in : A'=1+A, [ 0>=1+free_1 ], cost: 1 6: evalrandom2dbbin -> evalrandom2dbb10in : A'=1+A, [ free_2>=4 ], cost: 1 7: evalrandom2dbb2in -> evalrandom2dNodeBlock9in : [], cost: 1 8: evalrandom2dNodeBlock9in -> evalrandom2dNodeBlockin : [ 1>=D ], cost: 1 9: evalrandom2dNodeBlock9in -> evalrandom2dNodeBlock7in : [ D>=2 ], cost: 1 10: evalrandom2dNodeBlockin -> evalrandom2dLeafBlockin : [ 0>=D ], cost: 1 11: evalrandom2dNodeBlockin -> evalrandom2dLeafBlock1in : [ D>=1 ], cost: 1 12: evalrandom2dLeafBlockin -> evalrandom2dbb3in : [ D==0 ], cost: 1 13: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ 0>=1+D ], cost: 1 14: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ D>=1 ], cost: 1 15: evalrandom2dbb3in -> evalrandom2dbb10in : A'=C, [], cost: 1 16: evalrandom2dLeafBlock1in -> evalrandom2dbb5in : [ D==1 ], cost: 1 17: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ 0>=D ], cost: 1 18: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ D>=2 ], cost: 1 19: evalrandom2dbb5in -> evalrandom2dbb10in : A'=C, [], cost: 1 20: evalrandom2dNodeBlock7in -> evalrandom2dLeafBlock3in : [ 2>=D ], cost: 1 21: evalrandom2dNodeBlock7in -> evalrandom2dLeafBlock5in : [ D>=3 ], cost: 1 22: evalrandom2dLeafBlock3in -> evalrandom2dbb7in : [ D==2 ], cost: 1 23: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ 1>=D ], cost: 1 24: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ D>=3 ], cost: 1 25: evalrandom2dbb7in -> evalrandom2dbb10in : A'=C, [], cost: 1 26: evalrandom2dLeafBlock5in -> evalrandom2dbb9in : [ D==3 ], cost: 1 27: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ 2>=D ], cost: 1 28: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ D>=4 ], cost: 1 29: evalrandom2dbb9in -> evalrandom2dbb10in : A'=C, [], cost: 1 30: evalrandom2dNewDefaultin -> evalrandom2dbb10in : A'=C, [], cost: 1 31: evalrandom2dreturnin -> evalrandom2dstop : [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: evalrandom2dstart -> evalrandom2dentryin : [], cost: 1 Removed unreachable and leaf rules: Start location: evalrandom2dstart 0: evalrandom2dstart -> evalrandom2dentryin : [], cost: 1 1: evalrandom2dentryin -> evalrandom2dbb10in : A'=0, [], cost: 1 2: evalrandom2dbb10in -> evalrandom2dbbin : [ B>=1+A ], cost: 1 4: evalrandom2dbbin -> evalrandom2dbb2in : C'=1+A, D'=free, [ free>=0 && 3>=free ], cost: 1 5: evalrandom2dbbin -> evalrandom2dbb10in : A'=1+A, [ 0>=1+free_1 ], cost: 1 6: evalrandom2dbbin -> evalrandom2dbb10in : A'=1+A, [ free_2>=4 ], cost: 1 7: evalrandom2dbb2in -> evalrandom2dNodeBlock9in : [], cost: 1 8: evalrandom2dNodeBlock9in -> evalrandom2dNodeBlockin : [ 1>=D ], cost: 1 9: evalrandom2dNodeBlock9in -> evalrandom2dNodeBlock7in : [ D>=2 ], cost: 1 10: evalrandom2dNodeBlockin -> evalrandom2dLeafBlockin : [ 0>=D ], cost: 1 11: evalrandom2dNodeBlockin -> evalrandom2dLeafBlock1in : [ D>=1 ], cost: 1 12: evalrandom2dLeafBlockin -> evalrandom2dbb3in : [ D==0 ], cost: 1 13: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ 0>=1+D ], cost: 1 14: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ D>=1 ], cost: 1 15: evalrandom2dbb3in -> evalrandom2dbb10in : A'=C, [], cost: 1 16: evalrandom2dLeafBlock1in -> evalrandom2dbb5in : [ D==1 ], cost: 1 17: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ 0>=D ], cost: 1 18: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ D>=2 ], cost: 1 19: evalrandom2dbb5in -> evalrandom2dbb10in : A'=C, [], cost: 1 20: evalrandom2dNodeBlock7in -> evalrandom2dLeafBlock3in : [ 2>=D ], cost: 1 21: evalrandom2dNodeBlock7in -> evalrandom2dLeafBlock5in : [ D>=3 ], cost: 1 22: evalrandom2dLeafBlock3in -> evalrandom2dbb7in : [ D==2 ], cost: 1 23: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ 1>=D ], cost: 1 24: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ D>=3 ], cost: 1 25: evalrandom2dbb7in -> evalrandom2dbb10in : A'=C, [], cost: 1 26: evalrandom2dLeafBlock5in -> evalrandom2dbb9in : [ D==3 ], cost: 1 27: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ 2>=D ], cost: 1 28: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ D>=4 ], cost: 1 29: evalrandom2dbb9in -> evalrandom2dbb10in : A'=C, [], cost: 1 30: evalrandom2dNewDefaultin -> evalrandom2dbb10in : A'=C, [], cost: 1 Simplified all rules, resulting in: Start location: evalrandom2dstart 0: evalrandom2dstart -> evalrandom2dentryin : [], cost: 1 1: evalrandom2dentryin -> evalrandom2dbb10in : A'=0, [], cost: 1 2: evalrandom2dbb10in -> evalrandom2dbbin : [ B>=1+A ], cost: 1 4: evalrandom2dbbin -> evalrandom2dbb2in : C'=1+A, D'=free, [ free>=0 && 3>=free ], cost: 1 6: evalrandom2dbbin -> evalrandom2dbb10in : A'=1+A, [], cost: 1 7: evalrandom2dbb2in -> evalrandom2dNodeBlock9in : [], cost: 1 8: evalrandom2dNodeBlock9in -> evalrandom2dNodeBlockin : [ 1>=D ], cost: 1 9: evalrandom2dNodeBlock9in -> evalrandom2dNodeBlock7in : [ D>=2 ], cost: 1 10: evalrandom2dNodeBlockin -> evalrandom2dLeafBlockin : [ 0>=D ], cost: 1 11: evalrandom2dNodeBlockin -> evalrandom2dLeafBlock1in : [ D>=1 ], cost: 1 12: evalrandom2dLeafBlockin -> evalrandom2dbb3in : [ D==0 ], cost: 1 13: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ 0>=1+D ], cost: 1 14: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ D>=1 ], cost: 1 15: evalrandom2dbb3in -> evalrandom2dbb10in : A'=C, [], cost: 1 16: evalrandom2dLeafBlock1in -> evalrandom2dbb5in : [ D==1 ], cost: 1 17: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ 0>=D ], cost: 1 18: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ D>=2 ], cost: 1 19: evalrandom2dbb5in -> evalrandom2dbb10in : A'=C, [], cost: 1 20: evalrandom2dNodeBlock7in -> evalrandom2dLeafBlock3in : [ 2>=D ], cost: 1 21: evalrandom2dNodeBlock7in -> evalrandom2dLeafBlock5in : [ D>=3 ], cost: 1 22: evalrandom2dLeafBlock3in -> evalrandom2dbb7in : [ D==2 ], cost: 1 23: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ 1>=D ], cost: 1 24: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ D>=3 ], cost: 1 25: evalrandom2dbb7in -> evalrandom2dbb10in : A'=C, [], cost: 1 26: evalrandom2dLeafBlock5in -> evalrandom2dbb9in : [ D==3 ], cost: 1 27: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ 2>=D ], cost: 1 28: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ D>=4 ], cost: 1 29: evalrandom2dbb9in -> evalrandom2dbb10in : A'=C, [], cost: 1 30: evalrandom2dNewDefaultin -> evalrandom2dbb10in : A'=C, [], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalrandom2dstart 32: evalrandom2dstart -> evalrandom2dbb10in : A'=0, [], cost: 2 2: evalrandom2dbb10in -> evalrandom2dbbin : [ B>=1+A ], cost: 1 6: evalrandom2dbbin -> evalrandom2dbb10in : A'=1+A, [], cost: 1 33: evalrandom2dbbin -> evalrandom2dNodeBlock9in : C'=1+A, D'=free, [ free>=0 && 3>=free ], cost: 2 8: evalrandom2dNodeBlock9in -> evalrandom2dNodeBlockin : [ 1>=D ], cost: 1 9: evalrandom2dNodeBlock9in -> evalrandom2dNodeBlock7in : [ D>=2 ], cost: 1 10: evalrandom2dNodeBlockin -> evalrandom2dLeafBlockin : [ 0>=D ], cost: 1 11: evalrandom2dNodeBlockin -> evalrandom2dLeafBlock1in : [ D>=1 ], cost: 1 13: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ 0>=1+D ], cost: 1 14: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ D>=1 ], cost: 1 34: evalrandom2dLeafBlockin -> evalrandom2dbb10in : A'=C, [ D==0 ], cost: 2 17: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ 0>=D ], cost: 1 18: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ D>=2 ], cost: 1 35: evalrandom2dLeafBlock1in -> evalrandom2dbb10in : A'=C, [ D==1 ], cost: 2 20: evalrandom2dNodeBlock7in -> evalrandom2dLeafBlock3in : [ 2>=D ], cost: 1 21: evalrandom2dNodeBlock7in -> evalrandom2dLeafBlock5in : [ D>=3 ], cost: 1 23: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ 1>=D ], cost: 1 24: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ D>=3 ], cost: 1 36: evalrandom2dLeafBlock3in -> evalrandom2dbb10in : A'=C, [ D==2 ], cost: 2 27: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ 2>=D ], cost: 1 28: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ D>=4 ], cost: 1 37: evalrandom2dLeafBlock5in -> evalrandom2dbb10in : A'=C, [ D==3 ], cost: 2 30: evalrandom2dNewDefaultin -> evalrandom2dbb10in : A'=C, [], cost: 1 Eliminated locations (on tree-shaped paths): Start location: evalrandom2dstart 32: evalrandom2dstart -> evalrandom2dbb10in : A'=0, [], cost: 2 38: evalrandom2dbb10in -> evalrandom2dbb10in : A'=1+A, [ B>=1+A ], cost: 2 39: evalrandom2dbb10in -> evalrandom2dNodeBlock9in : C'=1+A, D'=free, [ B>=1+A && free>=0 && 3>=free ], cost: 3 40: evalrandom2dNodeBlock9in -> evalrandom2dLeafBlockin : [ 0>=D ], cost: 2 41: evalrandom2dNodeBlock9in -> evalrandom2dLeafBlock1in : [ 1>=D && D>=1 ], cost: 2 42: evalrandom2dNodeBlock9in -> evalrandom2dLeafBlock3in : [ D>=2 && 2>=D ], cost: 2 43: evalrandom2dNodeBlock9in -> evalrandom2dLeafBlock5in : [ D>=3 ], cost: 2 13: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ 0>=1+D ], cost: 1 14: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ D>=1 ], cost: 1 34: evalrandom2dLeafBlockin -> evalrandom2dbb10in : A'=C, [ D==0 ], cost: 2 17: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ 0>=D ], cost: 1 18: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ D>=2 ], cost: 1 35: evalrandom2dLeafBlock1in -> evalrandom2dbb10in : A'=C, [ D==1 ], cost: 2 23: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ 1>=D ], cost: 1 24: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ D>=3 ], cost: 1 36: evalrandom2dLeafBlock3in -> evalrandom2dbb10in : A'=C, [ D==2 ], cost: 2 27: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ 2>=D ], cost: 1 28: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ D>=4 ], cost: 1 37: evalrandom2dLeafBlock5in -> evalrandom2dbb10in : A'=C, [ D==3 ], cost: 2 30: evalrandom2dNewDefaultin -> evalrandom2dbb10in : A'=C, [], cost: 1 Accelerating simple loops of location 2. Accelerating the following rules: 38: evalrandom2dbb10in -> evalrandom2dbb10in : A'=1+A, [ B>=1+A ], cost: 2 Accelerated rule 38 with metering function -A+B, yielding the new rule 44. Removing the simple loops: 38. Accelerated all simple loops using metering functions (where possible): Start location: evalrandom2dstart 32: evalrandom2dstart -> evalrandom2dbb10in : A'=0, [], cost: 2 39: evalrandom2dbb10in -> evalrandom2dNodeBlock9in : C'=1+A, D'=free, [ B>=1+A && free>=0 && 3>=free ], cost: 3 44: evalrandom2dbb10in -> evalrandom2dbb10in : A'=B, [ B>=1+A ], cost: -2*A+2*B 40: evalrandom2dNodeBlock9in -> evalrandom2dLeafBlockin : [ 0>=D ], cost: 2 41: evalrandom2dNodeBlock9in -> evalrandom2dLeafBlock1in : [ 1>=D && D>=1 ], cost: 2 42: evalrandom2dNodeBlock9in -> evalrandom2dLeafBlock3in : [ D>=2 && 2>=D ], cost: 2 43: evalrandom2dNodeBlock9in -> evalrandom2dLeafBlock5in : [ D>=3 ], cost: 2 13: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ 0>=1+D ], cost: 1 14: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ D>=1 ], cost: 1 34: evalrandom2dLeafBlockin -> evalrandom2dbb10in : A'=C, [ D==0 ], cost: 2 17: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ 0>=D ], cost: 1 18: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ D>=2 ], cost: 1 35: evalrandom2dLeafBlock1in -> evalrandom2dbb10in : A'=C, [ D==1 ], cost: 2 23: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ 1>=D ], cost: 1 24: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ D>=3 ], cost: 1 36: evalrandom2dLeafBlock3in -> evalrandom2dbb10in : A'=C, [ D==2 ], cost: 2 27: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ 2>=D ], cost: 1 28: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ D>=4 ], cost: 1 37: evalrandom2dLeafBlock5in -> evalrandom2dbb10in : A'=C, [ D==3 ], cost: 2 30: evalrandom2dNewDefaultin -> evalrandom2dbb10in : A'=C, [], cost: 1 Chained accelerated rules (with incoming rules): Start location: evalrandom2dstart 32: evalrandom2dstart -> evalrandom2dbb10in : A'=0, [], cost: 2 46: evalrandom2dstart -> evalrandom2dbb10in : A'=B, [ B>=1 ], cost: 2+2*B 39: evalrandom2dbb10in -> evalrandom2dNodeBlock9in : C'=1+A, D'=free, [ B>=1+A && free>=0 && 3>=free ], cost: 3 40: evalrandom2dNodeBlock9in -> evalrandom2dLeafBlockin : [ 0>=D ], cost: 2 41: evalrandom2dNodeBlock9in -> evalrandom2dLeafBlock1in : [ 1>=D && D>=1 ], cost: 2 42: evalrandom2dNodeBlock9in -> evalrandom2dLeafBlock3in : [ D>=2 && 2>=D ], cost: 2 43: evalrandom2dNodeBlock9in -> evalrandom2dLeafBlock5in : [ D>=3 ], cost: 2 13: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ 0>=1+D ], cost: 1 14: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ D>=1 ], cost: 1 34: evalrandom2dLeafBlockin -> evalrandom2dbb10in : A'=C, [ D==0 ], cost: 2 47: evalrandom2dLeafBlockin -> evalrandom2dbb10in : A'=B, [ D==0 && B>=1+C ], cost: 2-2*C+2*B 17: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ 0>=D ], cost: 1 18: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ D>=2 ], cost: 1 35: evalrandom2dLeafBlock1in -> evalrandom2dbb10in : A'=C, [ D==1 ], cost: 2 48: evalrandom2dLeafBlock1in -> evalrandom2dbb10in : A'=B, [ D==1 && B>=1+C ], cost: 2-2*C+2*B 23: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ 1>=D ], cost: 1 24: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ D>=3 ], cost: 1 36: evalrandom2dLeafBlock3in -> evalrandom2dbb10in : A'=C, [ D==2 ], cost: 2 49: evalrandom2dLeafBlock3in -> evalrandom2dbb10in : A'=B, [ D==2 && B>=1+C ], cost: 2-2*C+2*B 27: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ 2>=D ], cost: 1 28: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ D>=4 ], cost: 1 37: evalrandom2dLeafBlock5in -> evalrandom2dbb10in : A'=C, [ D==3 ], cost: 2 50: evalrandom2dLeafBlock5in -> evalrandom2dbb10in : A'=B, [ D==3 && B>=1+C ], cost: 2-2*C+2*B 30: evalrandom2dNewDefaultin -> evalrandom2dbb10in : A'=C, [], cost: 1 45: evalrandom2dNewDefaultin -> evalrandom2dbb10in : A'=B, [ B>=1+C ], cost: 1-2*C+2*B Eliminated locations (on tree-shaped paths): Start location: evalrandom2dstart 32: evalrandom2dstart -> evalrandom2dbb10in : A'=0, [], cost: 2 46: evalrandom2dstart -> evalrandom2dbb10in : A'=B, [ B>=1 ], cost: 2+2*B 51: evalrandom2dbb10in -> evalrandom2dLeafBlockin : C'=1+A, D'=free, [ B>=1+A && free>=0 && 0>=free ], cost: 5 52: evalrandom2dbb10in -> evalrandom2dLeafBlock1in : C'=1+A, D'=free, [ B>=1+A && 1>=free && free>=1 ], cost: 5 53: evalrandom2dbb10in -> evalrandom2dLeafBlock3in : C'=1+A, D'=free, [ B>=1+A && free>=2 && 2>=free ], cost: 5 54: evalrandom2dbb10in -> evalrandom2dLeafBlock5in : C'=1+A, D'=free, [ B>=1+A && 3>=free && free>=3 ], cost: 5 13: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ 0>=1+D ], cost: 1 14: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ D>=1 ], cost: 1 34: evalrandom2dLeafBlockin -> evalrandom2dbb10in : A'=C, [ D==0 ], cost: 2 47: evalrandom2dLeafBlockin -> evalrandom2dbb10in : A'=B, [ D==0 && B>=1+C ], cost: 2-2*C+2*B 17: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ 0>=D ], cost: 1 18: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ D>=2 ], cost: 1 35: evalrandom2dLeafBlock1in -> evalrandom2dbb10in : A'=C, [ D==1 ], cost: 2 48: evalrandom2dLeafBlock1in -> evalrandom2dbb10in : A'=B, [ D==1 && B>=1+C ], cost: 2-2*C+2*B 23: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ 1>=D ], cost: 1 24: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ D>=3 ], cost: 1 36: evalrandom2dLeafBlock3in -> evalrandom2dbb10in : A'=C, [ D==2 ], cost: 2 49: evalrandom2dLeafBlock3in -> evalrandom2dbb10in : A'=B, [ D==2 && B>=1+C ], cost: 2-2*C+2*B 27: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ 2>=D ], cost: 1 28: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ D>=4 ], cost: 1 37: evalrandom2dLeafBlock5in -> evalrandom2dbb10in : A'=C, [ D==3 ], cost: 2 50: evalrandom2dLeafBlock5in -> evalrandom2dbb10in : A'=B, [ D==3 && B>=1+C ], cost: 2-2*C+2*B 30: evalrandom2dNewDefaultin -> evalrandom2dbb10in : A'=C, [], cost: 1 45: evalrandom2dNewDefaultin -> evalrandom2dbb10in : A'=B, [ B>=1+C ], cost: 1-2*C+2*B Eliminated locations (on tree-shaped paths): Start location: evalrandom2dstart 32: evalrandom2dstart -> evalrandom2dbb10in : A'=0, [], cost: 2 46: evalrandom2dstart -> evalrandom2dbb10in : A'=B, [ B>=1 ], cost: 2+2*B 55: evalrandom2dbb10in -> evalrandom2dbb10in : A'=1+A, C'=1+A, D'=free, [ B>=1+A && free==0 ], cost: 7 56: evalrandom2dbb10in -> evalrandom2dbb10in : A'=B, C'=1+A, D'=free, [ free==0 && B>=2+A ], cost: 5-2*A+2*B 57: evalrandom2dbb10in -> evalrandom2dbb10in : A'=1+A, C'=1+A, D'=free, [ B>=1+A && free==1 ], cost: 7 58: evalrandom2dbb10in -> evalrandom2dbb10in : A'=B, C'=1+A, D'=free, [ free==1 && B>=2+A ], cost: 5-2*A+2*B 59: evalrandom2dbb10in -> evalrandom2dbb10in : A'=1+A, C'=1+A, D'=free, [ B>=1+A && free==2 ], cost: 7 60: evalrandom2dbb10in -> evalrandom2dbb10in : A'=B, C'=1+A, D'=free, [ free==2 && B>=2+A ], cost: 5-2*A+2*B 61: evalrandom2dbb10in -> evalrandom2dbb10in : A'=1+A, C'=1+A, D'=free, [ B>=1+A && free==3 ], cost: 7 62: evalrandom2dbb10in -> evalrandom2dbb10in : A'=B, C'=1+A, D'=free, [ free==3 && B>=2+A ], cost: 5-2*A+2*B 30: evalrandom2dNewDefaultin -> evalrandom2dbb10in : A'=C, [], cost: 1 45: evalrandom2dNewDefaultin -> evalrandom2dbb10in : A'=B, [ B>=1+C ], cost: 1-2*C+2*B Applied pruning (of leafs and parallel rules): Start location: evalrandom2dstart 32: evalrandom2dstart -> evalrandom2dbb10in : A'=0, [], cost: 2 46: evalrandom2dstart -> evalrandom2dbb10in : A'=B, [ B>=1 ], cost: 2+2*B 56: evalrandom2dbb10in -> evalrandom2dbb10in : A'=B, C'=1+A, D'=free, [ free==0 && B>=2+A ], cost: 5-2*A+2*B 58: evalrandom2dbb10in -> evalrandom2dbb10in : A'=B, C'=1+A, D'=free, [ free==1 && B>=2+A ], cost: 5-2*A+2*B 59: evalrandom2dbb10in -> evalrandom2dbb10in : A'=1+A, C'=1+A, D'=free, [ B>=1+A && free==2 ], cost: 7 60: evalrandom2dbb10in -> evalrandom2dbb10in : A'=B, C'=1+A, D'=free, [ free==2 && B>=2+A ], cost: 5-2*A+2*B 62: evalrandom2dbb10in -> evalrandom2dbb10in : A'=B, C'=1+A, D'=free, [ free==3 && B>=2+A ], cost: 5-2*A+2*B Accelerating simple loops of location 2. Simplified some of the simple loops (and removed duplicate rules). Accelerating the following rules: 56: evalrandom2dbb10in -> evalrandom2dbb10in : A'=B, C'=1+A, D'=0, [ B>=2+A ], cost: 5-2*A+2*B 58: evalrandom2dbb10in -> evalrandom2dbb10in : A'=B, C'=1+A, D'=1, [ B>=2+A ], cost: 5-2*A+2*B 59: evalrandom2dbb10in -> evalrandom2dbb10in : A'=1+A, C'=1+A, D'=2, [ B>=1+A ], cost: 7 60: evalrandom2dbb10in -> evalrandom2dbb10in : A'=B, C'=1+A, D'=2, [ B>=2+A ], cost: 5-2*A+2*B 62: evalrandom2dbb10in -> evalrandom2dbb10in : A'=B, C'=1+A, D'=3, [ B>=2+A ], cost: 5-2*A+2*B Found no metering function for rule 56. Found no metering function for rule 58. Accelerated rule 59 with metering function -A+B, yielding the new rule 63. Found no metering function for rule 60. Found no metering function for rule 62. Removing the simple loops: 59. Accelerated all simple loops using metering functions (where possible): Start location: evalrandom2dstart 32: evalrandom2dstart -> evalrandom2dbb10in : A'=0, [], cost: 2 46: evalrandom2dstart -> evalrandom2dbb10in : A'=B, [ B>=1 ], cost: 2+2*B 56: evalrandom2dbb10in -> evalrandom2dbb10in : A'=B, C'=1+A, D'=0, [ B>=2+A ], cost: 5-2*A+2*B 58: evalrandom2dbb10in -> evalrandom2dbb10in : A'=B, C'=1+A, D'=1, [ B>=2+A ], cost: 5-2*A+2*B 60: evalrandom2dbb10in -> evalrandom2dbb10in : A'=B, C'=1+A, D'=2, [ B>=2+A ], cost: 5-2*A+2*B 62: evalrandom2dbb10in -> evalrandom2dbb10in : A'=B, C'=1+A, D'=3, [ B>=2+A ], cost: 5-2*A+2*B 63: evalrandom2dbb10in -> evalrandom2dbb10in : A'=B, C'=B, D'=2, [ B>=1+A ], cost: -7*A+7*B Chained accelerated rules (with incoming rules): Start location: evalrandom2dstart 32: evalrandom2dstart -> evalrandom2dbb10in : A'=0, [], cost: 2 46: evalrandom2dstart -> evalrandom2dbb10in : A'=B, [ B>=1 ], cost: 2+2*B 64: evalrandom2dstart -> evalrandom2dbb10in : A'=B, C'=1, D'=0, [ B>=2 ], cost: 7+2*B 65: evalrandom2dstart -> evalrandom2dbb10in : A'=B, C'=1, D'=1, [ B>=2 ], cost: 7+2*B 66: evalrandom2dstart -> evalrandom2dbb10in : A'=B, C'=1, D'=2, [ B>=2 ], cost: 7+2*B 67: evalrandom2dstart -> evalrandom2dbb10in : A'=B, C'=1, D'=3, [ B>=2 ], cost: 7+2*B 68: evalrandom2dstart -> evalrandom2dbb10in : A'=B, C'=B, D'=2, [ B>=1 ], cost: 2+7*B Removed unreachable locations (and leaf rules with constant cost): Start location: evalrandom2dstart 46: evalrandom2dstart -> evalrandom2dbb10in : A'=B, [ B>=1 ], cost: 2+2*B 64: evalrandom2dstart -> evalrandom2dbb10in : A'=B, C'=1, D'=0, [ B>=2 ], cost: 7+2*B 65: evalrandom2dstart -> evalrandom2dbb10in : A'=B, C'=1, D'=1, [ B>=2 ], cost: 7+2*B 66: evalrandom2dstart -> evalrandom2dbb10in : A'=B, C'=1, D'=2, [ B>=2 ], cost: 7+2*B 67: evalrandom2dstart -> evalrandom2dbb10in : A'=B, C'=1, D'=3, [ B>=2 ], cost: 7+2*B 68: evalrandom2dstart -> evalrandom2dbb10in : A'=B, C'=B, D'=2, [ B>=1 ], cost: 2+7*B ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalrandom2dstart 46: evalrandom2dstart -> evalrandom2dbb10in : A'=B, [ B>=1 ], cost: 2+2*B 67: evalrandom2dstart -> evalrandom2dbb10in : A'=B, C'=1, D'=3, [ B>=2 ], cost: 7+2*B 68: evalrandom2dstart -> evalrandom2dbb10in : A'=B, C'=B, D'=2, [ B>=1 ], cost: 2+7*B Computing asymptotic complexity for rule 46 Solved the limit problem by the following transformations: Created initial limit problem: 2+2*B (+), B (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {B==n} resulting limit problem: [solved] Solution: B / n Resulting cost 2+2*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: 2+2*n Rule cost: 2+2*B Rule guard: [ B>=1 ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (4) BOUNDS(n^1, INF)