LTS Termination Proof

by AProVE

Input

Integer Transition System

Proof

1 Switch to Cooperation Termination Proof

We consider the following cutpoint-transitions:
f2521_0_main_InvokeMethod f2521_0_main_InvokeMethod f2521_0_main_InvokeMethod: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9
f701_0_createTree_Return f701_0_createTree_Return f701_0_createTree_Return: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9
f355_0_createTree_Return f355_0_createTree_Return f355_0_createTree_Return: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9
f845_0_alternate_NONNULL f845_0_alternate_NONNULL f845_0_alternate_NONNULL: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9
f1242_0_alternate_InvokeMethod f1242_0_alternate_InvokeMethod f1242_0_alternate_InvokeMethod: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9
f2589_0_main_InvokeMethod f2589_0_main_InvokeMethod f2589_0_main_InvokeMethod: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9
f2712_0_createTree_LE f2712_0_createTree_LE f2712_0_createTree_LE: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9
f702_0_createTree_Return f702_0_createTree_Return f702_0_createTree_Return: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9
f2530_0_main_InvokeMethod f2530_0_main_InvokeMethod f2530_0_main_InvokeMethod: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9
f2504_0_createTree_LE f2504_0_createTree_LE f2504_0_createTree_LE: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9
f756_0_copy_NONNULL f756_0_copy_NONNULL f756_0_copy_NONNULL: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9
f61_0_createTree_Return f61_0_createTree_Return f61_0_createTree_Return: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9
f252_0_main_InvokeMethod f252_0_main_InvokeMethod f252_0_main_InvokeMethod: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9
__init __init __init: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9
f2588_0_createTree_NONNULL f2588_0_createTree_NONNULL f2588_0_createTree_NONNULL: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9
f1172_0_createNode_Return f1172_0_createNode_Return f1172_0_createNode_Return: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9
f741_0_random_GT f741_0_random_GT f741_0_random_GT: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9
f2671_0_createTree_FieldAccess f2671_0_createTree_FieldAccess f2671_0_createTree_FieldAccess: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9
f2777_0_createTree_FieldAccess f2777_0_createTree_FieldAccess f2777_0_createTree_FieldAccess: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9
f1247_0_copy_InvokeMethod f1247_0_copy_InvokeMethod f1247_0_copy_InvokeMethod: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9
f875_0_createTree_NE f875_0_createTree_NE f875_0_createTree_NE: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9
f1_0_main_Load f1_0_main_Load f1_0_main_Load: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9
and for every transition t, a duplicate t is considered.

2 SCC Decomposition

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

2.1 SCC Subproblem 1/3

Here we consider the SCC { f2671_0_createTree_FieldAccess, f2777_0_createTree_FieldAccess, f2712_0_createTree_LE, f2504_0_createTree_LE, f2588_0_createTree_NONNULL }.

2.1.1 Transition Removal

We remove transitions 22, 26, 27 using the following ranking functions, which are bounded by 0.

f2504_0_createTree_LE: −1 + x3 + x4
f2588_0_createTree_NONNULL: −2 + x1 + x5
f2712_0_createTree_LE: −2 + x1 + x5
f2777_0_createTree_FieldAccess: −2 + x1 + x4
f2671_0_createTree_FieldAccess: −2 + x1 + x4

2.1.2 Transition Removal

We remove transitions 23, 30, 31, 35, 34, 33, 32, 29, 28, 25, 24 using the following ranking functions, which are bounded by 0.

f2588_0_createTree_NONNULL: 2
f2504_0_createTree_LE: 0
f2712_0_createTree_LE: 3
f2777_0_createTree_FieldAccess: 1
f2671_0_createTree_FieldAccess: 1

2.1.3 Trivial Cooperation Program

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

2.2 SCC Subproblem 2/3

Here we consider the SCC { f845_0_alternate_NONNULL, f1242_0_alternate_InvokeMethod }.

2.2.1 Transition Removal

We remove transitions 38, 41, 40, 39 using the following ranking functions, which are bounded by 0.

f845_0_alternate_NONNULL: x4 + x3
f1242_0_alternate_InvokeMethod: x4 + x3 + 1

2.2.2 Trivial Cooperation Program

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

2.3 SCC Subproblem 3/3

Here we consider the SCC { f1247_0_copy_InvokeMethod, f756_0_copy_NONNULL }.

2.3.1 Transition Removal

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

f756_0_copy_NONNULL: x1
f1247_0_copy_InvokeMethod: −1 + x1

2.3.2 Trivial Cooperation Program

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

Tool configuration

AProVE