YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 String Reversal

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

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

1.1 Bounds

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

final states:

{201, 197, 193, 191, 186, 182, 177, 172, 169, 164, 160, 158, 157, 153, 150, 145, 140, 135, 131, 125, 122, 119, 116, 112, 109, 105, 100, 96, 93, 90, 86, 81, 77, 72, 68, 64, 61, 58, 55, 50, 48, 43, 38, 32, 26, 21, 18, 12, 7, 1}

transitions:

157 → 33

61 → 35

61 → 178

61 → 27

32 → 178

32 → 27

81 → 3

96 → 165

96 → 3

129 → 231

129 → 233

119 → 3

145 → 3

122 → 165

122 → 3

18 → 178

18 → 27

50 → 141

50 → 3

55 → 141

55 → 3

90 → 179

90 → 141

90 → 3

193 → 3

1 → 3

197 → 165

197 → 3

135 → 178

135 → 27

26 → 178

26 → 27

125 → 73

125 → 33

38 → 33

86 → 3

58 → 35

58 → 178

58 → 27

201 → 165

201 → 3

177 → 133

177 → 165

177 → 3

21 → 178

21 → 27

186 → 165

186 → 3

72 → 33

150 → 27

172 → 3

116 → 3

153 → 3

109 → 3

105 → 179

105 → 141

105 → 3

232 → 206

66 → 205

66 → 223

93 → 179

93 → 141

93 → 3

12 → 3

112 → 3

169 → 141

169 → 3

77 → 3

140 → 141

140 → 3

100 → 179

100 → 141

100 → 3

7 → 3

234 → 224

182 → 3

64 → 33

158 → 178

158 → 27

48 → 141

48 → 3

160 → 3

164 → 178

164 → 27

68 → 33

131 → 33

43 → 33

210 → 35

191 → 141

191 → 3

228 → 35

3₁(226) → 227

3₁(208) → 209

5₁(223) → 224

5₁(209) → 210

5₁(233) → 234

3₀(51) → 52

3₀(35) → 36

3₀(173) → 194

3₀(73) → 74

3₀(3) → 4

3₀(33) → 44

3₀(91) → 151

3₀(24) → 25

3₀(123) → 124

3₀(143) → 144

3₀(9) → 87

3₀(59) → 60

3₀(83) → 117

3₀(198) → 199

3₀(179) → 180

3₀(27) → 28

3₀(136) → 137

3₀(62) → 63

3₀(15) → 16

3₀(39) → 40

3₀(161) → 162

3₀(126) → 127

3₀(13) → 101

3₀(28) → 106

3₀(2) → 8

3₀(176) → 172

3₀(188) → 189

2₀(2) → 3

2₀(132) → 133

2₀(175) → 176

2₀(120) → 121

2₀(113) → 114

2₀(51) → 91

2₀(110) → 111

2₀(147) → 148

2₀(88) → 89

2₀(202) → 203

2₀(98) → 99

2₀(87) → 88

2₀(80) → 77

2₀(83) → 84

2₀(185) → 182

2₀(47) → 43

2₀(91) → 92

2₀(187) → 198

2₀(203) → 204

2₀(11) → 7

2₀(108) → 105

2₀(9) → 154

2₀(99) → 96

2₀(181) → 177

2₀(14) → 15

2₀(27) → 141

2₀(163) → 160

2₀(13) → 78

2₀(57) → 55

2₀(170) → 192

2₀(84) → 85

2₀(39) → 65

2₀(204) → 201

2₀(53) → 54

2₀(178) → 179

2₀(33) → 165

2₀(94) → 95

2₀(104) → 100

2₀(171) → 169

2₀(149) → 145

2₀(196) → 193

1₀(106) → 107

1₀(151) → 152

1₀(126) → 146

1₀(170) → 171

1₀(78) → 97

1₀(91) → 94

1₀(183) → 184

1₀(166) → 167

1₀(85) → 81

1₀(173) → 174

1₀(8) → 9

1₀(95) → 93

1₀(79) → 80

1₀(194) → 195

1₀(92) → 90

1₀(36) → 37

1₀(29) → 56

1₀(28) → 29

1₀(3) → 173

1₀(40) → 41

1₀(121) → 119

1₀(111) → 109

1₀(25) → 21

1₀(101) → 113

1₀(192) → 191

1₀(102) → 103

1₀(15) → 110

1₀(117) → 118

1₀(133) → 134

1₀(103) → 104

1₀(17) → 12

1₀(2) → 126

1₀(141) → 142

1₀(4) → 5

1₀(44) → 45

1₀(16) → 17

1₀(52) → 53

1₀(190) → 186

4₀(101) → 102

4₀(8) → 22

4₀(78) → 79

4₀(5) → 49

4₀(63) → 61

4₀(94) → 159

4₀(152) → 150

4₀(69) → 70

4₀(54) → 50

4₀(13) → 178

4₀(148) → 149

4₀(155) → 156

4₀(156) → 153

4₀(9) → 19

4₀(165) → 166

4₀(74) → 75

4₀(137) → 138

4₀(34) → 35

4₀(138) → 139

4₀(144) → 140

4₀(199) → 200

4₀(115) → 112

4₀(2) → 27

5₀(180) → 181

5₀(60) → 58

5₀(189) → 190

5₀(200) → 197

5₀(97) → 98

5₀(130) → 125

5₀(127) → 128

5₀(162) → 163

5₀(2) → 33

5₀(3) → 82

5₀(30) → 31

5₀(124) → 122

5₀(44) → 69

5₀(8) → 39

5₀(52) → 170

5₀(101) → 183

5₀(33) → 73

5₀(15) → 120

5₀(67) → 64

5₀(51) → 132

f6₀ → 2

0₀(2) → 13

0₀(167) → 168

0₀(51) → 59

0₀(114) → 115

0₀(46) → 47

0₀(56) → 57

0₀(9) → 10

0₀(65) → 66

0₀(128) → 129

0₀(134) → 131

0₀(10) → 11

0₀(184) → 185

0₀(49) → 48

0₀(146) → 147

0₀(19) → 20

0₀(71) → 68

0₀(107) → 108

0₀(159) → 158

0₀(37) → 32

0₀(76) → 72

0₀(89) → 86

0₀(3) → 187

0₀(6) → 1

0₀(118) → 116

0₀(141) → 161

0₀(66) → 67

0₀(70) → 71

0₀(23) → 24

0₀(139) → 135

0₀(29) → 30

0₀(33) → 34

0₀(27) → 51

0₀(195) → 196

0₀(45) → 46

0₀(129) → 130

0₀(22) → 23

0₀(42) → 38

0₀(75) → 76

0₀(20) → 18

0₀(82) → 83

0₀(126) → 136

0₀(174) → 175

0₀(97) → 123

0₀(154) → 155

0₀(142) → 143

0₀(41) → 42

0₀(34) → 62

0₀(44) → 202

0₀(187) → 188

0₀(31) → 26

0₀(5) → 6

0₀(13) → 14

0₀(47) → 157

0₀(168) → 164

0₁(225) → 226

0₁(207) → 208

0₁(206) → 207

0₁(224) → 225

4₁(205) → 206

4₁(227) → 228

4₁(231) → 232

157	→	33
61	→	35
61	→	178
61	→	27
32	→	178
32	→	27
81	→	3
96	→	165
96	→	3
129	→	231
129	→	233
119	→	3
145	→	3
122	→	165
122	→	3
18	→	178
18	→	27
50	→	141
50	→	3
55	→	141
55	→	3
90	→	179
90	→	141
90	→	3
193	→	3
1	→	3
197	→	165
197	→	3
135	→	178
135	→	27
26	→	178
26	→	27
125	→	73
125	→	33
38	→	33
86	→	3
58	→	35
58	→	178
58	→	27
201	→	165
201	→	3
177	→	133
177	→	165
177	→	3
21	→	178
21	→	27
186	→	165
186	→	3
72	→	33
150	→	27
172	→	3
116	→	3
153	→	3
109	→	3
105	→	179
105	→	141
105	→	3
232	→	206
66	→	205
66	→	223
93	→	179
93	→	141
93	→	3
12	→	3
112	→	3
169	→	141
169	→	3
77	→	3
140	→	141
140	→	3
100	→	179
100	→	141
100	→	3
7	→	3
234	→	224
182	→	3
64	→	33
158	→	178
158	→	27
48	→	141
48	→	3
160	→	3
164	→	178
164	→	27
68	→	33
131	→	33
43	→	33
210	→	35
191	→	141
191	→	3
228	→	35
3₁(226)	→	227
3₁(208)	→	209
5₁(223)	→	224
5₁(209)	→	210
5₁(233)	→	234
3₀(51)	→	52
3₀(35)	→	36
3₀(173)	→	194
3₀(73)	→	74
3₀(3)	→	4
3₀(33)	→	44
3₀(91)	→	151
3₀(24)	→	25
3₀(123)	→	124
3₀(143)	→	144
3₀(9)	→	87
3₀(59)	→	60
3₀(83)	→	117
3₀(198)	→	199
3₀(179)	→	180
3₀(27)	→	28
3₀(136)	→	137
3₀(62)	→	63
3₀(15)	→	16
3₀(39)	→	40
3₀(161)	→	162
3₀(126)	→	127
3₀(13)	→	101
3₀(28)	→	106
3₀(2)	→	8
3₀(176)	→	172
3₀(188)	→	189
2₀(2)	→	3
2₀(132)	→	133
2₀(175)	→	176
2₀(120)	→	121
2₀(113)	→	114
2₀(51)	→	91
2₀(110)	→	111
2₀(147)	→	148
2₀(88)	→	89
2₀(202)	→	203
2₀(98)	→	99
2₀(87)	→	88
2₀(80)	→	77
2₀(83)	→	84
2₀(185)	→	182
2₀(47)	→	43
2₀(91)	→	92
2₀(187)	→	198
2₀(203)	→	204
2₀(11)	→	7
2₀(108)	→	105
2₀(9)	→	154
2₀(99)	→	96
2₀(181)	→	177
2₀(14)	→	15
2₀(27)	→	141
2₀(163)	→	160
2₀(13)	→	78
2₀(57)	→	55
2₀(170)	→	192
2₀(84)	→	85
2₀(39)	→	65
2₀(204)	→	201
2₀(53)	→	54
2₀(178)	→	179
2₀(33)	→	165
2₀(94)	→	95
2₀(104)	→	100
2₀(171)	→	169
2₀(149)	→	145
2₀(196)	→	193
1₀(106)	→	107
1₀(151)	→	152
1₀(126)	→	146
1₀(170)	→	171
1₀(78)	→	97
1₀(91)	→	94
1₀(183)	→	184
1₀(166)	→	167
1₀(85)	→	81
1₀(173)	→	174
1₀(8)	→	9
1₀(95)	→	93
1₀(79)	→	80
1₀(194)	→	195
1₀(92)	→	90
1₀(36)	→	37
1₀(29)	→	56
1₀(28)	→	29
1₀(3)	→	173
1₀(40)	→	41
1₀(121)	→	119
1₀(111)	→	109
1₀(25)	→	21
1₀(101)	→	113
1₀(192)	→	191
1₀(102)	→	103
1₀(15)	→	110
1₀(117)	→	118
1₀(133)	→	134
1₀(103)	→	104
1₀(17)	→	12
1₀(2)	→	126
1₀(141)	→	142
1₀(4)	→	5
1₀(44)	→	45
1₀(16)	→	17
1₀(52)	→	53
1₀(190)	→	186
4₀(101)	→	102
4₀(8)	→	22
4₀(78)	→	79
4₀(5)	→	49
4₀(63)	→	61
4₀(94)	→	159
4₀(152)	→	150
4₀(69)	→	70
4₀(54)	→	50
4₀(13)	→	178
4₀(148)	→	149
4₀(155)	→	156
4₀(156)	→	153
4₀(9)	→	19
4₀(165)	→	166
4₀(74)	→	75
4₀(137)	→	138
4₀(34)	→	35
4₀(138)	→	139
4₀(144)	→	140
4₀(199)	→	200
4₀(115)	→	112
4₀(2)	→	27
5₀(180)	→	181
5₀(60)	→	58
5₀(189)	→	190
5₀(200)	→	197
5₀(97)	→	98
5₀(130)	→	125
5₀(127)	→	128
5₀(162)	→	163
5₀(2)	→	33
5₀(3)	→	82
5₀(30)	→	31
5₀(124)	→	122
5₀(44)	→	69
5₀(8)	→	39
5₀(52)	→	170
5₀(101)	→	183
5₀(33)	→	73
5₀(15)	→	120
5₀(67)	→	64
5₀(51)	→	132
f6₀	→	2
0₀(2)	→	13
0₀(167)	→	168
0₀(51)	→	59
0₀(114)	→	115
0₀(46)	→	47
0₀(56)	→	57
0₀(9)	→	10
0₀(65)	→	66
0₀(128)	→	129
0₀(134)	→	131
0₀(10)	→	11
0₀(184)	→	185
0₀(49)	→	48
0₀(146)	→	147
0₀(19)	→	20
0₀(71)	→	68
0₀(107)	→	108
0₀(159)	→	158
0₀(37)	→	32
0₀(76)	→	72
0₀(89)	→	86
0₀(3)	→	187
0₀(6)	→	1
0₀(118)	→	116
0₀(141)	→	161
0₀(66)	→	67
0₀(70)	→	71
0₀(23)	→	24
0₀(139)	→	135
0₀(29)	→	30
0₀(33)	→	34
0₀(27)	→	51
0₀(195)	→	196
0₀(45)	→	46
0₀(129)	→	130
0₀(22)	→	23
0₀(42)	→	38
0₀(75)	→	76
0₀(20)	→	18
0₀(82)	→	83
0₀(126)	→	136
0₀(174)	→	175
0₀(97)	→	123
0₀(154)	→	155
0₀(142)	→	143
0₀(41)	→	42
0₀(34)	→	62
0₀(44)	→	202
0₀(187)	→	188
0₀(31)	→	26
0₀(5)	→	6
0₀(13)	→	14
0₀(47)	→	157
0₀(168)	→	164
0₁(225)	→	226
0₁(207)	→	208
0₁(206)	→	207
0₁(224)	→	225
4₁(205)	→	206
4₁(227)	→	228
4₁(231)	→	232