YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 Bounds

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

final states:

{285, 266, 250, 232, 213, 198, 180, 164, 148, 133, 122, 111, 98, 87, 75, 63, 53, 44, 35, 27, 21, 16, 10, 5, 1}

transitions:

111 → 3

315 → 291

87 → 54

87 → 76

98 → 13

98 → 214

98 → 36

10 → 76

122 → 11

133 → 6

213 → 6

5 → 6

1 → 6

44 → 76

21 → 6

311 → 5

75 → 11

288 → 312

53 → 37

53 → 11

180 → 76

232 → 36

16 → 181

16 → 76

63 → 36

7 → 308

35 → 214

35 → 36

198 → 76

164 → 7

164 → 76

250 → 99

250 → 11

148 → 36

285 → 76

266 → 3

27 → 37

27 → 11

f6₀ → 2

5₀(235) → 236

5₀(284) → 266

5₀(176) → 177

5₀(262) → 263

5₀(132) → 122

5₀(135) → 136

5₀(60) → 61

5₀(65) → 66

5₀(265) → 250

5₀(200) → 201

5₀(152) → 153

5₀(227) → 228

5₀(166) → 167

5₀(278) → 279

5₀(205) → 206

5₀(253) → 254

5₀(157) → 158

5₀(34) → 27

5₀(169) → 170

5₀(92) → 93

5₀(238) → 239

5₀(190) → 191

5₀(114) → 115

5₀(50) → 51

5₀(69) → 70

5₀(269) → 270

5₀(11) → 45

5₀(62) → 53

5₀(119) → 120

5₀(76) → 99

5₀(144) → 145

5₀(245) → 246

5₀(162) → 163

5₀(281) → 282

5₀(2) → 11

5₀(45) → 112

5₀(36) → 37

5₀(168) → 169

5₀(143) → 144

5₀(129) → 130

5₀(208) → 209

5₀(56) → 57

5₀(33) → 34

5₀(47) → 48

5₀(102) → 103

5₀(294) → 295

5₀(39) → 40

5₀(15) → 10

5₀(254) → 255

5₀(86) → 75

5₀(154) → 155

5₀(204) → 205

5₀(209) → 210

5₀(257) → 258

3₀(244) → 245

3₀(106) → 107

3₀(151) → 152

3₀(137) → 138

3₀(241) → 242

3₀(225) → 226

3₀(70) → 71

3₀(298) → 299

3₀(81) → 82

3₀(42) → 43

3₀(216) → 217

3₀(279) → 280

3₀(37) → 38

3₀(230) → 231

3₀(108) → 109

3₀(292) → 293

3₀(293) → 294

3₀(11) → 64

3₀(32) → 33

3₀(38) → 39

3₀(187) → 188

3₀(149) → 150

3₀(242) → 243

3₀(158) → 159

3₀(194) → 195

3₀(268) → 269

3₀(222) → 223

3₀(3) → 4

3₀(243) → 244

3₀(259) → 260

3₀(276) → 277

3₀(64) → 65

3₀(121) → 111

3₀(104) → 105

3₀(255) → 256

3₀(57) → 58

3₀(221) → 222

3₀(191) → 192

3₀(248) → 249

3₀(94) → 95

3₀(80) → 81

3₀(127) → 128

3₀(215) → 216

3₀(287) → 288

3₀(181) → 182

3₀(71) → 72

3₀(291) → 292

3₀(2) → 3

3₀(233) → 234

3₀(214) → 215

3₀(188) → 189

3₀(68) → 69

3₀(211) → 212

3₀(22) → 23

1₀(260) → 261

1₀(67) → 68

1₀(19) → 20

1₀(11) → 12

1₀(229) → 230

1₀(300) → 301

1₀(37) → 233

1₀(41) → 42

1₀(112) → 113

1₀(193) → 194

1₀(280) → 281

1₀(45) → 46

1₀(91) → 92

1₀(273) → 274

1₀(123) → 124

1₀(61) → 62

1₀(184) → 185

1₀(8) → 9

1₀(286) → 287

1₀(52) → 44

1₀(89) → 90

1₀(170) → 171

1₀(272) → 273

1₀(18) → 19

1₀(237) → 238

1₀(113) → 123

1₀(289) → 290

1₀(99) → 100

1₀(302) → 303

1₀(249) → 232

1₀(96) → 97

1₀(274) → 275

1₀(247) → 248

1₀(109) → 110

1₀(76) → 149

1₀(13) → 14

1₀(107) → 108

1₀(88) → 89

1₀(295) → 296

1₀(90) → 91

1₀(261) → 262

1₀(4) → 134

1₀(36) → 214

1₀(43) → 35

1₀(40) → 41

1₀(139) → 140

1₀(2) → 36

1₀(178) → 179

1₀(172) → 173

1₀(54) → 55

1₀(12) → 13

1₀(297) → 298

1₀(264) → 265

1₀(219) → 220

0₁(310) → 311

0₁(314) → 315

2₀(73) → 74

2₀(2) → 28

2₀(117) → 118

2₀(155) → 156

2₀(177) → 178

2₀(275) → 276

2₀(179) → 164

2₀(113) → 114

2₀(201) → 202

2₀(48) → 49

2₀(147) → 133

2₀(202) → 203

2₀(192) → 193

2₀(37) → 286

2₀(59) → 60

2₀(136) → 137

2₀(46) → 47

2₀(283) → 284

2₀(224) → 225

2₀(76) → 77

2₀(83) → 84

2₀(165) → 166

2₀(85) → 86

2₀(185) → 186

2₀(199) → 200

2₀(126) → 127

2₀(11) → 88

2₀(183) → 184

2₀(128) → 129

2₀(195) → 196

2₀(23) → 24

2₀(17) → 22

2₀(118) → 119

2₀(282) → 283

2₀(142) → 143

2₀(206) → 207

2₀(49) → 50

2₀(3) → 17

2₀(252) → 253

2₀(29) → 30

2₀(196) → 197

2₀(239) → 240

2₀(288) → 289

2₀(7) → 8

0₀(2) → 6

0₀(51) → 52

0₀(46) → 251

0₀(28) → 29

0₀(156) → 157

0₀(263) → 264

0₀(299) → 300

0₀(9) → 5

0₀(258) → 259

0₀(271) → 272

0₀(175) → 176

0₀(146) → 147

0₀(105) → 106

0₀(110) → 98

0₀(277) → 278

0₀(79) → 80

0₀(55) → 56

0₀(24) → 25

0₀(131) → 132

0₀(25) → 26

0₀(4) → 1

0₀(26) → 21

0₀(138) → 139

0₀(150) → 151

0₀(223) → 224

0₀(17) → 18

0₀(11) → 267

0₀(84) → 85

0₀(14) → 15

0₀(218) → 219

0₀(141) → 142

0₀(203) → 204

0₀(256) → 257

0₀(140) → 141

0₀(1) → 199

0₀(228) → 229

0₀(130) → 131

0₀(290) → 291

0₀(101) → 102

0₀(240) → 241

0₀(82) → 83

0₀(120) → 121

0₀(174) → 175

0₀(78) → 79

0₀(58) → 59

0₀(231) → 213

0₀(72) → 73

0₀(160) → 161

0₀(207) → 208

0₀(116) → 117

0₀(301) → 302

0₀(153) → 154

0₀(182) → 183

0₀(171) → 172

3₁(313) → 314

3₁(308) → 309

3₁(309) → 310

3₁(312) → 313

4₀(125) → 126

4₀(100) → 101

4₀(186) → 187

4₀(246) → 247

4₀(296) → 297

4₀(97) → 87

4₀(124) → 125

4₀(11) → 181

4₀(66) → 67

4₀(226) → 227

4₀(36) → 54

4₀(236) → 237

4₀(6) → 7

4₀(270) → 271

4₀(93) → 94

4₀(234) → 235

4₀(220) → 221

4₀(20) → 16

4₀(167) → 168

4₀(161) → 162

4₀(149) → 165

4₀(251) → 252

4₀(159) → 160

4₀(267) → 268

4₀(103) → 104

4₀(145) → 146

4₀(189) → 190

4₀(217) → 218

4₀(31) → 32

4₀(74) → 63

4₀(30) → 31

4₀(197) → 180

4₀(163) → 148

4₀(95) → 96

4₀(173) → 174

4₀(210) → 211

4₀(134) → 135

4₀(77) → 78

4₀(212) → 198

4₀(303) → 285

4₀(115) → 116

4₀(2) → 76

111	→	3
315	→	291
87	→	54
87	→	76
98	→	13
98	→	214
98	→	36
10	→	76
122	→	11
133	→	6
213	→	6
5	→	6
1	→	6
44	→	76
21	→	6
311	→	5
75	→	11
288	→	312
53	→	37
53	→	11
180	→	76
232	→	36
16	→	181
16	→	76
63	→	36
7	→	308
35	→	214
35	→	36
198	→	76
164	→	7
164	→	76
250	→	99
250	→	11
148	→	36
285	→	76
266	→	3
27	→	37
27	→	11
f6₀	→	2
5₀(235)	→	236
5₀(284)	→	266
5₀(176)	→	177
5₀(262)	→	263
5₀(132)	→	122
5₀(135)	→	136
5₀(60)	→	61
5₀(65)	→	66
5₀(265)	→	250
5₀(200)	→	201
5₀(152)	→	153
5₀(227)	→	228
5₀(166)	→	167
5₀(278)	→	279
5₀(205)	→	206
5₀(253)	→	254
5₀(157)	→	158
5₀(34)	→	27
5₀(169)	→	170
5₀(92)	→	93
5₀(238)	→	239
5₀(190)	→	191
5₀(114)	→	115
5₀(50)	→	51
5₀(69)	→	70
5₀(269)	→	270
5₀(11)	→	45
5₀(62)	→	53
5₀(119)	→	120
5₀(76)	→	99
5₀(144)	→	145
5₀(245)	→	246
5₀(162)	→	163
5₀(281)	→	282
5₀(2)	→	11
5₀(45)	→	112
5₀(36)	→	37
5₀(168)	→	169
5₀(143)	→	144
5₀(129)	→	130
5₀(208)	→	209
5₀(56)	→	57
5₀(33)	→	34
5₀(47)	→	48
5₀(102)	→	103
5₀(294)	→	295
5₀(39)	→	40
5₀(15)	→	10
5₀(254)	→	255
5₀(86)	→	75
5₀(154)	→	155
5₀(204)	→	205
5₀(209)	→	210
5₀(257)	→	258
3₀(244)	→	245
3₀(106)	→	107
3₀(151)	→	152
3₀(137)	→	138
3₀(241)	→	242
3₀(225)	→	226
3₀(70)	→	71
3₀(298)	→	299
3₀(81)	→	82
3₀(42)	→	43
3₀(216)	→	217
3₀(279)	→	280
3₀(37)	→	38
3₀(230)	→	231
3₀(108)	→	109
3₀(292)	→	293
3₀(293)	→	294
3₀(11)	→	64
3₀(32)	→	33
3₀(38)	→	39
3₀(187)	→	188
3₀(149)	→	150
3₀(242)	→	243
3₀(158)	→	159
3₀(194)	→	195
3₀(268)	→	269
3₀(222)	→	223
3₀(3)	→	4
3₀(243)	→	244
3₀(259)	→	260
3₀(276)	→	277
3₀(64)	→	65
3₀(121)	→	111
3₀(104)	→	105
3₀(255)	→	256
3₀(57)	→	58
3₀(221)	→	222
3₀(191)	→	192
3₀(248)	→	249
3₀(94)	→	95
3₀(80)	→	81
3₀(127)	→	128
3₀(215)	→	216
3₀(287)	→	288
3₀(181)	→	182
3₀(71)	→	72
3₀(291)	→	292
3₀(2)	→	3
3₀(233)	→	234
3₀(214)	→	215
3₀(188)	→	189
3₀(68)	→	69
3₀(211)	→	212
3₀(22)	→	23
1₀(260)	→	261
1₀(67)	→	68
1₀(19)	→	20
1₀(11)	→	12
1₀(229)	→	230
1₀(300)	→	301
1₀(37)	→	233
1₀(41)	→	42
1₀(112)	→	113
1₀(193)	→	194
1₀(280)	→	281
1₀(45)	→	46
1₀(91)	→	92
1₀(273)	→	274
1₀(123)	→	124
1₀(61)	→	62
1₀(184)	→	185
1₀(8)	→	9
1₀(286)	→	287
1₀(52)	→	44
1₀(89)	→	90
1₀(170)	→	171
1₀(272)	→	273
1₀(18)	→	19
1₀(237)	→	238
1₀(113)	→	123
1₀(289)	→	290
1₀(99)	→	100
1₀(302)	→	303
1₀(249)	→	232
1₀(96)	→	97
1₀(274)	→	275
1₀(247)	→	248
1₀(109)	→	110
1₀(76)	→	149
1₀(13)	→	14
1₀(107)	→	108
1₀(88)	→	89
1₀(295)	→	296
1₀(90)	→	91
1₀(261)	→	262
1₀(4)	→	134
1₀(36)	→	214
1₀(43)	→	35
1₀(40)	→	41
1₀(139)	→	140
1₀(2)	→	36
1₀(178)	→	179
1₀(172)	→	173
1₀(54)	→	55
1₀(12)	→	13
1₀(297)	→	298
1₀(264)	→	265
1₀(219)	→	220
0₁(310)	→	311
0₁(314)	→	315
2₀(73)	→	74
2₀(2)	→	28
2₀(117)	→	118
2₀(155)	→	156
2₀(177)	→	178
2₀(275)	→	276
2₀(179)	→	164
2₀(113)	→	114
2₀(201)	→	202
2₀(48)	→	49
2₀(147)	→	133
2₀(202)	→	203
2₀(192)	→	193
2₀(37)	→	286
2₀(59)	→	60
2₀(136)	→	137
2₀(46)	→	47
2₀(283)	→	284
2₀(224)	→	225
2₀(76)	→	77
2₀(83)	→	84
2₀(165)	→	166
2₀(85)	→	86
2₀(185)	→	186
2₀(199)	→	200
2₀(126)	→	127
2₀(11)	→	88
2₀(183)	→	184
2₀(128)	→	129
2₀(195)	→	196
2₀(23)	→	24
2₀(17)	→	22
2₀(118)	→	119
2₀(282)	→	283
2₀(142)	→	143
2₀(206)	→	207
2₀(49)	→	50
2₀(3)	→	17
2₀(252)	→	253
2₀(29)	→	30
2₀(196)	→	197
2₀(239)	→	240
2₀(288)	→	289
2₀(7)	→	8
0₀(2)	→	6
0₀(51)	→	52
0₀(46)	→	251
0₀(28)	→	29
0₀(156)	→	157
0₀(263)	→	264
0₀(299)	→	300
0₀(9)	→	5
0₀(258)	→	259
0₀(271)	→	272
0₀(175)	→	176
0₀(146)	→	147
0₀(105)	→	106
0₀(110)	→	98
0₀(277)	→	278
0₀(79)	→	80
0₀(55)	→	56
0₀(24)	→	25
0₀(131)	→	132
0₀(25)	→	26
0₀(4)	→	1
0₀(26)	→	21
0₀(138)	→	139
0₀(150)	→	151
0₀(223)	→	224
0₀(17)	→	18
0₀(11)	→	267
0₀(84)	→	85
0₀(14)	→	15
0₀(218)	→	219
0₀(141)	→	142
0₀(203)	→	204
0₀(256)	→	257
0₀(140)	→	141
0₀(1)	→	199
0₀(228)	→	229
0₀(130)	→	131
0₀(290)	→	291
0₀(101)	→	102
0₀(240)	→	241
0₀(82)	→	83
0₀(120)	→	121
0₀(174)	→	175
0₀(78)	→	79
0₀(58)	→	59
0₀(231)	→	213
0₀(72)	→	73
0₀(160)	→	161
0₀(207)	→	208
0₀(116)	→	117
0₀(301)	→	302
0₀(153)	→	154
0₀(182)	→	183
0₀(171)	→	172
3₁(313)	→	314
3₁(308)	→	309
3₁(309)	→	310
3₁(312)	→	313
4₀(125)	→	126
4₀(100)	→	101
4₀(186)	→	187
4₀(246)	→	247
4₀(296)	→	297
4₀(97)	→	87
4₀(124)	→	125
4₀(11)	→	181
4₀(66)	→	67
4₀(226)	→	227
4₀(36)	→	54
4₀(236)	→	237
4₀(6)	→	7
4₀(270)	→	271
4₀(93)	→	94
4₀(234)	→	235
4₀(220)	→	221
4₀(20)	→	16
4₀(167)	→	168
4₀(161)	→	162
4₀(149)	→	165
4₀(251)	→	252
4₀(159)	→	160
4₀(267)	→	268
4₀(103)	→	104
4₀(145)	→	146
4₀(189)	→	190
4₀(217)	→	218
4₀(31)	→	32
4₀(74)	→	63
4₀(30)	→	31
4₀(197)	→	180
4₀(163)	→	148
4₀(95)	→	96
4₀(173)	→	174
4₀(210)	→	211
4₀(134)	→	135
4₀(77)	→	78
4₀(212)	→	198
4₀(303)	→	285
4₀(115)	→	116
4₀(2)	→	76