LTS Termination Proof

by T2Cert

Input

Integer Transition System

Proof

1 Switch to Cooperation Termination Proof

We consider the following cutpoint-transitions:
4 95 4: x598 + x598 ≤ 0x598x598 ≤ 0x592 + x592 ≤ 0x592x592 ≤ 0x581 + x581 ≤ 0x581x581 ≤ 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 102 5: x598 + x598 ≤ 0x598x598 ≤ 0x592 + x592 ≤ 0x592x592 ≤ 0x581 + x581 ≤ 0x581x581 ≤ 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 109 6: x598 + x598 ≤ 0x598x598 ≤ 0x592 + x592 ≤ 0x592x592 ≤ 0x581 + x581 ≤ 0x581x581 ≤ 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 116 8: x598 + x598 ≤ 0x598x598 ≤ 0x592 + x592 ≤ 0x592x592 ≤ 0x581 + x581 ≤ 0x581x581 ≤ 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, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 92, 94 using the following ranking functions, which are bounded by −27.

9: 0
0: 0
1: 0
8: 0
3: 0
4: 0
7: 0
5: 0
6: 0
9: −9
0: −10
1: −11
8: −12
8_var_snapshot: −12
8*: −12
3: −15
4: −16
7: −16
4_var_snapshot: −16
4*: −16
5: −19
5_var_snapshot: −19
5*: −19
6: −22
6_var_snapshot: −22
6*: −22

3 Location Addition

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

4* 98 4: x598 + x598 ≤ 0x598x598 ≤ 0x592 + x592 ≤ 0x592x592 ≤ 0x581 + x581 ≤ 0x581x581 ≤ 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 96 4_var_snapshot: x598 + x598 ≤ 0x598x598 ≤ 0x592 + x592 ≤ 0x592x592 ≤ 0x581 + x581 ≤ 0x581x581 ≤ 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.

5* 105 5: x598 + x598 ≤ 0x598x598 ≤ 0x592 + x592 ≤ 0x592x592 ≤ 0x581 + x581 ≤ 0x581x581 ≤ 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.

5 103 5_var_snapshot: x598 + x598 ≤ 0x598x598 ≤ 0x592 + x592 ≤ 0x592x592 ≤ 0x581 + x581 ≤ 0x581x581 ≤ 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.

6* 112 6: x598 + x598 ≤ 0x598x598 ≤ 0x592 + x592 ≤ 0x592x592 ≤ 0x581 + x581 ≤ 0x581x581 ≤ 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.

6 110 6_var_snapshot: x598 + x598 ≤ 0x598x598 ≤ 0x592 + x592 ≤ 0x592x592 ≤ 0x581 + x581 ≤ 0x581x581 ≤ 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 Location Addition

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

8* 119 8: x598 + x598 ≤ 0x598x598 ≤ 0x592 + x592 ≤ 0x592x592 ≤ 0x581 + x581 ≤ 0x581x581 ≤ 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

10 Location Addition

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

8 117 8_var_snapshot: x598 + x598 ≤ 0x598x598 ≤ 0x592 + x592 ≤ 0x592x592 ≤ 0x581 + x581 ≤ 0x581x581 ≤ 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

11 SCC Decomposition

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

11.1 SCC Subproblem 1/4

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

11.1.1 Transition Removal

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

8: arg1 + arg2
8_var_snapshot: arg1 + arg2
8*: 1 + arg1 + arg2

11.1.2 Transition Removal

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

8: −1
8_var_snapshot: −2
8*: 0

11.1.3 Splitting Cut-Point Transitions

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

11.1.3.1 Cut-Point Subproblem 1/1

Here we consider cut-point transition 116.

11.1.3.1.1 Splitting Cut-Point Transitions

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

11.2 SCC Subproblem 2/4

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

11.2.1 Transition Removal

We remove transitions 87, 88 using the following ranking functions, which are bounded by 5.

5: 2 + 3⋅arg2
5_var_snapshot: 3⋅arg2
5*: 4 + 3⋅arg2

11.2.2 Transition Removal

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

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

11.2.3 Splitting Cut-Point Transitions

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

11.2.3.1 Cut-Point Subproblem 1/1

Here we consider cut-point transition 102.

11.2.3.1.1 Splitting Cut-Point Transitions

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

11.3 SCC Subproblem 3/4

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

11.3.1 Transition Removal

We remove transitions 90, 91 using the following ranking functions, which are bounded by 5.

6: 1 + 2⋅arg2
6_var_snapshot: 2⋅arg2
6*: 2 + 2⋅arg2

11.3.2 Transition Removal

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

6: 2 + 3⋅arg2
6_var_snapshot: 3⋅arg2
6*: 4 + 3⋅arg2

11.3.3 Transition Removal

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

6: 0
6_var_snapshot: −1
6*: 1

11.3.4 Splitting Cut-Point Transitions

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

11.3.4.1 Cut-Point Subproblem 1/1

Here we consider cut-point transition 109.

11.3.4.1.1 Splitting Cut-Point Transitions

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

11.4 SCC Subproblem 4/4

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

11.4.1 Transition Removal

We remove transitions 15, 16, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86 using the following ranking functions, which are bounded by 0.

4: −1 − 4⋅arg2 + 4⋅arg3
7: −3 + 4⋅arg1 − 4⋅arg2
4_var_snapshot: −2 − 4⋅arg2 + 4⋅arg3
4*: −4⋅arg2 + 4⋅arg3

11.4.2 Transition Removal

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

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

11.4.3 Splitting Cut-Point Transitions

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

11.4.3.1 Cut-Point Subproblem 1/1

Here we consider cut-point transition 95.

11.4.3.1.1 Splitting Cut-Point Transitions

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

Tool configuration

T2Cert