unknown Initial ITS Start location: [1] Program variables: p q 0: [1] -> [2] : q'=nondet, T, cost: 1 1: [2] -> [3] : p'=nondet1, T, cost: 1 2: [3] -> [4] : (p > 0 /\ q > 0 /\ (p-q < 0 \/ p-q > 0)), cost: 1 15: [3] -> [14] : (p <= 0 \/ q <= 0 \/ (p-q <= 0 /\ p-q >= 0)), cost: 1 3: [4] -> [6] : -p+q < 0, cost: 1 7: [4] -> [9] : -p+q >= 0, cost: 1 14: [5] -> [3] : T, cost: 1 4: [6] -> [7] : q'=-1+q, T, cost: 1 5: [7] -> [8] : p'=nondet2, T, cost: 1 6: [8] -> [5] : T, cost: 1 8: [9] -> [11] : p-q < 0, cost: 1 12: [9] -> [10] : p-q >= 0, cost: 1 13: [10] -> [5] : T, cost: 1 9: [11] -> [12] : p'=-1+p, T, cost: 1 10: [12] -> [13] : q'=nondet3, T, cost: 1 11: [13] -> [10] : T, cost: 1 Chained Linear Paths Start location: [1] Program variables: p q 16: [1] -> [3] : p'=nondet1, q'=nondet, T, cost: 1 2: [3] -> [4] : (p > 0 /\ q > 0 /\ (p-q < 0 \/ p-q > 0)), cost: 1 15: [3] -> [14] : (p <= 0 \/ q <= 0 \/ (p-q <= 0 /\ p-q >= 0)), cost: 1 7: [4] -> [9] : -p+q >= 0, cost: 1 19: [4] -> [5] : p'=nondet2, q'=-1+q, -p+q < 0, cost: 1 14: [5] -> [3] : T, cost: 1 12: [9] -> [10] : p-q >= 0, cost: 1 22: [9] -> [10] : p'=-1+p, q'=nondet3, p-q < 0, cost: 1 13: [10] -> [5] : T, cost: 1 Eliminating location [2] by chaining: Applied chaining First rule: [1] -> [2] : q'=nondet, T, cost: 1 Second rule: [2] -> [3] : p'=nondet1, T, cost: 1 New rule: [1] -> [3] : p'=nondet1, q'=nondet, T, cost: 1 Applied deletion Removed the following rules: 0 1 Eliminating location [6] by chaining: Applied chaining First rule: [4] -> [6] : -p+q < 0, cost: 1 Second rule: [6] -> [7] : q'=-1+q, T, cost: 1 New rule: [4] -> [7] : q'=-1+q, -p+q < 0, cost: 1 Applied deletion Removed the following rules: 3 4 Eliminating location [7] by chaining: Applied chaining First rule: [4] -> [7] : q'=-1+q, -p+q < 0, cost: 1 Second rule: [7] -> [8] : p'=nondet2, T, cost: 1 New rule: [4] -> [8] : p'=nondet2, q'=-1+q, -p+q < 0, cost: 1 Applied deletion Removed the following rules: 5 17 Eliminating location [8] by chaining: Applied chaining First rule: [4] -> [8] : p'=nondet2, q'=-1+q, -p+q < 0, cost: 1 Second rule: [8] -> [5] : T, cost: 1 New rule: [4] -> [5] : p'=nondet2, q'=-1+q, -p+q < 0, cost: 1 Applied deletion Removed the following rules: 6 18 Eliminating location [11] by chaining: Applied chaining First rule: [9] -> [11] : p-q < 0, cost: 1 Second rule: [11] -> [12] : p'=-1+p, T, cost: 1 New rule: [9] -> [12] : p'=-1+p, p-q < 0, cost: 1 Applied deletion Removed the following rules: 8 9 Eliminating location [12] by chaining: Applied chaining First rule: [9] -> [12] : p'=-1+p, p-q < 0, cost: 1 Second rule: [12] -> [13] : q'=nondet3, T, cost: 1 New rule: [9] -> [13] : p'=-1+p, q'=nondet3, p-q < 0, cost: 1 Applied deletion Removed the following rules: 10 20 Eliminating location [13] by chaining: Applied chaining First rule: [9] -> [13] : p'=-1+p, q'=nondet3, p-q < 0, cost: 1 Second rule: [13] -> [10] : T, cost: 1 New rule: [9] -> [10] : p'=-1+p, q'=nondet3, p-q < 0, cost: 1 Applied deletion Removed the following rules: 11 21 Step with 16 Trace 16[T] Blocked [{}, {}] Step with 15 Trace 16[T], 15[(p <= 0)] Blocked [{}, {}, {}] Backtrack Trace 16[T] Blocked [{}, {15[p <= 0]}] Step with 15 Trace 16[T], 15[(q <= 0)] Blocked [{}, {15[p <= 0]}, {}] Backtrack Trace 16[T] Blocked [{}, {15[(p <= 0 /\ q <= 0)]}] Step with 15 Trace 16[T], 15[(p-q <= 0 /\ p-q >= 0)] Blocked [{}, {15[(p <= 0 /\ q <= 0)]}, {}] Backtrack Trace 16[T] Blocked [{}, {15[(p-q <= 0 /\ p-q >= 0 /\ p <= 0 /\ q <= 0)]}] Step with 2 Trace 16[T], 2[(p-q > 0 /\ p > 0 /\ q > 0)] Blocked [{}, {15[T]}, {}] Step with 19 Trace 16[T], 2[(p-q > 0 /\ p > 0 /\ q > 0)], 19[(-p+q < 0)] Blocked [{}, {15[T]}, {7[T]}, {}] Step with 14 Trace 16[T], 2[(p-q > 0 /\ p > 0 /\ q > 0)], 19[(-p+q < 0)], 14[T] Blocked [{}, {15[T]}, {7[T]}, {}, {}] Accelerate Start location: [1] Program variables: p q 16: [1] -> [3] : p'=nondet1, q'=nondet, T, cost: 1 2: [3] -> [4] : (p > 0 /\ q > 0 /\ (p-q < 0 \/ p-q > 0)), cost: 1 15: [3] -> [14] : (p <= 0 \/ q <= 0 \/ (p-q <= 0 /\ p-q >= 0)), cost: 1 23: [3] -> [3] : p'=nondet21, q'=-n+q, (p-q > 0 /\ -1-nondet21+p <= 0 /\ nondet21 > 0 /\ -1+n >= 0 /\ 1-n+q > 0), cost: 1 7: [4] -> [9] : -p+q >= 0, cost: 1 19: [4] -> [5] : p'=nondet2, q'=-1+q, -p+q < 0, cost: 1 14: [5] -> [3] : T, cost: 1 12: [9] -> [10] : p-q >= 0, cost: 1 22: [9] -> [10] : p'=-1+p, q'=nondet3, p-q < 0, cost: 1 13: [10] -> [5] : T, cost: 1 Loop Acceleration Original rule: [3] -> [3] : p'=nondet21, q'=-1+q, (p-q > 0 /\ -p+q < 0 /\ p > 0 /\ q > 0), cost: 1 New rule: [3] -> [3] : p'=nondet21, q'=-n+q, (p-q > 0 /\ -1-nondet21+p <= 0 /\ nondet21 > 0 /\ -1+n >= 0 /\ 1-n+q > 0), cost: 1 p-q > 0 [0]: eventual increase yields (p-q > 0 /\ -1-nondet21+p <= 0) p > 0 [0]: montonic decrease yields nondet21 > 0, dependencies: p-q > 0 q > 0 p > 0 [1]: eventual decrease yields (nondet21 > 0 /\ p > 0) p > 0 [2]: eventual increase yields (-nondet21+p <= 0 /\ p > 0) q > 0 [0]: montonic decrease yields 1-n+q > 0 q > 0 [1]: eventual increase yields (1 <= 0 /\ q > 0) Replacement map: {p-q > 0 -> (p-q > 0 /\ -1-nondet21+p <= 0), p > 0 -> nondet21 > 0, q > 0 -> 1-n+q > 0} Trace 16[T], 23[(p-q > 0 /\ -1-nondet21+p <= 0 /\ nondet21 > 0 /\ -1+n >= 0 /\ 1-n+q > 0)] Blocked [{}, {15[T]}, {23[T]}] Step with 15 Trace 16[T], 23[(p-q > 0 /\ -1-nondet21+p <= 0 /\ nondet21 > 0 /\ -1+n >= 0 /\ 1-n+q > 0)], 15[(q <= 0)] Blocked [{}, {15[T]}, {23[T]}, {}] Backtrack Trace 16[T], 23[(p-q > 0 /\ -1-nondet21+p <= 0 /\ nondet21 > 0 /\ -1+n >= 0 /\ 1-n+q > 0)] Blocked [{}, {15[T]}, {15[q <= 0], 23[T]}] Step with 2 Trace 16[T], 23[(p-q > 0 /\ -1-nondet21+p <= 0 /\ nondet21 > 0 /\ -1+n >= 0 /\ 1-n+q > 0)], 2[(p-q > 0 /\ p > 0 /\ q > 0)] Blocked [{}, {15[T]}, {15[T], 23[T]}, {}] Step with 19 Trace 16[T], 23[(p-q > 0 /\ -1-nondet21+p <= 0 /\ nondet21 > 0 /\ -1+n >= 0 /\ 1-n+q > 0)], 2[(p-q > 0 /\ p > 0 /\ q > 0)], 19[(-p+q < 0)] Blocked [{}, {15[T]}, {15[T], 23[T]}, {}, {}] Step with 14 Trace 16[T], 23[(p-q > 0 /\ -1-nondet21+p <= 0 /\ nondet21 > 0 /\ -1+n >= 0 /\ 1-n+q > 0)], 2[(p-q > 0 /\ p > 0 /\ q > 0)], 19[(-p+q < 0)], 14[T] Blocked [{}, {15[T]}, {15[T], 23[T]}, {}, {}, {}] Covered Trace 16[T], 23[(p-q > 0 /\ -1-nondet21+p <= 0 /\ nondet21 > 0 /\ -1+n >= 0 /\ 1-n+q > 0)], 2[(p-q > 0 /\ p > 0 /\ q > 0)], 19[(-p+q < 0)] Blocked [{}, {15[T]}, {15[T], 23[T]}, {}, {14[T]}] Backtrack Trace 16[T], 23[(p-q > 0 /\ -1-nondet21+p <= 0 /\ nondet21 > 0 /\ -1+n >= 0 /\ 1-n+q > 0)], 2[(p-q > 0 /\ p > 0 /\ q > 0)] Blocked [{}, {15[T]}, {15[T], 23[T]}, {19[T]}] Backtrack Trace 16[T], 23[(p-q > 0 /\ -1-nondet21+p <= 0 /\ nondet21 > 0 /\ -1+n >= 0 /\ 1-n+q > 0)] Blocked [{}, {15[T]}, {2[(p-q > 0 /\ p > 0 /\ q > 0)], 15[T], 23[T]}] Backtrack Trace 16[T] Blocked [{}, {15[T], 23[T]}] Step with 2 Trace 16[T], 2[(p-q < 0 /\ p > 0 /\ q > 0)] Blocked [{}, {15[T], 23[T]}, {}] Step with 7 Trace 16[T], 2[(p-q < 0 /\ p > 0 /\ q > 0)], 7[(-p+q >= 0)] Blocked [{}, {15[T], 23[T]}, {19[T]}, {}] Step with 22 Trace 16[T], 2[(p-q < 0 /\ p > 0 /\ q > 0)], 7[(-p+q >= 0)], 22[(p-q < 0)] Blocked [{}, {15[T], 23[T]}, {19[T]}, {12[T]}, {}] Step with 13 Trace 16[T], 2[(p-q < 0 /\ p > 0 /\ q > 0)], 7[(-p+q >= 0)], 22[(p-q < 0)], 13[T] Blocked [{}, {15[T], 23[T]}, {19[T]}, {12[T]}, {}, {}] Step with 14 Trace 16[T], 2[(p-q < 0 /\ p > 0 /\ q > 0)], 7[(-p+q >= 0)], 22[(p-q < 0)], 13[T], 14[T] Blocked [{}, {15[T], 23[T]}, {19[T]}, {12[T]}, {}, {}, {}] Accelerate Start location: [1] Program variables: p q 16: [1] -> [3] : p'=nondet1, q'=nondet, T, cost: 1 2: [3] -> [4] : (p > 0 /\ q > 0 /\ (p-q < 0 \/ p-q > 0)), cost: 1 15: [3] -> [14] : (p <= 0 \/ q <= 0 \/ (p-q <= 0 /\ p-q >= 0)), cost: 1 23: [3] -> [3] : p'=nondet21, q'=-n+q, (p-q > 0 /\ -1-nondet21+p <= 0 /\ nondet21 > 0 /\ -1+n >= 0 /\ 1-n+q > 0), cost: 1 24: [3] -> [3] : p'=-n2+p, q'=nondet31, (1-n2+p > 0 /\ -p+q > 0 /\ nondet31 > 0 /\ -1-nondet31+q <= 0 /\ -1+n2 >= 0 /\ -1+n2+nondet31-p >= 0), cost: 1 7: [4] -> [9] : -p+q >= 0, cost: 1 19: [4] -> [5] : p'=nondet2, q'=-1+q, -p+q < 0, cost: 1 14: [5] -> [3] : T, cost: 1 12: [9] -> [10] : p-q >= 0, cost: 1 22: [9] -> [10] : p'=-1+p, q'=nondet3, p-q < 0, cost: 1 13: [10] -> [5] : T, cost: 1 Loop Acceleration Original rule: [3] -> [3] : p'=-1+p, q'=nondet31, (p-q < 0 /\ -p+q >= 0 /\ p > 0 /\ q > 0), cost: 1 New rule: [3] -> [3] : p'=-n2+p, q'=nondet31, (1-n2+p > 0 /\ -p+q > 0 /\ nondet31 > 0 /\ -1-nondet31+q <= 0 /\ -1+n2 >= 0 /\ -1+n2+nondet31-p >= 0), cost: 1 -p+q > 0 [0]: eventual increase yields (-p+q > 0 /\ -1-nondet31+q <= 0) -p+q >= 0 [0]: montonic decrease yields -1+n2+nondet31-p >= 0, dependencies: -p+q > 0 -p+q >= 0 [1]: eventual increase yields (-p+q >= 0 /\ -1-nondet31+q <= 0) p > 0 [0]: montonic decrease yields 1-n2+p > 0 p > 0 [1]: eventual increase yields (1 <= 0 /\ p > 0) q > 0 [0]: montonic decrease yields nondet31 > 0, dependencies: -p+q > 0 p > 0 q > 0 [1]: eventual increase yields (-nondet31+q <= 0 /\ q > 0) Replacement map: {-p+q > 0 -> (-p+q > 0 /\ -1-nondet31+q <= 0), -p+q >= 0 -> -1+n2+nondet31-p >= 0, p > 0 -> 1-n2+p > 0, q > 0 -> nondet31 > 0} Trace 16[T], 24[(1-n2+p > 0 /\ -p+q > 0 /\ nondet31 > 0 /\ -1-nondet31+q <= 0 /\ -1+n2 >= 0 /\ -1+n2+nondet31-p >= 0)] Blocked [{}, {15[T], 23[T]}, {24[T]}] Step with 15 Trace 16[T], 24[(1-n2+p > 0 /\ -p+q > 0 /\ nondet31 > 0 /\ -1-nondet31+q <= 0 /\ -1+n2 >= 0 /\ -1+n2+nondet31-p >= 0)], 15[(p <= 0)] Blocked [{}, {15[T], 23[T]}, {24[T]}, {}] Backtrack Trace 16[T], 24[(1-n2+p > 0 /\ -p+q > 0 /\ nondet31 > 0 /\ -1-nondet31+q <= 0 /\ -1+n2 >= 0 /\ -1+n2+nondet31-p >= 0)] Blocked [{}, {15[T], 23[T]}, {15[p <= 0], 24[T]}] Step with 2 Trace 16[T], 24[(1-n2+p > 0 /\ -p+q > 0 /\ nondet31 > 0 /\ -1-nondet31+q <= 0 /\ -1+n2 >= 0 /\ -1+n2+nondet31-p >= 0)], 2[(p-q < 0 /\ p > 0 /\ q > 0)] Blocked [{}, {15[T], 23[T]}, {15[T], 24[T]}, {}] Step with 7 Trace 16[T], 24[(1-n2+p > 0 /\ -p+q > 0 /\ nondet31 > 0 /\ -1-nondet31+q <= 0 /\ -1+n2 >= 0 /\ -1+n2+nondet31-p >= 0)], 2[(p-q < 0 /\ p > 0 /\ q > 0)], 7[(-p+q >= 0)] Blocked [{}, {15[T], 23[T]}, {15[T], 24[T]}, {}, {}] Step with 22 Trace 16[T], 24[(1-n2+p > 0 /\ -p+q > 0 /\ nondet31 > 0 /\ -1-nondet31+q <= 0 /\ -1+n2 >= 0 /\ -1+n2+nondet31-p >= 0)], 2[(p-q < 0 /\ p > 0 /\ q > 0)], 7[(-p+q >= 0)], 22[(p-q < 0)] Blocked [{}, {15[T], 23[T]}, {15[T], 24[T]}, {}, {}, {}] Step with 13 Trace 16[T], 24[(1-n2+p > 0 /\ -p+q > 0 /\ nondet31 > 0 /\ -1-nondet31+q <= 0 /\ -1+n2 >= 0 /\ -1+n2+nondet31-p >= 0)], 2[(p-q < 0 /\ p > 0 /\ q > 0)], 7[(-p+q >= 0)], 22[(p-q < 0)], 13[T] Blocked [{}, {15[T], 23[T]}, {15[T], 24[T]}, {}, {}, {}, {}] Step with 14 Trace 16[T], 24[(1-n2+p > 0 /\ -p+q > 0 /\ nondet31 > 0 /\ -1-nondet31+q <= 0 /\ -1+n2 >= 0 /\ -1+n2+nondet31-p >= 0)], 2[(p-q < 0 /\ p > 0 /\ q > 0)], 7[(-p+q >= 0)], 22[(p-q < 0)], 13[T], 14[T] Blocked [{}, {15[T], 23[T]}, {15[T], 24[T]}, {}, {}, {}, {}, {}] Covered Trace 16[T], 24[(1-n2+p > 0 /\ -p+q > 0 /\ nondet31 > 0 /\ -1-nondet31+q <= 0 /\ -1+n2 >= 0 /\ -1+n2+nondet31-p >= 0)], 2[(p-q < 0 /\ p > 0 /\ q > 0)], 7[(-p+q >= 0)], 22[(p-q < 0)], 13[T] Blocked [{}, {15[T], 23[T]}, {15[T], 24[T]}, {}, {}, {}, {14[T]}] Backtrack Trace 16[T], 24[(1-n2+p > 0 /\ -p+q > 0 /\ nondet31 > 0 /\ -1-nondet31+q <= 0 /\ -1+n2 >= 0 /\ -1+n2+nondet31-p >= 0)], 2[(p-q < 0 /\ p > 0 /\ q > 0)], 7[(-p+q >= 0)], 22[(p-q < 0)] Blocked [{}, {15[T], 23[T]}, {15[T], 24[T]}, {}, {}, {13[T]}] Backtrack Trace 16[T], 24[(1-n2+p > 0 /\ -p+q > 0 /\ nondet31 > 0 /\ -1-nondet31+q <= 0 /\ -1+n2 >= 0 /\ -1+n2+nondet31-p >= 0)], 2[(p-q < 0 /\ p > 0 /\ q > 0)], 7[(-p+q >= 0)] Blocked [{}, {15[T], 23[T]}, {15[T], 24[T]}, {}, {22[T]}] Backtrack Trace 16[T], 24[(1-n2+p > 0 /\ -p+q > 0 /\ nondet31 > 0 /\ -1-nondet31+q <= 0 /\ -1+n2 >= 0 /\ -1+n2+nondet31-p >= 0)], 2[(p-q < 0 /\ p > 0 /\ q > 0)] Blocked [{}, {15[T], 23[T]}, {15[T], 24[T]}, {7[T]}] Backtrack Trace 16[T], 24[(1-n2+p > 0 /\ -p+q > 0 /\ nondet31 > 0 /\ -1-nondet31+q <= 0 /\ -1+n2 >= 0 /\ -1+n2+nondet31-p >= 0)] Blocked [{}, {15[T], 23[T]}, {2[(p-q < 0 /\ p > 0 /\ q > 0)], 15[T], 24[T]}] Backtrack Trace 16[T] Blocked [{}, {15[T], 23[T], 24[T]}] Step with 2 Trace 16[T], 2[(p-q < 0 /\ p > 0 /\ q > 0)] Blocked [{}, {15[T], 23[T], 24[T]}, {}] Step with 7 Trace 16[T], 2[(p-q < 0 /\ p > 0 /\ q > 0)], 7[(-p+q >= 0)] Blocked [{}, {15[T], 23[T], 24[T]}, {}, {}] Step with 22 Trace 16[T], 2[(p-q < 0 /\ p > 0 /\ q > 0)], 7[(-p+q >= 0)], 22[(p-q < 0)] Blocked [{}, {15[T], 23[T], 24[T]}, {}, {}, {}] Step with 13 Trace 16[T], 2[(p-q < 0 /\ p > 0 /\ q > 0)], 7[(-p+q >= 0)], 22[(p-q < 0)], 13[T] Blocked [{}, {15[T], 23[T], 24[T]}, {}, {}, {}, {}] Step with 14 Trace 16[T], 2[(p-q < 0 /\ p > 0 /\ q > 0)], 7[(-p+q >= 0)], 22[(p-q < 0)], 13[T], 14[T] Blocked [{}, {15[T], 23[T], 24[T]}, {}, {}, {}, {}, {}] Covered Trace 16[T], 2[(p-q < 0 /\ p > 0 /\ q > 0)], 7[(-p+q >= 0)], 22[(p-q < 0)], 13[T] Blocked [{}, {15[T], 23[T], 24[T]}, {}, {}, {}, {14[T]}] Backtrack Trace 16[T], 2[(p-q < 0 /\ p > 0 /\ q > 0)], 7[(-p+q >= 0)], 22[(p-q < 0)] Blocked [{}, {15[T], 23[T], 24[T]}, {}, {}, {13[T]}] Backtrack Trace 16[T], 2[(p-q < 0 /\ p > 0 /\ q > 0)], 7[(-p+q >= 0)] Blocked [{}, {15[T], 23[T], 24[T]}, {}, {22[T]}] Backtrack Trace 16[T], 2[(p-q < 0 /\ p > 0 /\ q > 0)] Blocked [{}, {15[T], 23[T], 24[T]}, {7[T]}] Backtrack Trace 16[T] Blocked [{}, {2[(p-q < 0 /\ p > 0 /\ q > 0)], 15[T], 23[T], 24[T]}] Step with 2 Trace 16[T], 2[(p-q > 0 /\ p > 0 /\ q > 0)] Blocked [{}, {2[(p-q < 0 /\ p > 0 /\ q > 0)], 15[T], 23[T], 24[T]}, {}] Step with 19 Trace 16[T], 2[(p-q > 0 /\ p > 0 /\ q > 0)], 19[(-p+q < 0)] Blocked [{}, {2[(p-q < 0 /\ p > 0 /\ q > 0)], 15[T], 23[T], 24[T]}, {7[T]}, {}] Step with 14 Trace 16[T], 2[(p-q > 0 /\ p > 0 /\ q > 0)], 19[(-p+q < 0)], 14[T] Blocked [{}, {2[(p-q < 0 /\ p > 0 /\ q > 0)], 15[T], 23[T], 24[T]}, {7[T]}, {}, {}] Covered Trace 16[T], 2[(p-q > 0 /\ p > 0 /\ q > 0)], 19[(-p+q < 0)] Blocked [{}, {2[(p-q < 0 /\ p > 0 /\ q > 0)], 15[T], 23[T], 24[T]}, {7[T]}, {14[T]}] Backtrack Trace 16[T], 2[(p-q > 0 /\ p > 0 /\ q > 0)] Blocked [{}, {2[(p-q < 0 /\ p > 0 /\ q > 0)], 15[T], 23[T], 24[T]}, {7[T], 19[T]}] Backtrack Trace 16[T] Blocked [{}, {2[(p-q < 0 /\ p-q > 0 /\ p > 0 /\ q > 0)], 15[T], 23[T], 24[T]}] Backtrack Trace Blocked [{16[T]}] Accept unknown Build SHA: a05f16bf13df659c382799650051f91bf6828c7b