NO Initial ITS Start location: l5 0: l0 -> l1 : Result_4^0'=Result_4^post0, x_5^0'=x_5^post0, (x_5^0-x_5^post0 == 0 /\ Result_4^0-Result_4^post0 == 0), cost: 1 1: l1 -> l2 : Result_4^0'=Result_4^post1, x_5^0'=x_5^post1, (0 == 0 /\ -x_5^post1+x_5^0 == 0 /\ -x_5^0 <= 0 /\ x_5^0 <= 0), cost: 1 2: l1 -> l3 : Result_4^0'=Result_4^post2, x_5^0'=x_5^post2, (0 == 0 /\ Result_4^0-Result_4^post2 == 0 /\ -x_5^0 <= 0 /\ 1-x_5^0 <= 0 /\ -2-x_5^10+x_5^post2 == 0), cost: 1 4: l1 -> l4 : Result_4^0'=Result_4^post4, x_5^0'=x_5^post4, (0 == 0 /\ Result_4^0-Result_4^post4 == 0 /\ 2-x_5^11+x_5^post4 == 0 /\ 1+x_5^0 <= 0), cost: 1 3: l3 -> l1 : Result_4^0'=Result_4^post3, x_5^0'=x_5^post3, (Result_4^0-Result_4^post3 == 0 /\ -x_5^post3+x_5^0 == 0), cost: 1 5: l4 -> l1 : Result_4^0'=Result_4^post5, x_5^0'=x_5^post5, (Result_4^0-Result_4^post5 == 0 /\ -x_5^post5+x_5^0 == 0), cost: 1 6: l5 -> l0 : Result_4^0'=Result_4^post6, x_5^0'=x_5^post6, (Result_4^0-Result_4^post6 == 0 /\ x_5^0-x_5^post6 == 0), cost: 1 Removed unreachable rules and leafs Start location: l5 0: l0 -> l1 : Result_4^0'=Result_4^post0, x_5^0'=x_5^post0, (x_5^0-x_5^post0 == 0 /\ Result_4^0-Result_4^post0 == 0), cost: 1 2: l1 -> l3 : Result_4^0'=Result_4^post2, x_5^0'=x_5^post2, (0 == 0 /\ Result_4^0-Result_4^post2 == 0 /\ -x_5^0 <= 0 /\ 1-x_5^0 <= 0 /\ -2-x_5^10+x_5^post2 == 0), cost: 1 4: l1 -> l4 : Result_4^0'=Result_4^post4, x_5^0'=x_5^post4, (0 == 0 /\ Result_4^0-Result_4^post4 == 0 /\ 2-x_5^11+x_5^post4 == 0 /\ 1+x_5^0 <= 0), cost: 1 3: l3 -> l1 : Result_4^0'=Result_4^post3, x_5^0'=x_5^post3, (Result_4^0-Result_4^post3 == 0 /\ -x_5^post3+x_5^0 == 0), cost: 1 5: l4 -> l1 : Result_4^0'=Result_4^post5, x_5^0'=x_5^post5, (Result_4^0-Result_4^post5 == 0 /\ -x_5^post5+x_5^0 == 0), cost: 1 6: l5 -> l0 : Result_4^0'=Result_4^post6, x_5^0'=x_5^post6, (Result_4^0-Result_4^post6 == 0 /\ x_5^0-x_5^post6 == 0), cost: 1 Applied preprocessing Original rule: l0 -> l1 : Result_4^0'=Result_4^post0, x_5^0'=x_5^post0, (x_5^0-x_5^post0 == 0 /\ Result_4^0-Result_4^post0 == 0), cost: 1 New rule: l0 -> l1 : TRUE, cost: 1 Applied preprocessing Original rule: l1 -> l3 : Result_4^0'=Result_4^post2, x_5^0'=x_5^post2, (0 == 0 /\ Result_4^0-Result_4^post2 == 0 /\ -x_5^0 <= 0 /\ 1-x_5^0 <= 0 /\ -2-x_5^10+x_5^post2 == 0), cost: 1 New rule: l1 -> l3 : x_5^0'=2+x_5^10, -1+x_5^0 >= 0, cost: 1 Applied preprocessing Original rule: l3 -> l1 : Result_4^0'=Result_4^post3, x_5^0'=x_5^post3, (Result_4^0-Result_4^post3 == 0 /\ -x_5^post3+x_5^0 == 0), cost: 1 New rule: l3 -> l1 : TRUE, cost: 1 Applied preprocessing Original rule: l1 -> l4 : Result_4^0'=Result_4^post4, x_5^0'=x_5^post4, (0 == 0 /\ Result_4^0-Result_4^post4 == 0 /\ 2-x_5^11+x_5^post4 == 0 /\ 1+x_5^0 <= 0), cost: 1 New rule: l1 -> l4 : x_5^0'=-2+x_5^11, 1+x_5^0 <= 0, cost: 1 Applied preprocessing Original rule: l4 -> l1 : Result_4^0'=Result_4^post5, x_5^0'=x_5^post5, (Result_4^0-Result_4^post5 == 0 /\ -x_5^post5+x_5^0 == 0), cost: 1 New rule: l4 -> l1 : TRUE, cost: 1 Applied preprocessing Original rule: l5 -> l0 : Result_4^0'=Result_4^post6, x_5^0'=x_5^post6, (Result_4^0-Result_4^post6 == 0 /\ x_5^0-x_5^post6 == 0), cost: 1 New rule: l5 -> l0 : TRUE, cost: 1 Simplified rules Start location: l5 7: l0 -> l1 : TRUE, cost: 1 8: l1 -> l3 : x_5^0'=2+x_5^10, -1+x_5^0 >= 0, cost: 1 10: l1 -> l4 : x_5^0'=-2+x_5^11, 1+x_5^0 <= 0, cost: 1 9: l3 -> l1 : TRUE, cost: 1 11: l4 -> l1 : TRUE, cost: 1 12: l5 -> l0 : TRUE, cost: 1 Eliminating location l0 by chaining: Applied chaining First rule: l5 -> l0 : TRUE, cost: 1 Second rule: l0 -> l1 : TRUE, cost: 1 New rule: l5 -> l1 : TRUE, cost: 2 Applied deletion Removed the following rules: 7 12 Eliminating location l3 by chaining: Applied chaining First rule: l1 -> l3 : x_5^0'=2+x_5^10, -1+x_5^0 >= 0, cost: 1 Second rule: l3 -> l1 : TRUE, cost: 1 New rule: l1 -> l1 : x_5^0'=2+x_5^10, -1+x_5^0 >= 0, cost: 2 Applied deletion Removed the following rules: 8 9 Eliminating location l4 by chaining: Applied chaining First rule: l1 -> l4 : x_5^0'=-2+x_5^11, 1+x_5^0 <= 0, cost: 1 Second rule: l4 -> l1 : TRUE, cost: 1 New rule: l1 -> l1 : x_5^0'=-2+x_5^11, 1+x_5^0 <= 0, cost: 2 Applied deletion Removed the following rules: 10 11 Eliminated locations on linear paths Start location: l5 14: l1 -> l1 : x_5^0'=2+x_5^10, -1+x_5^0 >= 0, cost: 2 15: l1 -> l1 : x_5^0'=-2+x_5^11, 1+x_5^0 <= 0, cost: 2 13: l5 -> l1 : TRUE, cost: 2 Applied acceleration Original rule: l1 -> l1 : x_5^0'=2+x_5^10, -1+x_5^0 >= 0, cost: 2 New rule: l1 -> l1 : x_5^0'=2+x_5^10, (-1+n1 >= 0 /\ -1+x_5^0 >= 0 /\ 1+x_5^10 >= 0), cost: 2*n1 Applied unrolling Original rule: l1 -> l1 : x_5^0'=2+x_5^10, -1+x_5^0 >= 0, cost: 2 New rule: l1 -> l1 : x_5^0'=2+x_5^10, (-1+x_5^0 >= 0 /\ 1+x_5^10 >= 0), cost: 4 Applied non-termination processor Original rule: l1 -> l1 : x_5^0'=2+x_5^10, (-1+x_5^0 >= 0 /\ 1+x_5^10 >= 0), cost: 4 New rule: l1 -> [6] : (-1+x_5^0 >= 0 /\ 1+x_5^10 >= 0), cost: NONTERM Applied acceleration Original rule: l1 -> l1 : x_5^0'=-2+x_5^11, 1+x_5^0 <= 0, cost: 2 New rule: l1 -> l1 : x_5^0'=-2+x_5^11, (-1+n3 >= 0 /\ 1-x_5^11 >= 0 /\ -1-x_5^0 >= 0), cost: 2*n3 Applied unrolling Original rule: l1 -> l1 : x_5^0'=-2+x_5^11, 1+x_5^0 <= 0, cost: 2 New rule: l1 -> l1 : x_5^0'=-2+x_5^11, (-1+x_5^11 <= 0 /\ 1+x_5^0 <= 0), cost: 4 Applied non-termination processor Original rule: l1 -> l1 : x_5^0'=-2+x_5^11, (-1+x_5^11 <= 0 /\ 1+x_5^0 <= 0), cost: 4 New rule: l1 -> [6] : (-1+x_5^11 <= 0 /\ 1+x_5^0 <= 0), cost: NONTERM Applied chaining First rule: l1 -> l1 : x_5^0'=2+x_5^10, -1+x_5^0 >= 0, cost: 2 Second rule: l1 -> l1 : x_5^0'=-2+x_5^11, 1+x_5^0 <= 0, cost: 2 New rule: l1 -> l1 : x_5^0'=-2+x_5^11, -1+x_5^0 >= 0, cost: 4 Applied acceleration Original rule: l1 -> l1 : x_5^0'=-2+x_5^11, -1+x_5^0 >= 0, cost: 4 New rule: l1 -> l1 : x_5^0'=-2+x_5^11, (-1+n5 >= 0 /\ -1+x_5^0 >= 0 /\ -3+x_5^11 >= 0), cost: 4*n5 Applied chaining First rule: l1 -> l1 : x_5^0'=-2+x_5^11, 1+x_5^0 <= 0, cost: 2 Second rule: l1 -> l1 : x_5^0'=-2+x_5^11, (-1+n5 >= 0 /\ -1+x_5^0 >= 0 /\ -3+x_5^11 >= 0), cost: 4*n5 New rule: l1 -> l1 : x_5^0'=-2+x_5^11, (-1+n5 >= 0 /\ 1+x_5^0 <= 0 /\ -3+x_5^11 >= 0), cost: 2+4*n5 Applied chaining First rule: l1 -> l1 : x_5^0'=-2+x_5^11, 1+x_5^0 <= 0, cost: 2 Second rule: l1 -> l1 : x_5^0'=2+x_5^10, -1+x_5^0 >= 0, cost: 2 New rule: l1 -> l1 : x_5^0'=2+x_5^10, 1+x_5^0 <= 0, cost: 4 Applied acceleration Original rule: l1 -> l1 : x_5^0'=2+x_5^10, 1+x_5^0 <= 0, cost: 4 New rule: l1 -> l1 : x_5^0'=2+x_5^10, (-3-x_5^10 >= 0 /\ -1+n7 >= 0 /\ -1-x_5^0 >= 0), cost: 4*n7 Applied chaining First rule: l1 -> l1 : x_5^0'=2+x_5^10, -1+x_5^0 >= 0, cost: 2 Second rule: l1 -> l1 : x_5^0'=2+x_5^10, (-3-x_5^10 >= 0 /\ -1+n7 >= 0 /\ -1-x_5^0 >= 0), cost: 4*n7 New rule: l1 -> l1 : x_5^0'=2+x_5^10, (-3-x_5^10 >= 0 /\ -1+x_5^0 >= 0 /\ -1+n7 >= 0), cost: 2+4*n7 Applied simplification Original rule: l1 -> l1 : x_5^0'=-2+x_5^11, (-1+n3 >= 0 /\ 1-x_5^11 >= 0 /\ -1-x_5^0 >= 0), cost: 2*n3 New rule: l1 -> l1 : x_5^0'=-2+x_5^11, (-1+n3 >= 0 /\ -1+x_5^11 <= 0 /\ 1+x_5^0 <= 0), cost: 2*n3 Applied simplification Original rule: l1 -> l1 : x_5^0'=2+x_5^10, (-3-x_5^10 >= 0 /\ -1+n7 >= 0 /\ -1-x_5^0 >= 0), cost: 4*n7 New rule: l1 -> l1 : x_5^0'=2+x_5^10, (3+x_5^10 <= 0 /\ -1+n7 >= 0 /\ 1+x_5^0 <= 0), cost: 4*n7 Applied simplification Original rule: l1 -> l1 : x_5^0'=2+x_5^10, (-3-x_5^10 >= 0 /\ -1+x_5^0 >= 0 /\ -1+n7 >= 0), cost: 2+4*n7 New rule: l1 -> l1 : x_5^0'=2+x_5^10, (-1+x_5^0 >= 0 /\ 3+x_5^10 <= 0 /\ -1+n7 >= 0), cost: 2+4*n7 Applied deletion Removed the following rules: 14 15 Accelerated simple loops Start location: l5 16: l1 -> l1 : x_5^0'=2+x_5^10, (-1+n1 >= 0 /\ -1+x_5^0 >= 0 /\ 1+x_5^10 >= 0), cost: 2*n1 17: l1 -> [6] : (-1+x_5^0 >= 0 /\ 1+x_5^10 >= 0), cost: NONTERM 19: l1 -> [6] : (-1+x_5^11 <= 0 /\ 1+x_5^0 <= 0), cost: NONTERM 20: l1 -> l1 : x_5^0'=-2+x_5^11, (-1+n5 >= 0 /\ -1+x_5^0 >= 0 /\ -3+x_5^11 >= 0), cost: 4*n5 21: l1 -> l1 : x_5^0'=-2+x_5^11, (-1+n5 >= 0 /\ 1+x_5^0 <= 0 /\ -3+x_5^11 >= 0), cost: 2+4*n5 24: l1 -> l1 : x_5^0'=-2+x_5^11, (-1+n3 >= 0 /\ -1+x_5^11 <= 0 /\ 1+x_5^0 <= 0), cost: 2*n3 25: l1 -> l1 : x_5^0'=2+x_5^10, (3+x_5^10 <= 0 /\ -1+n7 >= 0 /\ 1+x_5^0 <= 0), cost: 4*n7 26: l1 -> l1 : x_5^0'=2+x_5^10, (-1+x_5^0 >= 0 /\ 3+x_5^10 <= 0 /\ -1+n7 >= 0), cost: 2+4*n7 13: l5 -> l1 : TRUE, cost: 2 Applied chaining First rule: l5 -> l1 : TRUE, cost: 2 Second rule: l1 -> l1 : x_5^0'=2+x_5^10, (-1+n1 >= 0 /\ -1+x_5^0 >= 0 /\ 1+x_5^10 >= 0), cost: 2*n1 New rule: l5 -> l1 : x_5^0'=2+x_5^10, (-1+n1 >= 0 /\ -1+x_5^0 >= 0 /\ 1+x_5^10 >= 0), cost: 2+2*n1 Applied chaining First rule: l5 -> l1 : TRUE, cost: 2 Second rule: l1 -> [6] : (-1+x_5^0 >= 0 /\ 1+x_5^10 >= 0), cost: NONTERM New rule: l5 -> [6] : -1+x_5^0 >= 0, cost: NONTERM Applied chaining First rule: l5 -> l1 : TRUE, cost: 2 Second rule: l1 -> [6] : (-1+x_5^11 <= 0 /\ 1+x_5^0 <= 0), cost: NONTERM New rule: l5 -> [6] : 1+x_5^0 <= 0, cost: NONTERM Applied chaining First rule: l5 -> l1 : TRUE, cost: 2 Second rule: l1 -> l1 : x_5^0'=-2+x_5^11, (-1+n5 >= 0 /\ -1+x_5^0 >= 0 /\ -3+x_5^11 >= 0), cost: 4*n5 New rule: l5 -> l1 : x_5^0'=-2+x_5^11, (-1+n5 >= 0 /\ -1+x_5^0 >= 0 /\ -3+x_5^11 >= 0), cost: 2+4*n5 Applied chaining First rule: l5 -> l1 : TRUE, cost: 2 Second rule: l1 -> l1 : x_5^0'=-2+x_5^11, (-1+n5 >= 0 /\ 1+x_5^0 <= 0 /\ -3+x_5^11 >= 0), cost: 2+4*n5 New rule: l5 -> l1 : x_5^0'=-2+x_5^11, (-1+n5 >= 0 /\ 1+x_5^0 <= 0 /\ -3+x_5^11 >= 0), cost: 4+4*n5 Applied chaining First rule: l5 -> l1 : TRUE, cost: 2 Second rule: l1 -> l1 : x_5^0'=-2+x_5^11, (-1+n3 >= 0 /\ -1+x_5^11 <= 0 /\ 1+x_5^0 <= 0), cost: 2*n3 New rule: l5 -> l1 : x_5^0'=-2+x_5^11, (-1+n3 >= 0 /\ -1+x_5^11 <= 0 /\ 1+x_5^0 <= 0), cost: 2+2*n3 Applied chaining First rule: l5 -> l1 : TRUE, cost: 2 Second rule: l1 -> l1 : x_5^0'=2+x_5^10, (3+x_5^10 <= 0 /\ -1+n7 >= 0 /\ 1+x_5^0 <= 0), cost: 4*n7 New rule: l5 -> l1 : x_5^0'=2+x_5^10, (3+x_5^10 <= 0 /\ -1+n7 >= 0 /\ 1+x_5^0 <= 0), cost: 2+4*n7 Applied chaining First rule: l5 -> l1 : TRUE, cost: 2 Second rule: l1 -> l1 : x_5^0'=2+x_5^10, (-1+x_5^0 >= 0 /\ 3+x_5^10 <= 0 /\ -1+n7 >= 0), cost: 2+4*n7 New rule: l5 -> l1 : x_5^0'=2+x_5^10, (-1+x_5^0 >= 0 /\ 3+x_5^10 <= 0 /\ -1+n7 >= 0), cost: 4+4*n7 Applied deletion Removed the following rules: 16 17 19 20 21 24 25 26 Chained accelerated rules with incoming rules Start location: l5 13: l5 -> l1 : TRUE, cost: 2 27: l5 -> l1 : x_5^0'=2+x_5^10, (-1+n1 >= 0 /\ -1+x_5^0 >= 0 /\ 1+x_5^10 >= 0), cost: 2+2*n1 28: l5 -> [6] : -1+x_5^0 >= 0, cost: NONTERM 29: l5 -> [6] : 1+x_5^0 <= 0, cost: NONTERM 30: l5 -> l1 : x_5^0'=-2+x_5^11, (-1+n5 >= 0 /\ -1+x_5^0 >= 0 /\ -3+x_5^11 >= 0), cost: 2+4*n5 31: l5 -> l1 : x_5^0'=-2+x_5^11, (-1+n5 >= 0 /\ 1+x_5^0 <= 0 /\ -3+x_5^11 >= 0), cost: 4+4*n5 32: l5 -> l1 : x_5^0'=-2+x_5^11, (-1+n3 >= 0 /\ -1+x_5^11 <= 0 /\ 1+x_5^0 <= 0), cost: 2+2*n3 33: l5 -> l1 : x_5^0'=2+x_5^10, (3+x_5^10 <= 0 /\ -1+n7 >= 0 /\ 1+x_5^0 <= 0), cost: 2+4*n7 34: l5 -> l1 : x_5^0'=2+x_5^10, (-1+x_5^0 >= 0 /\ 3+x_5^10 <= 0 /\ -1+n7 >= 0), cost: 4+4*n7 Removed unreachable locations and irrelevant leafs Start location: l5 28: l5 -> [6] : -1+x_5^0 >= 0, cost: NONTERM 29: l5 -> [6] : 1+x_5^0 <= 0, cost: NONTERM Computing asymptotic complexity Proved nontermination of rule 28 via SMT. Proved the following lower bound Complexity: Nonterm Cpx degree: Nonterm Solved cost: NONTERM Rule cost: NONTERM Rule guard: -1+x_5^0 >= 0