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 = x3
l7 l7 l7: x1 = x1x2 = x2x3 = x3
l1 l1 l1: x1 = x1x2 = x2x3 = x3
l3 l3 l3: x1 = x1x2 = x2x3 = x3
l13 l13 l13: x1 = x1x2 = x2x3 = x3
l18 l18 l18: x1 = x1x2 = x2x3 = x3
l17 l17 l17: x1 = x1x2 = x2x3 = x3
l2 l2 l2: x1 = x1x2 = x2x3 = x3
l9 l9 l9: x1 = x1x2 = x2x3 = x3
l14 l14 l14: x1 = x1x2 = x2x3 = x3
l4 l4 l4: x1 = x1x2 = x2x3 = x3
l6 l6 l6: x1 = x1x2 = x2x3 = x3
l10 l10 l10: x1 = x1x2 = x2x3 = x3
l8 l8 l8: x1 = x1x2 = x2x3 = x3
l15 l15 l15: x1 = x1x2 = x2x3 = x3
l16 l16 l16: x1 = x1x2 = x2x3 = x3
l0 l0 l0: x1 = x1x2 = x2x3 = x3
l12 l12 l12: x1 = x1x2 = x2x3 = x3
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: x2
l2: −1 − x2
l6: x2
l12: −1 − x2
l14: −1 − x2
l15: −1 − x2
l13: −1 − x2
l16: −1 − x2

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 −6.

l6: −6
l0: −7
l12: −5
l2: 0
l14: −4
l15: −2
l13: −3
l16: −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 { 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: x2
l10: x2
l3: −1 − x2
l9: −1 − x2
l5: −1 − x2
l7: −1 − x2
l4: −1 − x2
l8: −1 − x2

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