LTS Termination Proof

by AProVE

Input

Integer Transition System

Proof

1 Switch to Cooperation Termination Proof

We consider the following cutpoint-transitions:
l22 l22 l22: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
l1 l1 l1: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
l13 l13 l13: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
l18 l18 l18: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
l17 l17 l17: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
l21 l21 l21: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
l9 l9 l9: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
l14 l14 l14: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
l25 l25 l25: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
l6 l6 l6: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
l8 l8 l8: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
l27 l27 l27: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
l0 l0 l0: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
l12 l12 l12: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
l19 l19 l19: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
l26 l26 l26: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
l7 l7 l7: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
l24 l24 l24: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
l11 l11 l11: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
l3 l3 l3: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
l20 l20 l20: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
l2 l2 l2: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
l23 l23 l23: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
l4 l4 l4: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
l10 l10 l10: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
l15 l15 l15: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
l16 l16 l16: x1 = x1 ∧ x2 = x2 ∧ x3 = x3 ∧ x4 = x4 ∧ x5 = x5 ∧ x6 = x6 ∧ x7 = x7 ∧ x8 = x8 ∧ x9 = x9 ∧ x10 = x10 ∧ x11 = x11 ∧ x12 = x12 ∧ x13 = x13 ∧ x14 = x14 ∧ x15 = x15 ∧ x16 = x16 ∧ x17 = x17 ∧ x18 = x18
and for every transition t, a duplicate t is considered.

2 SCC Decomposition

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

2.1 SCC Subproblem 1/1

Here we consider the SCC { l22, l7, l24, l11, l1, l3, l13, l20, l18, l17, l2, l21, l14, l9, l23, l10, l8, l15, l16, l0, l12, l19, l26 }.

2.1.1 Transition Removal

We remove transitions 30, 27, 10, 7 using the following ranking functions, which are bounded by 0.

l0: − x1 + x6
l1: − x1 + x6
l3: − x1 + x6
l26: − x1 + x6
l2: − x1 + x6
l14: − x1 + x6
l17: − x1 + x6
l13: − x1 + x6
l12: − x1 + x6
l8: − x1 + x6
l15: − x1 + x6
l16: − x1 + x6
l22: − x1 + x6
l20: − x1 + x6
l23: − x1 + x6
l24: − x1 + x6
l19: −1 − x1 + x6
l21: −1 − x1 + x6
l18: −1 − x1 + x6
l7: − x1 + x6
l9: − x1 + x6
l10: − x1 + x6
l11: − x1 + x6

2.1.2 Transition Removal

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

l0: −2 − x3 + x6
l1: −2 − x3 + x6
l3: −2 − x3 + x6
l26: −2 − x3 + x6
l2: −2 − x3 + x6
l14: −1 − x3 + x6
l17: −1 − x3 + x6
l13: −2 − x3 + x6
l12: −2 − x3 + x6
l8: −2 − x3 + x6
l15: −2 − x3 + x6
l16: −2 − x3 + x6
l22: −2 − x3 + x6
l20: −2 − x3 + x6
l23: −2 − x3 + x6
l24: −2 − x3 + x6
l19: −2 − x3 + x6
l21: −2 − x3 + x6
l18: −2 − x3 + x6
l7: −2 − x3 + x6
l9: −2 − x3 + x6
l10: −2 − x3 + x6
l11: −2 − x3 + x6

2.1.3 Transition Removal

We remove transitions 1, 20, 32, 36, 12, 17, 19, 18, 26, 28, 29, 31, 35, 34, 22, 25, 21, 24, 23 using the following ranking functions, which are bounded by 0.

l0: 10
l1: 9
l3: 10
l26: 10
l2: 10
l17: 0
l14: −1
l13: 1
l12: 2
l8: 2
l15: 3
l16: 4
l22: 5
l20: 6
l23: 7
l24: 8
l19: 7
l21: 9
l18: 8
l7: 2
l9: 2
l10: 2
l11: 2

2.1.4 Transition Removal

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

l3: −1 − x1 + 2⋅x2 + 3⋅x3 + 4⋅x6 − x7 + 5⋅x8 + 6⋅x9 + 7⋅x10 + 8⋅x11 + 9⋅x13 + 10⋅x14 + 11⋅x15 + 12⋅x16 + 13⋅x17 + 14⋅x18
l0: −1 − x1 + 2⋅x2 + 3⋅x3 + 4⋅x6 − x7 + 5⋅x8 + 6⋅x9 + 7⋅x10 + 8⋅x11 + 9⋅x13 + 10⋅x14 + 11⋅x15 + 12⋅x16 + 13⋅x17 + 14⋅x18
l26: −2 − x1 + 2⋅x2 + 3⋅x3 + 4⋅x6 − x7 + 5⋅x8 + 6⋅x9 + 7⋅x10 + 8⋅x11 + 9⋅x13 + 10⋅x14 + 11⋅x15 + 12⋅x16 + 13⋅x17 + 14⋅x18
l2: −2 − x1 + 2⋅x2 + 3⋅x3 − x4 + 4⋅x6 + 5⋅x8 + 6⋅x9 + 7⋅x10 + 8⋅x11 + 9⋅x13 + 10⋅x14 + 11⋅x15 + 12⋅x16 + 13⋅x17 + 14⋅x18
l8: − x2 + x6
l12: − x2 + x6
l7: −1 − x2 + x6
l9: −1 − x2 + x6
l10: −1 − x2 + x6
l11: −1 − x2 + x6

2.1.5 Transition Removal

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

l3: −1 − x1 + 5⋅x2 + 6⋅x3 + 7⋅x6 − x7 + 8⋅x8 + 9⋅x9 + 10⋅x10 + 11⋅x11 + 12⋅x13 + 13⋅x14 + 14⋅x15 + 15⋅x16 + 16⋅x17 + 17⋅x18
l0: −2 − x1 + 5⋅x2 + 6⋅x3 + 7⋅x6 − x7 + 8⋅x8 + 9⋅x9 + 10⋅x10 + 11⋅x11 + 12⋅x13 + 13⋅x14 + 14⋅x15 + 15⋅x16 + 16⋅x17 + 17⋅x18
l26: −2 − x1 + 5⋅x2 + 6⋅x3 + 7⋅x6 − x7 + 8⋅x8 + 9⋅x9 + 10⋅x10 + 11⋅x11 + 12⋅x13 + 13⋅x14 + 14⋅x15 + 15⋅x16 + 16⋅x17 + 17⋅x18
l2: −2 − x1 + 5⋅x2 + 6⋅x3 − x4 + 7⋅x6 + 8⋅x8 + 9⋅x9 + 10⋅x10 + 11⋅x11 + 12⋅x13 + 13⋅x14 + 14⋅x15 + 15⋅x16 + 16⋅x17 + 17⋅x18
l8: 0
l12: −1
l7: 1
l9: 2
l10: 3
l11: 4

2.1.6 Transition Removal

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

l3: −4⋅x1 + 4⋅x6 + 3
l0: −4⋅x1 + 4⋅x6 + 2
l26: −4⋅x1 + 4⋅x6
l2: −4⋅x1 + 4⋅x6 + 1

2.1.7 Transition Removal

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

l3: 0
l0: −1
l26: 1
l2: 2

2.1.8 Trivial Cooperation Program

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

Tool configuration

AProVE