LTS Termination Proof

by T2Cert

Input

Integer Transition System

Initial Location: 10

Transitions: (pre-variables and post-variables)

0	0	1:	0 ≤ 0 ∧ 0 ≤ 0 ∧ 0 ≤ 0 ∧ 0 ≤ 0 ∧ − ___const_100_0 + k_0 ≤ 0 ∧ i_post ≤ 0 ∧ − i_post ≤ 0 ∧ i_0 − i_post ≤ 0 ∧ − i_0 + i_post ≤ 0 ∧ tmp___0_0 − tmp___0_post ≤ 0 ∧ − tmp___0_0 + tmp___0_post ≤ 0 ∧ − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − k_post + k_post ≤ 0 ∧ k_post − k_post ≤ 0 ∧ − k_0 + k_0 ≤ 0 ∧ k_0 − k_0 ≤ 0 ∧ − j_post + j_post ≤ 0 ∧ j_post − j_post ≤ 0 ∧ − j_0 + j_0 ≤ 0 ∧ j_0 − j_0 ≤ 0 ∧ − ___const_100_0 + ___const_100_0 ≤ 0 ∧ ___const_100_0 − ___const_100_0 ≤ 0
0	1	2:	1 + ___const_100_0 − k_0 ≤ 0 ∧ − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp___0_post + tmp___0_post ≤ 0 ∧ tmp___0_post − tmp___0_post ≤ 0 ∧ − tmp___0_0 + tmp___0_0 ≤ 0 ∧ tmp___0_0 − tmp___0_0 ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − k_post + k_post ≤ 0 ∧ k_post − k_post ≤ 0 ∧ − k_0 + k_0 ≤ 0 ∧ k_0 − k_0 ≤ 0 ∧ − j_post + j_post ≤ 0 ∧ j_post − j_post ≤ 0 ∧ − j_0 + j_0 ≤ 0 ∧ j_0 − j_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − ___const_100_0 + ___const_100_0 ≤ 0 ∧ ___const_100_0 − ___const_100_0 ≤ 0
3	2	0:	1 − k_0 ≤ 0 ∧ − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp___0_post + tmp___0_post ≤ 0 ∧ tmp___0_post − tmp___0_post ≤ 0 ∧ − tmp___0_0 + tmp___0_0 ≤ 0 ∧ tmp___0_0 − tmp___0_0 ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − k_post + k_post ≤ 0 ∧ k_post − k_post ≤ 0 ∧ − k_0 + k_0 ≤ 0 ∧ k_0 − k_0 ≤ 0 ∧ − j_post + j_post ≤ 0 ∧ j_post − j_post ≤ 0 ∧ − j_0 + j_0 ≤ 0 ∧ j_0 − j_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − ___const_100_0 + ___const_100_0 ≤ 0 ∧ ___const_100_0 − ___const_100_0 ≤ 0
3	3	2:	k_0 ≤ 0 ∧ − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp___0_post + tmp___0_post ≤ 0 ∧ tmp___0_post − tmp___0_post ≤ 0 ∧ − tmp___0_0 + tmp___0_0 ≤ 0 ∧ tmp___0_0 − tmp___0_0 ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − k_post + k_post ≤ 0 ∧ k_post − k_post ≤ 0 ∧ − k_0 + k_0 ≤ 0 ∧ k_0 − k_0 ≤ 0 ∧ − j_post + j_post ≤ 0 ∧ j_post − j_post ≤ 0 ∧ − j_0 + j_0 ≤ 0 ∧ j_0 − j_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − ___const_100_0 + ___const_100_0 ≤ 0 ∧ ___const_100_0 − ___const_100_0 ≤ 0
1	4	4:	− tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp___0_post + tmp___0_post ≤ 0 ∧ tmp___0_post − tmp___0_post ≤ 0 ∧ − tmp___0_0 + tmp___0_0 ≤ 0 ∧ tmp___0_0 − tmp___0_0 ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − k_post + k_post ≤ 0 ∧ k_post − k_post ≤ 0 ∧ − k_0 + k_0 ≤ 0 ∧ k_0 − k_0 ≤ 0 ∧ − j_post + j_post ≤ 0 ∧ j_post − j_post ≤ 0 ∧ − j_0 + j_0 ≤ 0 ∧ j_0 − j_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − ___const_100_0 + ___const_100_0 ≤ 0 ∧ ___const_100_0 − ___const_100_0 ≤ 0
5	5	2:	i_0 − j_0 ≤ 0 ∧ − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp___0_post + tmp___0_post ≤ 0 ∧ tmp___0_post − tmp___0_post ≤ 0 ∧ − tmp___0_0 + tmp___0_0 ≤ 0 ∧ tmp___0_0 − tmp___0_0 ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − k_post + k_post ≤ 0 ∧ k_post − k_post ≤ 0 ∧ − k_0 + k_0 ≤ 0 ∧ k_0 − k_0 ≤ 0 ∧ − j_post + j_post ≤ 0 ∧ j_post − j_post ≤ 0 ∧ − j_0 + j_0 ≤ 0 ∧ j_0 − j_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − ___const_100_0 + ___const_100_0 ≤ 0 ∧ ___const_100_0 − ___const_100_0 ≤ 0
5	6	6:	0 ≤ 0 ∧ 0 ≤ 0 ∧ 1 − i_0 + j_0 ≤ 0 ∧ −1 − j_0 + j_post ≤ 0 ∧ 1 + j_0 − j_post ≤ 0 ∧ j_0 − j_post ≤ 0 ∧ − j_0 + j_post ≤ 0 ∧ − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp___0_post + tmp___0_post ≤ 0 ∧ tmp___0_post − tmp___0_post ≤ 0 ∧ − tmp___0_0 + tmp___0_0 ≤ 0 ∧ tmp___0_0 − tmp___0_0 ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − k_post + k_post ≤ 0 ∧ k_post − k_post ≤ 0 ∧ − k_0 + k_0 ≤ 0 ∧ k_0 − k_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − ___const_100_0 + ___const_100_0 ≤ 0 ∧ ___const_100_0 − ___const_100_0 ≤ 0
7	7	6:	0 ≤ 0 ∧ 0 ≤ 0 ∧ 0 ≤ 0 ∧ 0 ≤ 0 ∧ 1 − i_0 + i_post ≤ 0 ∧ −1 + i_0 − i_post ≤ 0 ∧ j_post ≤ 0 ∧ − j_post ≤ 0 ∧ i_0 − i_post ≤ 0 ∧ − i_0 + i_post ≤ 0 ∧ j_0 − j_post ≤ 0 ∧ − j_0 + j_post ≤ 0 ∧ − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp___0_post + tmp___0_post ≤ 0 ∧ tmp___0_post − tmp___0_post ≤ 0 ∧ − tmp___0_0 + tmp___0_0 ≤ 0 ∧ tmp___0_0 − tmp___0_0 ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − k_post + k_post ≤ 0 ∧ k_post − k_post ≤ 0 ∧ − k_0 + k_0 ≤ 0 ∧ k_0 − k_0 ≤ 0 ∧ − ___const_100_0 + ___const_100_0 ≤ 0 ∧ ___const_100_0 − ___const_100_0 ≤ 0
6	8	5:	− tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp___0_post + tmp___0_post ≤ 0 ∧ tmp___0_post − tmp___0_post ≤ 0 ∧ − tmp___0_0 + tmp___0_0 ≤ 0 ∧ tmp___0_0 − tmp___0_0 ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − k_post + k_post ≤ 0 ∧ k_post − k_post ≤ 0 ∧ − k_0 + k_0 ≤ 0 ∧ k_0 − k_0 ≤ 0 ∧ − j_post + j_post ≤ 0 ∧ j_post − j_post ≤ 0 ∧ − j_0 + j_0 ≤ 0 ∧ j_0 − j_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − ___const_100_0 + ___const_100_0 ≤ 0 ∧ ___const_100_0 − ___const_100_0 ≤ 0
8	9	1:	0 ≤ 0 ∧ 0 ≤ 0 ∧ −1 − i_0 + i_post ≤ 0 ∧ 1 + i_0 − i_post ≤ 0 ∧ i_0 − i_post ≤ 0 ∧ − i_0 + i_post ≤ 0 ∧ − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp___0_post + tmp___0_post ≤ 0 ∧ tmp___0_post − tmp___0_post ≤ 0 ∧ − tmp___0_0 + tmp___0_0 ≤ 0 ∧ tmp___0_0 − tmp___0_0 ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − k_post + k_post ≤ 0 ∧ k_post − k_post ≤ 0 ∧ − k_0 + k_0 ≤ 0 ∧ k_0 − k_0 ≤ 0 ∧ − j_post + j_post ≤ 0 ∧ j_post − j_post ≤ 0 ∧ − j_0 + j_0 ≤ 0 ∧ j_0 − j_0 ≤ 0 ∧ − ___const_100_0 + ___const_100_0 ≤ 0 ∧ ___const_100_0 − ___const_100_0 ≤ 0
8	10	7:	− tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp___0_post + tmp___0_post ≤ 0 ∧ tmp___0_post − tmp___0_post ≤ 0 ∧ − tmp___0_0 + tmp___0_0 ≤ 0 ∧ tmp___0_0 − tmp___0_0 ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − k_post + k_post ≤ 0 ∧ k_post − k_post ≤ 0 ∧ − k_0 + k_0 ≤ 0 ∧ k_0 − k_0 ≤ 0 ∧ − j_post + j_post ≤ 0 ∧ j_post − j_post ≤ 0 ∧ − j_0 + j_0 ≤ 0 ∧ j_0 − j_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − ___const_100_0 + ___const_100_0 ≤ 0 ∧ ___const_100_0 − ___const_100_0 ≤ 0
4	11	7:	i_0 − k_0 ≤ 0 ∧ − i_0 + k_0 ≤ 0 ∧ − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp___0_post + tmp___0_post ≤ 0 ∧ tmp___0_post − tmp___0_post ≤ 0 ∧ − tmp___0_0 + tmp___0_0 ≤ 0 ∧ tmp___0_0 − tmp___0_0 ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − k_post + k_post ≤ 0 ∧ k_post − k_post ≤ 0 ∧ − k_0 + k_0 ≤ 0 ∧ k_0 − k_0 ≤ 0 ∧ − j_post + j_post ≤ 0 ∧ j_post − j_post ≤ 0 ∧ − j_0 + j_0 ≤ 0 ∧ j_0 − j_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − ___const_100_0 + ___const_100_0 ≤ 0 ∧ ___const_100_0 − ___const_100_0 ≤ 0
4	12	8:	1 − i_0 + k_0 ≤ 0 ∧ − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp___0_post + tmp___0_post ≤ 0 ∧ tmp___0_post − tmp___0_post ≤ 0 ∧ − tmp___0_0 + tmp___0_0 ≤ 0 ∧ tmp___0_0 − tmp___0_0 ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − k_post + k_post ≤ 0 ∧ k_post − k_post ≤ 0 ∧ − k_0 + k_0 ≤ 0 ∧ k_0 − k_0 ≤ 0 ∧ − j_post + j_post ≤ 0 ∧ j_post − j_post ≤ 0 ∧ − j_0 + j_0 ≤ 0 ∧ j_0 − j_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − ___const_100_0 + ___const_100_0 ≤ 0 ∧ ___const_100_0 − ___const_100_0 ≤ 0
4	13	8:	1 + i_0 − k_0 ≤ 0 ∧ − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp___0_post + tmp___0_post ≤ 0 ∧ tmp___0_post − tmp___0_post ≤ 0 ∧ − tmp___0_0 + tmp___0_0 ≤ 0 ∧ tmp___0_0 − tmp___0_0 ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − k_post + k_post ≤ 0 ∧ k_post − k_post ≤ 0 ∧ − k_0 + k_0 ≤ 0 ∧ k_0 − k_0 ≤ 0 ∧ − j_post + j_post ≤ 0 ∧ j_post − j_post ≤ 0 ∧ − j_0 + j_0 ≤ 0 ∧ j_0 − j_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − ___const_100_0 + ___const_100_0 ≤ 0 ∧ ___const_100_0 − ___const_100_0 ≤ 0
9	14	3:	0 ≤ 0 ∧ 0 ≤ 0 ∧ 0 ≤ 0 ∧ 0 ≤ 0 ∧ k_post − tmp_post ≤ 0 ∧ − k_post + tmp_post ≤ 0 ∧ k_0 − k_post ≤ 0 ∧ − k_0 + k_post ≤ 0 ∧ tmp_0 − tmp_post ≤ 0 ∧ − tmp_0 + tmp_post ≤ 0 ∧ − tmp___0_post + tmp___0_post ≤ 0 ∧ tmp___0_post − tmp___0_post ≤ 0 ∧ − tmp___0_0 + tmp___0_0 ≤ 0 ∧ tmp___0_0 − tmp___0_0 ≤ 0 ∧ − j_post + j_post ≤ 0 ∧ j_post − j_post ≤ 0 ∧ − j_0 + j_0 ≤ 0 ∧ j_0 − j_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − ___const_100_0 + ___const_100_0 ≤ 0 ∧ ___const_100_0 − ___const_100_0 ≤ 0
10	15	9:	− tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp___0_post + tmp___0_post ≤ 0 ∧ tmp___0_post − tmp___0_post ≤ 0 ∧ − tmp___0_0 + tmp___0_0 ≤ 0 ∧ tmp___0_0 − tmp___0_0 ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − k_post + k_post ≤ 0 ∧ k_post − k_post ≤ 0 ∧ − k_0 + k_0 ≤ 0 ∧ k_0 − k_0 ≤ 0 ∧ − j_post + j_post ≤ 0 ∧ j_post − j_post ≤ 0 ∧ − j_0 + j_0 ≤ 0 ∧ j_0 − j_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − ___const_100_0 + ___const_100_0 ≤ 0 ∧ ___const_100_0 − ___const_100_0 ≤ 0

Proof

1 Invariant Updates

The following invariants are asserted.

0:	1 − k_0 ≤ 0
1:	1 − k_0 ≤ 0
2:	TRUE
3:	TRUE
4:	1 − k_0 ≤ 0
5:	1 − k_0 ≤ 0
6:	1 − k_0 ≤ 0
7:	1 − k_0 ≤ 0
8:	1 − k_0 ≤ 0
9:	TRUE
10:	TRUE

The invariants are proved as follows.

IMPACT Invariant Proof

nodes (location) invariant:

0	(0)	1 − k_0 ≤ 0
1	(1)	1 − k_0 ≤ 0
2	(2)	TRUE
3	(3)	TRUE
4	(4)	1 − k_0 ≤ 0
5	(5)	1 − k_0 ≤ 0
6	(6)	1 − k_0 ≤ 0
7	(7)	1 − k_0 ≤ 0
8	(8)	1 − k_0 ≤ 0
9	(9)	TRUE
10	(10)	TRUE

initial node: 10
cover edges:
transition edges:

0 0 1

0 1 2

1 4 4

3 2 0

3 3 2

4 11 7

4 12 8

4 13 8

5 5 2

5 6 6

6 8 5

7 7 6

8 9 1

8 10 7

9 14 3

10 15 9

2 Switch to Cooperation Termination Proof

We consider the following cutpoint-transitions:

1	16	1:	− tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp___0_post + tmp___0_post ≤ 0 ∧ tmp___0_post − tmp___0_post ≤ 0 ∧ − tmp___0_0 + tmp___0_0 ≤ 0 ∧ tmp___0_0 − tmp___0_0 ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − k_post + k_post ≤ 0 ∧ k_post − k_post ≤ 0 ∧ − k_0 + k_0 ≤ 0 ∧ k_0 − k_0 ≤ 0 ∧ − j_post + j_post ≤ 0 ∧ j_post − j_post ≤ 0 ∧ − j_0 + j_0 ≤ 0 ∧ j_0 − j_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − ___const_100_0 + ___const_100_0 ≤ 0 ∧ ___const_100_0 − ___const_100_0 ≤ 0
6	23	6:	− tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp___0_post + tmp___0_post ≤ 0 ∧ tmp___0_post − tmp___0_post ≤ 0 ∧ − tmp___0_0 + tmp___0_0 ≤ 0 ∧ tmp___0_0 − tmp___0_0 ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − k_post + k_post ≤ 0 ∧ k_post − k_post ≤ 0 ∧ − k_0 + k_0 ≤ 0 ∧ k_0 − k_0 ≤ 0 ∧ − j_post + j_post ≤ 0 ∧ j_post − j_post ≤ 0 ∧ − j_0 + j_0 ≤ 0 ∧ j_0 − j_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − ___const_100_0 + ___const_100_0 ≤ 0 ∧ ___const_100_0 − ___const_100_0 ≤ 0

and for every transition t, a duplicate t is considered.

3 Transition Removal

We remove transitions 0, 1, 2, 3, 5, 7, 10, 11, 14, 15 using the following ranking functions, which are bounded by −23.

10:	0
9:	0
3:	0
0:	0
1:	0
4:	0
8:	0
7:	0
5:	0
6:	0
2:	0
10:	−9
9:	−10
3:	−11
0:	−12
1:	−13
4:	−13
8:	−13
1_var_snapshot:	−13
1*:	−13
7:	−14
5:	−15
6:	−15
6_var_snapshot:	−15
6*:	−15
2:	−21

4 Location Addition

The following skip-transition is inserted and corresponding redirections w.r.t. the old location are performed.

1* 19 1: − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp___0_post + tmp___0_post ≤ 0 ∧ tmp___0_post − tmp___0_post ≤ 0 ∧ − tmp___0_0 + tmp___0_0 ≤ 0 ∧ tmp___0_0 − tmp___0_0 ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − k_post + k_post ≤ 0 ∧ k_post − k_post ≤ 0 ∧ − k_0 + k_0 ≤ 0 ∧ k_0 − k_0 ≤ 0 ∧ − j_post + j_post ≤ 0 ∧ j_post − j_post ≤ 0 ∧ − j_0 + j_0 ≤ 0 ∧ j_0 − j_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − ___const_100_0 + ___const_100_0 ≤ 0 ∧ ___const_100_0 − ___const_100_0 ≤ 0

5 Location Addition

The following skip-transition is inserted and corresponding redirections w.r.t. the old location are performed.

1 17 1_var_snapshot: − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp___0_post + tmp___0_post ≤ 0 ∧ tmp___0_post − tmp___0_post ≤ 0 ∧ − tmp___0_0 + tmp___0_0 ≤ 0 ∧ tmp___0_0 − tmp___0_0 ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − k_post + k_post ≤ 0 ∧ k_post − k_post ≤ 0 ∧ − k_0 + k_0 ≤ 0 ∧ k_0 − k_0 ≤ 0 ∧ − j_post + j_post ≤ 0 ∧ j_post − j_post ≤ 0 ∧ − j_0 + j_0 ≤ 0 ∧ j_0 − j_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − ___const_100_0 + ___const_100_0 ≤ 0 ∧ ___const_100_0 − ___const_100_0 ≤ 0

6 Location Addition

The following skip-transition is inserted and corresponding redirections w.r.t. the old location are performed.

6* 26 6: − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp___0_post + tmp___0_post ≤ 0 ∧ tmp___0_post − tmp___0_post ≤ 0 ∧ − tmp___0_0 + tmp___0_0 ≤ 0 ∧ tmp___0_0 − tmp___0_0 ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − k_post + k_post ≤ 0 ∧ k_post − k_post ≤ 0 ∧ − k_0 + k_0 ≤ 0 ∧ k_0 − k_0 ≤ 0 ∧ − j_post + j_post ≤ 0 ∧ j_post − j_post ≤ 0 ∧ − j_0 + j_0 ≤ 0 ∧ j_0 − j_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − ___const_100_0 + ___const_100_0 ≤ 0 ∧ ___const_100_0 − ___const_100_0 ≤ 0

7 Location Addition

The following skip-transition is inserted and corresponding redirections w.r.t. the old location are performed.

6 24 6_var_snapshot: − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp___0_post + tmp___0_post ≤ 0 ∧ tmp___0_post − tmp___0_post ≤ 0 ∧ − tmp___0_0 + tmp___0_0 ≤ 0 ∧ tmp___0_0 − tmp___0_0 ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − k_post + k_post ≤ 0 ∧ k_post − k_post ≤ 0 ∧ − k_0 + k_0 ≤ 0 ∧ k_0 − k_0 ≤ 0 ∧ − j_post + j_post ≤ 0 ∧ j_post − j_post ≤ 0 ∧ − j_0 + j_0 ≤ 0 ∧ j_0 − j_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − ___const_100_0 + ___const_100_0 ≤ 0 ∧ ___const_100_0 − ___const_100_0 ≤ 0

8 SCC Decomposition

We consider subproblems for each of the 2 SCC(s) of the program graph.

8.1 SCC Subproblem 1/2

Here we consider the SCC { 5, 6, 6_var_snapshot, 6* }.

8.1.1 Transition Removal

We remove transition 6 using the following ranking functions, which are bounded by 2.

5:	−1 + 4⋅i_0 − 4⋅j_0
6:	1 + 4⋅i_0 − 4⋅j_0
6_var_snapshot:	4⋅i_0 − 4⋅j_0
6*:	2 + 4⋅i_0 − 4⋅j_0

8.1.2 Transition Removal

We remove transitions 24, 26, 8 using the following ranking functions, which are bounded by −1.

5:	−1
6:	−1 + 2⋅k_0
6_var_snapshot:	0
6*:	2⋅k_0

8.1.3 Splitting Cut-Point Transitions

We consider 1 subproblems corresponding to sets of cut-point transitions as follows.

8.1.3.1 Cut-Point Subproblem 1/1

Here we consider cut-point transition 23.

8.1.3.1.1 Splitting Cut-Point Transitions

There remain no cut-point transition to consider. Hence the cooperation termination is trivial.

8.2 SCC Subproblem 2/2

Here we consider the SCC { 1, 4, 8, 1_var_snapshot, 1* }.

8.2.1 Transition Removal

We remove transition 13 using the following ranking functions, which are bounded by 4.

1:	2 − 5⋅i_0 + 5⋅k_0
4:	−5⋅i_0 + 5⋅k_0
8:	−1 − 5⋅i_0 + 5⋅k_0
1_var_snapshot:	1 − 5⋅i_0 + 5⋅k_0
1*:	3 − 5⋅i_0 + 5⋅k_0

8.2.2 Splitting Cut-Point Transitions

We consider 1 subproblems corresponding to sets of cut-point transitions as follows.

8.2.2.1 Cut-Point Subproblem 1/1

Here we consider cut-point transition 16.

8.2.2.1.1 Invariant Updates

The following invariants are asserted.

0:	1 − k_0 ≤ 0
1:	−1 + i_0 ≤ 0 ∧ 1 − k_0 ≤ 0 ∨ i_0 − k_0 ≤ 0 ∧ 1 − k_0 ≤ 0
2:	TRUE
3:	TRUE
4:	−1 + i_0 ≤ 0 ∧ 1 − k_0 ≤ 0 ∨ i_0 − k_0 ≤ 0 ∧ 1 − k_0 ≤ 0
5:	1 − k_0 ≤ 0
6:	1 − k_0 ≤ 0
7:	1 − k_0 ≤ 0
8:	1 ≤ 0 ∧ 1 − k_0 ≤ 0 ∨ 1 + i_0 − k_0 ≤ 0 ∧ 1 − k_0 ≤ 0
9:	TRUE
10:	TRUE
1:	−1 + i_0 ≤ 0 ∧ 1 − k_0 ≤ 0 ∨ i_0 − k_0 ≤ 0 ∧ 1 − k_0 ≤ 0
4:	−1 + i_0 ≤ 0 ∧ 1 − k_0 ≤ 0 ∨ i_0 − k_0 ≤ 0 ∧ 1 − k_0 ≤ 0
8:	1 ≤ 0 ∧ 1 − k_0 ≤ 0
1_var_snapshot:	−1 + i_0 ≤ 0 ∧ 1 − k_0 ≤ 0 ∨ i_0 − k_0 ≤ 0 ∧ 1 − k_0 ≤ 0
1*:	1 ≤ 0 ∧ 1 − k_0 ≤ 0

The invariants are proved as follows.

IMPACT Invariant Proof

nodes (location) invariant:

0	(10)	TRUE
1	(9)	TRUE
2	(3)	TRUE
3	(0)	1 − k_0 ≤ 0
4	(2)	TRUE
5	(1)	−1 + i_0 ≤ 0 ∧ 1 − k_0 ≤ 0
6	(2)	TRUE
7	(4)	−1 + i_0 ≤ 0 ∧ 1 − k_0 ≤ 0
8	(1)	−1 + i_0 ≤ 0 ∧ 1 − k_0 ≤ 0
9	(1_var_snapshot)	−1 + i_0 ≤ 0 ∧ 1 − k_0 ≤ 0
14	(7)	1 − k_0 ≤ 0
15	(8)	1 ≤ 0 ∧ 1 − k_0 ≤ 0
16	(8)	1 + i_0 − k_0 ≤ 0 ∧ 1 − k_0 ≤ 0
17	(1)	i_0 − k_0 ≤ 0 ∧ 1 − k_0 ≤ 0
18	(7)	1 − k_0 ≤ 0
23	(4)	−1 + i_0 ≤ 0 ∧ 1 − k_0 ≤ 0
24	(8)	1 ≤ 0 ∧ 1 − k_0 ≤ 0
32	(6)	1 − k_0 ≤ 0
33	(5)	1 − k_0 ≤ 0
35	(2)	TRUE
36	(6)	1 − k_0 ≤ 0
38	(4)	i_0 − k_0 ≤ 0 ∧ 1 − k_0 ≤ 0
39	(1)	i_0 − k_0 ≤ 0 ∧ 1 − k_0 ≤ 0
40	(1_var_snapshot)	i_0 − k_0 ≤ 0 ∧ 1 − k_0 ≤ 0
45	(4)	i_0 − k_0 ≤ 0 ∧ 1 − k_0 ≤ 0
46	(8)	1 ≤ 0 ∧ 1 − k_0 ≤ 0
51	(7)	1 − k_0 ≤ 0
52	(8)	1 ≤ 0 ∧ 1 − k_0 ≤ 0
53	(8)	1 + i_0 − k_0 ≤ 0 ∧ 1 − k_0 ≤ 0

initial node: 0
cover edges:

4 → 6

14 → 18

35 → 6

36 → 32

51 → 18

53 → 16

transition edges:

0	15 1
1	14 2
2	2 3
2	3 4
3	0 5
3	1 6
5	4 7
5	16 8
7	11 14
7	12 15
7	13 16
8	17 9
9	4 23
16	9 17
16	10 18
17	4 38
17	16 39
18	7 32
23	12 24
32	8 33
33	5 35
33	6 36
38	11 51
38	12 52
38	13 53
39	17 40
40	4 45
45	12 46

8.2.2.1.2 Transition Removal

We remove transition 17 using the following ranking functions, which are bounded by −7.

1:	−1
1_var_snapshot:	−2
4:	−3
8:	−4
1*:	−5

8.2.2.1.3 Splitting Cut-Point Transitions

There remain no cut-point transition to consider. Hence the cooperation termination is trivial.

Tool configuration

T2Cert

version: 1.0

0	0 1
0	1 2
1	4 4
3	2 0
3	3 2
4	11 7
4	12 8
4	13 8
5	5 2
5	6 6
6	8 5
7	7 6
8	9 1
8	10 7
9	14 3
10	15 9

4	→ 6
14	→ 18
35	→ 6
36	→ 32
51	→ 18
53	→ 16