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: 9 − x2
l2: 8 − x2
l6: 9 − x2
l12: 8 − x2
l14: 8 − x2
l15: 8 − x2
l13: 8 − x2
l16: 8 − 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 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 −70.

l1: −8⋅x2 + 3
l10: −8⋅x2 + 2
l3: −8⋅x2 − 4
l9: −8⋅x2 + 1
l5: −8⋅x2 − 3
l7: −8⋅x2 − 1
l4: −8⋅x2 − 2
l8: −8⋅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