NO Initial ITS Start location: l6 0: l0 -> l1 : __retres3_7^0'=__retres3_7^post0, __cil_tmp2_10^0'=__cil_tmp2_10^post0, i_5^0'=i_5^post0, __retres1_9^0'=__retres1_9^post0, Result_4^0'=Result_4^post0, d_6^0'=d_6^post0, __cil_tmp4_8^0'=__cil_tmp4_8^post0, (__retres3_7^0-__retres3_7^post0 == 0 /\ -__cil_tmp2_10^post0+__cil_tmp2_10^0 == 0 /\ -__cil_tmp4_8^post0+__cil_tmp4_8^0 == 0 /\ -d_6^post0+d_6^0 == 0 /\ -Result_4^post0+Result_4^0 == 0 /\ __retres1_9^0-__retres1_9^post0 == 0 /\ i_5^0-i_5^post0 == 0), cost: 1 4: l1 -> l3 : __retres3_7^0'=__retres3_7^post4, __cil_tmp2_10^0'=__cil_tmp2_10^post4, i_5^0'=i_5^post4, __retres1_9^0'=__retres1_9^post4, Result_4^0'=Result_4^post4, d_6^0'=d_6^post4, __cil_tmp4_8^0'=__cil_tmp4_8^post4, (-i_5^post4+i_5^0 == 0 /\ __cil_tmp4_8^post4-__retres3_7^post4 == 0 /\ -__cil_tmp4_8^post4+Result_4^post4 == 0 /\ -d_6^0 <= 0 /\ __retres3_7^post4 == 0 /\ -__retres1_9^post4+__retres1_9^0 == 0 /\ d_6^0-d_6^post4 == 0 /\ __cil_tmp2_10^0-__cil_tmp2_10^post4 == 0), cost: 1 5: l1 -> l2 : __retres3_7^0'=__retres3_7^post5, __cil_tmp2_10^0'=__cil_tmp2_10^post5, i_5^0'=i_5^post5, __retres1_9^0'=__retres1_9^post5, Result_4^0'=Result_4^post5, d_6^0'=d_6^post5, __cil_tmp4_8^0'=__cil_tmp4_8^post5, (__retres1_9^0-__retres1_9^post5 == 0 /\ -i_5^post5+i_5^0 == 0 /\ -__cil_tmp4_8^post5+__cil_tmp4_8^0 == 0 /\ 1+d_6^0 <= 0 /\ Result_4^0-Result_4^post5 == 0 /\ -d_6^post5+d_6^0 == 0 /\ __cil_tmp2_10^0-__cil_tmp2_10^post5 == 0 /\ __retres3_7^0-__retres3_7^post5 == 0), cost: 1 1: l2 -> l3 : __retres3_7^0'=__retres3_7^post1, __cil_tmp2_10^0'=__cil_tmp2_10^post1, i_5^0'=i_5^post1, __retres1_9^0'=__retres1_9^post1, Result_4^0'=Result_4^post1, d_6^0'=d_6^post1, __cil_tmp4_8^0'=__cil_tmp4_8^post1, (Result_4^post1-__cil_tmp4_8^post1 == 0 /\ i_5^0-i_5^post1 == 0 /\ __cil_tmp2_10^0-__cil_tmp2_10^post1 == 0 /\ __cil_tmp4_8^post1-__retres3_7^post1 == 0 /\ __retres1_9^0-__retres1_9^post1 == 0 /\ -d_6^post1+d_6^0 == 0 /\ __retres3_7^post1 == 0 /\ 1+i_5^0 <= 0), cost: 1 2: l2 -> l4 : __retres3_7^0'=__retres3_7^post2, __cil_tmp2_10^0'=__cil_tmp2_10^post2, i_5^0'=i_5^post2, __retres1_9^0'=__retres1_9^post2, Result_4^0'=Result_4^post2, d_6^0'=d_6^post2, __cil_tmp4_8^0'=__cil_tmp4_8^post2, (__cil_tmp2_10^0-__cil_tmp2_10^post2 == 0 /\ __cil_tmp4_8^0-__cil_tmp4_8^post2 == 0 /\ -i_5^0 <= 0 /\ __retres3_7^0-__retres3_7^post2 == 0 /\ -d_6^post2+d_6^0 == 0 /\ -i_5^0+d_6^0+i_5^post2 == 0 /\ -__retres1_9^post2+__retres1_9^0 == 0 /\ -Result_4^post2+Result_4^0 == 0), cost: 1 6: l3 -> l5 : __retres3_7^0'=__retres3_7^post6, __cil_tmp2_10^0'=__cil_tmp2_10^post6, i_5^0'=i_5^post6, __retres1_9^0'=__retres1_9^post6, Result_4^0'=Result_4^post6, d_6^0'=d_6^post6, __cil_tmp4_8^0'=__cil_tmp4_8^post6, (__retres3_7^0-__retres3_7^post6 == 0 /\ -d_6^post6+d_6^0 == 0 /\ __cil_tmp2_10^post6-__retres1_9^post6 == 0 /\ -__cil_tmp4_8^post6+__cil_tmp4_8^0 == 0 /\ __retres1_9^post6 == 0 /\ i_5^0-i_5^post6 == 0 /\ -__cil_tmp2_10^post6+Result_4^post6 == 0), cost: 1 3: l4 -> l2 : __retres3_7^0'=__retres3_7^post3, __cil_tmp2_10^0'=__cil_tmp2_10^post3, i_5^0'=i_5^post3, __retres1_9^0'=__retres1_9^post3, Result_4^0'=Result_4^post3, d_6^0'=d_6^post3, __cil_tmp4_8^0'=__cil_tmp4_8^post3, (-__cil_tmp4_8^post3+__cil_tmp4_8^0 == 0 /\ -i_5^post3+i_5^0 == 0 /\ __cil_tmp2_10^0-__cil_tmp2_10^post3 == 0 /\ __retres3_7^0-__retres3_7^post3 == 0 /\ -__retres1_9^post3+__retres1_9^0 == 0 /\ d_6^0-d_6^post3 == 0 /\ Result_4^0-Result_4^post3 == 0), cost: 1 7: l6 -> l0 : __retres3_7^0'=__retres3_7^post7, __cil_tmp2_10^0'=__cil_tmp2_10^post7, i_5^0'=i_5^post7, __retres1_9^0'=__retres1_9^post7, Result_4^0'=Result_4^post7, d_6^0'=d_6^post7, __cil_tmp4_8^0'=__cil_tmp4_8^post7, (-__retres1_9^post7+__retres1_9^0 == 0 /\ -__cil_tmp4_8^post7+__cil_tmp4_8^0 == 0 /\ -d_6^post7+d_6^0 == 0 /\ i_5^0-i_5^post7 == 0 /\ __retres3_7^0-__retres3_7^post7 == 0 /\ -Result_4^post7+Result_4^0 == 0 /\ __cil_tmp2_10^0-__cil_tmp2_10^post7 == 0), cost: 1 Removed unreachable rules and leafs Start location: l6 0: l0 -> l1 : __retres3_7^0'=__retres3_7^post0, __cil_tmp2_10^0'=__cil_tmp2_10^post0, i_5^0'=i_5^post0, __retres1_9^0'=__retres1_9^post0, Result_4^0'=Result_4^post0, d_6^0'=d_6^post0, __cil_tmp4_8^0'=__cil_tmp4_8^post0, (__retres3_7^0-__retres3_7^post0 == 0 /\ -__cil_tmp2_10^post0+__cil_tmp2_10^0 == 0 /\ -__cil_tmp4_8^post0+__cil_tmp4_8^0 == 0 /\ -d_6^post0+d_6^0 == 0 /\ -Result_4^post0+Result_4^0 == 0 /\ __retres1_9^0-__retres1_9^post0 == 0 /\ i_5^0-i_5^post0 == 0), cost: 1 5: l1 -> l2 : __retres3_7^0'=__retres3_7^post5, __cil_tmp2_10^0'=__cil_tmp2_10^post5, i_5^0'=i_5^post5, __retres1_9^0'=__retres1_9^post5, Result_4^0'=Result_4^post5, d_6^0'=d_6^post5, __cil_tmp4_8^0'=__cil_tmp4_8^post5, (__retres1_9^0-__retres1_9^post5 == 0 /\ -i_5^post5+i_5^0 == 0 /\ -__cil_tmp4_8^post5+__cil_tmp4_8^0 == 0 /\ 1+d_6^0 <= 0 /\ Result_4^0-Result_4^post5 == 0 /\ -d_6^post5+d_6^0 == 0 /\ __cil_tmp2_10^0-__cil_tmp2_10^post5 == 0 /\ __retres3_7^0-__retres3_7^post5 == 0), cost: 1 2: l2 -> l4 : __retres3_7^0'=__retres3_7^post2, __cil_tmp2_10^0'=__cil_tmp2_10^post2, i_5^0'=i_5^post2, __retres1_9^0'=__retres1_9^post2, Result_4^0'=Result_4^post2, d_6^0'=d_6^post2, __cil_tmp4_8^0'=__cil_tmp4_8^post2, (__cil_tmp2_10^0-__cil_tmp2_10^post2 == 0 /\ __cil_tmp4_8^0-__cil_tmp4_8^post2 == 0 /\ -i_5^0 <= 0 /\ __retres3_7^0-__retres3_7^post2 == 0 /\ -d_6^post2+d_6^0 == 0 /\ -i_5^0+d_6^0+i_5^post2 == 0 /\ -__retres1_9^post2+__retres1_9^0 == 0 /\ -Result_4^post2+Result_4^0 == 0), cost: 1 3: l4 -> l2 : __retres3_7^0'=__retres3_7^post3, __cil_tmp2_10^0'=__cil_tmp2_10^post3, i_5^0'=i_5^post3, __retres1_9^0'=__retres1_9^post3, Result_4^0'=Result_4^post3, d_6^0'=d_6^post3, __cil_tmp4_8^0'=__cil_tmp4_8^post3, (-__cil_tmp4_8^post3+__cil_tmp4_8^0 == 0 /\ -i_5^post3+i_5^0 == 0 /\ __cil_tmp2_10^0-__cil_tmp2_10^post3 == 0 /\ __retres3_7^0-__retres3_7^post3 == 0 /\ -__retres1_9^post3+__retres1_9^0 == 0 /\ d_6^0-d_6^post3 == 0 /\ Result_4^0-Result_4^post3 == 0), cost: 1 7: l6 -> l0 : __retres3_7^0'=__retres3_7^post7, __cil_tmp2_10^0'=__cil_tmp2_10^post7, i_5^0'=i_5^post7, __retres1_9^0'=__retres1_9^post7, Result_4^0'=Result_4^post7, d_6^0'=d_6^post7, __cil_tmp4_8^0'=__cil_tmp4_8^post7, (-__retres1_9^post7+__retres1_9^0 == 0 /\ -__cil_tmp4_8^post7+__cil_tmp4_8^0 == 0 /\ -d_6^post7+d_6^0 == 0 /\ i_5^0-i_5^post7 == 0 /\ __retres3_7^0-__retres3_7^post7 == 0 /\ -Result_4^post7+Result_4^0 == 0 /\ __cil_tmp2_10^0-__cil_tmp2_10^post7 == 0), cost: 1 Applied preprocessing Original rule: l0 -> l1 : __retres3_7^0'=__retres3_7^post0, __cil_tmp2_10^0'=__cil_tmp2_10^post0, i_5^0'=i_5^post0, __retres1_9^0'=__retres1_9^post0, Result_4^0'=Result_4^post0, d_6^0'=d_6^post0, __cil_tmp4_8^0'=__cil_tmp4_8^post0, (__retres3_7^0-__retres3_7^post0 == 0 /\ -__cil_tmp2_10^post0+__cil_tmp2_10^0 == 0 /\ -__cil_tmp4_8^post0+__cil_tmp4_8^0 == 0 /\ -d_6^post0+d_6^0 == 0 /\ -Result_4^post0+Result_4^0 == 0 /\ __retres1_9^0-__retres1_9^post0 == 0 /\ i_5^0-i_5^post0 == 0), cost: 1 New rule: l0 -> l1 : TRUE, cost: 1 Applied preprocessing Original rule: l2 -> l4 : __retres3_7^0'=__retres3_7^post2, __cil_tmp2_10^0'=__cil_tmp2_10^post2, i_5^0'=i_5^post2, __retres1_9^0'=__retres1_9^post2, Result_4^0'=Result_4^post2, d_6^0'=d_6^post2, __cil_tmp4_8^0'=__cil_tmp4_8^post2, (__cil_tmp2_10^0-__cil_tmp2_10^post2 == 0 /\ __cil_tmp4_8^0-__cil_tmp4_8^post2 == 0 /\ -i_5^0 <= 0 /\ __retres3_7^0-__retres3_7^post2 == 0 /\ -d_6^post2+d_6^0 == 0 /\ -i_5^0+d_6^0+i_5^post2 == 0 /\ -__retres1_9^post2+__retres1_9^0 == 0 /\ -Result_4^post2+Result_4^0 == 0), cost: 1 New rule: l2 -> l4 : i_5^0'=i_5^0-d_6^0, i_5^0 >= 0, cost: 1 Applied preprocessing Original rule: l4 -> l2 : __retres3_7^0'=__retres3_7^post3, __cil_tmp2_10^0'=__cil_tmp2_10^post3, i_5^0'=i_5^post3, __retres1_9^0'=__retres1_9^post3, Result_4^0'=Result_4^post3, d_6^0'=d_6^post3, __cil_tmp4_8^0'=__cil_tmp4_8^post3, (-__cil_tmp4_8^post3+__cil_tmp4_8^0 == 0 /\ -i_5^post3+i_5^0 == 0 /\ __cil_tmp2_10^0-__cil_tmp2_10^post3 == 0 /\ __retres3_7^0-__retres3_7^post3 == 0 /\ -__retres1_9^post3+__retres1_9^0 == 0 /\ d_6^0-d_6^post3 == 0 /\ Result_4^0-Result_4^post3 == 0), cost: 1 New rule: l4 -> l2 : TRUE, cost: 1 Applied preprocessing Original rule: l1 -> l2 : __retres3_7^0'=__retres3_7^post5, __cil_tmp2_10^0'=__cil_tmp2_10^post5, i_5^0'=i_5^post5, __retres1_9^0'=__retres1_9^post5, Result_4^0'=Result_4^post5, d_6^0'=d_6^post5, __cil_tmp4_8^0'=__cil_tmp4_8^post5, (__retres1_9^0-__retres1_9^post5 == 0 /\ -i_5^post5+i_5^0 == 0 /\ -__cil_tmp4_8^post5+__cil_tmp4_8^0 == 0 /\ 1+d_6^0 <= 0 /\ Result_4^0-Result_4^post5 == 0 /\ -d_6^post5+d_6^0 == 0 /\ __cil_tmp2_10^0-__cil_tmp2_10^post5 == 0 /\ __retres3_7^0-__retres3_7^post5 == 0), cost: 1 New rule: l1 -> l2 : 1+d_6^0 <= 0, cost: 1 Applied preprocessing Original rule: l6 -> l0 : __retres3_7^0'=__retres3_7^post7, __cil_tmp2_10^0'=__cil_tmp2_10^post7, i_5^0'=i_5^post7, __retres1_9^0'=__retres1_9^post7, Result_4^0'=Result_4^post7, d_6^0'=d_6^post7, __cil_tmp4_8^0'=__cil_tmp4_8^post7, (-__retres1_9^post7+__retres1_9^0 == 0 /\ -__cil_tmp4_8^post7+__cil_tmp4_8^0 == 0 /\ -d_6^post7+d_6^0 == 0 /\ i_5^0-i_5^post7 == 0 /\ __retres3_7^0-__retres3_7^post7 == 0 /\ -Result_4^post7+Result_4^0 == 0 /\ __cil_tmp2_10^0-__cil_tmp2_10^post7 == 0), cost: 1 New rule: l6 -> l0 : TRUE, cost: 1 Simplified rules Start location: l6 8: l0 -> l1 : TRUE, cost: 1 11: l1 -> l2 : 1+d_6^0 <= 0, cost: 1 9: l2 -> l4 : i_5^0'=i_5^0-d_6^0, i_5^0 >= 0, cost: 1 10: l4 -> l2 : TRUE, cost: 1 12: l6 -> l0 : TRUE, cost: 1 Eliminating location l0 by chaining: Applied chaining First rule: l6 -> l0 : TRUE, cost: 1 Second rule: l0 -> l1 : TRUE, cost: 1 New rule: l6 -> l1 : TRUE, cost: 2 Applied deletion Removed the following rules: 8 12 Eliminating location l1 by chaining: Applied chaining First rule: l6 -> l1 : TRUE, cost: 2 Second rule: l1 -> l2 : 1+d_6^0 <= 0, cost: 1 New rule: l6 -> l2 : 1+d_6^0 <= 0, cost: 3 Applied deletion Removed the following rules: 11 13 Eliminating location l4 by chaining: Applied chaining First rule: l2 -> l4 : i_5^0'=i_5^0-d_6^0, i_5^0 >= 0, cost: 1 Second rule: l4 -> l2 : TRUE, cost: 1 New rule: l2 -> l2 : i_5^0'=i_5^0-d_6^0, i_5^0 >= 0, cost: 2 Applied deletion Removed the following rules: 9 10 Eliminated locations on linear paths Start location: l6 15: l2 -> l2 : i_5^0'=i_5^0-d_6^0, i_5^0 >= 0, cost: 2 14: l6 -> l2 : 1+d_6^0 <= 0, cost: 3 Applied acceleration Original rule: l2 -> l2 : i_5^0'=i_5^0-d_6^0, i_5^0 >= 0, cost: 2 New rule: l2 -> l2 : i_5^0'=i_5^0-n*d_6^0, (i_5^0 >= 0 /\ n >= 0 /\ i_5^0-d_6^0*(-1+n) >= 0), cost: 2*n Sub-proof via acceration calculus written to file:///tmp/tmpnam_CHDnPB.txt Applied nonterm Original rule: l2 -> l2 : i_5^0'=i_5^0-d_6^0, i_5^0 >= 0, cost: 2 New rule: l2 -> [7] : (i_5^0 >= 0 /\ d_6^0 <= 0), cost: NONTERM Sub-proof via acceration calculus written to file:///tmp/tmpnam_hgFpIm.txt Applied deletion Removed the following rules: 15 Accelerated simple loops Start location: l6 16: l2 -> l2 : i_5^0'=i_5^0-n*d_6^0, (i_5^0 >= 0 /\ n >= 0 /\ i_5^0-d_6^0*(-1+n) >= 0), cost: 2*n 17: l2 -> [7] : (i_5^0 >= 0 /\ d_6^0 <= 0), cost: NONTERM 14: l6 -> l2 : 1+d_6^0 <= 0, cost: 3 Applied chaining First rule: l6 -> l2 : 1+d_6^0 <= 0, cost: 3 Second rule: l2 -> l2 : i_5^0'=i_5^0-n*d_6^0, (i_5^0 >= 0 /\ n >= 0 /\ i_5^0-d_6^0*(-1+n) >= 0), cost: 2*n New rule: l6 -> l2 : i_5^0'=i_5^0-n*d_6^0, (i_5^0 >= 0 /\ 1+d_6^0 <= 0 /\ n >= 0 /\ i_5^0-d_6^0*(-1+n) >= 0), cost: 3+2*n Applied chaining First rule: l6 -> l2 : 1+d_6^0 <= 0, cost: 3 Second rule: l2 -> [7] : (i_5^0 >= 0 /\ d_6^0 <= 0), cost: NONTERM New rule: l6 -> [7] : (i_5^0 >= 0 /\ 1+d_6^0 <= 0), cost: NONTERM Applied deletion Removed the following rules: 16 17 Chained accelerated rules with incoming rules Start location: l6 14: l6 -> l2 : 1+d_6^0 <= 0, cost: 3 18: l6 -> l2 : i_5^0'=i_5^0-n*d_6^0, (i_5^0 >= 0 /\ 1+d_6^0 <= 0 /\ n >= 0 /\ i_5^0-d_6^0*(-1+n) >= 0), cost: 3+2*n 19: l6 -> [7] : (i_5^0 >= 0 /\ 1+d_6^0 <= 0), cost: NONTERM Removed unreachable locations and irrelevant leafs Start location: l6 19: l6 -> [7] : (i_5^0 >= 0 /\ 1+d_6^0 <= 0), cost: NONTERM Computing asymptotic complexity Proved nontermination of rule 19 via SMT. Proved the following lower bound Complexity: Nonterm Cpx degree: Nonterm Solved cost: NONTERM Rule cost: NONTERM Rule guard: (i_5^0 >= 0 /\ 1+d_6^0 <= 0)