WORST_CASE(Omega(1),?) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: l21 0: l0 -> l1 : nDim^0'=nDim^post_1, ni^0'=ni^post_1, nj^0'=nj^post_1, nk^0'=nk^post_1, tmp^0'=tmp^post_1, tmp___0^0'=tmp___0^post_1, tmp___1^0'=tmp___1^post_1, [ nDim^0==nDim^post_1 && ni^0==ni^post_1 && nj^0==nj^post_1 && nk^0==nk^post_1 && tmp^0==tmp^post_1 && tmp___0^0==tmp___0^post_1 && tmp___1^0==tmp___1^post_1 ], cost: 1 30: l1 -> l13 : nDim^0'=nDim^post_31, ni^0'=ni^post_31, nj^0'=nj^post_31, nk^0'=nk^post_31, tmp^0'=tmp^post_31, tmp___0^0'=tmp___0^post_31, tmp___1^0'=tmp___1^post_31, [ nDim^0<=ni^0 && ni^post_31==0 && nDim^0==nDim^post_31 && nj^0==nj^post_31 && nk^0==nk^post_31 && tmp^0==tmp^post_31 && tmp___0^0==tmp___0^post_31 && tmp___1^0==tmp___1^post_31 ], cost: 1 31: l1 -> l2 : nDim^0'=nDim^post_32, ni^0'=ni^post_32, nj^0'=nj^post_32, nk^0'=nk^post_32, tmp^0'=tmp^post_32, tmp___0^0'=tmp___0^post_32, tmp___1^0'=tmp___1^post_32, [ 1+ni^0<=nDim^0 && nj^post_32==0 && nDim^0==nDim^post_32 && ni^0==ni^post_32 && nk^0==nk^post_32 && tmp^0==tmp^post_32 && tmp___0^0==tmp___0^post_32 && tmp___1^0==tmp___1^post_32 ], cost: 1 1: l2 -> l3 : nDim^0'=nDim^post_2, ni^0'=ni^post_2, nj^0'=nj^post_2, nk^0'=nk^post_2, tmp^0'=tmp^post_2, tmp___0^0'=tmp___0^post_2, tmp___1^0'=tmp___1^post_2, [ nDim^0==nDim^post_2 && ni^0==ni^post_2 && nj^0==nj^post_2 && nk^0==nk^post_2 && tmp^0==tmp^post_2 && tmp___0^0==tmp___0^post_2 && tmp___1^0==tmp___1^post_2 ], cost: 1 28: l3 -> l0 : nDim^0'=nDim^post_29, ni^0'=ni^post_29, nj^0'=nj^post_29, nk^0'=nk^post_29, tmp^0'=tmp^post_29, tmp___0^0'=tmp___0^post_29, tmp___1^0'=tmp___1^post_29, [ nDim^0<=nj^0 && ni^post_29==1+ni^0 && nDim^0==nDim^post_29 && nj^0==nj^post_29 && nk^0==nk^post_29 && tmp^0==tmp^post_29 && tmp___0^0==tmp___0^post_29 && tmp___1^0==tmp___1^post_29 ], cost: 1 29: l3 -> l2 : nDim^0'=nDim^post_30, ni^0'=ni^post_30, nj^0'=nj^post_30, nk^0'=nk^post_30, tmp^0'=tmp^post_30, tmp___0^0'=tmp___0^post_30, tmp___1^0'=tmp___1^post_30, [ 1+nj^0<=nDim^0 && nj^post_30==1+nj^0 && nDim^0==nDim^post_30 && ni^0==ni^post_30 && nk^0==nk^post_30 && tmp^0==tmp^post_30 && tmp___0^0==tmp___0^post_30 && tmp___1^0==tmp___1^post_30 ], cost: 1 2: l4 -> l5 : nDim^0'=nDim^post_3, ni^0'=ni^post_3, nj^0'=nj^post_3, nk^0'=nk^post_3, tmp^0'=tmp^post_3, tmp___0^0'=tmp___0^post_3, tmp___1^0'=tmp___1^post_3, [ tmp___1^post_3==1 && nDim^0==nDim^post_3 && ni^0==ni^post_3 && nj^0==nj^post_3 && nk^0==nk^post_3 && tmp^0==tmp^post_3 && tmp___0^0==tmp___0^post_3 ], cost: 1 6: l5 -> l9 : nDim^0'=nDim^post_7, ni^0'=ni^post_7, nj^0'=nj^post_7, nk^0'=nk^post_7, tmp^0'=tmp^post_7, tmp___0^0'=tmp___0^post_7, tmp___1^0'=tmp___1^post_7, [ nDim^0==nDim^post_7 && ni^0==ni^post_7 && nj^0==nj^post_7 && nk^0==nk^post_7 && tmp^0==tmp^post_7 && tmp___0^0==tmp___0^post_7 && tmp___1^0==tmp___1^post_7 ], cost: 1 3: l6 -> l5 : nDim^0'=nDim^post_4, ni^0'=ni^post_4, nj^0'=nj^post_4, nk^0'=nk^post_4, tmp^0'=tmp^post_4, tmp___0^0'=tmp___0^post_4, tmp___1^0'=tmp___1^post_4, [ tmp___1^post_4==1 && nDim^0==nDim^post_4 && ni^0==ni^post_4 && nj^0==nj^post_4 && nk^0==nk^post_4 && tmp^0==tmp^post_4 && tmp___0^0==tmp___0^post_4 ], cost: 1 4: l7 -> l5 : nDim^0'=nDim^post_5, ni^0'=ni^post_5, nj^0'=nj^post_5, nk^0'=nk^post_5, tmp^0'=tmp^post_5, tmp___0^0'=tmp___0^post_5, tmp___1^0'=tmp___1^post_5, [ tmp___1^post_5==1 && nDim^0==nDim^post_5 && ni^0==ni^post_5 && nj^0==nj^post_5 && nk^0==nk^post_5 && tmp^0==tmp^post_5 && tmp___0^0==tmp___0^post_5 ], cost: 1 5: l8 -> l5 : nDim^0'=nDim^post_6, ni^0'=ni^post_6, nj^0'=nj^post_6, nk^0'=nk^post_6, tmp^0'=tmp^post_6, tmp___0^0'=tmp___0^post_6, tmp___1^0'=tmp___1^post_6, [ tmp___1^post_6==1 && nDim^0==nDim^post_6 && ni^0==ni^post_6 && nj^0==nj^post_6 && nk^0==nk^post_6 && tmp^0==tmp^post_6 && tmp___0^0==tmp___0^post_6 ], cost: 1 7: l10 -> l8 : nDim^0'=nDim^post_8, ni^0'=ni^post_8, nj^0'=nj^post_8, nk^0'=nk^post_8, tmp^0'=tmp^post_8, tmp___0^0'=tmp___0^post_8, tmp___1^0'=tmp___1^post_8, [ nDim^0==nDim^post_8 && ni^0==ni^post_8 && nj^0==nj^post_8 && nk^0==nk^post_8 && tmp^0==tmp^post_8 && tmp___0^0==tmp___0^post_8 && tmp___1^0==tmp___1^post_8 ], cost: 1 8: l10 -> l5 : nDim^0'=nDim^post_9, ni^0'=ni^post_9, nj^0'=nj^post_9, nk^0'=nk^post_9, tmp^0'=tmp^post_9, tmp___0^0'=tmp___0^post_9, tmp___1^0'=tmp___1^post_9, [ tmp___1^post_9==0 && nDim^0==nDim^post_9 && ni^0==ni^post_9 && nj^0==nj^post_9 && nk^0==nk^post_9 && tmp^0==tmp^post_9 && tmp___0^0==tmp___0^post_9 ], cost: 1 9: l10 -> l8 : nDim^0'=nDim^post_10, ni^0'=ni^post_10, nj^0'=nj^post_10, nk^0'=nk^post_10, tmp^0'=tmp^post_10, tmp___0^0'=tmp___0^post_10, tmp___1^0'=tmp___1^post_10, [ nDim^0==nDim^post_10 && ni^0==ni^post_10 && nj^0==nj^post_10 && nk^0==nk^post_10 && tmp^0==tmp^post_10 && tmp___0^0==tmp___0^post_10 && tmp___1^0==tmp___1^post_10 ], cost: 1 10: l11 -> l7 : nDim^0'=nDim^post_11, ni^0'=ni^post_11, nj^0'=nj^post_11, nk^0'=nk^post_11, tmp^0'=tmp^post_11, tmp___0^0'=tmp___0^post_11, tmp___1^0'=tmp___1^post_11, [ nDim^0==nDim^post_11 && ni^0==ni^post_11 && nj^0==nj^post_11 && nk^0==nk^post_11 && tmp^0==tmp^post_11 && tmp___0^0==tmp___0^post_11 && tmp___1^0==tmp___1^post_11 ], cost: 1 11: l11 -> l7 : nDim^0'=nDim^post_12, ni^0'=ni^post_12, nj^0'=nj^post_12, nk^0'=nk^post_12, tmp^0'=tmp^post_12, tmp___0^0'=tmp___0^post_12, tmp___1^0'=tmp___1^post_12, [ nDim^0==nDim^post_12 && ni^0==ni^post_12 && nj^0==nj^post_12 && nk^0==nk^post_12 && tmp^0==tmp^post_12 && tmp___0^0==tmp___0^post_12 && tmp___1^0==tmp___1^post_12 ], cost: 1 12: l11 -> l10 : nDim^0'=nDim^post_13, ni^0'=ni^post_13, nj^0'=nj^post_13, nk^0'=nk^post_13, tmp^0'=tmp^post_13, tmp___0^0'=tmp___0^post_13, tmp___1^0'=tmp___1^post_13, [ nDim^0==nDim^post_13 && ni^0==ni^post_13 && nj^0==nj^post_13 && nk^0==nk^post_13 && tmp^0==tmp^post_13 && tmp___0^0==tmp___0^post_13 && tmp___1^0==tmp___1^post_13 ], cost: 1 13: l12 -> l6 : nDim^0'=nDim^post_14, ni^0'=ni^post_14, nj^0'=nj^post_14, nk^0'=nk^post_14, tmp^0'=tmp^post_14, tmp___0^0'=tmp___0^post_14, tmp___1^0'=tmp___1^post_14, [ nDim^0==nDim^post_14 && ni^0==ni^post_14 && nj^0==nj^post_14 && nk^0==nk^post_14 && tmp^0==tmp^post_14 && tmp___0^0==tmp___0^post_14 && tmp___1^0==tmp___1^post_14 ], cost: 1 14: l12 -> l6 : nDim^0'=nDim^post_15, ni^0'=ni^post_15, nj^0'=nj^post_15, nk^0'=nk^post_15, tmp^0'=tmp^post_15, tmp___0^0'=tmp___0^post_15, tmp___1^0'=tmp___1^post_15, [ nDim^0==nDim^post_15 && ni^0==ni^post_15 && nj^0==nj^post_15 && nk^0==nk^post_15 && tmp^0==tmp^post_15 && tmp___0^0==tmp___0^post_15 && tmp___1^0==tmp___1^post_15 ], cost: 1 15: l12 -> l11 : nDim^0'=nDim^post_16, ni^0'=ni^post_16, nj^0'=nj^post_16, nk^0'=nk^post_16, tmp^0'=tmp^post_16, tmp___0^0'=tmp___0^post_16, tmp___1^0'=tmp___1^post_16, [ nDim^0==nDim^post_16 && ni^0==ni^post_16 && nj^0==nj^post_16 && nk^0==nk^post_16 && tmp^0==tmp^post_16 && tmp___0^0==tmp___0^post_16 && tmp___1^0==tmp___1^post_16 ], cost: 1 16: l13 -> l14 : nDim^0'=nDim^post_17, ni^0'=ni^post_17, nj^0'=nj^post_17, nk^0'=nk^post_17, tmp^0'=tmp^post_17, tmp___0^0'=tmp___0^post_17, tmp___1^0'=tmp___1^post_17, [ nDim^0==nDim^post_17 && ni^0==ni^post_17 && nj^0==nj^post_17 && nk^0==nk^post_17 && tmp^0==tmp^post_17 && tmp___0^0==tmp___0^post_17 && tmp___1^0==tmp___1^post_17 ], cost: 1 25: l14 -> l15 : nDim^0'=nDim^post_26, ni^0'=ni^post_26, nj^0'=nj^post_26, nk^0'=nk^post_26, tmp^0'=tmp^post_26, tmp___0^0'=tmp___0^post_26, tmp___1^0'=tmp___1^post_26, [ nDim^0<=ni^0 && nDim^0==nDim^post_26 && ni^0==ni^post_26 && nj^0==nj^post_26 && nk^0==nk^post_26 && tmp^0==tmp^post_26 && tmp___0^0==tmp___0^post_26 && tmp___1^0==tmp___1^post_26 ], cost: 1 26: l14 -> l17 : nDim^0'=nDim^post_27, ni^0'=ni^post_27, nj^0'=nj^post_27, nk^0'=nk^post_27, tmp^0'=tmp^post_27, tmp___0^0'=tmp___0^post_27, tmp___1^0'=tmp___1^post_27, [ 1+ni^0<=nDim^0 && nj^post_27==0 && nDim^0==nDim^post_27 && ni^0==ni^post_27 && nk^0==nk^post_27 && tmp^0==tmp^post_27 && tmp___0^0==tmp___0^post_27 && tmp___1^0==tmp___1^post_27 ], cost: 1 17: l15 -> l4 : nDim^0'=nDim^post_18, ni^0'=ni^post_18, nj^0'=nj^post_18, nk^0'=nk^post_18, tmp^0'=tmp^post_18, tmp___0^0'=tmp___0^post_18, tmp___1^0'=tmp___1^post_18, [ nDim^0==nDim^post_18 && ni^0==ni^post_18 && nj^0==nj^post_18 && nk^0==nk^post_18 && tmp^0==tmp^post_18 && tmp___0^0==tmp___0^post_18 && tmp___1^0==tmp___1^post_18 ], cost: 1 18: l15 -> l4 : nDim^0'=nDim^post_19, ni^0'=ni^post_19, nj^0'=nj^post_19, nk^0'=nk^post_19, tmp^0'=tmp^post_19, tmp___0^0'=tmp___0^post_19, tmp___1^0'=tmp___1^post_19, [ nDim^0==nDim^post_19 && ni^0==ni^post_19 && nj^0==nj^post_19 && nk^0==nk^post_19 && tmp^0==tmp^post_19 && tmp___0^0==tmp___0^post_19 && tmp___1^0==tmp___1^post_19 ], cost: 1 19: l15 -> l12 : nDim^0'=nDim^post_20, ni^0'=ni^post_20, nj^0'=nj^post_20, nk^0'=nk^post_20, tmp^0'=tmp^post_20, tmp___0^0'=tmp___0^post_20, tmp___1^0'=tmp___1^post_20, [ nDim^0==nDim^post_20 && ni^0==ni^post_20 && nj^0==nj^post_20 && nk^0==nk^post_20 && tmp^0==tmp^post_20 && tmp___0^0==tmp___0^post_20 && tmp___1^0==tmp___1^post_20 ], cost: 1 20: l16 -> l17 : nDim^0'=nDim^post_21, ni^0'=ni^post_21, nj^0'=nj^post_21, nk^0'=nk^post_21, tmp^0'=tmp^post_21, tmp___0^0'=tmp___0^post_21, tmp___1^0'=tmp___1^post_21, [ nDim^0<=nk^0 && nj^post_21==1+nj^0 && nDim^0==nDim^post_21 && ni^0==ni^post_21 && nk^0==nk^post_21 && tmp^0==tmp^post_21 && tmp___0^0==tmp___0^post_21 && tmp___1^0==tmp___1^post_21 ], cost: 1 21: l16 -> l18 : nDim^0'=nDim^post_22, ni^0'=ni^post_22, nj^0'=nj^post_22, nk^0'=nk^post_22, tmp^0'=tmp^post_22, tmp___0^0'=tmp___0^post_22, tmp___1^0'=tmp___1^post_22, [ 1+nk^0<=nDim^0 && nk^post_22==1+nk^0 && nDim^0==nDim^post_22 && ni^0==ni^post_22 && nj^0==nj^post_22 && tmp^0==tmp^post_22 && tmp___0^0==tmp___0^post_22 && tmp___1^0==tmp___1^post_22 ], cost: 1 22: l17 -> l19 : nDim^0'=nDim^post_23, ni^0'=ni^post_23, nj^0'=nj^post_23, nk^0'=nk^post_23, tmp^0'=tmp^post_23, tmp___0^0'=tmp___0^post_23, tmp___1^0'=tmp___1^post_23, [ nDim^0==nDim^post_23 && ni^0==ni^post_23 && nj^0==nj^post_23 && nk^0==nk^post_23 && tmp^0==tmp^post_23 && tmp___0^0==tmp___0^post_23 && tmp___1^0==tmp___1^post_23 ], cost: 1 27: l18 -> l16 : nDim^0'=nDim^post_28, ni^0'=ni^post_28, nj^0'=nj^post_28, nk^0'=nk^post_28, tmp^0'=tmp^post_28, tmp___0^0'=tmp___0^post_28, tmp___1^0'=tmp___1^post_28, [ nDim^0==nDim^post_28 && ni^0==ni^post_28 && nj^0==nj^post_28 && nk^0==nk^post_28 && tmp^0==tmp^post_28 && tmp___0^0==tmp___0^post_28 && tmp___1^0==tmp___1^post_28 ], cost: 1 23: l19 -> l13 : nDim^0'=nDim^post_24, ni^0'=ni^post_24, nj^0'=nj^post_24, nk^0'=nk^post_24, tmp^0'=tmp^post_24, tmp___0^0'=tmp___0^post_24, tmp___1^0'=tmp___1^post_24, [ nDim^0<=nj^0 && ni^post_24==1+ni^0 && nDim^0==nDim^post_24 && nj^0==nj^post_24 && nk^0==nk^post_24 && tmp^0==tmp^post_24 && tmp___0^0==tmp___0^post_24 && tmp___1^0==tmp___1^post_24 ], cost: 1 24: l19 -> l18 : nDim^0'=nDim^post_25, ni^0'=ni^post_25, nj^0'=nj^post_25, nk^0'=nk^post_25, tmp^0'=tmp^post_25, tmp___0^0'=tmp___0^post_25, tmp___1^0'=tmp___1^post_25, [ 1+nj^0<=nDim^0 && nk^post_25==0 && nDim^0==nDim^post_25 && ni^0==ni^post_25 && nj^0==nj^post_25 && tmp^0==tmp^post_25 && tmp___0^0==tmp___0^post_25 && tmp___1^0==tmp___1^post_25 ], cost: 1 32: l20 -> l0 : nDim^0'=nDim^post_33, ni^0'=ni^post_33, nj^0'=nj^post_33, nk^0'=nk^post_33, tmp^0'=tmp^post_33, tmp___0^0'=tmp___0^post_33, tmp___1^0'=tmp___1^post_33, [ nDim^post_33==2 && tmp^post_33==tmp^post_33 && tmp___0^post_33==tmp___0^post_33 && ni^post_33==0 && nj^0==nj^post_33 && nk^0==nk^post_33 && tmp___1^0==tmp___1^post_33 ], cost: 1 33: l21 -> l20 : nDim^0'=nDim^post_34, ni^0'=ni^post_34, nj^0'=nj^post_34, nk^0'=nk^post_34, tmp^0'=tmp^post_34, tmp___0^0'=tmp___0^post_34, tmp___1^0'=tmp___1^post_34, [ nDim^0==nDim^post_34 && ni^0==ni^post_34 && nj^0==nj^post_34 && nk^0==nk^post_34 && tmp^0==tmp^post_34 && tmp___0^0==tmp___0^post_34 && tmp___1^0==tmp___1^post_34 ], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 33: l21 -> l20 : nDim^0'=nDim^post_34, ni^0'=ni^post_34, nj^0'=nj^post_34, nk^0'=nk^post_34, tmp^0'=tmp^post_34, tmp___0^0'=tmp___0^post_34, tmp___1^0'=tmp___1^post_34, [ nDim^0==nDim^post_34 && ni^0==ni^post_34 && nj^0==nj^post_34 && nk^0==nk^post_34 && tmp^0==tmp^post_34 && tmp___0^0==tmp___0^post_34 && tmp___1^0==tmp___1^post_34 ], cost: 1 Removed unreachable and leaf rules: Start location: l21 0: l0 -> l1 : nDim^0'=nDim^post_1, ni^0'=ni^post_1, nj^0'=nj^post_1, nk^0'=nk^post_1, tmp^0'=tmp^post_1, tmp___0^0'=tmp___0^post_1, tmp___1^0'=tmp___1^post_1, [ nDim^0==nDim^post_1 && ni^0==ni^post_1 && nj^0==nj^post_1 && nk^0==nk^post_1 && tmp^0==tmp^post_1 && tmp___0^0==tmp___0^post_1 && tmp___1^0==tmp___1^post_1 ], cost: 1 30: l1 -> l13 : nDim^0'=nDim^post_31, ni^0'=ni^post_31, nj^0'=nj^post_31, nk^0'=nk^post_31, tmp^0'=tmp^post_31, tmp___0^0'=tmp___0^post_31, tmp___1^0'=tmp___1^post_31, [ nDim^0<=ni^0 && ni^post_31==0 && nDim^0==nDim^post_31 && nj^0==nj^post_31 && nk^0==nk^post_31 && tmp^0==tmp^post_31 && tmp___0^0==tmp___0^post_31 && tmp___1^0==tmp___1^post_31 ], cost: 1 31: l1 -> l2 : nDim^0'=nDim^post_32, ni^0'=ni^post_32, nj^0'=nj^post_32, nk^0'=nk^post_32, tmp^0'=tmp^post_32, tmp___0^0'=tmp___0^post_32, tmp___1^0'=tmp___1^post_32, [ 1+ni^0<=nDim^0 && nj^post_32==0 && nDim^0==nDim^post_32 && ni^0==ni^post_32 && nk^0==nk^post_32 && tmp^0==tmp^post_32 && tmp___0^0==tmp___0^post_32 && tmp___1^0==tmp___1^post_32 ], cost: 1 1: l2 -> l3 : nDim^0'=nDim^post_2, ni^0'=ni^post_2, nj^0'=nj^post_2, nk^0'=nk^post_2, tmp^0'=tmp^post_2, tmp___0^0'=tmp___0^post_2, tmp___1^0'=tmp___1^post_2, [ nDim^0==nDim^post_2 && ni^0==ni^post_2 && nj^0==nj^post_2 && nk^0==nk^post_2 && tmp^0==tmp^post_2 && tmp___0^0==tmp___0^post_2 && tmp___1^0==tmp___1^post_2 ], cost: 1 28: l3 -> l0 : nDim^0'=nDim^post_29, ni^0'=ni^post_29, nj^0'=nj^post_29, nk^0'=nk^post_29, tmp^0'=tmp^post_29, tmp___0^0'=tmp___0^post_29, tmp___1^0'=tmp___1^post_29, [ nDim^0<=nj^0 && ni^post_29==1+ni^0 && nDim^0==nDim^post_29 && nj^0==nj^post_29 && nk^0==nk^post_29 && tmp^0==tmp^post_29 && tmp___0^0==tmp___0^post_29 && tmp___1^0==tmp___1^post_29 ], cost: 1 29: l3 -> l2 : nDim^0'=nDim^post_30, ni^0'=ni^post_30, nj^0'=nj^post_30, nk^0'=nk^post_30, tmp^0'=tmp^post_30, tmp___0^0'=tmp___0^post_30, tmp___1^0'=tmp___1^post_30, [ 1+nj^0<=nDim^0 && nj^post_30==1+nj^0 && nDim^0==nDim^post_30 && ni^0==ni^post_30 && nk^0==nk^post_30 && tmp^0==tmp^post_30 && tmp___0^0==tmp___0^post_30 && tmp___1^0==tmp___1^post_30 ], cost: 1 16: l13 -> l14 : nDim^0'=nDim^post_17, ni^0'=ni^post_17, nj^0'=nj^post_17, nk^0'=nk^post_17, tmp^0'=tmp^post_17, tmp___0^0'=tmp___0^post_17, tmp___1^0'=tmp___1^post_17, [ nDim^0==nDim^post_17 && ni^0==ni^post_17 && nj^0==nj^post_17 && nk^0==nk^post_17 && tmp^0==tmp^post_17 && tmp___0^0==tmp___0^post_17 && tmp___1^0==tmp___1^post_17 ], cost: 1 26: l14 -> l17 : nDim^0'=nDim^post_27, ni^0'=ni^post_27, nj^0'=nj^post_27, nk^0'=nk^post_27, tmp^0'=tmp^post_27, tmp___0^0'=tmp___0^post_27, tmp___1^0'=tmp___1^post_27, [ 1+ni^0<=nDim^0 && nj^post_27==0 && nDim^0==nDim^post_27 && ni^0==ni^post_27 && nk^0==nk^post_27 && tmp^0==tmp^post_27 && tmp___0^0==tmp___0^post_27 && tmp___1^0==tmp___1^post_27 ], cost: 1 20: l16 -> l17 : nDim^0'=nDim^post_21, ni^0'=ni^post_21, nj^0'=nj^post_21, nk^0'=nk^post_21, tmp^0'=tmp^post_21, tmp___0^0'=tmp___0^post_21, tmp___1^0'=tmp___1^post_21, [ nDim^0<=nk^0 && nj^post_21==1+nj^0 && nDim^0==nDim^post_21 && ni^0==ni^post_21 && nk^0==nk^post_21 && tmp^0==tmp^post_21 && tmp___0^0==tmp___0^post_21 && tmp___1^0==tmp___1^post_21 ], cost: 1 21: l16 -> l18 : nDim^0'=nDim^post_22, ni^0'=ni^post_22, nj^0'=nj^post_22, nk^0'=nk^post_22, tmp^0'=tmp^post_22, tmp___0^0'=tmp___0^post_22, tmp___1^0'=tmp___1^post_22, [ 1+nk^0<=nDim^0 && nk^post_22==1+nk^0 && nDim^0==nDim^post_22 && ni^0==ni^post_22 && nj^0==nj^post_22 && tmp^0==tmp^post_22 && tmp___0^0==tmp___0^post_22 && tmp___1^0==tmp___1^post_22 ], cost: 1 22: l17 -> l19 : nDim^0'=nDim^post_23, ni^0'=ni^post_23, nj^0'=nj^post_23, nk^0'=nk^post_23, tmp^0'=tmp^post_23, tmp___0^0'=tmp___0^post_23, tmp___1^0'=tmp___1^post_23, [ nDim^0==nDim^post_23 && ni^0==ni^post_23 && nj^0==nj^post_23 && nk^0==nk^post_23 && tmp^0==tmp^post_23 && tmp___0^0==tmp___0^post_23 && tmp___1^0==tmp___1^post_23 ], cost: 1 27: l18 -> l16 : nDim^0'=nDim^post_28, ni^0'=ni^post_28, nj^0'=nj^post_28, nk^0'=nk^post_28, tmp^0'=tmp^post_28, tmp___0^0'=tmp___0^post_28, tmp___1^0'=tmp___1^post_28, [ nDim^0==nDim^post_28 && ni^0==ni^post_28 && nj^0==nj^post_28 && nk^0==nk^post_28 && tmp^0==tmp^post_28 && tmp___0^0==tmp___0^post_28 && tmp___1^0==tmp___1^post_28 ], cost: 1 23: l19 -> l13 : nDim^0'=nDim^post_24, ni^0'=ni^post_24, nj^0'=nj^post_24, nk^0'=nk^post_24, tmp^0'=tmp^post_24, tmp___0^0'=tmp___0^post_24, tmp___1^0'=tmp___1^post_24, [ nDim^0<=nj^0 && ni^post_24==1+ni^0 && nDim^0==nDim^post_24 && nj^0==nj^post_24 && nk^0==nk^post_24 && tmp^0==tmp^post_24 && tmp___0^0==tmp___0^post_24 && tmp___1^0==tmp___1^post_24 ], cost: 1 24: l19 -> l18 : nDim^0'=nDim^post_25, ni^0'=ni^post_25, nj^0'=nj^post_25, nk^0'=nk^post_25, tmp^0'=tmp^post_25, tmp___0^0'=tmp___0^post_25, tmp___1^0'=tmp___1^post_25, [ 1+nj^0<=nDim^0 && nk^post_25==0 && nDim^0==nDim^post_25 && ni^0==ni^post_25 && nj^0==nj^post_25 && tmp^0==tmp^post_25 && tmp___0^0==tmp___0^post_25 && tmp___1^0==tmp___1^post_25 ], cost: 1 32: l20 -> l0 : nDim^0'=nDim^post_33, ni^0'=ni^post_33, nj^0'=nj^post_33, nk^0'=nk^post_33, tmp^0'=tmp^post_33, tmp___0^0'=tmp___0^post_33, tmp___1^0'=tmp___1^post_33, [ nDim^post_33==2 && tmp^post_33==tmp^post_33 && tmp___0^post_33==tmp___0^post_33 && ni^post_33==0 && nj^0==nj^post_33 && nk^0==nk^post_33 && tmp___1^0==tmp___1^post_33 ], cost: 1 33: l21 -> l20 : nDim^0'=nDim^post_34, ni^0'=ni^post_34, nj^0'=nj^post_34, nk^0'=nk^post_34, tmp^0'=tmp^post_34, tmp___0^0'=tmp___0^post_34, tmp___1^0'=tmp___1^post_34, [ nDim^0==nDim^post_34 && ni^0==ni^post_34 && nj^0==nj^post_34 && nk^0==nk^post_34 && tmp^0==tmp^post_34 && tmp___0^0==tmp___0^post_34 && tmp___1^0==tmp___1^post_34 ], cost: 1 Simplified all rules, resulting in: Start location: l21 0: l0 -> l1 : [], cost: 1 30: l1 -> l13 : ni^0'=0, [ nDim^0<=ni^0 ], cost: 1 31: l1 -> l2 : nj^0'=0, [ 1+ni^0<=nDim^0 ], cost: 1 1: l2 -> l3 : [], cost: 1 28: l3 -> l0 : ni^0'=1+ni^0, [ nDim^0<=nj^0 ], cost: 1 29: l3 -> l2 : nj^0'=1+nj^0, [ 1+nj^0<=nDim^0 ], cost: 1 16: l13 -> l14 : [], cost: 1 26: l14 -> l17 : nj^0'=0, [ 1+ni^0<=nDim^0 ], cost: 1 20: l16 -> l17 : nj^0'=1+nj^0, [ nDim^0<=nk^0 ], cost: 1 21: l16 -> l18 : nk^0'=1+nk^0, [ 1+nk^0<=nDim^0 ], cost: 1 22: l17 -> l19 : [], cost: 1 27: l18 -> l16 : [], cost: 1 23: l19 -> l13 : ni^0'=1+ni^0, [ nDim^0<=nj^0 ], cost: 1 24: l19 -> l18 : nk^0'=0, [ 1+nj^0<=nDim^0 ], cost: 1 32: l20 -> l0 : nDim^0'=2, ni^0'=0, tmp^0'=tmp^post_33, tmp___0^0'=tmp___0^post_33, [], cost: 1 33: l21 -> l20 : [], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: l21 0: l0 -> l1 : [], cost: 1 30: l1 -> l13 : ni^0'=0, [ nDim^0<=ni^0 ], cost: 1 31: l1 -> l2 : nj^0'=0, [ 1+ni^0<=nDim^0 ], cost: 1 1: l2 -> l3 : [], cost: 1 28: l3 -> l0 : ni^0'=1+ni^0, [ nDim^0<=nj^0 ], cost: 1 29: l3 -> l2 : nj^0'=1+nj^0, [ 1+nj^0<=nDim^0 ], cost: 1 35: l13 -> l17 : nj^0'=0, [ 1+ni^0<=nDim^0 ], cost: 2 20: l16 -> l17 : nj^0'=1+nj^0, [ nDim^0<=nk^0 ], cost: 1 21: l16 -> l18 : nk^0'=1+nk^0, [ 1+nk^0<=nDim^0 ], cost: 1 22: l17 -> l19 : [], cost: 1 27: l18 -> l16 : [], cost: 1 23: l19 -> l13 : ni^0'=1+ni^0, [ nDim^0<=nj^0 ], cost: 1 24: l19 -> l18 : nk^0'=0, [ 1+nj^0<=nDim^0 ], cost: 1 34: l21 -> l0 : nDim^0'=2, ni^0'=0, tmp^0'=tmp^post_33, tmp___0^0'=tmp___0^post_33, [], cost: 2 Eliminated locations (on tree-shaped paths): Start location: l21 36: l0 -> l13 : ni^0'=0, [ nDim^0<=ni^0 ], cost: 2 37: l0 -> l2 : nj^0'=0, [ 1+ni^0<=nDim^0 ], cost: 2 38: l2 -> l0 : ni^0'=1+ni^0, [ nDim^0<=nj^0 ], cost: 2 39: l2 -> l2 : nj^0'=1+nj^0, [ 1+nj^0<=nDim^0 ], cost: 2 35: l13 -> l17 : nj^0'=0, [ 1+ni^0<=nDim^0 ], cost: 2 40: l17 -> l13 : ni^0'=1+ni^0, [ nDim^0<=nj^0 ], cost: 2 41: l17 -> l18 : nk^0'=0, [ 1+nj^0<=nDim^0 ], cost: 2 42: l18 -> l17 : nj^0'=1+nj^0, [ nDim^0<=nk^0 ], cost: 2 43: l18 -> l18 : nk^0'=1+nk^0, [ 1+nk^0<=nDim^0 ], cost: 2 34: l21 -> l0 : nDim^0'=2, ni^0'=0, tmp^0'=tmp^post_33, tmp___0^0'=tmp___0^post_33, [], cost: 2 Accelerating simple loops of location 2. Accelerating the following rules: 39: l2 -> l2 : nj^0'=1+nj^0, [ 1+nj^0<=nDim^0 ], cost: 2 Accelerated rule 39 with backward acceleration, yielding the new rule 44. [accelerate] Nesting with 1 inner and 1 outer candidates Removing the simple loops: 39. Accelerating simple loops of location 18. Accelerating the following rules: 43: l18 -> l18 : nk^0'=1+nk^0, [ 1+nk^0<=nDim^0 ], cost: 2 Accelerated rule 43 with backward acceleration, yielding the new rule 45. [accelerate] Nesting with 1 inner and 1 outer candidates Removing the simple loops: 43. Accelerated all simple loops using metering functions (where possible): Start location: l21 36: l0 -> l13 : ni^0'=0, [ nDim^0<=ni^0 ], cost: 2 37: l0 -> l2 : nj^0'=0, [ 1+ni^0<=nDim^0 ], cost: 2 38: l2 -> l0 : ni^0'=1+ni^0, [ nDim^0<=nj^0 ], cost: 2 44: l2 -> l2 : nj^0'=nDim^0, [ -nj^0+nDim^0>=0 ], cost: -2*nj^0+2*nDim^0 35: l13 -> l17 : nj^0'=0, [ 1+ni^0<=nDim^0 ], cost: 2 40: l17 -> l13 : ni^0'=1+ni^0, [ nDim^0<=nj^0 ], cost: 2 41: l17 -> l18 : nk^0'=0, [ 1+nj^0<=nDim^0 ], cost: 2 42: l18 -> l17 : nj^0'=1+nj^0, [ nDim^0<=nk^0 ], cost: 2 45: l18 -> l18 : nk^0'=nDim^0, [ -nk^0+nDim^0>=0 ], cost: -2*nk^0+2*nDim^0 34: l21 -> l0 : nDim^0'=2, ni^0'=0, tmp^0'=tmp^post_33, tmp___0^0'=tmp___0^post_33, [], cost: 2 Chained accelerated rules (with incoming rules): Start location: l21 36: l0 -> l13 : ni^0'=0, [ nDim^0<=ni^0 ], cost: 2 37: l0 -> l2 : nj^0'=0, [ 1+ni^0<=nDim^0 ], cost: 2 46: l0 -> l2 : nj^0'=nDim^0, [ 1+ni^0<=nDim^0 && nDim^0>=0 ], cost: 2+2*nDim^0 38: l2 -> l0 : ni^0'=1+ni^0, [ nDim^0<=nj^0 ], cost: 2 35: l13 -> l17 : nj^0'=0, [ 1+ni^0<=nDim^0 ], cost: 2 40: l17 -> l13 : ni^0'=1+ni^0, [ nDim^0<=nj^0 ], cost: 2 41: l17 -> l18 : nk^0'=0, [ 1+nj^0<=nDim^0 ], cost: 2 47: l17 -> l18 : nk^0'=nDim^0, [ 1+nj^0<=nDim^0 && nDim^0>=0 ], cost: 2+2*nDim^0 42: l18 -> l17 : nj^0'=1+nj^0, [ nDim^0<=nk^0 ], cost: 2 34: l21 -> l0 : nDim^0'=2, ni^0'=0, tmp^0'=tmp^post_33, tmp___0^0'=tmp___0^post_33, [], cost: 2 Eliminated locations (on tree-shaped paths): Start location: l21 36: l0 -> l13 : ni^0'=0, [ nDim^0<=ni^0 ], cost: 2 48: l0 -> l0 : ni^0'=1+ni^0, nj^0'=0, [ 1+ni^0<=nDim^0 && nDim^0<=0 ], cost: 4 49: l0 -> l0 : ni^0'=1+ni^0, nj^0'=nDim^0, [ 1+ni^0<=nDim^0 && nDim^0>=0 ], cost: 4+2*nDim^0 35: l13 -> l17 : nj^0'=0, [ 1+ni^0<=nDim^0 ], cost: 2 40: l17 -> l13 : ni^0'=1+ni^0, [ nDim^0<=nj^0 ], cost: 2 50: l17 -> l17 : nj^0'=1+nj^0, nk^0'=0, [ 1+nj^0<=nDim^0 && nDim^0<=0 ], cost: 4 51: l17 -> l17 : nj^0'=1+nj^0, nk^0'=nDim^0, [ 1+nj^0<=nDim^0 && nDim^0>=0 ], cost: 4+2*nDim^0 34: l21 -> l0 : nDim^0'=2, ni^0'=0, tmp^0'=tmp^post_33, tmp___0^0'=tmp___0^post_33, [], cost: 2 Accelerating simple loops of location 0. Accelerating the following rules: 48: l0 -> l0 : ni^0'=1+ni^0, nj^0'=0, [ 1+ni^0<=nDim^0 && nDim^0<=0 ], cost: 4 49: l0 -> l0 : ni^0'=1+ni^0, nj^0'=nDim^0, [ 1+ni^0<=nDim^0 && nDim^0>=0 ], cost: 4+2*nDim^0 Accelerated rule 48 with backward acceleration, yielding the new rule 52. Accelerated rule 49 with backward acceleration, yielding the new rule 53. [accelerate] Nesting with 2 inner and 2 outer candidates Removing the simple loops: 48 49. Accelerating simple loops of location 17. Accelerating the following rules: 50: l17 -> l17 : nj^0'=1+nj^0, nk^0'=0, [ 1+nj^0<=nDim^0 && nDim^0<=0 ], cost: 4 51: l17 -> l17 : nj^0'=1+nj^0, nk^0'=nDim^0, [ 1+nj^0<=nDim^0 && nDim^0>=0 ], cost: 4+2*nDim^0 Accelerated rule 50 with backward acceleration, yielding the new rule 54. Accelerated rule 51 with backward acceleration, yielding the new rule 55. [accelerate] Nesting with 2 inner and 2 outer candidates Removing the simple loops: 50 51. Accelerated all simple loops using metering functions (where possible): Start location: l21 36: l0 -> l13 : ni^0'=0, [ nDim^0<=ni^0 ], cost: 2 52: l0 -> l0 : ni^0'=nDim^0, nj^0'=0, [ nDim^0<=0 && -ni^0+nDim^0>=1 ], cost: -4*ni^0+4*nDim^0 53: l0 -> l0 : ni^0'=nDim^0, nj^0'=nDim^0, [ nDim^0>=0 && -ni^0+nDim^0>=1 ], cost: -4*ni^0-2*(ni^0-nDim^0)*nDim^0+4*nDim^0 35: l13 -> l17 : nj^0'=0, [ 1+ni^0<=nDim^0 ], cost: 2 40: l17 -> l13 : ni^0'=1+ni^0, [ nDim^0<=nj^0 ], cost: 2 54: l17 -> l17 : nj^0'=nDim^0, nk^0'=0, [ nDim^0<=0 && -nj^0+nDim^0>=1 ], cost: -4*nj^0+4*nDim^0 55: l17 -> l17 : nj^0'=nDim^0, nk^0'=nDim^0, [ nDim^0>=0 && -nj^0+nDim^0>=1 ], cost: -2*(nj^0-nDim^0)*nDim^0-4*nj^0+4*nDim^0 34: l21 -> l0 : nDim^0'=2, ni^0'=0, tmp^0'=tmp^post_33, tmp___0^0'=tmp___0^post_33, [], cost: 2 Chained accelerated rules (with incoming rules): Start location: l21 36: l0 -> l13 : ni^0'=0, [ nDim^0<=ni^0 ], cost: 2 35: l13 -> l17 : nj^0'=0, [ 1+ni^0<=nDim^0 ], cost: 2 57: l13 -> l17 : nj^0'=nDim^0, nk^0'=nDim^0, [ 1+ni^0<=nDim^0 && nDim^0>=1 ], cost: 2+2*nDim^0^2+4*nDim^0 40: l17 -> l13 : ni^0'=1+ni^0, [ nDim^0<=nj^0 ], cost: 2 34: l21 -> l0 : nDim^0'=2, ni^0'=0, tmp^0'=tmp^post_33, tmp___0^0'=tmp___0^post_33, [], cost: 2 56: l21 -> l0 : nDim^0'=2, ni^0'=2, nj^0'=2, tmp^0'=tmp^post_33, tmp___0^0'=tmp___0^post_33, [], cost: 18 Eliminated locations (on tree-shaped paths): Start location: l21 59: l13 -> l13 : ni^0'=1+ni^0, nj^0'=0, [ 1+ni^0<=nDim^0 && nDim^0<=0 ], cost: 4 60: l13 -> l13 : ni^0'=1+ni^0, nj^0'=nDim^0, nk^0'=nDim^0, [ 1+ni^0<=nDim^0 && nDim^0>=1 ], cost: 4+2*nDim^0^2+4*nDim^0 58: l21 -> l13 : nDim^0'=2, ni^0'=0, nj^0'=2, tmp^0'=tmp^post_33, tmp___0^0'=tmp___0^post_33, [], cost: 20 Accelerating simple loops of location 13. Accelerating the following rules: 59: l13 -> l13 : ni^0'=1+ni^0, nj^0'=0, [ 1+ni^0<=nDim^0 && nDim^0<=0 ], cost: 4 60: l13 -> l13 : ni^0'=1+ni^0, nj^0'=nDim^0, nk^0'=nDim^0, [ 1+ni^0<=nDim^0 && nDim^0>=1 ], cost: 4+2*nDim^0^2+4*nDim^0 Accelerated rule 59 with backward acceleration, yielding the new rule 61. Accelerated rule 60 with backward acceleration, yielding the new rule 62. [accelerate] Nesting with 2 inner and 2 outer candidates Removing the simple loops: 59 60. Accelerated all simple loops using metering functions (where possible): Start location: l21 61: l13 -> l13 : ni^0'=nDim^0, nj^0'=0, [ nDim^0<=0 && -ni^0+nDim^0>=1 ], cost: -4*ni^0+4*nDim^0 62: l13 -> l13 : ni^0'=nDim^0, nj^0'=nDim^0, nk^0'=nDim^0, [ nDim^0>=1 && -ni^0+nDim^0>=1 ], cost: -2*(ni^0-nDim^0)*nDim^0^2-4*ni^0-4*(ni^0-nDim^0)*nDim^0+4*nDim^0 58: l21 -> l13 : nDim^0'=2, ni^0'=0, nj^0'=2, tmp^0'=tmp^post_33, tmp___0^0'=tmp___0^post_33, [], cost: 20 Chained accelerated rules (with incoming rules): Start location: l21 58: l21 -> l13 : nDim^0'=2, ni^0'=0, nj^0'=2, tmp^0'=tmp^post_33, tmp___0^0'=tmp___0^post_33, [], cost: 20 63: l21 -> l13 : nDim^0'=2, ni^0'=2, nj^0'=2, nk^0'=2, tmp^0'=tmp^post_33, tmp___0^0'=tmp___0^post_33, [], cost: 60 Removed unreachable locations (and leaf rules with constant cost): Start location: l21 ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: l21 Obtained the following overall complexity (w.r.t. the length of the input n): Complexity: Constant Cpx degree: 0 Solved cost: 1 Rule cost: 1 Rule guard: [ nDim^0==nDim^post_34 && ni^0==ni^post_34 && nj^0==nj^post_34 && nk^0==nk^post_34 && tmp^0==tmp^post_34 && tmp___0^0==tmp___0^post_34 && tmp___1^0==tmp___1^post_34 ] WORST_CASE(Omega(1),?)