Certification Problem

Input (TPDB SRS_Standard/Waldmann_06_SRS/e)

The rewrite relation of the following TRS is considered.

2(7(x1)) → 1(8(x1)) (1)
2(8(1(x1))) → 8(x1) (2)
2(8(x1)) → 4(x1) (3)
5(9(x1)) → 0(x1) (4)
4(x1) → 5(2(3(x1))) (5)
5(3(x1)) → 6(0(x1)) (6)
2(8(x1)) → 7(x1) (7)
4(7(x1)) → 1(3(x1)) (8)
5(2(6(x1))) → 6(2(4(x1))) (9)
9(7(x1)) → 7(5(x1)) (10)
7(2(x1)) → 4(x1) (11)
7(0(x1)) → 9(3(x1)) (12)
6(9(x1)) → 9(x1) (13)
9(5(9(x1))) → 5(7(x1)) (14)
4(x1) → 9(6(6(x1))) (15)
9(x1) → 6(7(x1)) (16)
6(2(x1)) → 7(7(x1)) (17)
2(4(x1)) → 0(7(x1)) (18)
6(6(x1)) → 3(x1) (19)
0(3(x1)) → 5(3(x1)) (20)

Property / Task

Prove or disprove termination.

Answer / Result

Yes.

Proof (by AProVE @ termCOMP 2023)

1 Dependency Pair Transformation

The following set of initial dependency pairs has been identified.
2#(8(x1)) → 4#(x1) (21)
5#(9(x1)) → 0#(x1) (22)
4#(x1) → 5#(2(3(x1))) (23)
4#(x1) → 2#(3(x1)) (24)
5#(3(x1)) → 6#(0(x1)) (25)
5#(3(x1)) → 0#(x1) (26)
2#(8(x1)) → 7#(x1) (27)
5#(2(6(x1))) → 6#(2(4(x1))) (28)
5#(2(6(x1))) → 2#(4(x1)) (29)
5#(2(6(x1))) → 4#(x1) (30)
9#(7(x1)) → 7#(5(x1)) (31)
9#(7(x1)) → 5#(x1) (32)
7#(2(x1)) → 4#(x1) (33)
7#(0(x1)) → 9#(3(x1)) (34)
9#(5(9(x1))) → 5#(7(x1)) (35)
9#(5(9(x1))) → 7#(x1) (36)
4#(x1) → 9#(6(6(x1))) (37)
4#(x1) → 6#(6(x1)) (38)
4#(x1) → 6#(x1) (39)
9#(x1) → 6#(7(x1)) (40)
9#(x1) → 7#(x1) (41)
6#(2(x1)) → 7#(7(x1)) (42)
6#(2(x1)) → 7#(x1) (43)
2#(4(x1)) → 0#(7(x1)) (44)
2#(4(x1)) → 7#(x1) (45)
0#(3(x1)) → 5#(3(x1)) (46)

1.1 Dependency Graph Processor

The dependency pairs are split into 2 components.