LTS Termination Proof

by AProVE

Input

Integer Transition System

Proof

1 Switch to Cooperation Termination Proof

We consider the following cutpoint-transitions:
f913_0__init__GE f913_0__init__GE f913_0__init__GE: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f9340_0_possibleValues_GE f9340_0_possibleValues_GE f9340_0_possibleValues_GE: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f8234_0_resolve_aux_GE f8234_0_resolve_aux_GE f8234_0_resolve_aux_GE: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f9691_0_possibleValues_GE f9691_0_possibleValues_GE f9691_0_possibleValues_GE: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
__init __init __init: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f9214_0_possibleValues_GE f9214_0_possibleValues_GE f9214_0_possibleValues_GE: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f8739_0_possibleValues_GE f8739_0_possibleValues_GE f8739_0_possibleValues_GE: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f10650_0_resolve_aux_GE f10650_0_resolve_aux_GE f10650_0_resolve_aux_GE: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f1158_0__init__GE f1158_0__init__GE f1158_0__init__GE: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f7719_0_resolve_aux_LE f7719_0_resolve_aux_LE f7719_0_resolve_aux_LE: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f10649_0_resolve_aux_GE f10649_0_resolve_aux_GE f10649_0_resolve_aux_GE: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f9214_0_possibleValues_GE' f9214_0_possibleValues_GE' f9214_0_possibleValues_GE': x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f1907_0_resolve_GE f1907_0_resolve_GE f1907_0_resolve_GE: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f2103_0_resolve_GE f2103_0_resolve_GE f2103_0_resolve_GE: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6
f8467_0_resolve_aux_GE f8467_0_resolve_aux_GE f8467_0_resolve_aux_GE: 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
f8384_0_possibleValues_GE f8384_0_possibleValues_GE f8384_0_possibleValues_GE: 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 7 SCC(s) of the program graph.

2.1 SCC Subproblem 1/7

Here we consider the SCC { f913_0__init__GE, f1158_0__init__GE }.

2.1.1 Transition Removal

We remove transition 2 using the following ranking functions, which are bounded by −16.

f913_0__init__GE: −2⋅x2
f1158_0__init__GE: −2⋅x2 − 1

2.1.2 Transition Removal

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

f1158_0__init__GE: 0
f913_0__init__GE: −1

2.1.3 Transition Removal

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

f1158_0__init__GE: x3

2.1.4 Trivial Cooperation Program

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

2.2 SCC Subproblem 2/7

Here we consider the SCC { f1907_0_resolve_GE, f2103_0_resolve_GE }.

2.2.1 Transition Removal

We remove transition 7 using the following ranking functions, which are bounded by −14.

f1907_0_resolve_GE: −2⋅x4 + 2
f2103_0_resolve_GE: −2⋅x3 + 1

2.2.2 Transition Removal

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

f2103_0_resolve_GE: 0
f1907_0_resolve_GE: −1

2.2.3 Transition Removal

We remove transitions 9, 10, 11 using the following ranking functions, which are bounded by 0.

f2103_0_resolve_GE: 8 − x4

2.2.4 Trivial Cooperation Program

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

2.3 SCC Subproblem 3/7

Here we consider the SCC { f10650_0_resolve_aux_GE, f7719_0_resolve_aux_LE, f10649_0_resolve_aux_GE, f8467_0_resolve_aux_GE, f8234_0_resolve_aux_GE }.

2.3.1 Transition Removal

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

f7719_0_resolve_aux_LE: −1 + x1
f8234_0_resolve_aux_GE: −2 + x1
f10650_0_resolve_aux_GE: −2 + x1
f8467_0_resolve_aux_GE: −2 + x1
f10649_0_resolve_aux_GE: −2 + x1

2.3.2 Transition Removal

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

f10650_0_resolve_aux_GE: −1 − x1
f7719_0_resolve_aux_LE: −2 − x1
f8467_0_resolve_aux_GE: −1 + x1
f10649_0_resolve_aux_GE: −1 − x1
f8234_0_resolve_aux_GE: −1 + x1

2.3.3 Transition Removal

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

f10650_0_resolve_aux_GE: −1 − x1
f7719_0_resolve_aux_LE: −2 − x1
f10649_0_resolve_aux_GE: −5 + x1 + x2
f8467_0_resolve_aux_GE: 7 − x2
f8234_0_resolve_aux_GE: 8 − x3

2.3.4 Transition Removal

We remove transitions 15, 16 using the following ranking functions, which are bounded by 0.

f10650_0_resolve_aux_GE: −1 − x1
f7719_0_resolve_aux_LE: −2 − x1
f10649_0_resolve_aux_GE: −5 + x1 + x2
f8467_0_resolve_aux_GE: 8 − x3
f8234_0_resolve_aux_GE: 8 − x2

2.3.5 Transition Removal

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

f10650_0_resolve_aux_GE: −1 − x1
f7719_0_resolve_aux_LE: −2 − x1
f10649_0_resolve_aux_GE: −5 + x1 + x2
f8467_0_resolve_aux_GE: 0
f8234_0_resolve_aux_GE: −1

2.3.6 Transition Removal

We remove transitions 24, 23 using the following ranking functions, which are bounded by 0.

f10650_0_resolve_aux_GE: −1 + x1
f7719_0_resolve_aux_LE: −1 + x1
f10649_0_resolve_aux_GE: −4 + x1 + x2

2.3.7 Transition Removal

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

f10650_0_resolve_aux_GE: 8 − x4
f10649_0_resolve_aux_GE: −4 + x1 + x2
f7719_0_resolve_aux_LE: −1 + x1

2.3.8 Transition Removal

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

f10649_0_resolve_aux_GE: −3 + x1 + x2
f7719_0_resolve_aux_LE: −1 + x1

2.3.9 Transition Removal

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

f10649_0_resolve_aux_GE: 8 − x4

2.3.10 Trivial Cooperation Program

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

2.4 SCC Subproblem 4/7

Here we consider the SCC { f8384_0_possibleValues_GE }.

2.4.1 Transition Removal

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

f8384_0_possibleValues_GE: 8 − x3

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/7

Here we consider the SCC { f8739_0_possibleValues_GE }.

2.5.1 Transition Removal

We remove transitions 33, 34, 35 using the following ranking functions, which are bounded by −8.

f8739_0_possibleValues_GE: x3

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/7

Here we consider the SCC { f9214_0_possibleValues_GE }.

2.6.1 Transition Removal

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

f9214_0_possibleValues_GE: 8 − x3

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/7

Here we consider the SCC { f9340_0_possibleValues_GE, f9691_0_possibleValues_GE }.

2.7.1 Transition Removal

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

f9340_0_possibleValues_GE: x3 + x4
f9691_0_possibleValues_GE: −1 + x2x3

2.7.2 Transition Removal

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

f9691_0_possibleValues_GE: 0
f9340_0_possibleValues_GE: −1

2.7.3 Transition Removal

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

f9691_0_possibleValues_GE: x5 + x6

2.7.4 Trivial Cooperation Program

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

Tool configuration

AProVE