LTS Termination Proof

by T2Cert

Input

Integer Transition System

Proof

1 Switch to Cooperation Termination Proof

We consider the following cutpoint-transitions:
4 54 4: x90 + x90 ≤ 0x90x90 ≤ 0x88 + x88 ≤ 0x88x88 ≤ 0x82 + x82 ≤ 0x82x82 ≤ 0x79 + x79 ≤ 0x79x79 ≤ 0arg9P + arg9P ≤ 0arg9Parg9P ≤ 0arg9 + arg9 ≤ 0arg9arg9 ≤ 0arg8P + arg8P ≤ 0arg8Parg8P ≤ 0arg8 + arg8 ≤ 0arg8arg8 ≤ 0arg7P + arg7P ≤ 0arg7Parg7P ≤ 0arg7 + arg7 ≤ 0arg7arg7 ≤ 0arg6P + arg6P ≤ 0arg6Parg6P ≤ 0arg6 + arg6 ≤ 0arg6arg6 ≤ 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
13 61 13: x90 + x90 ≤ 0x90x90 ≤ 0x88 + x88 ≤ 0x88x88 ≤ 0x82 + x82 ≤ 0x82x82 ≤ 0x79 + x79 ≤ 0x79x79 ≤ 0arg9P + arg9P ≤ 0arg9Parg9P ≤ 0arg9 + arg9 ≤ 0arg9arg9 ≤ 0arg8P + arg8P ≤ 0arg8Parg8P ≤ 0arg8 + arg8 ≤ 0arg8arg8 ≤ 0arg7P + arg7P ≤ 0arg7Parg7P ≤ 0arg7 + arg7 ≤ 0arg7arg7 ≤ 0arg6P + arg6P ≤ 0arg6Parg6P ≤ 0arg6 + arg6 ≤ 0arg6arg6 ≤ 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
18 68 18: x90 + x90 ≤ 0x90x90 ≤ 0x88 + x88 ≤ 0x88x88 ≤ 0x82 + x82 ≤ 0x82x82 ≤ 0x79 + x79 ≤ 0x79x79 ≤ 0arg9P + arg9P ≤ 0arg9Parg9P ≤ 0arg9 + arg9 ≤ 0arg9arg9 ≤ 0arg8P + arg8P ≤ 0arg8Parg8P ≤ 0arg8 + arg8 ≤ 0arg8arg8 ≤ 0arg7P + arg7P ≤ 0arg7Parg7P ≤ 0arg7 + arg7 ≤ 0arg7arg7 ≤ 0arg6P + arg6P ≤ 0arg6Parg6P ≤ 0arg6 + arg6 ≤ 0arg6arg6 ≤ 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.

2 Transition Removal

We remove transitions 0, 1, 3, 4, 5, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 35, 36, 50, 51, 52, 53 using the following ranking functions, which are bounded by −35.

22: 0
0: 0
1: 0
3: 0
7: 0
5: 0
9: 0
4: 0
19: 0
18: 0
20: 0
10: 0
11: 0
13: 0
14: 0
15: 0
16: 0
17: 0
21: 0
22: −14
0: −15
1: −16
3: −17
7: −18
5: −19
9: −20
4: −21
19: −21
4_var_snapshot: −21
4*: −21
18: −24
20: −24
18_var_snapshot: −24
18*: −24
10: −27
11: −28
13: −29
14: −29
15: −29
16: −29
17: −29
13_var_snapshot: −29
13*: −29
21: −33

3 Location Addition

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

4* 57 4: x90 + x90 ≤ 0x90x90 ≤ 0x88 + x88 ≤ 0x88x88 ≤ 0x82 + x82 ≤ 0x82x82 ≤ 0x79 + x79 ≤ 0x79x79 ≤ 0arg9P + arg9P ≤ 0arg9Parg9P ≤ 0arg9 + arg9 ≤ 0arg9arg9 ≤ 0arg8P + arg8P ≤ 0arg8Parg8P ≤ 0arg8 + arg8 ≤ 0arg8arg8 ≤ 0arg7P + arg7P ≤ 0arg7Parg7P ≤ 0arg7 + arg7 ≤ 0arg7arg7 ≤ 0arg6P + arg6P ≤ 0arg6Parg6P ≤ 0arg6 + arg6 ≤ 0arg6arg6 ≤ 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

4 Location Addition

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

4 55 4_var_snapshot: x90 + x90 ≤ 0x90x90 ≤ 0x88 + x88 ≤ 0x88x88 ≤ 0x82 + x82 ≤ 0x82x82 ≤ 0x79 + x79 ≤ 0x79x79 ≤ 0arg9P + arg9P ≤ 0arg9Parg9P ≤ 0arg9 + arg9 ≤ 0arg9arg9 ≤ 0arg8P + arg8P ≤ 0arg8Parg8P ≤ 0arg8 + arg8 ≤ 0arg8arg8 ≤ 0arg7P + arg7P ≤ 0arg7Parg7P ≤ 0arg7 + arg7 ≤ 0arg7arg7 ≤ 0arg6P + arg6P ≤ 0arg6Parg6P ≤ 0arg6 + arg6 ≤ 0arg6arg6 ≤ 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.

13* 64 13: x90 + x90 ≤ 0x90x90 ≤ 0x88 + x88 ≤ 0x88x88 ≤ 0x82 + x82 ≤ 0x82x82 ≤ 0x79 + x79 ≤ 0x79x79 ≤ 0arg9P + arg9P ≤ 0arg9Parg9P ≤ 0arg9 + arg9 ≤ 0arg9arg9 ≤ 0arg8P + arg8P ≤ 0arg8Parg8P ≤ 0arg8 + arg8 ≤ 0arg8arg8 ≤ 0arg7P + arg7P ≤ 0arg7Parg7P ≤ 0arg7 + arg7 ≤ 0arg7arg7 ≤ 0arg6P + arg6P ≤ 0arg6Parg6P ≤ 0arg6 + arg6 ≤ 0arg6arg6 ≤ 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.

13 62 13_var_snapshot: x90 + x90 ≤ 0x90x90 ≤ 0x88 + x88 ≤ 0x88x88 ≤ 0x82 + x82 ≤ 0x82x82 ≤ 0x79 + x79 ≤ 0x79x79 ≤ 0arg9P + arg9P ≤ 0arg9Parg9P ≤ 0arg9 + arg9 ≤ 0arg9arg9 ≤ 0arg8P + arg8P ≤ 0arg8Parg8P ≤ 0arg8 + arg8 ≤ 0arg8arg8 ≤ 0arg7P + arg7P ≤ 0arg7Parg7P ≤ 0arg7 + arg7 ≤ 0arg7arg7 ≤ 0arg6P + arg6P ≤ 0arg6Parg6P ≤ 0arg6 + arg6 ≤ 0arg6arg6 ≤ 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.

18* 71 18: x90 + x90 ≤ 0x90x90 ≤ 0x88 + x88 ≤ 0x88x88 ≤ 0x82 + x82 ≤ 0x82x82 ≤ 0x79 + x79 ≤ 0x79x79 ≤ 0arg9P + arg9P ≤ 0arg9Parg9P ≤ 0arg9 + arg9 ≤ 0arg9arg9 ≤ 0arg8P + arg8P ≤ 0arg8Parg8P ≤ 0arg8 + arg8 ≤ 0arg8arg8 ≤ 0arg7P + arg7P ≤ 0arg7Parg7P ≤ 0arg7 + arg7 ≤ 0arg7arg7 ≤ 0arg6P + arg6P ≤ 0arg6Parg6P ≤ 0arg6 + arg6 ≤ 0arg6arg6 ≤ 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.

18 69 18_var_snapshot: x90 + x90 ≤ 0x90x90 ≤ 0x88 + x88 ≤ 0x88x88 ≤ 0x82 + x82 ≤ 0x82x82 ≤ 0x79 + x79 ≤ 0x79x79 ≤ 0arg9P + arg9P ≤ 0arg9Parg9P ≤ 0arg9 + arg9 ≤ 0arg9arg9 ≤ 0arg8P + arg8P ≤ 0arg8Parg8P ≤ 0arg8 + arg8 ≤ 0arg8arg8 ≤ 0arg7P + arg7P ≤ 0arg7Parg7P ≤ 0arg7 + arg7 ≤ 0arg7arg7 ≤ 0arg6P + arg6P ≤ 0arg6Parg6P ≤ 0arg6 + arg6 ≤ 0arg6arg6 ≤ 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 SCC Decomposition

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

9.1 SCC Subproblem 1/3

Here we consider the SCC { 18, 20, 18_var_snapshot, 18* }.

9.1.1 Transition Removal

We remove transitions 43, 44, 45, 46, 47, 48, 49 using the following ranking functions, which are bounded by 0.

18: −1 + 3⋅arg1
20: 1 + 3⋅arg3
18_var_snapshot: −2 + 3⋅arg1
18*: 3⋅arg1

9.1.2 Transition Removal

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

18: 0
20: 0
18_var_snapshot: −1
18*: 1

9.1.3 Splitting Cut-Point Transitions

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

9.1.3.1 Cut-Point Subproblem 1/1

Here we consider cut-point transition 68.

9.1.3.1.1 Splitting Cut-Point Transitions

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

9.2 SCC Subproblem 2/3

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

9.2.1 Transition Removal

We remove transitions 37, 38, 39, 40, 41, 42 using the following ranking functions, which are bounded by −1.

4: −4 + arg2 + 3⋅arg3 + 2⋅arg4
19: 3⋅arg3 + 3⋅arg6
4_var_snapshot: −5 + arg2 + 3⋅arg3 + 2⋅arg4
4*: −3 + arg2 + 3⋅arg3 + 2⋅arg4

9.2.2 Transition Removal

We remove transitions 55, 57 using the following ranking functions, which are bounded by −2.

4: −1
19: 0
4_var_snapshot: −2
4*: 0

9.2.3 Splitting Cut-Point Transitions

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

9.2.3.1 Cut-Point Subproblem 1/1

Here we consider cut-point transition 54.

9.2.3.1.1 Splitting Cut-Point Transitions

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

9.3 SCC Subproblem 3/3

Here we consider the SCC { 13, 14, 15, 16, 17, 13_var_snapshot, 13* }.

9.3.1 Transition Removal

We remove transitions 21, 23, 24, 25, 31, 32 using the following ranking functions, which are bounded by 1.

13: −1 + 7⋅arg3
14: −5 + 7⋅arg1
15: −6 + 7⋅arg1
16: −3 + 7⋅arg1
17: −4 + 7⋅arg1
13_var_snapshot: −2 + 7⋅arg3
13*: 7⋅arg3

9.3.2 Transition Removal

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

13: −1 + arg3 + 3⋅arg4 − 3⋅arg5
14: −1 + arg1 + 3⋅arg5 − 3⋅arg6
15: arg1 + 3⋅arg4 − 3⋅arg5
16: arg1 + 3⋅arg5 − 3⋅arg6
17: arg1 + 3⋅arg4 − 3⋅arg5
13_var_snapshot: −2 + arg3 + 3⋅arg4 − 3⋅arg5
13*: arg3 + 3⋅arg4 − 3⋅arg5

9.3.3 Transition Removal

We remove transitions 62, 64, 22, 27, 28, 29, 30, 33, 34 using the following ranking functions, which are bounded by −2.

13: −1
14: 1
15: arg2
16: 2
17: arg2
13_var_snapshot: −2
13*: 0

9.3.4 Splitting Cut-Point Transitions

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

9.3.4.1 Cut-Point Subproblem 1/1

Here we consider cut-point transition 61.

9.3.4.1.1 Splitting Cut-Point Transitions

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

Tool configuration

T2Cert