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 = x18
l7 l7 l7: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18
l11 l11 l11: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18
l1 l1 l1: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18
l13 l13 l13: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18
l3 l3 l3: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18
l17 l17 l17: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18
l2 l2 l2: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18
l9 l9 l9: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18
l4 l4 l4: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18
l6 l6 l6: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18
l10 l10 l10: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18
l8 l8 l8: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18
l15 l15 l15: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18
l0 l0 l0: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18
l12 l12 l12: x1 = x1x2 = x2x3 = x3x4 = x4x5 = x5x6 = x6x7 = x7x8 = x8x9 = x9x10 = x10x11 = x11x12 = x12x13 = x13x14 = x14x15 = x15x16 = x16x17 = x17x18 = x18
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 { l5, l6 }.

2.1.1 Transition Removal

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

l5: 3⋅x13 − 3⋅x14 + 1
l6: 3⋅x13 − 3⋅x14 + 2

2.1.2 Transition Removal

We remove transitions 5, 6 using the following ranking functions, which are bounded by 0.

l5: 0
l6: x4x14

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 { l10, l11, l8, l1, l13, l0, l12, l2, l9 }.

2.2.1 Transition Removal

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

l0: 6⋅x13 − 6⋅x15 + 5
l1: 6⋅x13 − 6⋅x15 + 4
l2: 6⋅x13 − 6⋅x15 + 6
l8: 6⋅x13 − 6⋅x15 + 1
l12: 6⋅x13 − 6⋅x15 + 2
l10: 6⋅x13 − 6⋅x15 + 4
l13: 6⋅x13 − 6⋅x15 + 4
l11: 6⋅x13 − 6⋅x15 + 4
l9: 6⋅x13 − 6⋅x15 + 4

2.2.2 Transition Removal

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

l0: 0
l1: −1 + x15x16
l8: −1 + x15x16
l2: 2⋅x5x6x15
l12: −1 + x15x16
l10: −2 + x15x16
l13: −2 + x15x16
l11: −2 + x15x16
l9: −2 + x15x16

2.2.3 Transition Removal

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

l8: 0
l2: x5x15
l12: 1
l1: 2
l10: 2
l13: 2
l11: 2
l9: 2

2.2.4 Transition Removal

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

l10: 5⋅x13 − 5⋅x16 − 2
l1: 5⋅x13 − 5⋅x16 + 2
l13: 5⋅x13 − 5⋅x16 + 1
l11: 5⋅x13 − 5⋅x16
l9: 5⋅x13 − 5⋅x16 − 1

2.2.5 Transition Removal

We remove transitions 12, 18, 13, 11, 14, 19 using the following ranking functions, which are bounded by 0.

l10: 0
l1: x6x16
l13: 3
l11: 2
l9: 1

2.2.6 Trivial Cooperation Program

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

Tool configuration

AProVE