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 = x4
l7 l7 l7: x1 = x1x2 = x2x3 = x3x4 = x4
l1 l1 l1: x1 = x1x2 = x2x3 = x3x4 = x4
l3 l3 l3: x1 = x1x2 = x2x3 = x3x4 = x4
l13 l13 l13: x1 = x1x2 = x2x3 = x3x4 = x4
l18 l18 l18: x1 = x1x2 = x2x3 = x3x4 = x4
l17 l17 l17: x1 = x1x2 = x2x3 = x3x4 = x4
l2 l2 l2: x1 = x1x2 = x2x3 = x3x4 = x4
l9 l9 l9: x1 = x1x2 = x2x3 = x3x4 = x4
l14 l14 l14: x1 = x1x2 = x2x3 = x3x4 = x4
l4 l4 l4: x1 = x1x2 = x2x3 = x3x4 = x4
l6 l6 l6: x1 = x1x2 = x2x3 = x3x4 = x4
l10 l10 l10: x1 = x1x2 = x2x3 = x3x4 = x4
l8 l8 l8: x1 = x1x2 = x2x3 = x3x4 = x4
l15 l15 l15: x1 = x1x2 = x2x3 = x3x4 = x4
l16 l16 l16: x1 = x1x2 = x2x3 = x3x4 = x4
l0 l0 l0: x1 = x1x2 = x2x3 = x3x4 = x4
l12 l12 l12: x1 = x1x2 = x2x3 = x3x4 = x4
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 { l6, l13, l15, l16, l0, l12, l2, l14 }.

2.1.1 Transition Removal

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

l0: −1 + x1x3
l2: −2 + x1x3
l6: −1 + x1x3
l12: −2 + x1x3
l14: −2 + x1x3
l15: −2 + x1x3
l13: −2 + x1x3
l16: −2 + x1x3

2.1.2 Transition Removal

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

l6: 0
l0: −1
l12: 1
l2: 6
l14: 2
l15: 4
l13: 3
l16: 5

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 { l5, l4, l7, l10, l1, l8, l3, l9 }.

2.2.1 Transition Removal

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

l1: 8⋅x1 − 8⋅x3 + 3
l10: 8⋅x1 − 8⋅x3 + 2
l3: 8⋅x1 − 8⋅x3 − 4
l9: 8⋅x1 − 8⋅x3 + 1
l5: 8⋅x1 − 8⋅x3 − 3
l7: 8⋅x1 − 8⋅x3 − 1
l4: 8⋅x1 − 8⋅x3 − 2
l8: 8⋅x1 − 8⋅x3

2.2.2 Transition Removal

We remove transitions 15, 3, 11, 5, 8, 4, 7, 9, 10 using the following ranking functions, which are bounded by 0.

l1: 0
l10: −1
l3: 1
l9: 6
l5: 2
l7: 4
l4: 3
l8: 5

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