LTS Termination Proof

by T2Cert

Input

• Initial Location: 10
• Transitions: (pre-variables and post-variables)

  0	0	1:		0 ≤ 0 ∧ 0 ≤ 0 ∧ −2 − x_0 + x_post ≤ 0 ∧ 2 + x_0 − x_post ≤ 0 ∧ x_0 − x_post ≤ 0 ∧ − x_0 + x_post ≤ 0 ∧ − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − N_0 + N_0 ≤ 0 ∧ N_0 − N_0 ≤ 0
  0	1	1:		− x_post + x_post ≤ 0 ∧ x_post − x_post ≤ 0 ∧ − x_0 + x_0 ≤ 0 ∧ x_0 − x_0 ≤ 0 ∧ − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − N_0 + N_0 ≤ 0 ∧ N_0 − N_0 ≤ 0
  2	2	3:		N_0 − i_0 ≤ 0 ∧ − x_post + x_post ≤ 0 ∧ x_post − x_post ≤ 0 ∧ − x_0 + x_0 ≤ 0 ∧ x_0 − x_0 ≤ 0 ∧ − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − N_0 + N_0 ≤ 0 ∧ N_0 − N_0 ≤ 0
  2	3	0:		1 − N_0 + i_0 ≤ 0 ∧ − x_post + x_post ≤ 0 ∧ x_post − x_post ≤ 0 ∧ − x_0 + x_0 ≤ 0 ∧ x_0 − x_0 ≤ 0 ∧ − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − N_0 + N_0 ≤ 0 ∧ N_0 − N_0 ≤ 0
  4	4	2:		− x_post + x_post ≤ 0 ∧ x_post − x_post ≤ 0 ∧ − x_0 + x_0 ≤ 0 ∧ x_0 − x_0 ≤ 0 ∧ − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − N_0 + N_0 ≤ 0 ∧ N_0 − N_0 ≤ 0
  5	5	6:		0 ≤ 0 ∧ 0 ≤ 0 ∧ tmp_post ≤ 0 ∧ − tmp_post ≤ 0 ∧ tmp_0 − tmp_post ≤ 0 ∧ − tmp_0 + tmp_post ≤ 0 ∧ − x_post + x_post ≤ 0 ∧ x_post − x_post ≤ 0 ∧ − x_0 + x_0 ≤ 0 ∧ x_0 − x_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − N_0 + N_0 ≤ 0 ∧ N_0 − N_0 ≤ 0
  7	6	5:		2 + N_0 − x_0 ≤ 0 ∧ − x_post + x_post ≤ 0 ∧ x_post − x_post ≤ 0 ∧ − x_0 + x_0 ≤ 0 ∧ x_0 − x_0 ≤ 0 ∧ − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − N_0 + N_0 ≤ 0 ∧ N_0 − N_0 ≤ 0
  7	7	5:		− N_0 + x_0 ≤ 0 ∧ − x_post + x_post ≤ 0 ∧ x_post − x_post ≤ 0 ∧ − x_0 + x_0 ≤ 0 ∧ x_0 − x_0 ≤ 0 ∧ − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − N_0 + N_0 ≤ 0 ∧ N_0 − N_0 ≤ 0
  7	8	6:		0 ≤ 0 ∧ 0 ≤ 0 ∧ −1 − N_0 + x_0 ≤ 0 ∧ 1 + N_0 − x_0 ≤ 0 ∧ −1 + tmp_post ≤ 0 ∧ 1 − tmp_post ≤ 0 ∧ tmp_0 − tmp_post ≤ 0 ∧ − tmp_0 + tmp_post ≤ 0 ∧ − x_post + x_post ≤ 0 ∧ x_post − x_post ≤ 0 ∧ − x_0 + x_0 ≤ 0 ∧ x_0 − x_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − N_0 + N_0 ≤ 0 ∧ N_0 − N_0 ≤ 0
  6	9	8:		− x_post + x_post ≤ 0 ∧ x_post − x_post ≤ 0 ∧ − x_0 + x_0 ≤ 0 ∧ x_0 − x_0 ≤ 0 ∧ − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − N_0 + N_0 ≤ 0 ∧ N_0 − N_0 ≤ 0
  3	10	7:		1 + N_0 − x_0 ≤ 0 ∧ − x_post + x_post ≤ 0 ∧ x_post − x_post ≤ 0 ∧ − x_0 + x_0 ≤ 0 ∧ x_0 − x_0 ≤ 0 ∧ − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − N_0 + N_0 ≤ 0 ∧ N_0 − N_0 ≤ 0
  3	11	7:		1 − N_0 + x_0 ≤ 0 ∧ − x_post + x_post ≤ 0 ∧ x_post − x_post ≤ 0 ∧ − x_0 + x_0 ≤ 0 ∧ x_0 − x_0 ≤ 0 ∧ − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − N_0 + N_0 ≤ 0 ∧ N_0 − N_0 ≤ 0
  3	12	6:		0 ≤ 0 ∧ 0 ≤ 0 ∧ − N_0 + x_0 ≤ 0 ∧ N_0 − x_0 ≤ 0 ∧ −1 + tmp_post ≤ 0 ∧ 1 − tmp_post ≤ 0 ∧ tmp_0 − tmp_post ≤ 0 ∧ − tmp_0 + tmp_post ≤ 0 ∧ − x_post + x_post ≤ 0 ∧ x_post − x_post ≤ 0 ∧ − x_0 + x_0 ≤ 0 ∧ x_0 − x_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − N_0 + N_0 ≤ 0 ∧ N_0 − N_0 ≤ 0
  1	13	4:		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 ∧ − x_post + x_post ≤ 0 ∧ x_post − x_post ≤ 0 ∧ − x_0 + x_0 ≤ 0 ∧ x_0 − x_0 ≤ 0 ∧ − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − N_0 + N_0 ≤ 0 ∧ N_0 − N_0 ≤ 0
  9	14	4:		0 ≤ 0 ∧ 0 ≤ 0 ∧ 0 ≤ 0 ∧ 0 ≤ 0 ∧ x_post ≤ 0 ∧ − x_post ≤ 0 ∧ i_post ≤ 0 ∧ − i_post ≤ 0 ∧ i_0 − i_post ≤ 0 ∧ − i_0 + i_post ≤ 0 ∧ x_0 − x_post ≤ 0 ∧ − x_0 + x_post ≤ 0 ∧ − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − N_0 + N_0 ≤ 0 ∧ N_0 − N_0 ≤ 0
  10	15	9:		− x_post + x_post ≤ 0 ∧ x_post − x_post ≤ 0 ∧ − x_0 + x_0 ≤ 0 ∧ x_0 − x_0 ≤ 0 ∧ − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − N_0 + N_0 ≤ 0 ∧ N_0 − N_0 ≤ 0

Proof

1 Invariant Updates

The following invariants are asserted.

The invariants are proved as follows.

IMPACT Invariant Proof

• nodes (location) invariant:

  0		(0)		TRUE
  1		(1)		TRUE
  2		(2)		TRUE
  3		(3)		TRUE
  4		(4)		TRUE
  5		(5)		TRUE
  6		(6)		−1 + tmp_post ≤ 0 ∧ −1 + tmp_0 ≤ 0
  7		(7)		TRUE
  8		(8)		−1 + tmp_post ≤ 0 ∧ −1 + tmp_0 ≤ 0
  9		(9)		TRUE
  10		(10)		TRUE

• initial node: 10
• cover edges:
• transition edges:

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

2 Switch to Cooperation Termination Proof

3 Transition Removal

We remove transitions 2, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15 using the following ranking functions, which are bounded by −21.

4 Location Addition

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

4* 19 4: − x_post + x_post ≤ 0 ∧ x_post − x_post ≤ 0 ∧ − x_0 + x_0 ≤ 0 ∧ x_0 − x_0 ≤ 0 ∧ − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − N_0 + N_0 ≤ 0 ∧ N_0 − N_0 ≤ 0

5 Location Addition

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

4 17 4_var_snapshot: − x_post + x_post ≤ 0 ∧ x_post − x_post ≤ 0 ∧ − x_0 + x_0 ≤ 0 ∧ x_0 − x_0 ≤ 0 ∧ − tmp_post + tmp_post ≤ 0 ∧ tmp_post − tmp_post ≤ 0 ∧ − tmp_0 + tmp_0 ≤ 0 ∧ tmp_0 − tmp_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − N_0 + N_0 ≤ 0 ∧ N_0 − N_0 ≤ 0

6 SCC Decomposition

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

6.1 SCC Subproblem 1/1

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

6.1.1 Transition Removal

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

6.1.2 Transition Removal

We remove transitions 17, 19, 0, 1, 4, 13 using the following ranking functions, which are bounded by −4.

6.1.3 Splitting Cut-Point Transitions

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

6.1.3.1 Cut-Point Subproblem 1/1

6.1.3.1.1 Splitting Cut-Point Transitions

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

Tool configuration

T2Cert

• version: 1.0