YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 Bounds

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

final states:

{274, 256, 239, 220, 206, 189, 175, 159, 145, 133, 121, 110, 99, 89, 80, 70, 62, 52, 43, 35, 27, 20, 13, 6, 1}

transitions:

239 → 222

239 → 14

89 → 122

89 → 14

80 → 44

274 → 14

145 → 28

145 → 3

133 → 1

133 → 21

110 → 21

175 → 16

175 → 22

175 → 7

20 → 44

99 → 45

99 → 21

62 → 90

62 → 44

1 → 44

13 → 44

121 → 190

121 → 53

6 → 136

6 → 208

6 → 7

220 → 53

52 → 100

52 → 3

189 → 3

35 → 71

35 → 53

256 → 146

256 → 53

159 → 28

159 → 3

206 → 45

206 → 21

43 → 100

43 → 3

27 → 3

70 → 28

70 → 3

2₀(254) → 255

2₀(11) → 12

2₀(169) → 170

2₀(245) → 246

2₀(78) → 79

2₀(146) → 240

2₀(227) → 228

2₀(112) → 113

2₀(251) → 252

2₀(7) → 28

2₀(86) → 87

2₀(186) → 187

2₀(44) → 100

2₀(222) → 223

2₀(98) → 89

2₀(61) → 52

2₀(184) → 185

2₀(143) → 144

2₀(111) → 112

2₀(288) → 289

2₀(138) → 139

2₀(56) → 57

2₀(199) → 200

2₀(289) → 290

2₀(201) → 202

2₀(131) → 132

2₀(136) → 137

2₀(177) → 178

2₀(284) → 285

2₀(102) → 103

2₀(196) → 197

2₀(88) → 80

2₀(191) → 192

2₀(202) → 203

2₀(122) → 123

2₀(2) → 3

2₀(246) → 247

2₀(266) → 267

2₀(154) → 155

2₀(241) → 242

2₀(172) → 173

2₀(168) → 169

2₀(69) → 62

2₀(100) → 101

2₀(226) → 227

2₀(153) → 154

3₀(73) → 74

3₀(2) → 14

3₀(255) → 239

3₀(132) → 121

3₀(235) → 236

3₀(21) → 134

3₀(74) → 75

3₀(205) → 189

3₀(51) → 43

3₀(193) → 194

3₀(44) → 122

3₀(209) → 210

3₀(50) → 51

3₀(24) → 25

3₀(46) → 47

3₀(34) → 27

3₀(140) → 141

3₀(165) → 166

3₀(286) → 287

3₀(280) → 281

3₀(185) → 186

3₀(47) → 48

3₀(198) → 199

3₀(114) → 115

3₀(60) → 61

3₀(203) → 204

3₀(214) → 215

3₀(55) → 56

3₀(141) → 142

3₀(92) → 93

3₀(36) → 37

3₀(290) → 274

3₀(125) → 126

3₀(18) → 19

3₀(200) → 201

3₀(97) → 98

3₀(148) → 149

3₀(156) → 157

3₀(236) → 237

3₀(182) → 183

3₀(262) → 263

3₀(90) → 91

3₀(285) → 286

3₀(221) → 222

3₀(259) → 260

3₀(271) → 272

3₀(146) → 147

3₀(130) → 131

3₀(3) → 221

3₀(10) → 11

3₀(29) → 30

3₀(104) → 105

3₀(96) → 97

3₀(30) → 31

3₀(158) → 145

3₀(272) → 273

3₀(151) → 152

5₀(225) → 226

5₀(100) → 257

5₀(150) → 151

5₀(260) → 261

5₀(41) → 42

5₀(216) → 217

5₀(91) → 92

5₀(63) → 64

5₀(59) → 60

5₀(7) → 8

5₀(207) → 208

5₀(217) → 218

5₀(174) → 159

5₀(84) → 85

5₀(210) → 211

5₀(105) → 106

5₀(167) → 168

5₀(257) → 258

5₀(107) → 108

5₀(77) → 78

5₀(129) → 130

5₀(263) → 264

5₀(268) → 269

5₀(82) → 83

5₀(3) → 4

5₀(40) → 41

5₀(164) → 165

5₀(116) → 117

5₀(25) → 26

5₀(232) → 233

5₀(12) → 6

5₀(161) → 162

5₀(248) → 249

5₀(128) → 129

5₀(261) → 262

5₀(94) → 95

5₀(192) → 193

5₀(180) → 181

5₀(83) → 84

5₀(127) → 128

5₀(15) → 16

5₀(223) → 224

5₀(49) → 50

5₀(135) → 136

5₀(21) → 22

5₀(53) → 54

5₀(2) → 7

5₀(188) → 175

5₀(171) → 172

5₀(240) → 241

0₀(19) → 13

0₀(108) → 109

0₀(17) → 18

0₀(106) → 107

0₀(21) → 90

0₀(8) → 9

0₀(160) → 161

0₀(279) → 280

0₀(278) → 279

0₀(123) → 124

0₀(230) → 231

0₀(124) → 125

0₀(242) → 243

0₀(7) → 160

0₀(270) → 271

0₀(234) → 235

0₀(22) → 81

0₀(147) → 148

0₀(9) → 10

0₀(72) → 73

0₀(119) → 120

0₀(14) → 207

0₀(48) → 49

0₀(31) → 32

0₀(65) → 66

0₀(81) → 82

0₀(57) → 58

0₀(32) → 33

0₀(163) → 164

0₀(250) → 251

0₀(183) → 184

0₀(45) → 46

0₀(134) → 135

0₀(64) → 65

0₀(76) → 77

0₀(38) → 39

0₀(33) → 34

0₀(231) → 232

0₀(204) → 205

0₀(75) → 76

0₀(253) → 254

0₀(2) → 44

1₀(224) → 225

1₀(176) → 177

1₀(275) → 276

1₀(16) → 17

1₀(265) → 266

1₀(53) → 190

1₀(233) → 234

1₀(197) → 198

1₀(155) → 156

1₀(247) → 248

1₀(79) → 70

1₀(152) → 153

1₀(166) → 167

1₀(21) → 146

1₀(95) → 96

1₀(139) → 140

1₀(157) → 158

1₀(7) → 71

1₀(238) → 220

1₀(22) → 23

1₀(190) → 191

1₀(243) → 244

1₀(277) → 278

1₀(23) → 24

1₀(194) → 195

1₀(237) → 238

1₀(42) → 35

1₀(269) → 270

1₀(213) → 214

1₀(252) → 253

1₀(66) → 67

1₀(117) → 118

1₀(162) → 163

1₀(218) → 219

1₀(113) → 114

1₀(2) → 53

1₀(228) → 229

1₀(3) → 111

1₀(26) → 20

1₀(142) → 143

1₀(170) → 171

1₀(37) → 38

1₀(28) → 29

1₀(276) → 277

1₀(282) → 283

1₀(115) → 116

1₀(134) → 176

1₀(39) → 40

1₀(67) → 68

1₀(195) → 196

f6₀ → 2

4₀(2) → 21

4₀(149) → 150

4₀(258) → 259

4₀(54) → 55

4₀(215) → 216

4₀(55) → 275

4₀(71) → 72

4₀(4) → 5

4₀(244) → 245

4₀(178) → 179

4₀(181) → 182

4₀(281) → 282

4₀(264) → 265

4₀(249) → 250

4₀(14) → 15

4₀(87) → 88

4₀(211) → 212

4₀(118) → 119

4₀(173) → 174

4₀(208) → 209

4₀(137) → 138

4₀(7) → 36

4₀(15) → 63

4₀(93) → 94

4₀(267) → 268

4₀(101) → 102

4₀(103) → 104

4₀(85) → 86

4₀(120) → 110

4₀(126) → 127

4₀(212) → 213

4₀(229) → 230

4₀(44) → 45

4₀(187) → 188

4₀(219) → 206

4₀(109) → 99

4₀(58) → 59

4₀(5) → 1

4₀(144) → 133

4₀(287) → 288

4₀(283) → 284

4₀(179) → 180

4₀(68) → 69

4₀(273) → 256

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