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 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18x19 = x19x20 = x20x21 = x21x22 = x22x23 = x23x24 = x24x25 = x25x26 = x26x27 = x27x28 = x28x29 = x29x30 = x30x31 = x31x32 = x32x33 = x33
l7 l7 l7: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18x19 = x19x20 = x20x21 = x21x22 = x22x23 = x23x24 = x24x25 = x25x26 = x26x27 = x27x28 = x28x29 = x29x30 = x30x31 = x31x32 = x32x33 = x33
l11 l11 l11: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18x19 = x19x20 = x20x21 = x21x22 = x22x23 = x23x24 = x24x25 = x25x26 = x26x27 = x27x28 = x28x29 = x29x30 = x30x31 = x31x32 = x32x33 = x33
l1 l1 l1: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18x19 = x19x20 = x20x21 = x21x22 = x22x23 = x23x24 = x24x25 = x25x26 = x26x27 = x27x28 = x28x29 = x29x30 = x30x31 = x31x32 = x32x33 = x33
l3 l3 l3: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18x19 = x19x20 = x20x21 = x21x22 = x22x23 = x23x24 = x24x25 = x25x26 = x26x27 = x27x28 = x28x29 = x29x30 = x30x31 = x31x32 = x32x33 = x33
l13 l13 l13: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18x19 = x19x20 = x20x21 = x21x22 = x22x23 = x23x24 = x24x25 = x25x26 = x26x27 = x27x28 = x28x29 = x29x30 = x30x31 = x31x32 = x32x33 = x33
l20 l20 l20: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18x19 = x19x20 = x20x21 = x21x22 = x22x23 = x23x24 = x24x25 = x25x26 = x26x27 = x27x28 = x28x29 = x29x30 = x30x31 = x31x32 = x32x33 = x33
l17 l17 l17: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18x19 = x19x20 = x20x21 = x21x22 = x22x23 = x23x24 = x24x25 = x25x26 = x26x27 = x27x28 = x28x29 = x29x30 = x30x31 = x31x32 = x32x33 = x33
l2 l2 l2: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18x19 = x19x20 = x20x21 = x21x22 = x22x23 = x23x24 = x24x25 = x25x26 = x26x27 = x27x28 = x28x29 = x29x30 = x30x31 = x31x32 = x32x33 = x33
l21 l21 l21: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18x19 = x19x20 = x20x21 = x21x22 = x22x23 = x23x24 = x24x25 = x25x26 = x26x27 = x27x28 = x28x29 = x29x30 = x30x31 = x31x32 = x32x33 = x33
l9 l9 l9: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18x19 = x19x20 = x20x21 = x21x22 = x22x23 = x23x24 = x24x25 = x25x26 = x26x27 = x27x28 = x28x29 = x29x30 = x30x31 = x31x32 = x32x33 = x33
l14 l14 l14: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18x19 = x19x20 = x20x21 = x21x22 = x22x23 = x23x24 = x24x25 = x25x26 = x26x27 = x27x28 = x28x29 = x29x30 = x30x31 = x31x32 = x32x33 = x33
l4 l4 l4: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18x19 = x19x20 = x20x21 = x21x22 = x22x23 = x23x24 = x24x25 = x25x26 = x26x27 = x27x28 = x28x29 = x29x30 = x30x31 = x31x32 = x32x33 = x33
l6 l6 l6: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18x19 = x19x20 = x20x21 = x21x22 = x22x23 = x23x24 = x24x25 = x25x26 = x26x27 = x27x28 = x28x29 = x29x30 = x30x31 = x31x32 = x32x33 = x33
l10 l10 l10: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18x19 = x19x20 = x20x21 = x21x22 = x22x23 = x23x24 = x24x25 = x25x26 = x26x27 = x27x28 = x28x29 = x29x30 = x30x31 = x31x32 = x32x33 = x33
l8 l8 l8: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18x19 = x19x20 = x20x21 = x21x22 = x22x23 = x23x24 = x24x25 = x25x26 = x26x27 = x27x28 = x28x29 = x29x30 = x30x31 = x31x32 = x32x33 = x33
l16 l16 l16: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18x19 = x19x20 = x20x21 = x21x22 = x22x23 = x23x24 = x24x25 = x25x26 = x26x27 = x27x28 = x28x29 = x29x30 = x30x31 = x31x32 = x32x33 = x33
l0 l0 l0: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18x19 = x19x20 = x20x21 = x21x22 = x22x23 = x23x24 = x24x25 = x25x26 = x26x27 = x27x28 = x28x29 = x29x30 = x30x31 = x31x32 = x32x33 = x33
l12 l12 l12: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18x19 = x19x20 = x20x21 = x21x22 = x22x23 = x23x24 = x24x25 = x25x26 = x26x27 = x27x28 = x28x29 = x29x30 = x30x31 = x31x32 = x32x33 = x33
l19 l19 l19: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18x19 = x19x20 = x20x21 = x21x22 = x22x23 = x23x24 = x24x25 = x25x26 = x26x27 = x27x28 = x28x29 = x29x30 = x30x31 = x31x32 = x32x33 = x33
and for every transition t, a duplicate t is considered.

2 SCC Decomposition

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

2.1 SCC Subproblem 1/2

Here we consider the SCC { l10, l0 }.

2.1.1 Transition Removal

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

l0: −2⋅x14 + 2⋅x18
l10: −2⋅x14 + 2⋅x18 + 1

2.1.2 Transition Removal

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

l10: 0
l0: −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/2

Here we consider the SCC { l1, l13, l20, l19, l12, l14 }.

2.2.1 Transition Removal

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

l1: 1 + 3⋅x6 + x16
l13: 3⋅x6 + x15
l20: 1 + 3⋅x6 + x16
l19: 1 + 3⋅x6 + x16
l12: 3⋅x6 + x15
l14: 3⋅x6 + x15

2.2.2 Transition Removal

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

l20: 0
l1: −1 + 0⋅x23
l19: 1
l14: 0
l12: −1 + 0⋅x23
l13: 1

2.2.3 Trivial Cooperation Program

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

Tool configuration

AProVE