YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

4(2(4(x0)))	→	2(0(0(5(3(3(5(2(0(4(x0))))))))))
4(4(2(4(2(x0)))))	→	2(0(5(2(1(4(0(2(0(1(x0))))))))))
0(5(4(2(4(3(x0))))))	→	5(1(5(5(3(5(3(0(0(0(x0))))))))))
1(1(4(5(3(3(x0))))))	→	1(3(1(1(3(0(1(2(2(1(x0))))))))))
3(1(4(3(1(2(x0))))))	→	0(0(1(1(4(2(3(0(0(3(x0))))))))))
3(2(4(2(4(1(x0))))))	→	0(2(1(1(1(5(3(1(3(3(x0))))))))))
3(3(0(4(1(2(x0))))))	→	3(5(1(2(0(2(0(5(3(1(x0))))))))))
4(1(4(5(0(5(4(x0)))))))	→	4(1(5(3(1(0(5(3(1(0(x0))))))))))
4(4(0(5(4(2(2(x0)))))))	→	4(0(4(3(4(4(4(5(4(1(x0))))))))))
5(4(5(3(2(4(3(x0)))))))	→	2(5(5(5(0(4(5(0(1(4(x0))))))))))

Proof

1 String Reversal

Since only unary symbols occur, one can reverse all terms and obtains the TRS

4(2(4(x0)))	→	4(0(2(5(3(3(5(0(0(2(x0))))))))))
2(4(2(4(4(x0)))))	→	1(0(2(0(4(1(2(5(0(2(x0))))))))))
3(4(2(4(5(0(x0))))))	→	0(0(0(3(5(3(5(5(1(5(x0))))))))))
3(3(5(4(1(1(x0))))))	→	1(2(2(1(0(3(1(1(3(1(x0))))))))))
2(1(3(4(1(3(x0))))))	→	3(0(0(3(2(4(1(1(0(0(x0))))))))))
1(4(2(4(2(3(x0))))))	→	3(3(1(3(5(1(1(1(2(0(x0))))))))))
2(1(4(0(3(3(x0))))))	→	1(3(5(0(2(0(2(1(5(3(x0))))))))))
4(5(0(5(4(1(4(x0)))))))	→	0(1(3(5(0(1(3(5(1(4(x0))))))))))
2(2(4(5(0(4(4(x0)))))))	→	1(4(5(4(4(4(3(4(0(4(x0))))))))))
3(4(2(3(5(4(5(x0)))))))	→	4(1(0(5(4(0(5(5(5(2(x0))))))))))

1.1 Bounds

The given TRS is match-bounded by 0. This is shown by the following automaton.

final states:

{88, 79, 69, 59, 50, 40, 30, 20, 12, 1}

transitions:

50 → 71

50 → 31

59 → 3

20 → 60

1 → 70

40 → 3

79 → 3

88 → 60

12 → 3

69 → 70

30 → 60

2₀(37) → 38

2₀(41) → 51

2₀(45) → 46

2₀(64) → 65

2₀(9) → 10

2₀(62) → 63

2₀(13) → 14

2₀(2) → 3

2₀(17) → 18

2₀(38) → 39

5₀(2) → 21

5₀(25) → 26

5₀(71) → 72

5₀(4) → 13

5₀(85) → 86

5₀(8) → 9

5₀(89) → 90

5₀(60) → 61

5₀(93) → 94

5₀(23) → 24

5₀(54) → 55

5₀(90) → 91

5₀(66) → 67

5₀(3) → 89

5₀(75) → 76

5₀(5) → 6

5₀(22) → 23

0₀(65) → 66

0₀(70) → 80

0₀(41) → 42

0₀(78) → 69

0₀(91) → 92

0₀(63) → 64

0₀(35) → 36

0₀(29) → 20

0₀(18) → 19

0₀(28) → 29

0₀(3) → 4

0₀(47) → 48

0₀(94) → 95

0₀(27) → 28

0₀(74) → 75

0₀(48) → 49

0₀(10) → 11

0₀(2) → 41

0₀(4) → 5

0₀(16) → 17

3₀(58) → 50

3₀(46) → 47

3₀(26) → 27

3₀(7) → 8

3₀(6) → 7

3₀(67) → 68

3₀(49) → 40

3₀(72) → 73

3₀(31) → 32

3₀(34) → 35

3₀(81) → 82

3₀(57) → 58

3₀(24) → 25

3₀(76) → 77

3₀(55) → 56

3₀(2) → 60

1₀(70) → 71

1₀(87) → 79

1₀(77) → 78

1₀(53) → 54

1₀(68) → 59

1₀(21) → 22

1₀(95) → 96

1₀(19) → 12

1₀(73) → 74

1₀(32) → 33

1₀(61) → 62

1₀(42) → 43

1₀(14) → 15

1₀(43) → 44

1₀(2) → 31

1₀(36) → 37

1₀(52) → 53

1₀(56) → 57

1₀(33) → 34

1₀(39) → 30

1₀(51) → 52

f6₀ → 2

4₀(2) → 70

4₀(80) → 81

4₀(92) → 93

4₀(96) → 88

4₀(11) → 1

4₀(84) → 85

4₀(86) → 87

4₀(83) → 84

4₀(15) → 16

4₀(82) → 83

4₀(44) → 45

50	→	71
50	→	31
59	→	3
20	→	60
1	→	70
40	→	3
79	→	3
88	→	60
12	→	3
69	→	70
30	→	60
2₀(37)	→	38
2₀(41)	→	51
2₀(45)	→	46
2₀(64)	→	65
2₀(9)	→	10
2₀(62)	→	63
2₀(13)	→	14
2₀(2)	→	3
2₀(17)	→	18
2₀(38)	→	39
5₀(2)	→	21
5₀(25)	→	26
5₀(71)	→	72
5₀(4)	→	13
5₀(85)	→	86
5₀(8)	→	9
5₀(89)	→	90
5₀(60)	→	61
5₀(93)	→	94
5₀(23)	→	24
5₀(54)	→	55
5₀(90)	→	91
5₀(66)	→	67
5₀(3)	→	89
5₀(75)	→	76
5₀(5)	→	6
5₀(22)	→	23
0₀(65)	→	66
0₀(70)	→	80
0₀(41)	→	42
0₀(78)	→	69
0₀(91)	→	92
0₀(63)	→	64
0₀(35)	→	36
0₀(29)	→	20
0₀(18)	→	19
0₀(28)	→	29
0₀(3)	→	4
0₀(47)	→	48
0₀(94)	→	95
0₀(27)	→	28
0₀(74)	→	75
0₀(48)	→	49
0₀(10)	→	11
0₀(2)	→	41
0₀(4)	→	5
0₀(16)	→	17
3₀(58)	→	50
3₀(46)	→	47
3₀(26)	→	27
3₀(7)	→	8
3₀(6)	→	7
3₀(67)	→	68
3₀(49)	→	40
3₀(72)	→	73
3₀(31)	→	32
3₀(34)	→	35
3₀(81)	→	82
3₀(57)	→	58
3₀(24)	→	25
3₀(76)	→	77
3₀(55)	→	56
3₀(2)	→	60
1₀(70)	→	71
1₀(87)	→	79
1₀(77)	→	78
1₀(53)	→	54
1₀(68)	→	59
1₀(21)	→	22
1₀(95)	→	96
1₀(19)	→	12
1₀(73)	→	74
1₀(32)	→	33
1₀(61)	→	62
1₀(42)	→	43
1₀(14)	→	15
1₀(43)	→	44
1₀(2)	→	31
1₀(36)	→	37
1₀(52)	→	53
1₀(56)	→	57
1₀(33)	→	34
1₀(39)	→	30
1₀(51)	→	52
f6₀	→	2
4₀(2)	→	70
4₀(80)	→	81
4₀(92)	→	93
4₀(96)	→	88
4₀(11)	→	1
4₀(84)	→	85
4₀(86)	→	87
4₀(83)	→	84
4₀(15)	→	16
4₀(82)	→	83
4₀(44)	→	45