LTS Termination Proof

by T2Cert

Input

Integer Transition System

Proof

1 Invariant Updates

The following invariants are asserted.

0: TRUE
1: TRUE
2: 1 − arg1P ≤ 0arg2P ≤ 01 − arg1 ≤ 0arg2 ≤ 0
3: arg1P ≤ 0arg1 ≤ 0
4: 1 − arg1P ≤ 01 − arg2P ≤ 01 − arg1 ≤ 01 − arg2 ≤ 0
5: 1 − arg1 ≤ 0
6: arg2P ≤ 0arg2 ≤ 0
7: arg2P ≤ 0arg2 ≤ 0
8: 4 − arg1P ≤ 02 − arg2P ≤ 04 − arg1 ≤ 02 − arg2 ≤ 0
9: 1 − arg1P ≤ 01 − arg1 ≤ 0
10: 4 − arg1P ≤ 02 − arg2P ≤ 04 − arg1 ≤ 02 − arg2 ≤ 0
11: 4 − arg1P ≤ 02 − arg2P ≤ 04 − arg1 ≤ 02 − arg2 ≤ 0
12: 4 − arg1P ≤ 02 − arg2P ≤ 04 − arg1 ≤ 02 − arg2 ≤ 0
13: TRUE

The invariants are proved as follows.

IMPACT Invariant Proof

2 Switch to Cooperation Termination Proof

We consider the following cutpoint-transitions:
1 39 1: x54 + x54 ≤ 0x54x54 ≤ 0x40 + x40 ≤ 0x40x40 ≤ 0x35 + x35 ≤ 0x35x35 ≤ 0x29 + x29 ≤ 0x29x29 ≤ 0x23 + x23 ≤ 0x23x23 ≤ 0x195 + x195 ≤ 0x195x195 ≤ 0x18 + x18 ≤ 0x18x18 ≤ 0x164 + x164 ≤ 0x164x164 ≤ 0x145 + x145 ≤ 0x145x145 ≤ 0x140 + x140 ≤ 0x140x140 ≤ 0x115 + x115 ≤ 0x115x115 ≤ 0x110 + x110 ≤ 0x110x110 ≤ 0x105 + x105 ≤ 0x105x105 ≤ 0arg5P + arg5P ≤ 0arg5Parg5P ≤ 0arg5 + arg5 ≤ 0arg5arg5 ≤ 0arg4P + arg4P ≤ 0arg4Parg4P ≤ 0arg4 + arg4 ≤ 0arg4arg4 ≤ 0arg3P + arg3P ≤ 0arg3Parg3P ≤ 0arg3 + arg3 ≤ 0arg3arg3 ≤ 0arg2P + arg2P ≤ 0arg2Parg2P ≤ 0arg2 + arg2 ≤ 0arg2arg2 ≤ 0arg1P + arg1P ≤ 0arg1Parg1P ≤ 0arg1 + arg1 ≤ 0arg1arg1 ≤ 0
3 46 3: x54 + x54 ≤ 0x54x54 ≤ 0x40 + x40 ≤ 0x40x40 ≤ 0x35 + x35 ≤ 0x35x35 ≤ 0x29 + x29 ≤ 0x29x29 ≤ 0x23 + x23 ≤ 0x23x23 ≤ 0x195 + x195 ≤ 0x195x195 ≤ 0x18 + x18 ≤ 0x18x18 ≤ 0x164 + x164 ≤ 0x164x164 ≤ 0x145 + x145 ≤ 0x145x145 ≤ 0x140 + x140 ≤ 0x140x140 ≤ 0x115 + x115 ≤ 0x115x115 ≤ 0x110 + x110 ≤ 0x110x110 ≤ 0x105 + x105 ≤ 0x105x105 ≤ 0arg5P + arg5P ≤ 0arg5Parg5P ≤ 0arg5 + arg5 ≤ 0arg5arg5 ≤ 0arg4P + arg4P ≤ 0arg4Parg4P ≤ 0arg4 + arg4 ≤ 0arg4arg4 ≤ 0arg3P + arg3P ≤ 0arg3Parg3P ≤ 0arg3 + arg3 ≤ 0arg3arg3 ≤ 0arg2P + arg2P ≤ 0arg2Parg2P ≤ 0arg2 + arg2 ≤ 0arg2arg2 ≤ 0arg1P + arg1P ≤ 0arg1Parg1P ≤ 0arg1 + arg1 ≤ 0arg1arg1 ≤ 0
6 53 6: x54 + x54 ≤ 0x54x54 ≤ 0x40 + x40 ≤ 0x40x40 ≤ 0x35 + x35 ≤ 0x35x35 ≤ 0x29 + x29 ≤ 0x29x29 ≤ 0x23 + x23 ≤ 0x23x23 ≤ 0x195 + x195 ≤ 0x195x195 ≤ 0x18 + x18 ≤ 0x18x18 ≤ 0x164 + x164 ≤ 0x164x164 ≤ 0x145 + x145 ≤ 0x145x145 ≤ 0x140 + x140 ≤ 0x140x140 ≤ 0x115 + x115 ≤ 0x115x115 ≤ 0x110 + x110 ≤ 0x110x110 ≤ 0x105 + x105 ≤ 0x105x105 ≤ 0arg5P + arg5P ≤ 0arg5Parg5P ≤ 0arg5 + arg5 ≤ 0arg5arg5 ≤ 0arg4P + arg4P ≤ 0arg4Parg4P ≤ 0arg4 + arg4 ≤ 0arg4arg4 ≤ 0arg3P + arg3P ≤ 0arg3Parg3P ≤ 0arg3 + arg3 ≤ 0arg3arg3 ≤ 0arg2P + arg2P ≤ 0arg2Parg2P ≤ 0arg2 + arg2 ≤ 0arg2arg2 ≤ 0arg1P + arg1P ≤ 0arg1Parg1P ≤ 0arg1 + arg1 ≤ 0arg1arg1 ≤ 0
7 60 7: x54 + x54 ≤ 0x54x54 ≤ 0x40 + x40 ≤ 0x40x40 ≤ 0x35 + x35 ≤ 0x35x35 ≤ 0x29 + x29 ≤ 0x29x29 ≤ 0x23 + x23 ≤ 0x23x23 ≤ 0x195 + x195 ≤ 0x195x195 ≤ 0x18 + x18 ≤ 0x18x18 ≤ 0x164 + x164 ≤ 0x164x164 ≤ 0x145 + x145 ≤ 0x145x145 ≤ 0x140 + x140 ≤ 0x140x140 ≤ 0x115 + x115 ≤ 0x115x115 ≤ 0x110 + x110 ≤ 0x110x110 ≤ 0x105 + x105 ≤ 0x105x105 ≤ 0arg5P + arg5P ≤ 0arg5Parg5P ≤ 0arg5 + arg5 ≤ 0arg5arg5 ≤ 0arg4P + arg4P ≤ 0arg4Parg4P ≤ 0arg4 + arg4 ≤ 0arg4arg4 ≤ 0arg3P + arg3P ≤ 0arg3Parg3P ≤ 0arg3 + arg3 ≤ 0arg3arg3 ≤ 0arg2P + arg2P ≤ 0arg2Parg2P ≤ 0arg2 + arg2 ≤ 0arg2arg2 ≤ 0arg1P + arg1P ≤ 0arg1Parg1P ≤ 0arg1 + arg1 ≤ 0arg1arg1 ≤ 0
and for every transition t, a duplicate t is considered.

3 Transition Removal

We remove transitions 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 21, 22, 38 using the following ranking functions, which are bounded by −25.

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

4 Location Addition

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

1* 42 1: x54 + x54 ≤ 0x54x54 ≤ 0x40 + x40 ≤ 0x40x40 ≤ 0x35 + x35 ≤ 0x35x35 ≤ 0x29 + x29 ≤ 0x29x29 ≤ 0x23 + x23 ≤ 0x23x23 ≤ 0x195 + x195 ≤ 0x195x195 ≤ 0x18 + x18 ≤ 0x18x18 ≤ 0x164 + x164 ≤ 0x164x164 ≤ 0x145 + x145 ≤ 0x145x145 ≤ 0x140 + x140 ≤ 0x140x140 ≤ 0x115 + x115 ≤ 0x115x115 ≤ 0x110 + x110 ≤ 0x110x110 ≤ 0x105 + x105 ≤ 0x105x105 ≤ 0arg5P + arg5P ≤ 0arg5Parg5P ≤ 0arg5 + arg5 ≤ 0arg5arg5 ≤ 0arg4P + arg4P ≤ 0arg4Parg4P ≤ 0arg4 + arg4 ≤ 0arg4arg4 ≤ 0arg3P + arg3P ≤ 0arg3Parg3P ≤ 0arg3 + arg3 ≤ 0arg3arg3 ≤ 0arg2P + arg2P ≤ 0arg2Parg2P ≤ 0arg2 + arg2 ≤ 0arg2arg2 ≤ 0arg1P + arg1P ≤ 0arg1Parg1P ≤ 0arg1 + arg1 ≤ 0arg1arg1 ≤ 0

5 Location Addition

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

1 40 1_var_snapshot: x54 + x54 ≤ 0x54x54 ≤ 0x40 + x40 ≤ 0x40x40 ≤ 0x35 + x35 ≤ 0x35x35 ≤ 0x29 + x29 ≤ 0x29x29 ≤ 0x23 + x23 ≤ 0x23x23 ≤ 0x195 + x195 ≤ 0x195x195 ≤ 0x18 + x18 ≤ 0x18x18 ≤ 0x164 + x164 ≤ 0x164x164 ≤ 0x145 + x145 ≤ 0x145x145 ≤ 0x140 + x140 ≤ 0x140x140 ≤ 0x115 + x115 ≤ 0x115x115 ≤ 0x110 + x110 ≤ 0x110x110 ≤ 0x105 + x105 ≤ 0x105x105 ≤ 0arg5P + arg5P ≤ 0arg5Parg5P ≤ 0arg5 + arg5 ≤ 0arg5arg5 ≤ 0arg4P + arg4P ≤ 0arg4Parg4P ≤ 0arg4 + arg4 ≤ 0arg4arg4 ≤ 0arg3P + arg3P ≤ 0arg3Parg3P ≤ 0arg3 + arg3 ≤ 0arg3arg3 ≤ 0arg2P + arg2P ≤ 0arg2Parg2P ≤ 0arg2 + arg2 ≤ 0arg2arg2 ≤ 0arg1P + arg1P ≤ 0arg1Parg1P ≤ 0arg1 + arg1 ≤ 0arg1arg1 ≤ 0

6 Location Addition

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

3* 49 3: x54 + x54 ≤ 0x54x54 ≤ 0x40 + x40 ≤ 0x40x40 ≤ 0x35 + x35 ≤ 0x35x35 ≤ 0x29 + x29 ≤ 0x29x29 ≤ 0x23 + x23 ≤ 0x23x23 ≤ 0x195 + x195 ≤ 0x195x195 ≤ 0x18 + x18 ≤ 0x18x18 ≤ 0x164 + x164 ≤ 0x164x164 ≤ 0x145 + x145 ≤ 0x145x145 ≤ 0x140 + x140 ≤ 0x140x140 ≤ 0x115 + x115 ≤ 0x115x115 ≤ 0x110 + x110 ≤ 0x110x110 ≤ 0x105 + x105 ≤ 0x105x105 ≤ 0arg5P + arg5P ≤ 0arg5Parg5P ≤ 0arg5 + arg5 ≤ 0arg5arg5 ≤ 0arg4P + arg4P ≤ 0arg4Parg4P ≤ 0arg4 + arg4 ≤ 0arg4arg4 ≤ 0arg3P + arg3P ≤ 0arg3Parg3P ≤ 0arg3 + arg3 ≤ 0arg3arg3 ≤ 0arg2P + arg2P ≤ 0arg2Parg2P ≤ 0arg2 + arg2 ≤ 0arg2arg2 ≤ 0arg1P + arg1P ≤ 0arg1Parg1P ≤ 0arg1 + arg1 ≤ 0arg1arg1 ≤ 0

7 Location Addition

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

3 47 3_var_snapshot: x54 + x54 ≤ 0x54x54 ≤ 0x40 + x40 ≤ 0x40x40 ≤ 0x35 + x35 ≤ 0x35x35 ≤ 0x29 + x29 ≤ 0x29x29 ≤ 0x23 + x23 ≤ 0x23x23 ≤ 0x195 + x195 ≤ 0x195x195 ≤ 0x18 + x18 ≤ 0x18x18 ≤ 0x164 + x164 ≤ 0x164x164 ≤ 0x145 + x145 ≤ 0x145x145 ≤ 0x140 + x140 ≤ 0x140x140 ≤ 0x115 + x115 ≤ 0x115x115 ≤ 0x110 + x110 ≤ 0x110x110 ≤ 0x105 + x105 ≤ 0x105x105 ≤ 0arg5P + arg5P ≤ 0arg5Parg5P ≤ 0arg5 + arg5 ≤ 0arg5arg5 ≤ 0arg4P + arg4P ≤ 0arg4Parg4P ≤ 0arg4 + arg4 ≤ 0arg4arg4 ≤ 0arg3P + arg3P ≤ 0arg3Parg3P ≤ 0arg3 + arg3 ≤ 0arg3arg3 ≤ 0arg2P + arg2P ≤ 0arg2Parg2P ≤ 0arg2 + arg2 ≤ 0arg2arg2 ≤ 0arg1P + arg1P ≤ 0arg1Parg1P ≤ 0arg1 + arg1 ≤ 0arg1arg1 ≤ 0

8 Location Addition

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

6* 56 6: x54 + x54 ≤ 0x54x54 ≤ 0x40 + x40 ≤ 0x40x40 ≤ 0x35 + x35 ≤ 0x35x35 ≤ 0x29 + x29 ≤ 0x29x29 ≤ 0x23 + x23 ≤ 0x23x23 ≤ 0x195 + x195 ≤ 0x195x195 ≤ 0x18 + x18 ≤ 0x18x18 ≤ 0x164 + x164 ≤ 0x164x164 ≤ 0x145 + x145 ≤ 0x145x145 ≤ 0x140 + x140 ≤ 0x140x140 ≤ 0x115 + x115 ≤ 0x115x115 ≤ 0x110 + x110 ≤ 0x110x110 ≤ 0x105 + x105 ≤ 0x105x105 ≤ 0arg5P + arg5P ≤ 0arg5Parg5P ≤ 0arg5 + arg5 ≤ 0arg5arg5 ≤ 0arg4P + arg4P ≤ 0arg4Parg4P ≤ 0arg4 + arg4 ≤ 0arg4arg4 ≤ 0arg3P + arg3P ≤ 0arg3Parg3P ≤ 0arg3 + arg3 ≤ 0arg3arg3 ≤ 0arg2P + arg2P ≤ 0arg2Parg2P ≤ 0arg2 + arg2 ≤ 0arg2arg2 ≤ 0arg1P + arg1P ≤ 0arg1Parg1P ≤ 0arg1 + arg1 ≤ 0arg1arg1 ≤ 0

9 Location Addition

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

6 54 6_var_snapshot: x54 + x54 ≤ 0x54x54 ≤ 0x40 + x40 ≤ 0x40x40 ≤ 0x35 + x35 ≤ 0x35x35 ≤ 0x29 + x29 ≤ 0x29x29 ≤ 0x23 + x23 ≤ 0x23x23 ≤ 0x195 + x195 ≤ 0x195x195 ≤ 0x18 + x18 ≤ 0x18x18 ≤ 0x164 + x164 ≤ 0x164x164 ≤ 0x145 + x145 ≤ 0x145x145 ≤ 0x140 + x140 ≤ 0x140x140 ≤ 0x115 + x115 ≤ 0x115x115 ≤ 0x110 + x110 ≤ 0x110x110 ≤ 0x105 + x105 ≤ 0x105x105 ≤ 0arg5P + arg5P ≤ 0arg5Parg5P ≤ 0arg5 + arg5 ≤ 0arg5arg5 ≤ 0arg4P + arg4P ≤ 0arg4Parg4P ≤ 0arg4 + arg4 ≤ 0arg4arg4 ≤ 0arg3P + arg3P ≤ 0arg3Parg3P ≤ 0arg3 + arg3 ≤ 0arg3arg3 ≤ 0arg2P + arg2P ≤ 0arg2Parg2P ≤ 0arg2 + arg2 ≤ 0arg2arg2 ≤ 0arg1P + arg1P ≤ 0arg1Parg1P ≤ 0arg1 + arg1 ≤ 0arg1arg1 ≤ 0

10 Location Addition

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

7* 63 7: x54 + x54 ≤ 0x54x54 ≤ 0x40 + x40 ≤ 0x40x40 ≤ 0x35 + x35 ≤ 0x35x35 ≤ 0x29 + x29 ≤ 0x29x29 ≤ 0x23 + x23 ≤ 0x23x23 ≤ 0x195 + x195 ≤ 0x195x195 ≤ 0x18 + x18 ≤ 0x18x18 ≤ 0x164 + x164 ≤ 0x164x164 ≤ 0x145 + x145 ≤ 0x145x145 ≤ 0x140 + x140 ≤ 0x140x140 ≤ 0x115 + x115 ≤ 0x115x115 ≤ 0x110 + x110 ≤ 0x110x110 ≤ 0x105 + x105 ≤ 0x105x105 ≤ 0arg5P + arg5P ≤ 0arg5Parg5P ≤ 0arg5 + arg5 ≤ 0arg5arg5 ≤ 0arg4P + arg4P ≤ 0arg4Parg4P ≤ 0arg4 + arg4 ≤ 0arg4arg4 ≤ 0arg3P + arg3P ≤ 0arg3Parg3P ≤ 0arg3 + arg3 ≤ 0arg3arg3 ≤ 0arg2P + arg2P ≤ 0arg2Parg2P ≤ 0arg2 + arg2 ≤ 0arg2arg2 ≤ 0arg1P + arg1P ≤ 0arg1Parg1P ≤ 0arg1 + arg1 ≤ 0arg1arg1 ≤ 0

11 Location Addition

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

7 61 7_var_snapshot: x54 + x54 ≤ 0x54x54 ≤ 0x40 + x40 ≤ 0x40x40 ≤ 0x35 + x35 ≤ 0x35x35 ≤ 0x29 + x29 ≤ 0x29x29 ≤ 0x23 + x23 ≤ 0x23x23 ≤ 0x195 + x195 ≤ 0x195x195 ≤ 0x18 + x18 ≤ 0x18x18 ≤ 0x164 + x164 ≤ 0x164x164 ≤ 0x145 + x145 ≤ 0x145x145 ≤ 0x140 + x140 ≤ 0x140x140 ≤ 0x115 + x115 ≤ 0x115x115 ≤ 0x110 + x110 ≤ 0x110x110 ≤ 0x105 + x105 ≤ 0x105x105 ≤ 0arg5P + arg5P ≤ 0arg5Parg5P ≤ 0arg5 + arg5 ≤ 0arg5arg5 ≤ 0arg4P + arg4P ≤ 0arg4Parg4P ≤ 0arg4 + arg4 ≤ 0arg4arg4 ≤ 0arg3P + arg3P ≤ 0arg3Parg3P ≤ 0arg3 + arg3 ≤ 0arg3arg3 ≤ 0arg2P + arg2P ≤ 0arg2Parg2P ≤ 0arg2 + arg2 ≤ 0arg2arg2 ≤ 0arg1P + arg1P ≤ 0arg1Parg1P ≤ 0arg1 + arg1 ≤ 0arg1arg1 ≤ 0

12 SCC Decomposition

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

12.1 SCC Subproblem 1/2

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

12.1.1 Transition Removal

We remove transitions 12, 13, 15 using the following ranking functions, which are bounded by 3.

1: 2 + 4⋅arg1
5: 4⋅arg1
1_var_snapshot: 1 + 4⋅arg1
1*: 3 + 4⋅arg1

12.1.2 Transition Removal

We remove transitions 40, 14 using the following ranking functions, which are bounded by −1.

1: 1
5: arg1
1_var_snapshot: 0
1*: 2

12.1.3 Transition Removal

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

1: −1
5: 0
1_var_snapshot: 0
1*: 0

12.1.4 Splitting Cut-Point Transitions

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

12.1.4.1 Cut-Point Subproblem 1/1

Here we consider cut-point transition 39.

12.1.4.1.1 Splitting Cut-Point Transitions

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

12.2 SCC Subproblem 2/2

Here we consider the SCC { 3, 6, 7, 8, 10, 11, 12, 3_var_snapshot, 3*, 6_var_snapshot, 6*, 7_var_snapshot, 7* }.

12.2.1 Transition Removal

We remove transitions 47, 49, 54, 56, 61, 63, 16, 18, 19, 20, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37 using the following ranking functions, which are bounded by −5.

3: −3 + 7⋅arg1
6: 1 + 7⋅arg2
7: 1 + 7⋅arg2
8: 9 + 7⋅arg2
10: −1 + 7⋅arg2
11: −1 + 7⋅arg2
12: −1 + 7⋅arg1
3_var_snapshot: −4 + 7⋅arg1
3*: −2 + 7⋅arg1
6_var_snapshot: 7⋅arg2
6*: 2 + 7⋅arg2
7_var_snapshot: 7⋅arg2
7*: 2 + 7⋅arg2

12.2.2 Transition Removal

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

3: 0
6: 0
7: 0
8: 0
10: 0
11: 0
12: 0
3_var_snapshot: 1
3*: 0
6_var_snapshot: 0
6*: 0
7_var_snapshot: 0
7*: 0

12.2.3 Splitting Cut-Point Transitions

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

12.2.3.1 Cut-Point Subproblem 1/3

Here we consider cut-point transition 46.

12.2.3.1.1 Splitting Cut-Point Transitions

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

12.2.3.2 Cut-Point Subproblem 2/3

Here we consider cut-point transition 53.

12.2.3.2.1 Splitting Cut-Point Transitions

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

12.2.3.3 Cut-Point Subproblem 3/3

Here we consider cut-point transition 60.

12.2.3.3.1 Splitting Cut-Point Transitions

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

Tool configuration

T2Cert