NO Initial ITS Start location: [1] Program variables: i j 0: [1] -> [2] : i'=nondet, T, cost: 1 1: [2] -> [3] : -10+i < 0, cost: 1 9: [2] -> [9] : -10+i >= 0, cost: 1 2: [3] -> [4] : j'=i, T, cost: 1 3: [4] -> [5] : -5+j > 0, cost: 1 6: [4] -> [7] : -5+j <= 0, cost: 1 4: [5] -> [6] : j'=1+j, T, cost: 1 5: [6] -> [4] : T, cost: 1 7: [7] -> [8] : i'=1+i, T, cost: 1 8: [8] -> [2] : T, cost: 1 Chained Linear Paths Start location: [1] Program variables: i j 0: [1] -> [2] : i'=nondet, T, cost: 1 9: [2] -> [9] : -10+i >= 0, cost: 1 10: [2] -> [4] : j'=i, -10+i < 0, cost: 1 13: [4] -> [4] : j'=1+j, -5+j > 0, cost: 1 14: [4] -> [2] : i'=1+i, -5+j <= 0, cost: 1 Eliminating location [3] by chaining: Applied chaining First rule: [2] -> [3] : -10+i < 0, cost: 1 Second rule: [3] -> [4] : j'=i, T, cost: 1 New rule: [2] -> [4] : j'=i, -10+i < 0, cost: 1 Applied deletion Removed the following rules: 1 2 Eliminating location [5] by chaining: Applied chaining First rule: [4] -> [5] : -5+j > 0, cost: 1 Second rule: [5] -> [6] : j'=1+j, T, cost: 1 New rule: [4] -> [6] : j'=1+j, -5+j > 0, cost: 1 Applied deletion Removed the following rules: 3 4 Eliminating location [7] by chaining: Applied chaining First rule: [4] -> [7] : -5+j <= 0, cost: 1 Second rule: [7] -> [8] : i'=1+i, T, cost: 1 New rule: [4] -> [8] : i'=1+i, -5+j <= 0, cost: 1 Applied deletion Removed the following rules: 6 7 Eliminating location [6] by chaining: Applied chaining First rule: [4] -> [6] : j'=1+j, -5+j > 0, cost: 1 Second rule: [6] -> [4] : T, cost: 1 New rule: [4] -> [4] : j'=1+j, -5+j > 0, cost: 1 Applied deletion Removed the following rules: 5 11 Eliminating location [8] by chaining: Applied chaining First rule: [4] -> [8] : i'=1+i, -5+j <= 0, cost: 1 Second rule: [8] -> [2] : T, cost: 1 New rule: [4] -> [2] : i'=1+i, -5+j <= 0, cost: 1 Applied deletion Removed the following rules: 8 12 Step with 0 Trace 0[T] Blocked [{}, {}] Step with 9 Trace 0[T], 9[(-10+i >= 0)] Blocked [{}, {}, {}] Backtrack Trace 0[T] Blocked [{}, {9[T]}] Step with 10 Trace 0[T], 10[(-10+i < 0)] Blocked [{}, {9[T]}, {}] Step with 13 Trace 0[T], 10[(-10+i < 0)], 13[(-5+j > 0)] Blocked [{}, {9[T]}, {}, {}] Nonterm Start location: [1] Program variables: i j 0: [1] -> [2] : i'=nondet, T, cost: 1 9: [2] -> [9] : -10+i >= 0, cost: 1 10: [2] -> [4] : j'=i, -10+i < 0, cost: 1 13: [4] -> [4] : j'=1+j, -5+j > 0, cost: 1 14: [4] -> [2] : i'=1+i, -5+j <= 0, cost: 1 15: [4] -> LoAT_sink : (-1+n >= 0 /\ -5+j > 0), cost: NONTERM 16: [4] -> [4] : j'=n+j, (-1+n >= 0 /\ -5+j > 0), cost: 1 Certificate of Non-Termination Original rule: [4] -> [4] : j'=1+j, (-5+j > 0), cost: 1 New rule: [4] -> LoAT_sink : (-1+n >= 0 /\ -5+j > 0), cost: NONTERM -5+j > 0 [0]: monotonic increase yields -5+j > 0 Replacement map: {-5+j > 0 -> -5+j > 0} Loop Acceleration Original rule: [4] -> [4] : j'=1+j, (-5+j > 0), cost: 1 New rule: [4] -> [4] : j'=n+j, (-1+n >= 0 /\ -5+j > 0), cost: 1 -5+j > 0 [0]: monotonic increase yields -5+j > 0 Replacement map: {-5+j > 0 -> -5+j > 0} Step with 15 Trace 0[T], 10[(-10+i < 0)], 15[(-1+n >= 0 /\ -5+j > 0)] Blocked [{}, {9[T]}, {}, {15[T]}] Refute Counterexample [ i=9 j=0 ] 0 [ i=9 j=9 ] 10 [ i=i j=0 ] 15 NO Build SHA: a05f16bf13df659c382799650051f91bf6828c7b