LTS Termination Proof

by T2Cert

Input

Integer Transition System

Initial Location: 9

Transitions: (pre-variables and post-variables)

0	0	1:	0 ≤ 0 ∧ 0 ≤ 0 ∧ − j_0 + n_0 ≤ 0 ∧ −1 − i_0 + i_post ≤ 0 ∧ 1 + i_0 − i_post ≤ 0 ∧ i_0 − i_post ≤ 0 ∧ − i_0 + i_post ≤ 0 ∧ − n_post + n_post ≤ 0 ∧ n_post − n_post ≤ 0 ∧ − n_0 + n_0 ≤ 0 ∧ n_0 − n_0 ≤ 0 ∧ − j_post + j_post ≤ 0 ∧ j_post − j_post ≤ 0 ∧ − j_0 + j_0 ≤ 0 ∧ j_0 − j_0 ≤ 0 ∧ − guard_post + guard_post ≤ 0 ∧ guard_post − guard_post ≤ 0 ∧ − guard_0 + guard_0 ≤ 0 ∧ guard_0 − guard_0 ≤ 0
0	1	2:	0 ≤ 0 ∧ 0 ≤ 0 ∧ 1 + j_0 − n_0 ≤ 0 ∧ guard_0 − guard_post ≤ 0 ∧ − guard_0 + guard_post ≤ 0 ∧ − n_post + n_post ≤ 0 ∧ n_post − n_post ≤ 0 ∧ − n_0 + n_0 ≤ 0 ∧ n_0 − n_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
3	2	4:	− i_0 + n_0 ≤ 0 ∧ − n_post + n_post ≤ 0 ∧ n_post − n_post ≤ 0 ∧ − n_0 + n_0 ≤ 0 ∧ n_0 − n_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 ∧ − guard_post + guard_post ≤ 0 ∧ guard_post − guard_post ≤ 0 ∧ − guard_0 + guard_0 ≤ 0 ∧ guard_0 − guard_0 ≤ 0
3	3	5:	0 ≤ 0 ∧ 0 ≤ 0 ∧ 1 + i_0 − n_0 ≤ 0 ∧ −1 − i_0 + j_post ≤ 0 ∧ 1 + i_0 − j_post ≤ 0 ∧ j_0 − j_post ≤ 0 ∧ − j_0 + j_post ≤ 0 ∧ − n_post + n_post ≤ 0 ∧ n_post − n_post ≤ 0 ∧ − n_0 + n_0 ≤ 0 ∧ n_0 − n_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − guard_post + guard_post ≤ 0 ∧ guard_post − guard_post ≤ 0 ∧ − guard_0 + guard_0 ≤ 0 ∧ guard_0 − guard_0 ≤ 0
1	4	3:	− n_post + n_post ≤ 0 ∧ n_post − n_post ≤ 0 ∧ − n_0 + n_0 ≤ 0 ∧ n_0 − n_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 ∧ − guard_post + guard_post ≤ 0 ∧ guard_post − guard_post ≤ 0 ∧ − guard_0 + guard_0 ≤ 0 ∧ guard_0 − guard_0 ≤ 0
5	5	0:	− n_post + n_post ≤ 0 ∧ n_post − n_post ≤ 0 ∧ − n_0 + n_0 ≤ 0 ∧ n_0 − n_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 ∧ − guard_post + guard_post ≤ 0 ∧ guard_post − guard_post ≤ 0 ∧ − guard_0 + guard_0 ≤ 0 ∧ guard_0 − guard_0 ≤ 0
6	6	5:	0 ≤ 0 ∧ 0 ≤ 0 ∧ −1 − j_0 + j_post ≤ 0 ∧ 1 + j_0 − j_post ≤ 0 ∧ j_0 − j_post ≤ 0 ∧ − j_0 + j_post ≤ 0 ∧ − n_post + n_post ≤ 0 ∧ n_post − n_post ≤ 0 ∧ − n_0 + n_0 ≤ 0 ∧ n_0 − n_0 ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − guard_post + guard_post ≤ 0 ∧ guard_post − guard_post ≤ 0 ∧ − guard_0 + guard_0 ≤ 0 ∧ guard_0 − guard_0 ≤ 0
7	7	6:	0 ≤ 0 ∧ 0 ≤ 0 ∧ 0 ≤ 0 ∧ 0 ≤ 0 ∧ 1 − j_0 + j_post ≤ 0 ∧ −1 + j_0 − j_post ≤ 0 ∧ 1 − n_0 + n_post ≤ 0 ∧ −1 + n_0 − n_post ≤ 0 ∧ j_0 − j_post ≤ 0 ∧ − j_0 + j_post ≤ 0 ∧ n_0 − n_post ≤ 0 ∧ − n_0 + n_post ≤ 0 ∧ − i_post + i_post ≤ 0 ∧ i_post − i_post ≤ 0 ∧ − i_0 + i_0 ≤ 0 ∧ i_0 − i_0 ≤ 0 ∧ − guard_post + guard_post ≤ 0 ∧ guard_post − guard_post ≤ 0 ∧ − guard_0 + guard_0 ≤ 0 ∧ guard_0 − guard_0 ≤ 0
2	8	6:	guard_0 ≤ 0 ∧ − guard_0 ≤ 0 ∧ − n_post + n_post ≤ 0 ∧ n_post − n_post ≤ 0 ∧ − n_0 + n_0 ≤ 0 ∧ n_0 − n_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 ∧ − guard_post + guard_post ≤ 0 ∧ guard_post − guard_post ≤ 0 ∧ − guard_0 + guard_0 ≤ 0 ∧ guard_0 − guard_0 ≤ 0
2	9	7:	1 − guard_0 ≤ 0 ∧ − n_post + n_post ≤ 0 ∧ n_post − n_post ≤ 0 ∧ − n_0 + n_0 ≤ 0 ∧ n_0 − n_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 ∧ − guard_post + guard_post ≤ 0 ∧ guard_post − guard_post ≤ 0 ∧ − guard_0 + guard_0 ≤ 0 ∧ guard_0 − guard_0 ≤ 0
2	10	7:	1 + guard_0 ≤ 0 ∧ − n_post + n_post ≤ 0 ∧ n_post − n_post ≤ 0 ∧ − n_0 + n_0 ≤ 0 ∧ n_0 − n_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 ∧ − guard_post + guard_post ≤ 0 ∧ guard_post − guard_post ≤ 0 ∧ − guard_0 + guard_0 ≤ 0 ∧ guard_0 − guard_0 ≤ 0
8	11	1:	0 ≤ 0 ∧ 0 ≤ 0 ∧ i_post ≤ 0 ∧ − i_post ≤ 0 ∧ i_0 − i_post ≤ 0 ∧ − i_0 + i_post ≤ 0 ∧ − n_post + n_post ≤ 0 ∧ n_post − n_post ≤ 0 ∧ − n_0 + n_0 ≤ 0 ∧ n_0 − n_0 ≤ 0 ∧ − j_post + j_post ≤ 0 ∧ j_post − j_post ≤ 0 ∧ − j_0 + j_0 ≤ 0 ∧ j_0 − j_0 ≤ 0 ∧ − guard_post + guard_post ≤ 0 ∧ guard_post − guard_post ≤ 0 ∧ − guard_0 + guard_0 ≤ 0 ∧ guard_0 − guard_0 ≤ 0
9	12	8:	− n_post + n_post ≤ 0 ∧ n_post − n_post ≤ 0 ∧ − n_0 + n_0 ≤ 0 ∧ n_0 − n_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 ∧ − guard_post + guard_post ≤ 0 ∧ guard_post − guard_post ≤ 0 ∧ − guard_0 + guard_0 ≤ 0 ∧ guard_0 − guard_0 ≤ 0

Proof

1 Switch to Cooperation Termination Proof

We consider the following cutpoint-transitions:

1	13	1:	− n_post + n_post ≤ 0 ∧ n_post − n_post ≤ 0 ∧ − n_0 + n_0 ≤ 0 ∧ n_0 − n_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 ∧ − guard_post + guard_post ≤ 0 ∧ guard_post − guard_post ≤ 0 ∧ − guard_0 + guard_0 ≤ 0 ∧ guard_0 − guard_0 ≤ 0
5	20	5:	− n_post + n_post ≤ 0 ∧ n_post − n_post ≤ 0 ∧ − n_0 + n_0 ≤ 0 ∧ n_0 − n_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 ∧ − guard_post + guard_post ≤ 0 ∧ guard_post − guard_post ≤ 0 ∧ − guard_0 + guard_0 ≤ 0 ∧ guard_0 − guard_0 ≤ 0

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

2 Transition Removal

We remove transitions 2, 11, 12 using the following ranking functions, which are bounded by −15.

9:	0
8:	0
0:	0
1:	0
2:	0
3:	0
5:	0
6:	0
7:	0
4:	0
9:	−5
8:	−6
0:	−7
1:	−7
2:	−7
3:	−7
5:	−7
6:	−7
7:	−7
1_var_snapshot:	−7
1*:	−7
5_var_snapshot:	−7
5*:	−7
4:	−10

3 Location Addition

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

1* 16 1: − n_post + n_post ≤ 0 ∧ n_post − n_post ≤ 0 ∧ − n_0 + n_0 ≤ 0 ∧ n_0 − n_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 ∧ − guard_post + guard_post ≤ 0 ∧ guard_post − guard_post ≤ 0 ∧ − guard_0 + guard_0 ≤ 0 ∧ guard_0 − guard_0 ≤ 0

4 Location Addition

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

1 14 1_var_snapshot: − n_post + n_post ≤ 0 ∧ n_post − n_post ≤ 0 ∧ − n_0 + n_0 ≤ 0 ∧ n_0 − n_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 ∧ − guard_post + guard_post ≤ 0 ∧ guard_post − guard_post ≤ 0 ∧ − guard_0 + guard_0 ≤ 0 ∧ guard_0 − guard_0 ≤ 0

5 Location Addition

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

5* 23 5: − n_post + n_post ≤ 0 ∧ n_post − n_post ≤ 0 ∧ − n_0 + n_0 ≤ 0 ∧ n_0 − n_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 ∧ − guard_post + guard_post ≤ 0 ∧ guard_post − guard_post ≤ 0 ∧ − guard_0 + guard_0 ≤ 0 ∧ guard_0 − guard_0 ≤ 0

6 Location Addition

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

5 21 5_var_snapshot: − n_post + n_post ≤ 0 ∧ n_post − n_post ≤ 0 ∧ − n_0 + n_0 ≤ 0 ∧ n_0 − n_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 ∧ − guard_post + guard_post ≤ 0 ∧ guard_post − guard_post ≤ 0 ∧ − guard_0 + guard_0 ≤ 0 ∧ guard_0 − guard_0 ≤ 0

7 SCC Decomposition

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

7.1 SCC Subproblem 1/1

Here we consider the SCC { 0, 1, 2, 3, 5, 6, 7, 1_var_snapshot, 1*, 5_var_snapshot, 5* }.

7.1.1 Transition Removal

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

0:	−5⋅i_0 + 5⋅n_0
1:	3 − 5⋅i_0 + 5⋅n_0
2:	−5⋅i_0 + 5⋅n_0
3:	1 − 5⋅i_0 + 5⋅n_0
5:	−5⋅i_0 + 5⋅n_0
6:	−5⋅i_0 + 5⋅n_0
7:	−5 − 5⋅i_0 + 5⋅n_0
1_var_snapshot:	2 − 5⋅i_0 + 5⋅n_0
1*:	4 − 5⋅i_0 + 5⋅n_0
5_var_snapshot:	−5⋅i_0 + 5⋅n_0
5*:	−5⋅i_0 + 5⋅n_0

7.1.2 Transition Removal

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

0:	1 − 6⋅j_0 + 6⋅n_0
1:	−1 − 6⋅j_0 + 6⋅n_0
2:	−6⋅j_0 + 6⋅n_0
3:	−2 − 6⋅j_0 + 6⋅n_0
5:	2 − 6⋅j_0 + 6⋅n_0
6:	−2 − 6⋅j_0 + 6⋅n_0
7:	−1 − 6⋅j_0 + 6⋅n_0
1_var_snapshot:	−1 − 6⋅j_0 + 6⋅n_0
1*:	−6⋅j_0 + 6⋅n_0
5_var_snapshot:	2 − 6⋅j_0 + 6⋅n_0
5*:	3 − 6⋅j_0 + 6⋅n_0

7.1.3 Transition Removal

We remove transitions 14, 16, 21, 23, 0, 4, 5, 6, 7, 8, 9, 10 using the following ranking functions, which are bounded by −10.

0:	−6
1:	−8
2:	0
3:	−10
5:	−4
6:	−2
7:	−1
1_var_snapshot:	−9
1*:	−7
5_var_snapshot:	−5
5*:	−3

7.1.4 Splitting Cut-Point Transitions

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

7.1.4.1 Cut-Point Subproblem 1/2

Here we consider cut-point transition 13.

7.1.4.1.1 Splitting Cut-Point Transitions

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

7.1.4.2 Cut-Point Subproblem 2/2

Here we consider cut-point transition 20.

7.1.4.2.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