YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 Bounds

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

final states:

{141, 132, 123, 114, 105, 96, 86, 76, 68, 60, 51, 41, 31, 22, 12, 1}

transitions:

51 → 13

96 → 13

41 → 77

31 → 77

1 → 77

123 → 78

123 → 3

60 → 87

76 → 78

76 → 3

86 → 106

86 → 13

141 → 124

141 → 32

22 → 13

105 → 77

114 → 87

12 → 13

68 → 14

68 → 3

132 → 125

132 → 3

f6₀ → 2

1₀(138) → 139

1₀(128) → 129

1₀(139) → 140

1₀(46) → 47

1₀(50) → 41

1₀(133) → 134

1₀(84) → 85

1₀(38) → 39

1₀(63) → 64

1₀(49) → 50

1₀(148) → 149

1₀(2) → 77

1₀(45) → 46

1₀(44) → 45

1₀(101) → 102

1₀(13) → 23

1₀(39) → 40

1₀(25) → 26

5₀(126) → 127

5₀(23) → 24

5₀(78) → 79

5₀(91) → 92

5₀(30) → 22

5₀(7) → 8

5₀(136) → 137

5₀(35) → 36

5₀(112) → 113

5₀(125) → 126

5₀(32) → 115

5₀(107) → 108

5₀(79) → 80

5₀(77) → 124

5₀(110) → 111

5₀(149) → 141

5₀(131) → 123

5₀(18) → 19

5₀(3) → 4

5₀(69) → 70

5₀(146) → 147

5₀(80) → 81

5₀(61) → 62

5₀(15) → 16

5₀(21) → 12

5₀(10) → 11

5₀(2) → 32

2₀(74) → 75

2₀(130) → 131

2₀(37) → 38

2₀(129) → 130

2₀(98) → 99

2₀(48) → 49

2₀(8) → 9

2₀(108) → 109

2₀(142) → 143

2₀(64) → 65

2₀(119) → 120

2₀(75) → 68

2₀(42) → 43

2₀(55) → 56

2₀(13) → 97

2₀(5) → 6

2₀(117) → 118

2₀(2) → 42

2₀(100) → 101

0₀(72) → 73

0₀(111) → 112

0₀(2) → 13

0₀(95) → 86

0₀(6) → 7

0₀(71) → 72

0₀(16) → 17

0₀(32) → 33

0₀(24) → 25

0₀(34) → 35

0₀(77) → 106

0₀(83) → 84

0₀(70) → 71

0₀(47) → 48

0₀(89) → 90

0₀(106) → 107

0₀(92) → 93

0₀(93) → 94

0₀(27) → 28

0₀(56) → 57

0₀(134) → 135

0₀(13) → 52

0₀(62) → 63

0₀(90) → 91

0₀(66) → 67

0₀(53) → 54

0₀(3) → 133

0₀(52) → 69

0₀(43) → 44

0₀(127) → 128

0₀(104) → 96

0₀(65) → 66

3₀(2) → 87

3₀(9) → 10

3₀(54) → 55

3₀(67) → 60

3₀(99) → 100

3₀(19) → 20

3₀(113) → 105

3₀(36) → 37

3₀(4) → 61

3₀(26) → 27

3₀(17) → 18

3₀(11) → 1

3₀(135) → 136

3₀(118) → 119

3₀(94) → 95

3₀(81) → 82

3₀(52) → 53

3₀(42) → 142

3₀(82) → 83

3₀(120) → 121

3₀(73) → 74

3₀(57) → 58

3₀(97) → 98

3₀(109) → 110

3₀(145) → 146

3₀(122) → 114

3₀(102) → 103

4₀(87) → 88

4₀(29) → 30

4₀(140) → 132

4₀(143) → 144

4₀(58) → 59

4₀(88) → 89

4₀(124) → 125

4₀(59) → 51

4₀(4) → 5

4₀(28) → 29

4₀(13) → 14

4₀(147) → 148

4₀(20) → 21

4₀(116) → 117

4₀(14) → 15

4₀(40) → 31

4₀(103) → 104

4₀(137) → 138

4₀(121) → 122

4₀(144) → 145

4₀(85) → 76

4₀(77) → 78

4₀(33) → 34

4₀(115) → 116

4₀(2) → 3

51	→	13
96	→	13
41	→	77
31	→	77
1	→	77
123	→	78
123	→	3
60	→	87
76	→	78
76	→	3
86	→	106
86	→	13
141	→	124
141	→	32
22	→	13
105	→	77
114	→	87
12	→	13
68	→	14
68	→	3
132	→	125
132	→	3
f6₀	→	2
1₀(138)	→	139
1₀(128)	→	129
1₀(139)	→	140
1₀(46)	→	47
1₀(50)	→	41
1₀(133)	→	134
1₀(84)	→	85
1₀(38)	→	39
1₀(63)	→	64
1₀(49)	→	50
1₀(148)	→	149
1₀(2)	→	77
1₀(45)	→	46
1₀(44)	→	45
1₀(101)	→	102
1₀(13)	→	23
1₀(39)	→	40
1₀(25)	→	26
5₀(126)	→	127
5₀(23)	→	24
5₀(78)	→	79
5₀(91)	→	92
5₀(30)	→	22
5₀(7)	→	8
5₀(136)	→	137
5₀(35)	→	36
5₀(112)	→	113
5₀(125)	→	126
5₀(32)	→	115
5₀(107)	→	108
5₀(79)	→	80
5₀(77)	→	124
5₀(110)	→	111
5₀(149)	→	141
5₀(131)	→	123
5₀(18)	→	19
5₀(3)	→	4
5₀(69)	→	70
5₀(146)	→	147
5₀(80)	→	81
5₀(61)	→	62
5₀(15)	→	16
5₀(21)	→	12
5₀(10)	→	11
5₀(2)	→	32
2₀(74)	→	75
2₀(130)	→	131
2₀(37)	→	38
2₀(129)	→	130
2₀(98)	→	99
2₀(48)	→	49
2₀(8)	→	9
2₀(108)	→	109
2₀(142)	→	143
2₀(64)	→	65
2₀(119)	→	120
2₀(75)	→	68
2₀(42)	→	43
2₀(55)	→	56
2₀(13)	→	97
2₀(5)	→	6
2₀(117)	→	118
2₀(2)	→	42
2₀(100)	→	101
0₀(72)	→	73
0₀(111)	→	112
0₀(2)	→	13
0₀(95)	→	86
0₀(6)	→	7
0₀(71)	→	72
0₀(16)	→	17
0₀(32)	→	33
0₀(24)	→	25
0₀(34)	→	35
0₀(77)	→	106
0₀(83)	→	84
0₀(70)	→	71
0₀(47)	→	48
0₀(89)	→	90
0₀(106)	→	107
0₀(92)	→	93
0₀(93)	→	94
0₀(27)	→	28
0₀(56)	→	57
0₀(134)	→	135
0₀(13)	→	52
0₀(62)	→	63
0₀(90)	→	91
0₀(66)	→	67
0₀(53)	→	54
0₀(3)	→	133
0₀(52)	→	69
0₀(43)	→	44
0₀(127)	→	128
0₀(104)	→	96
0₀(65)	→	66
3₀(2)	→	87
3₀(9)	→	10
3₀(54)	→	55
3₀(67)	→	60
3₀(99)	→	100
3₀(19)	→	20
3₀(113)	→	105
3₀(36)	→	37
3₀(4)	→	61
3₀(26)	→	27
3₀(17)	→	18
3₀(11)	→	1
3₀(135)	→	136
3₀(118)	→	119
3₀(94)	→	95
3₀(81)	→	82
3₀(52)	→	53
3₀(42)	→	142
3₀(82)	→	83
3₀(120)	→	121
3₀(73)	→	74
3₀(57)	→	58
3₀(97)	→	98
3₀(109)	→	110
3₀(145)	→	146
3₀(122)	→	114
3₀(102)	→	103
4₀(87)	→	88
4₀(29)	→	30
4₀(140)	→	132
4₀(143)	→	144
4₀(58)	→	59
4₀(88)	→	89
4₀(124)	→	125
4₀(59)	→	51
4₀(4)	→	5
4₀(28)	→	29
4₀(13)	→	14
4₀(147)	→	148
4₀(20)	→	21
4₀(116)	→	117
4₀(14)	→	15
4₀(40)	→	31
4₀(103)	→	104
4₀(137)	→	138
4₀(121)	→	122
4₀(144)	→	145
4₀(85)	→	76
4₀(77)	→	78
4₀(33)	→	34
4₀(115)	→	116
4₀(2)	→	3