LTS Termination Proof

by AProVE

Input

Integer Transition System

Proof

1 Switch to Cooperation Termination Proof

We consider the following cutpoint-transitions:
l5 l5 l5: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l22 l22 l22: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l13 l13 l13: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l18 l18 l18: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l17 l17 l17: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l21 l21 l21: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l14 l14 l14: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l9 l9 l9: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l25 l25 l25: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l6 l6 l6: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l8 l8 l8: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l27 l27 l27: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l0 l0 l0: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l12 l12 l12: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l19 l19 l19: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l26 l26 l26: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l7 l7 l7: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l24 l24 l24: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l11 l11 l11: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l3 l3 l3: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l20 l20 l20: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l28 l28 l28: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l2 l2 l2: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l23 l23 l23: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l4 l4 l4: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l10 l10 l10: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l29 l29 l29: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l16 l16 l16: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l15 l15 l15: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
l30 l30 l30: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13
and for every transition t, a duplicate t is considered.

2 SCC Decomposition

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

2.1 SCC Subproblem 1/4

Here we consider the SCC { l7, l6 }.

2.1.1 Transition Removal

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

l6: −1 + x6x7
l7: −1 + x6x7

2.1.2 Transition Removal

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

l6: 0
l7: −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/4

Here we consider the SCC { l25, l27, l15, l28, l26, l14 }.

2.2.1 Transition Removal

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

l14: −1 + x6x7
l15: −1 + x6x7
l25: −2 + x6x7
l28: −2 + x6x7
l27: −2 + x6x7
l26: −2 + x6x7

2.2.2 Transition Removal

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

l14: 0
l15: −1
l25: 1
l28: 4
l27: 3
l26: 2

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

Here we consider the SCC { l23, l22, l24, l20, l18, l17, l19, l21 }.

2.3.1 Transition Removal

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

l19: −1 + x6x7
l20: −1 + x6x7
l24: −2 + x6x7
l18: −2 + x6x7
l17: −2 + x6x7
l23: −2 + x6x7
l22: −2 + x6x7
l21: −2 + x6x7

2.3.2 Transition Removal

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

l19: −2
l20: −2
l24: 0
l18: 0
l17: 0
l23: 0
l22: 0
l21: 0

2.3.3 Transition Removal

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

l19: 1
l20: 0
l18: −1 + 2⋅x1 + 3⋅x3 + 4⋅x4 + 5⋅x5 + x6 + 6⋅x7 − 2⋅x8 + 7⋅x9 + 8⋅x10 + 9⋅x12 + 10⋅x13
l24: −3 + 2⋅x1 + 3⋅x3 + 4⋅x4 + 5⋅x5 + x6 + 6⋅x7 − 2⋅x8 + 7⋅x9 + 8⋅x10 + 9⋅x12 + 10⋅x13
l17: −3 + 2⋅x1 + 3⋅x3 + 4⋅x4 + 5⋅x5 + x6 + 6⋅x7 − 2⋅x8 + 7⋅x9 + 8⋅x10 + 9⋅x12 + 10⋅x13
l23: −3 + 2⋅x1 + 3⋅x3 + 4⋅x4 + 5⋅x5 + x6 + 6⋅x7 − 2⋅x8 + 7⋅x9 + 8⋅x10 + 9⋅x12 + 10⋅x13
l22: −3 + 2⋅x1 + 3⋅x3 + 4⋅x4 + 5⋅x5 + x6 + 6⋅x7 − 2⋅x8 + 7⋅x9 + 8⋅x10 + 9⋅x12 + 10⋅x13
l21: −3 + 2⋅x1 + 3⋅x3 + 4⋅x4 + 5⋅x5 + x6 + 6⋅x7 − 2⋅x8 + 7⋅x9 + 8⋅x10 + 9⋅x12 + 10⋅x13

2.3.4 Transition Removal

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

l18: −1 + x6x8
l24: −1 + x6x8
l17: −2 + x6x8
l23: −2 + x6x8
l22: −2 + x6x8
l21: −2 + x6x8

2.3.5 Transition Removal

We remove transitions 38, 26, 31, 30, 28, 29, 33, 32 using the following ranking functions, which are bounded by 0.

l18: 0
l24: −1
l17: 1
l23: 4
l22: 3
l21: 2

2.3.6 Trivial Cooperation Program

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

2.4 SCC Subproblem 4/4

Here we consider the SCC { l10, l11, l8, l13, l16, l12, l9 }.

2.4.1 Transition Removal

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

l9: −1 + x6x7
l16: −1 + x6x7
l8: −2 + x6x7
l13: −2 + x6x7
l12: −2 + x6x7
l11: −2 + x6x7
l10: −2 + x6x7

2.4.2 Transition Removal

We remove transitions 47, 13, 20, 18, 15, 14, 17, 16, 19, 22, 21 using the following ranking functions, which are bounded by 0.

l9: 0
l16: −1
l8: 1
l13: 5
l12: 4
l11: 3
l10: 2

2.4.3 Trivial Cooperation Program

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

Tool configuration

AProVE