/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.koat /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^1)) proof of /export/starexec/sandbox2/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, 420 ms] (2) BOUNDS(1, n^1) (3) Loat Proof [FINISHED, 3232 ms] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: eval_random2d_start(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_bb0_in(v_1, v_2, v_N, v_i_0)) :|: TRUE eval_random2d_bb0_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_0(v_1, v_2, v_N, v_i_0)) :|: TRUE eval_random2d_0(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_1(v_1, v_2, v_N, v_i_0)) :|: TRUE eval_random2d_1(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_2(v_1, v_2, v_N, v_i_0)) :|: TRUE eval_random2d_2(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_3(v_1, v_2, v_N, v_i_0)) :|: TRUE eval_random2d_3(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_4(v_1, v_2, v_N, v_i_0)) :|: TRUE eval_random2d_4(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_5(v_1, v_2, v_N, v_i_0)) :|: TRUE eval_random2d_5(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_6(v_1, v_2, v_N, v_i_0)) :|: TRUE eval_random2d_6(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_7(v_1, v_2, v_N, v_i_0)) :|: TRUE eval_random2d_7(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_8(v_1, v_2, v_N, v_i_0)) :|: TRUE eval_random2d_8(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_9(v_1, v_2, v_N, v_i_0)) :|: TRUE eval_random2d_9(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_10(v_1, v_2, v_N, v_i_0)) :|: TRUE eval_random2d_10(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_bb1_in(v_1, v_2, v_N, 0)) :|: TRUE eval_random2d_bb1_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_bb2_in(v_1, v_2, v_N, v_i_0)) :|: v_i_0 < v_N eval_random2d_bb1_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_bb8_in(v_1, v_2, v_N, v_i_0)) :|: v_i_0 >= v_N eval_random2d_bb2_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_12(v_i_0 + 1, v_2, v_N, v_i_0)) :|: TRUE eval_random2d_12(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_13(v_1, nondef_0, v_N, v_i_0)) :|: TRUE eval_random2d_13(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_bb3_in(v_1, v_2, v_N, v_i_0)) :|: v_2 >= 0 && v_2 <= 3 eval_random2d_13(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_bb1_in(v_1, v_2, v_N, v_1)) :|: v_2 < 0 eval_random2d_13(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_bb1_in(v_1, v_2, v_N, v_1)) :|: v_2 > 3 eval_random2d_bb3_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_NodeBlock9_in(v_1, v_2, v_N, v_i_0)) :|: TRUE eval_random2d_NodeBlock9_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_NodeBlock_in(v_1, v_2, v_N, v_i_0)) :|: v_2 < 2 eval_random2d_NodeBlock9_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_NodeBlock7_in(v_1, v_2, v_N, v_i_0)) :|: v_2 >= 2 eval_random2d_NodeBlock_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_LeafBlock_in(v_1, v_2, v_N, v_i_0)) :|: v_2 < 1 eval_random2d_NodeBlock_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_LeafBlock1_in(v_1, v_2, v_N, v_i_0)) :|: v_2 >= 1 eval_random2d_LeafBlock_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_bb4_in(v_1, v_2, v_N, v_i_0)) :|: v_2 >= 0 && v_2 <= 0 eval_random2d_LeafBlock_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_NewDefault_in(v_1, v_2, v_N, v_i_0)) :|: v_2 < 0 eval_random2d_LeafBlock_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_NewDefault_in(v_1, v_2, v_N, v_i_0)) :|: v_2 > 0 eval_random2d_bb4_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_bb1_in(v_1, v_2, v_N, v_1)) :|: TRUE eval_random2d_LeafBlock1_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_bb5_in(v_1, v_2, v_N, v_i_0)) :|: v_2 >= 1 && v_2 <= 1 eval_random2d_LeafBlock1_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_NewDefault_in(v_1, v_2, v_N, v_i_0)) :|: v_2 < 1 eval_random2d_LeafBlock1_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_NewDefault_in(v_1, v_2, v_N, v_i_0)) :|: v_2 > 1 eval_random2d_bb5_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_bb1_in(v_1, v_2, v_N, v_1)) :|: TRUE eval_random2d_NodeBlock7_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_LeafBlock3_in(v_1, v_2, v_N, v_i_0)) :|: v_2 < 3 eval_random2d_NodeBlock7_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_LeafBlock5_in(v_1, v_2, v_N, v_i_0)) :|: v_2 >= 3 eval_random2d_LeafBlock3_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_bb6_in(v_1, v_2, v_N, v_i_0)) :|: v_2 >= 2 && v_2 <= 2 eval_random2d_LeafBlock3_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_NewDefault_in(v_1, v_2, v_N, v_i_0)) :|: v_2 < 2 eval_random2d_LeafBlock3_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_NewDefault_in(v_1, v_2, v_N, v_i_0)) :|: v_2 > 2 eval_random2d_bb6_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_bb1_in(v_1, v_2, v_N, v_1)) :|: TRUE eval_random2d_LeafBlock5_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_bb7_in(v_1, v_2, v_N, v_i_0)) :|: v_2 >= 3 && v_2 <= 3 eval_random2d_LeafBlock5_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_NewDefault_in(v_1, v_2, v_N, v_i_0)) :|: v_2 < 3 eval_random2d_LeafBlock5_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_NewDefault_in(v_1, v_2, v_N, v_i_0)) :|: v_2 > 3 eval_random2d_bb7_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_bb1_in(v_1, v_2, v_N, v_1)) :|: TRUE eval_random2d_NewDefault_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_bb1_in(v_1, v_2, v_N, v_1)) :|: TRUE eval_random2d_bb8_in(v_1, v_2, v_N, v_i_0) -> Com_1(eval_random2d_stop(v_1, v_2, v_N, v_i_0)) :|: TRUE The start-symbols are:[eval_random2d_start_4] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 29*Ar_1 + 17) Initial complexity problem: 1: T: (Comp: ?, Cost: 1) evalrandom2dstart(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb0in(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb0in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d0(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2d0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d1(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2d1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d2(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2d2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d3(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2d3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d4(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2d4(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d5(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2d5(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d6(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2d6(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d7(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2d7(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d8(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2d8(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d9(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2d9(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d10(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2d10(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb2in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 >= Ar_0 + 1 ] (Comp: ?, Cost: 1) evalrandom2dbb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb8in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= Ar_1 ] (Comp: ?, Cost: 1) evalrandom2dbb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d12(Ar_0, Ar_1, Ar_0 + 1, Ar_3)) (Comp: ?, Cost: 1) evalrandom2d12(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d13(Ar_0, Ar_1, Ar_2, Fresh_0)) (Comp: ?, Cost: 1) evalrandom2d13(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 0 /\ 3 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2d13(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_3 + 1 ] (Comp: ?, Cost: 1) evalrandom2d13(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 4 ] (Comp: ?, Cost: 1) evalrandom2dbb3in(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(evalrandom2dbb4in(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) evalrandom2dbb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(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(evalrandom2dbb1in(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(evalrandom2dbb6in(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) evalrandom2dbb6in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dLeafBlock5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb7in(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) evalrandom2dbb7in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb8in(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) evalrandom2dbb7in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb6in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(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(evalrandom2dbb7in(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(evalrandom2dbb6in(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(evalrandom2dbb4in(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) evalrandom2dbb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNodeBlock9in(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2d13(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 4 ] (Comp: ?, Cost: 1) evalrandom2d13(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_3 + 1 ] (Comp: ?, Cost: 1) evalrandom2d13(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 0 /\ 3 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2d12(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d13(Ar_0, Ar_1, Ar_2, Fresh_0)) (Comp: ?, Cost: 1) evalrandom2dbb8in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dstop(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d12(Ar_0, Ar_1, Ar_0 + 1, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb8in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= Ar_1 ] (Comp: ?, Cost: 1) evalrandom2dbb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb2in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 >= Ar_0 + 1 ] (Comp: ?, Cost: 1) evalrandom2d10(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2d9(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d10(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2d8(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d9(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2d7(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d8(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2d6(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d7(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2d5(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d6(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2d4(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d5(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2d3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d4(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2d2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d3(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2d1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d2(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2d0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d1(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb0in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d0(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dstart(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb0in(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) evalrandom2dbb7in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb6in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(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(evalrandom2dbb7in(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(evalrandom2dbb6in(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(evalrandom2dbb4in(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) evalrandom2dbb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNodeBlock9in(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2d13(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 4 ] (Comp: ?, Cost: 1) evalrandom2d13(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_3 + 1 ] (Comp: ?, Cost: 1) evalrandom2d13(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 0 /\ 3 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2d12(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d13(Ar_0, Ar_1, Ar_2, Fresh_0)) (Comp: ?, Cost: 1) evalrandom2dbb8in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dstop(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d12(Ar_0, Ar_1, Ar_0 + 1, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb8in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= Ar_1 ] (Comp: ?, Cost: 1) evalrandom2dbb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb2in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 >= Ar_0 + 1 ] (Comp: 1, Cost: 1) evalrandom2d10(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d9(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d10(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d8(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d9(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d7(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d8(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d6(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d7(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d5(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d6(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d4(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d5(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d4(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d3(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d2(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d1(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2dbb0in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d0(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2dstart(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb0in(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(evalrandom2dbb7in) = 2 Pol(evalrandom2dbb1in) = 2 Pol(evalrandom2dbb6in) = 2 Pol(evalrandom2dbb5in) = 2 Pol(evalrandom2dNewDefaultin) = 2 Pol(evalrandom2dbb4in) = 2 Pol(evalrandom2dLeafBlock5in) = 2 Pol(evalrandom2dLeafBlock3in) = 2 Pol(evalrandom2dLeafBlock1in) = 2 Pol(evalrandom2dLeafBlockin) = 2 Pol(evalrandom2dNodeBlock7in) = 2 Pol(evalrandom2dNodeBlockin) = 2 Pol(evalrandom2dNodeBlock9in) = 2 Pol(evalrandom2dbb3in) = 2 Pol(evalrandom2d13) = 2 Pol(evalrandom2d12) = 2 Pol(evalrandom2dbb8in) = 1 Pol(evalrandom2dstop) = 0 Pol(evalrandom2dbb2in) = 2 Pol(evalrandom2d10) = 2 Pol(evalrandom2d9) = 2 Pol(evalrandom2d8) = 2 Pol(evalrandom2d7) = 2 Pol(evalrandom2d6) = 2 Pol(evalrandom2d5) = 2 Pol(evalrandom2d4) = 2 Pol(evalrandom2d3) = 2 Pol(evalrandom2d2) = 2 Pol(evalrandom2d1) = 2 Pol(evalrandom2d0) = 2 Pol(evalrandom2dbb0in) = 2 Pol(evalrandom2dstart) = 2 Pol(koat_start) = 2 orients all transitions weakly and the transitions evalrandom2dbb8in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dstop(Ar_0, Ar_1, Ar_2, Ar_3)) evalrandom2dbb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb8in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= Ar_1 ] strictly and produces the following problem: 4: T: (Comp: ?, Cost: 1) evalrandom2dbb7in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb6in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(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(evalrandom2dbb7in(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(evalrandom2dbb6in(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(evalrandom2dbb4in(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) evalrandom2dbb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNodeBlock9in(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2d13(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 4 ] (Comp: ?, Cost: 1) evalrandom2d13(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_3 + 1 ] (Comp: ?, Cost: 1) evalrandom2d13(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 0 /\ 3 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2d12(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d13(Ar_0, Ar_1, Ar_2, Fresh_0)) (Comp: 2, Cost: 1) evalrandom2dbb8in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dstop(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d12(Ar_0, Ar_1, Ar_0 + 1, Ar_3)) (Comp: 2, Cost: 1) evalrandom2dbb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb8in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= Ar_1 ] (Comp: ?, Cost: 1) evalrandom2dbb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb2in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 >= Ar_0 + 1 ] (Comp: 1, Cost: 1) evalrandom2d10(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d9(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d10(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d8(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d9(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d7(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d8(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d6(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d7(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d5(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d6(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d4(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d5(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d4(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d3(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d2(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d1(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2dbb0in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d0(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2dstart(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb0in(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(evalrandom2dbb7in) = V_2 - V_3 Pol(evalrandom2dbb1in) = -V_1 + V_2 Pol(evalrandom2dbb6in) = V_2 - V_3 Pol(evalrandom2dbb5in) = V_2 - V_3 Pol(evalrandom2dNewDefaultin) = V_2 - V_3 Pol(evalrandom2dbb4in) = 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(evalrandom2dbb3in) = V_2 - V_3 Pol(evalrandom2d13) = V_2 - V_3 Pol(evalrandom2d12) = V_2 - V_3 Pol(evalrandom2dbb8in) = -V_1 + V_2 Pol(evalrandom2dstop) = -V_1 + V_2 Pol(evalrandom2dbb2in) = -V_1 + V_2 - 1 Pol(evalrandom2d10) = V_2 Pol(evalrandom2d9) = V_2 Pol(evalrandom2d8) = V_2 Pol(evalrandom2d7) = V_2 Pol(evalrandom2d6) = V_2 Pol(evalrandom2d5) = V_2 Pol(evalrandom2d4) = V_2 Pol(evalrandom2d3) = V_2 Pol(evalrandom2d2) = V_2 Pol(evalrandom2d1) = V_2 Pol(evalrandom2d0) = V_2 Pol(evalrandom2dbb0in) = V_2 Pol(evalrandom2dstart) = V_2 Pol(koat_start) = V_2 orients all transitions weakly and the transition evalrandom2dbb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb2in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 >= Ar_0 + 1 ] strictly and produces the following problem: 5: T: (Comp: ?, Cost: 1) evalrandom2dbb7in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb6in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dNewDefaultin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(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(evalrandom2dbb7in(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(evalrandom2dbb6in(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(evalrandom2dbb4in(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) evalrandom2dbb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNodeBlock9in(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2d13(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 4 ] (Comp: ?, Cost: 1) evalrandom2d13(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_3 + 1 ] (Comp: ?, Cost: 1) evalrandom2d13(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 0 /\ 3 >= Ar_3 ] (Comp: ?, Cost: 1) evalrandom2d12(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d13(Ar_0, Ar_1, Ar_2, Fresh_0)) (Comp: 2, Cost: 1) evalrandom2dbb8in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dstop(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalrandom2dbb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d12(Ar_0, Ar_1, Ar_0 + 1, Ar_3)) (Comp: 2, Cost: 1) evalrandom2dbb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb8in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= Ar_1 ] (Comp: Ar_1, Cost: 1) evalrandom2dbb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb2in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 >= Ar_0 + 1 ] (Comp: 1, Cost: 1) evalrandom2d10(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d9(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d10(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d8(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d9(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d7(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d8(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d6(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d7(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d5(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d6(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d4(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d5(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d4(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d3(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d2(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d1(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2dbb0in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d0(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2dstart(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb0in(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) evalrandom2dbb7in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: Ar_1, Cost: 1) evalrandom2dbb6in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: Ar_1, Cost: 1) evalrandom2dbb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(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(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) (Comp: Ar_1, Cost: 1) evalrandom2dbb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(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(evalrandom2dbb7in(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(evalrandom2dbb6in(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(evalrandom2dbb4in(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) evalrandom2dbb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dNodeBlock9in(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: Ar_1, Cost: 1) evalrandom2d13(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 4 ] (Comp: Ar_1, Cost: 1) evalrandom2d13(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(Ar_2, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_3 + 1 ] (Comp: Ar_1, Cost: 1) evalrandom2d13(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 0 /\ 3 >= Ar_3 ] (Comp: Ar_1, Cost: 1) evalrandom2d12(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d13(Ar_0, Ar_1, Ar_2, Fresh_0)) (Comp: 2, Cost: 1) evalrandom2dbb8in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dstop(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: Ar_1, Cost: 1) evalrandom2dbb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d12(Ar_0, Ar_1, Ar_0 + 1, Ar_3)) (Comp: 2, Cost: 1) evalrandom2dbb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb8in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= Ar_1 ] (Comp: Ar_1, Cost: 1) evalrandom2dbb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb2in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 >= Ar_0 + 1 ] (Comp: 1, Cost: 1) evalrandom2d10(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb1in(0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d9(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d10(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d8(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d9(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d7(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d8(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d6(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d7(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d5(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d6(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d4(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d5(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d3(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d4(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d2(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d3(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d1(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d2(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2d0(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d1(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2dbb0in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2d0(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalrandom2dstart(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalrandom2dbb0in(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 29*Ar_1 + 17 Time: 0.376 sec (SMT: 0.239 sec) ---------------------------------------- (2) BOUNDS(1, n^1) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalrandom2dstart 0: evalrandom2dstart -> evalrandom2dbb0in : [], cost: 1 1: evalrandom2dbb0in -> evalrandom2d0 : [], cost: 1 2: evalrandom2d0 -> evalrandom2d1 : [], cost: 1 3: evalrandom2d1 -> evalrandom2d2 : [], cost: 1 4: evalrandom2d2 -> evalrandom2d3 : [], cost: 1 5: evalrandom2d3 -> evalrandom2d4 : [], cost: 1 6: evalrandom2d4 -> evalrandom2d5 : [], cost: 1 7: evalrandom2d5 -> evalrandom2d6 : [], cost: 1 8: evalrandom2d6 -> evalrandom2d7 : [], cost: 1 9: evalrandom2d7 -> evalrandom2d8 : [], cost: 1 10: evalrandom2d8 -> evalrandom2d9 : [], cost: 1 11: evalrandom2d9 -> evalrandom2d10 : [], cost: 1 12: evalrandom2d10 -> evalrandom2dbb1in : A'=0, [], cost: 1 13: evalrandom2dbb1in -> evalrandom2dbb2in : [ B>=1+A ], cost: 1 14: evalrandom2dbb1in -> evalrandom2dbb8in : [ A>=B ], cost: 1 15: evalrandom2dbb2in -> evalrandom2d12 : C'=1+A, [], cost: 1 16: evalrandom2d12 -> evalrandom2d13 : D'=free, [], cost: 1 17: evalrandom2d13 -> evalrandom2dbb3in : [ D>=0 && 3>=D ], cost: 1 18: evalrandom2d13 -> evalrandom2dbb1in : A'=C, [ 0>=1+D ], cost: 1 19: evalrandom2d13 -> evalrandom2dbb1in : A'=C, [ D>=4 ], cost: 1 20: evalrandom2dbb3in -> evalrandom2dNodeBlock9in : [], cost: 1 21: evalrandom2dNodeBlock9in -> evalrandom2dNodeBlockin : [ 1>=D ], cost: 1 22: evalrandom2dNodeBlock9in -> evalrandom2dNodeBlock7in : [ D>=2 ], cost: 1 23: evalrandom2dNodeBlockin -> evalrandom2dLeafBlockin : [ 0>=D ], cost: 1 24: evalrandom2dNodeBlockin -> evalrandom2dLeafBlock1in : [ D>=1 ], cost: 1 25: evalrandom2dLeafBlockin -> evalrandom2dbb4in : [ D==0 ], cost: 1 26: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ 0>=1+D ], cost: 1 27: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ D>=1 ], cost: 1 28: evalrandom2dbb4in -> evalrandom2dbb1in : A'=C, [], cost: 1 29: evalrandom2dLeafBlock1in -> evalrandom2dbb5in : [ D==1 ], cost: 1 30: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ 0>=D ], cost: 1 31: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ D>=2 ], cost: 1 32: evalrandom2dbb5in -> evalrandom2dbb1in : A'=C, [], cost: 1 33: evalrandom2dNodeBlock7in -> evalrandom2dLeafBlock3in : [ 2>=D ], cost: 1 34: evalrandom2dNodeBlock7in -> evalrandom2dLeafBlock5in : [ D>=3 ], cost: 1 35: evalrandom2dLeafBlock3in -> evalrandom2dbb6in : [ D==2 ], cost: 1 36: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ 1>=D ], cost: 1 37: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ D>=3 ], cost: 1 38: evalrandom2dbb6in -> evalrandom2dbb1in : A'=C, [], cost: 1 39: evalrandom2dLeafBlock5in -> evalrandom2dbb7in : [ D==3 ], cost: 1 40: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ 2>=D ], cost: 1 41: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ D>=4 ], cost: 1 42: evalrandom2dbb7in -> evalrandom2dbb1in : A'=C, [], cost: 1 43: evalrandom2dNewDefaultin -> evalrandom2dbb1in : A'=C, [], cost: 1 44: evalrandom2dbb8in -> evalrandom2dstop : [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: evalrandom2dstart -> evalrandom2dbb0in : [], cost: 1 Removed unreachable and leaf rules: Start location: evalrandom2dstart 0: evalrandom2dstart -> evalrandom2dbb0in : [], cost: 1 1: evalrandom2dbb0in -> evalrandom2d0 : [], cost: 1 2: evalrandom2d0 -> evalrandom2d1 : [], cost: 1 3: evalrandom2d1 -> evalrandom2d2 : [], cost: 1 4: evalrandom2d2 -> evalrandom2d3 : [], cost: 1 5: evalrandom2d3 -> evalrandom2d4 : [], cost: 1 6: evalrandom2d4 -> evalrandom2d5 : [], cost: 1 7: evalrandom2d5 -> evalrandom2d6 : [], cost: 1 8: evalrandom2d6 -> evalrandom2d7 : [], cost: 1 9: evalrandom2d7 -> evalrandom2d8 : [], cost: 1 10: evalrandom2d8 -> evalrandom2d9 : [], cost: 1 11: evalrandom2d9 -> evalrandom2d10 : [], cost: 1 12: evalrandom2d10 -> evalrandom2dbb1in : A'=0, [], cost: 1 13: evalrandom2dbb1in -> evalrandom2dbb2in : [ B>=1+A ], cost: 1 15: evalrandom2dbb2in -> evalrandom2d12 : C'=1+A, [], cost: 1 16: evalrandom2d12 -> evalrandom2d13 : D'=free, [], cost: 1 17: evalrandom2d13 -> evalrandom2dbb3in : [ D>=0 && 3>=D ], cost: 1 18: evalrandom2d13 -> evalrandom2dbb1in : A'=C, [ 0>=1+D ], cost: 1 19: evalrandom2d13 -> evalrandom2dbb1in : A'=C, [ D>=4 ], cost: 1 20: evalrandom2dbb3in -> evalrandom2dNodeBlock9in : [], cost: 1 21: evalrandom2dNodeBlock9in -> evalrandom2dNodeBlockin : [ 1>=D ], cost: 1 22: evalrandom2dNodeBlock9in -> evalrandom2dNodeBlock7in : [ D>=2 ], cost: 1 23: evalrandom2dNodeBlockin -> evalrandom2dLeafBlockin : [ 0>=D ], cost: 1 24: evalrandom2dNodeBlockin -> evalrandom2dLeafBlock1in : [ D>=1 ], cost: 1 25: evalrandom2dLeafBlockin -> evalrandom2dbb4in : [ D==0 ], cost: 1 26: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ 0>=1+D ], cost: 1 27: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ D>=1 ], cost: 1 28: evalrandom2dbb4in -> evalrandom2dbb1in : A'=C, [], cost: 1 29: evalrandom2dLeafBlock1in -> evalrandom2dbb5in : [ D==1 ], cost: 1 30: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ 0>=D ], cost: 1 31: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ D>=2 ], cost: 1 32: evalrandom2dbb5in -> evalrandom2dbb1in : A'=C, [], cost: 1 33: evalrandom2dNodeBlock7in -> evalrandom2dLeafBlock3in : [ 2>=D ], cost: 1 34: evalrandom2dNodeBlock7in -> evalrandom2dLeafBlock5in : [ D>=3 ], cost: 1 35: evalrandom2dLeafBlock3in -> evalrandom2dbb6in : [ D==2 ], cost: 1 36: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ 1>=D ], cost: 1 37: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ D>=3 ], cost: 1 38: evalrandom2dbb6in -> evalrandom2dbb1in : A'=C, [], cost: 1 39: evalrandom2dLeafBlock5in -> evalrandom2dbb7in : [ D==3 ], cost: 1 40: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ 2>=D ], cost: 1 41: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ D>=4 ], cost: 1 42: evalrandom2dbb7in -> evalrandom2dbb1in : A'=C, [], cost: 1 43: evalrandom2dNewDefaultin -> evalrandom2dbb1in : A'=C, [], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalrandom2dstart 56: evalrandom2dstart -> evalrandom2dbb1in : A'=0, [], cost: 13 58: evalrandom2dbb1in -> evalrandom2d13 : C'=1+A, D'=free, [ B>=1+A ], cost: 3 18: evalrandom2d13 -> evalrandom2dbb1in : A'=C, [ 0>=1+D ], cost: 1 19: evalrandom2d13 -> evalrandom2dbb1in : A'=C, [ D>=4 ], cost: 1 59: evalrandom2d13 -> evalrandom2dNodeBlock9in : [ D>=0 && 3>=D ], cost: 2 21: evalrandom2dNodeBlock9in -> evalrandom2dNodeBlockin : [ 1>=D ], cost: 1 22: evalrandom2dNodeBlock9in -> evalrandom2dNodeBlock7in : [ D>=2 ], cost: 1 23: evalrandom2dNodeBlockin -> evalrandom2dLeafBlockin : [ 0>=D ], cost: 1 24: evalrandom2dNodeBlockin -> evalrandom2dLeafBlock1in : [ D>=1 ], cost: 1 26: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ 0>=1+D ], cost: 1 27: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ D>=1 ], cost: 1 60: evalrandom2dLeafBlockin -> evalrandom2dbb1in : A'=C, [ D==0 ], cost: 2 30: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ 0>=D ], cost: 1 31: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ D>=2 ], cost: 1 61: evalrandom2dLeafBlock1in -> evalrandom2dbb1in : A'=C, [ D==1 ], cost: 2 33: evalrandom2dNodeBlock7in -> evalrandom2dLeafBlock3in : [ 2>=D ], cost: 1 34: evalrandom2dNodeBlock7in -> evalrandom2dLeafBlock5in : [ D>=3 ], cost: 1 36: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ 1>=D ], cost: 1 37: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ D>=3 ], cost: 1 62: evalrandom2dLeafBlock3in -> evalrandom2dbb1in : A'=C, [ D==2 ], cost: 2 40: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ 2>=D ], cost: 1 41: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ D>=4 ], cost: 1 63: evalrandom2dLeafBlock5in -> evalrandom2dbb1in : A'=C, [ D==3 ], cost: 2 43: evalrandom2dNewDefaultin -> evalrandom2dbb1in : A'=C, [], cost: 1 Eliminated locations (on tree-shaped paths): Start location: evalrandom2dstart 56: evalrandom2dstart -> evalrandom2dbb1in : A'=0, [], cost: 13 64: evalrandom2dbb1in -> evalrandom2dbb1in : A'=1+A, C'=1+A, D'=free, [ B>=1+A && 0>=1+free ], cost: 4 65: evalrandom2dbb1in -> evalrandom2dbb1in : A'=1+A, C'=1+A, D'=free, [ B>=1+A && free>=4 ], cost: 4 66: evalrandom2dbb1in -> evalrandom2dNodeBlock9in : C'=1+A, D'=free, [ B>=1+A && free>=0 && 3>=free ], cost: 5 67: evalrandom2dNodeBlock9in -> evalrandom2dLeafBlockin : [ 0>=D ], cost: 2 68: evalrandom2dNodeBlock9in -> evalrandom2dLeafBlock1in : [ 1>=D && D>=1 ], cost: 2 69: evalrandom2dNodeBlock9in -> evalrandom2dLeafBlock3in : [ D>=2 && 2>=D ], cost: 2 70: evalrandom2dNodeBlock9in -> evalrandom2dLeafBlock5in : [ D>=3 ], cost: 2 26: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ 0>=1+D ], cost: 1 27: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ D>=1 ], cost: 1 60: evalrandom2dLeafBlockin -> evalrandom2dbb1in : A'=C, [ D==0 ], cost: 2 30: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ 0>=D ], cost: 1 31: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ D>=2 ], cost: 1 61: evalrandom2dLeafBlock1in -> evalrandom2dbb1in : A'=C, [ D==1 ], cost: 2 36: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ 1>=D ], cost: 1 37: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ D>=3 ], cost: 1 62: evalrandom2dLeafBlock3in -> evalrandom2dbb1in : A'=C, [ D==2 ], cost: 2 40: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ 2>=D ], cost: 1 41: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ D>=4 ], cost: 1 63: evalrandom2dLeafBlock5in -> evalrandom2dbb1in : A'=C, [ D==3 ], cost: 2 43: evalrandom2dNewDefaultin -> evalrandom2dbb1in : A'=C, [], cost: 1 Accelerating simple loops of location 13. Accelerating the following rules: 64: evalrandom2dbb1in -> evalrandom2dbb1in : A'=1+A, C'=1+A, D'=free, [ B>=1+A && 0>=1+free ], cost: 4 65: evalrandom2dbb1in -> evalrandom2dbb1in : A'=1+A, C'=1+A, D'=free, [ B>=1+A && free>=4 ], cost: 4 Accelerated rule 64 with metering function -A+B, yielding the new rule 71. Accelerated rule 65 with metering function -A+B, yielding the new rule 72. Removing the simple loops: 64 65. Accelerated all simple loops using metering functions (where possible): Start location: evalrandom2dstart 56: evalrandom2dstart -> evalrandom2dbb1in : A'=0, [], cost: 13 66: evalrandom2dbb1in -> evalrandom2dNodeBlock9in : C'=1+A, D'=free, [ B>=1+A && free>=0 && 3>=free ], cost: 5 71: evalrandom2dbb1in -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ B>=1+A && 0>=1+free ], cost: -4*A+4*B 72: evalrandom2dbb1in -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ B>=1+A && free>=4 ], cost: -4*A+4*B 67: evalrandom2dNodeBlock9in -> evalrandom2dLeafBlockin : [ 0>=D ], cost: 2 68: evalrandom2dNodeBlock9in -> evalrandom2dLeafBlock1in : [ 1>=D && D>=1 ], cost: 2 69: evalrandom2dNodeBlock9in -> evalrandom2dLeafBlock3in : [ D>=2 && 2>=D ], cost: 2 70: evalrandom2dNodeBlock9in -> evalrandom2dLeafBlock5in : [ D>=3 ], cost: 2 26: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ 0>=1+D ], cost: 1 27: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ D>=1 ], cost: 1 60: evalrandom2dLeafBlockin -> evalrandom2dbb1in : A'=C, [ D==0 ], cost: 2 30: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ 0>=D ], cost: 1 31: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ D>=2 ], cost: 1 61: evalrandom2dLeafBlock1in -> evalrandom2dbb1in : A'=C, [ D==1 ], cost: 2 36: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ 1>=D ], cost: 1 37: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ D>=3 ], cost: 1 62: evalrandom2dLeafBlock3in -> evalrandom2dbb1in : A'=C, [ D==2 ], cost: 2 40: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ 2>=D ], cost: 1 41: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ D>=4 ], cost: 1 63: evalrandom2dLeafBlock5in -> evalrandom2dbb1in : A'=C, [ D==3 ], cost: 2 43: evalrandom2dNewDefaultin -> evalrandom2dbb1in : A'=C, [], cost: 1 Chained accelerated rules (with incoming rules): Start location: evalrandom2dstart 56: evalrandom2dstart -> evalrandom2dbb1in : A'=0, [], cost: 13 74: evalrandom2dstart -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ B>=1 && 0>=1+free ], cost: 13+4*B 80: evalrandom2dstart -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ B>=1 && free>=4 ], cost: 13+4*B 66: evalrandom2dbb1in -> evalrandom2dNodeBlock9in : C'=1+A, D'=free, [ B>=1+A && free>=0 && 3>=free ], cost: 5 67: evalrandom2dNodeBlock9in -> evalrandom2dLeafBlockin : [ 0>=D ], cost: 2 68: evalrandom2dNodeBlock9in -> evalrandom2dLeafBlock1in : [ 1>=D && D>=1 ], cost: 2 69: evalrandom2dNodeBlock9in -> evalrandom2dLeafBlock3in : [ D>=2 && 2>=D ], cost: 2 70: evalrandom2dNodeBlock9in -> evalrandom2dLeafBlock5in : [ D>=3 ], cost: 2 26: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ 0>=1+D ], cost: 1 27: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ D>=1 ], cost: 1 60: evalrandom2dLeafBlockin -> evalrandom2dbb1in : A'=C, [ D==0 ], cost: 2 75: evalrandom2dLeafBlockin -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ D==0 && B>=1+C && 0>=1+free ], cost: 2-4*C+4*B 81: evalrandom2dLeafBlockin -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ D==0 && B>=1+C && free>=4 ], cost: 2-4*C+4*B 30: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ 0>=D ], cost: 1 31: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ D>=2 ], cost: 1 61: evalrandom2dLeafBlock1in -> evalrandom2dbb1in : A'=C, [ D==1 ], cost: 2 76: evalrandom2dLeafBlock1in -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ D==1 && B>=1+C && 0>=1+free ], cost: 2-4*C+4*B 82: evalrandom2dLeafBlock1in -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ D==1 && B>=1+C && free>=4 ], cost: 2-4*C+4*B 36: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ 1>=D ], cost: 1 37: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ D>=3 ], cost: 1 62: evalrandom2dLeafBlock3in -> evalrandom2dbb1in : A'=C, [ D==2 ], cost: 2 77: evalrandom2dLeafBlock3in -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ D==2 && B>=1+C && 0>=1+free ], cost: 2-4*C+4*B 83: evalrandom2dLeafBlock3in -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ D==2 && B>=1+C && free>=4 ], cost: 2-4*C+4*B 40: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ 2>=D ], cost: 1 41: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ D>=4 ], cost: 1 63: evalrandom2dLeafBlock5in -> evalrandom2dbb1in : A'=C, [ D==3 ], cost: 2 78: evalrandom2dLeafBlock5in -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ D==3 && B>=1+C && 0>=1+free ], cost: 2-4*C+4*B 84: evalrandom2dLeafBlock5in -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ D==3 && B>=1+C && free>=4 ], cost: 2-4*C+4*B 43: evalrandom2dNewDefaultin -> evalrandom2dbb1in : A'=C, [], cost: 1 73: evalrandom2dNewDefaultin -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ B>=1+C && 0>=1+free ], cost: 1-4*C+4*B 79: evalrandom2dNewDefaultin -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ B>=1+C && free>=4 ], cost: 1-4*C+4*B Eliminated locations (on tree-shaped paths): Start location: evalrandom2dstart 56: evalrandom2dstart -> evalrandom2dbb1in : A'=0, [], cost: 13 74: evalrandom2dstart -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ B>=1 && 0>=1+free ], cost: 13+4*B 80: evalrandom2dstart -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ B>=1 && free>=4 ], cost: 13+4*B 85: evalrandom2dbb1in -> evalrandom2dLeafBlockin : C'=1+A, D'=free, [ B>=1+A && free>=0 && 0>=free ], cost: 7 86: evalrandom2dbb1in -> evalrandom2dLeafBlock1in : C'=1+A, D'=free, [ B>=1+A && 1>=free && free>=1 ], cost: 7 87: evalrandom2dbb1in -> evalrandom2dLeafBlock3in : C'=1+A, D'=free, [ B>=1+A && free>=2 && 2>=free ], cost: 7 88: evalrandom2dbb1in -> evalrandom2dLeafBlock5in : C'=1+A, D'=free, [ B>=1+A && 3>=free && free>=3 ], cost: 7 26: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ 0>=1+D ], cost: 1 27: evalrandom2dLeafBlockin -> evalrandom2dNewDefaultin : [ D>=1 ], cost: 1 60: evalrandom2dLeafBlockin -> evalrandom2dbb1in : A'=C, [ D==0 ], cost: 2 75: evalrandom2dLeafBlockin -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ D==0 && B>=1+C && 0>=1+free ], cost: 2-4*C+4*B 81: evalrandom2dLeafBlockin -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ D==0 && B>=1+C && free>=4 ], cost: 2-4*C+4*B 30: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ 0>=D ], cost: 1 31: evalrandom2dLeafBlock1in -> evalrandom2dNewDefaultin : [ D>=2 ], cost: 1 61: evalrandom2dLeafBlock1in -> evalrandom2dbb1in : A'=C, [ D==1 ], cost: 2 76: evalrandom2dLeafBlock1in -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ D==1 && B>=1+C && 0>=1+free ], cost: 2-4*C+4*B 82: evalrandom2dLeafBlock1in -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ D==1 && B>=1+C && free>=4 ], cost: 2-4*C+4*B 36: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ 1>=D ], cost: 1 37: evalrandom2dLeafBlock3in -> evalrandom2dNewDefaultin : [ D>=3 ], cost: 1 62: evalrandom2dLeafBlock3in -> evalrandom2dbb1in : A'=C, [ D==2 ], cost: 2 77: evalrandom2dLeafBlock3in -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ D==2 && B>=1+C && 0>=1+free ], cost: 2-4*C+4*B 83: evalrandom2dLeafBlock3in -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ D==2 && B>=1+C && free>=4 ], cost: 2-4*C+4*B 40: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ 2>=D ], cost: 1 41: evalrandom2dLeafBlock5in -> evalrandom2dNewDefaultin : [ D>=4 ], cost: 1 63: evalrandom2dLeafBlock5in -> evalrandom2dbb1in : A'=C, [ D==3 ], cost: 2 78: evalrandom2dLeafBlock5in -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ D==3 && B>=1+C && 0>=1+free ], cost: 2-4*C+4*B 84: evalrandom2dLeafBlock5in -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ D==3 && B>=1+C && free>=4 ], cost: 2-4*C+4*B 43: evalrandom2dNewDefaultin -> evalrandom2dbb1in : A'=C, [], cost: 1 73: evalrandom2dNewDefaultin -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ B>=1+C && 0>=1+free ], cost: 1-4*C+4*B 79: evalrandom2dNewDefaultin -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ B>=1+C && free>=4 ], cost: 1-4*C+4*B Eliminated locations (on tree-shaped paths): Start location: evalrandom2dstart 56: evalrandom2dstart -> evalrandom2dbb1in : A'=0, [], cost: 13 74: evalrandom2dstart -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ B>=1 && 0>=1+free ], cost: 13+4*B 80: evalrandom2dstart -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ B>=1 && free>=4 ], cost: 13+4*B 89: evalrandom2dbb1in -> evalrandom2dbb1in : A'=1+A, C'=1+A, D'=free, [ B>=1+A && free==0 ], cost: 9 90: evalrandom2dbb1in -> evalrandom2dbb1in : A'=1+A, C'=1+A, D'=free, [ B>=1+A && free==1 ], cost: 9 91: evalrandom2dbb1in -> evalrandom2dbb1in : A'=1+A, C'=1+A, D'=free, [ B>=1+A && free==2 ], cost: 9 92: evalrandom2dbb1in -> evalrandom2dbb1in : A'=1+A, C'=1+A, D'=free, [ B>=1+A && free==3 ], cost: 9 43: evalrandom2dNewDefaultin -> evalrandom2dbb1in : A'=C, [], cost: 1 73: evalrandom2dNewDefaultin -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ B>=1+C && 0>=1+free ], cost: 1-4*C+4*B 79: evalrandom2dNewDefaultin -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ B>=1+C && free>=4 ], cost: 1-4*C+4*B Applied pruning (of leafs and parallel rules): Start location: evalrandom2dstart 56: evalrandom2dstart -> evalrandom2dbb1in : A'=0, [], cost: 13 74: evalrandom2dstart -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ B>=1 && 0>=1+free ], cost: 13+4*B 80: evalrandom2dstart -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ B>=1 && free>=4 ], cost: 13+4*B 89: evalrandom2dbb1in -> evalrandom2dbb1in : A'=1+A, C'=1+A, D'=free, [ B>=1+A && free==0 ], cost: 9 90: evalrandom2dbb1in -> evalrandom2dbb1in : A'=1+A, C'=1+A, D'=free, [ B>=1+A && free==1 ], cost: 9 91: evalrandom2dbb1in -> evalrandom2dbb1in : A'=1+A, C'=1+A, D'=free, [ B>=1+A && free==2 ], cost: 9 92: evalrandom2dbb1in -> evalrandom2dbb1in : A'=1+A, C'=1+A, D'=free, [ B>=1+A && free==3 ], cost: 9 Accelerating simple loops of location 13. Simplified some of the simple loops (and removed duplicate rules). Accelerating the following rules: 89: evalrandom2dbb1in -> evalrandom2dbb1in : A'=1+A, C'=1+A, D'=0, [ B>=1+A ], cost: 9 90: evalrandom2dbb1in -> evalrandom2dbb1in : A'=1+A, C'=1+A, D'=1, [ B>=1+A ], cost: 9 91: evalrandom2dbb1in -> evalrandom2dbb1in : A'=1+A, C'=1+A, D'=2, [ B>=1+A ], cost: 9 92: evalrandom2dbb1in -> evalrandom2dbb1in : A'=1+A, C'=1+A, D'=3, [ B>=1+A ], cost: 9 Accelerated rule 89 with metering function -A+B, yielding the new rule 93. Accelerated rule 90 with metering function -A+B, yielding the new rule 94. Accelerated rule 91 with metering function -A+B, yielding the new rule 95. Accelerated rule 92 with metering function -A+B, yielding the new rule 96. Removing the simple loops: 89 90 91 92. Accelerated all simple loops using metering functions (where possible): Start location: evalrandom2dstart 56: evalrandom2dstart -> evalrandom2dbb1in : A'=0, [], cost: 13 74: evalrandom2dstart -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ B>=1 && 0>=1+free ], cost: 13+4*B 80: evalrandom2dstart -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ B>=1 && free>=4 ], cost: 13+4*B 93: evalrandom2dbb1in -> evalrandom2dbb1in : A'=B, C'=B, D'=0, [ B>=1+A ], cost: -9*A+9*B 94: evalrandom2dbb1in -> evalrandom2dbb1in : A'=B, C'=B, D'=1, [ B>=1+A ], cost: -9*A+9*B 95: evalrandom2dbb1in -> evalrandom2dbb1in : A'=B, C'=B, D'=2, [ B>=1+A ], cost: -9*A+9*B 96: evalrandom2dbb1in -> evalrandom2dbb1in : A'=B, C'=B, D'=3, [ B>=1+A ], cost: -9*A+9*B Chained accelerated rules (with incoming rules): Start location: evalrandom2dstart 56: evalrandom2dstart -> evalrandom2dbb1in : A'=0, [], cost: 13 74: evalrandom2dstart -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ B>=1 && 0>=1+free ], cost: 13+4*B 80: evalrandom2dstart -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ B>=1 && free>=4 ], cost: 13+4*B 97: evalrandom2dstart -> evalrandom2dbb1in : A'=B, C'=B, D'=0, [ B>=1 ], cost: 13+9*B 98: evalrandom2dstart -> evalrandom2dbb1in : A'=B, C'=B, D'=1, [ B>=1 ], cost: 13+9*B 99: evalrandom2dstart -> evalrandom2dbb1in : A'=B, C'=B, D'=2, [ B>=1 ], cost: 13+9*B 100: evalrandom2dstart -> evalrandom2dbb1in : A'=B, C'=B, D'=3, [ B>=1 ], cost: 13+9*B Removed unreachable locations (and leaf rules with constant cost): Start location: evalrandom2dstart 74: evalrandom2dstart -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ B>=1 && 0>=1+free ], cost: 13+4*B 80: evalrandom2dstart -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ B>=1 && free>=4 ], cost: 13+4*B 97: evalrandom2dstart -> evalrandom2dbb1in : A'=B, C'=B, D'=0, [ B>=1 ], cost: 13+9*B 98: evalrandom2dstart -> evalrandom2dbb1in : A'=B, C'=B, D'=1, [ B>=1 ], cost: 13+9*B 99: evalrandom2dstart -> evalrandom2dbb1in : A'=B, C'=B, D'=2, [ B>=1 ], cost: 13+9*B 100: evalrandom2dstart -> evalrandom2dbb1in : A'=B, C'=B, D'=3, [ B>=1 ], cost: 13+9*B ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalrandom2dstart 74: evalrandom2dstart -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ B>=1 && 0>=1+free ], cost: 13+4*B 80: evalrandom2dstart -> evalrandom2dbb1in : A'=B, C'=B, D'=free, [ B>=1 && free>=4 ], cost: 13+4*B 100: evalrandom2dstart -> evalrandom2dbb1in : A'=B, C'=B, D'=3, [ B>=1 ], cost: 13+9*B Computing asymptotic complexity for rule 74 Solved the limit problem by the following transformations: Created initial limit problem: 13+4*B (+), B (+/+!), -free (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {free==-n,B==n} resulting limit problem: [solved] Solution: free / -n B / n Resulting cost 13+4*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: 13+4*n Rule cost: 13+4*B Rule guard: [ B>=1 && 0>=1+free ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (4) BOUNDS(n^1, INF)