LTS Termination Proof

by AProVE

Input

Integer Transition System

Proof

1 Switch to Cooperation Termination Proof

We consider the following cutpoint-transitions:
f4135_0_sublistAutoDual_InvokeMethod f4135_0_sublistAutoDual_InvokeMethod f4135_0_sublistAutoDual_InvokeMethod: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f2375_0_generation_InvokeMethod f2375_0_generation_InvokeMethod f2375_0_generation_InvokeMethod: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f1674_0_number_greater_LT f1674_0_number_greater_LT f1674_0_number_greater_LT: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f2374_0_generation_InvokeMethod f2374_0_generation_InvokeMethod f2374_0_generation_InvokeMethod: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
__init __init __init: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f4661_0_sublistOddDistinctParts_InvokeMethod' f4661_0_sublistOddDistinctParts_InvokeMethod' f4661_0_sublistOddDistinctParts_InvokeMethod': x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f3187_0_generation_InvokeMethod f3187_0_generation_InvokeMethod f3187_0_generation_InvokeMethod: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f2470_0_sublistAutoDual_InvokeMethod f2470_0_sublistAutoDual_InvokeMethod f2470_0_sublistAutoDual_InvokeMethod: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f741_0_generation_Return f741_0_generation_Return f741_0_generation_Return: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f3192_0_dual_LE f3192_0_dual_LE f3192_0_dual_LE: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f789_0_generation_Return f789_0_generation_Return f789_0_generation_Return: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f4740_0_sublistOddDistinctParts_NULL f4740_0_sublistOddDistinctParts_NULL f4740_0_sublistOddDistinctParts_NULL: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f2503_0_isEqual_NONNULL f2503_0_isEqual_NONNULL f2503_0_isEqual_NONNULL: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f2372_0_main_InvokeMethod f2372_0_main_InvokeMethod f2372_0_main_InvokeMethod: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f654_0_generation_NE f654_0_generation_NE f654_0_generation_NE: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f609_0_generation_NONNULL f609_0_generation_NONNULL f609_0_generation_NONNULL: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f2504_0_union_NONNULL f2504_0_union_NONNULL f2504_0_union_NONNULL: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f3931_0_sublistAutoDual_InvokeMethod f3931_0_sublistAutoDual_InvokeMethod f3931_0_sublistAutoDual_InvokeMethod: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f2440_0_insert_NONNULL f2440_0_insert_NONNULL f2440_0_insert_NONNULL: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f4854_0_sublistOddDistinctParts_EQ f4854_0_sublistOddDistinctParts_EQ f4854_0_sublistOddDistinctParts_EQ: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f2373_0_generation_InvokeMethod f2373_0_generation_InvokeMethod f2373_0_generation_InvokeMethod: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f4689_0_oddDistinctParts_NE f4689_0_oddDistinctParts_NE f4689_0_oddDistinctParts_NE: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f4119_0_main_InvokeMethod f4119_0_main_InvokeMethod f4119_0_main_InvokeMethod: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f740_0_generation_Return f740_0_generation_Return f740_0_generation_Return: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f742_0_generation_Return f742_0_generation_Return f742_0_generation_Return: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f4661_0_sublistOddDistinctParts_InvokeMethod f4661_0_sublistOddDistinctParts_InvokeMethod f4661_0_sublistOddDistinctParts_InvokeMethod: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f283_0_partitionOf_GT f283_0_partitionOf_GT f283_0_partitionOf_GT: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f1_0_main_Load f1_0_main_Load f1_0_main_Load: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f4689_0_oddDistinctParts_NE' f4689_0_oddDistinctParts_NE' f4689_0_oddDistinctParts_NE': x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
and for every transition t, a duplicate t is considered.

2 SCC Decomposition

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

2.1 SCC Subproblem 1/9

Here we consider the SCC { f283_0_partitionOf_GT }.

2.1.1 Transition Removal

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

f283_0_partitionOf_GT: x3 + x4

2.1.2 Trivial Cooperation Program

There are no more "sharp" transitions in the cooperation program. Hence the cooperation termination is proved.

2.2 SCC Subproblem 2/9

Here we consider the SCC { f2470_0_sublistAutoDual_InvokeMethod, f3192_0_dual_LE }.

2.2.1 Transition Removal

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

f2470_0_sublistAutoDual_InvokeMethod: x1 + 1
f3192_0_dual_LE: x1

2.2.2 Transition Removal

We remove transitions 36, 48, 49, 50 using the following ranking functions, which are bounded by 0.

f2470_0_sublistAutoDual_InvokeMethod: x1
f3192_0_dual_LE: −1 + x1 + x4x5

2.2.3 Trivial Cooperation Program

There are no more "sharp" transitions in the cooperation program. Hence the cooperation termination is proved.

2.3 SCC Subproblem 3/9

Here we consider the SCC { f1674_0_number_greater_LT }.

2.3.1 Transition Removal

We remove transitions 77, 78 using the following ranking functions, which are bounded by 0.

f1674_0_number_greater_LT: −3 + x1

2.3.2 Trivial Cooperation Program

There are no more "sharp" transitions in the cooperation program. Hence the cooperation termination is proved.

2.4 SCC Subproblem 4/9

Here we consider the SCC { f2503_0_isEqual_NONNULL }.

2.4.1 Transition Removal

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

f2503_0_isEqual_NONNULL: x2

2.4.2 Trivial Cooperation Program

There are no more "sharp" transitions in the cooperation program. Hence the cooperation termination is proved.

2.5 SCC Subproblem 5/9

Here we consider the SCC { f4661_0_sublistOddDistinctParts_InvokeMethod, f4854_0_sublistOddDistinctParts_EQ, f4740_0_sublistOddDistinctParts_NULL }.

2.5.1 Transition Removal

We remove transitions 90, 91, 98, 93, 92, 99, 97, 96, 95, 94 using the following ranking functions, which are bounded by 0.

f4661_0_sublistOddDistinctParts_InvokeMethod: 1 + 2⋅x1
f4740_0_sublistOddDistinctParts_NULL: −1 + 2⋅x1
f4854_0_sublistOddDistinctParts_EQ: 2⋅x1

2.5.2 Trivial Cooperation Program

There are no more "sharp" transitions in the cooperation program. Hence the cooperation termination is proved.

2.6 SCC Subproblem 6/9

Here we consider the SCC { f4689_0_oddDistinctParts_NE, f4689_0_oddDistinctParts_NE' }.

2.6.1 Transition Removal

We remove transitions 102, 106, 103, 107, 104, 108, 105, 109 using the following ranking functions, which are bounded by 0.

f4689_0_oddDistinctParts_NE: 1 + x1
f4689_0_oddDistinctParts_NE': x1

2.6.2 Trivial Cooperation Program

There are no more "sharp" transitions in the cooperation program. Hence the cooperation termination is proved.

2.7 SCC Subproblem 7/9

Here we consider the SCC { f3187_0_generation_InvokeMethod, f654_0_generation_NE, f609_0_generation_NONNULL, f2373_0_generation_InvokeMethod }.

2.7.1 Transition Removal

We remove transitions 10, 13, 11, 27, 16, 31, 30, 29, 17, 15, 14 using the following ranking functions, which are bounded by 0.

f609_0_generation_NONNULL: 3⋅x3 − 1
f654_0_generation_NE: 3⋅x2 − 2
f2373_0_generation_InvokeMethod: 3⋅x2 − 2
f3187_0_generation_InvokeMethod: 3⋅x3

2.7.2 Transition Removal

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

f609_0_generation_NONNULL: x1

2.7.3 Trivial Cooperation Program

There are no more "sharp" transitions in the cooperation program. Hence the cooperation termination is proved.

2.8 SCC Subproblem 8/9

Here we consider the SCC { f2504_0_union_NONNULL }.

2.8.1 Transition Removal

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

f2504_0_union_NONNULL: x1

2.8.2 Trivial Cooperation Program

There are no more "sharp" transitions in the cooperation program. Hence the cooperation termination is proved.

2.9 SCC Subproblem 9/9

Here we consider the SCC { f2440_0_insert_NONNULL }.

2.9.1 Transition Removal

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

f2440_0_insert_NONNULL: x1

2.9.2 Trivial Cooperation Program

There are no more "sharp" transitions in the cooperation program. Hence the cooperation termination is proved.

Tool configuration

AProVE