YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 Bounds

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

final states:

{280, 264, 246, 231, 218, 203, 189, 174, 158, 144, 130, 116, 102, 88, 74, 62, 53, 45, 38, 31, 24, 17, 13, 7, 1}

transitions:

280 → 18

102 → 248

102 → 32

97 → 305

218 → 18

130 → 247

62 → 25

31 → 204

31 → 32

246 → 190

246 → 204

246 → 32

1 → 32

13 → 3

38 → 18

311 → 19

116 → 248

116 → 32

88 → 18

174 → 247

264 → 18

53 → 18

45 → 25

7 → 19

7 → 32

189 → 131

189 → 8

158 → 232

158 → 32

231 → 25

17 → 25

203 → 8

74 → 64

74 → 18

24 → 204

24 → 32

144 → 247

f6₀ → 2

5₀(123) → 124

5₀(48) → 49

5₀(293) → 294

5₀(156) → 157

5₀(230) → 218

5₀(155) → 156

5₀(273) → 274

5₀(172) → 173

5₀(40) → 41

5₀(61) → 53

5₀(46) → 47

5₀(191) → 192

5₀(237) → 238

5₀(145) → 146

5₀(213) → 214

5₀(84) → 85

5₀(4) → 281

5₀(63) → 64

5₀(240) → 241

5₀(162) → 163

5₀(171) → 172

5₀(89) → 175

5₀(2) → 18

5₀(3) → 14

5₀(26) → 27

5₀(27) → 28

5₀(44) → 38

5₀(292) → 293

5₀(149) → 150

5₀(78) → 79

5₀(101) → 88

5₀(282) → 283

5₀(288) → 289

5₀(244) → 245

5₀(259) → 260

5₀(115) → 102

5₀(272) → 273

5₀(294) → 295

5₀(207) → 208

5₀(254) → 255

5₀(100) → 101

5₀(153) → 154

5₀(57) → 58

3₀(98) → 99

3₀(33) → 34

3₀(148) → 149

3₀(73) → 62

3₀(225) → 226

3₀(206) → 207

3₀(170) → 171

3₀(200) → 201

3₀(26) → 219

3₀(41) → 42

3₀(216) → 217

3₀(91) → 92

3₀(30) → 24

3₀(289) → 290

3₀(147) → 148

3₀(86) → 87

3₀(199) → 200

3₀(118) → 119

3₀(58) → 59

3₀(51) → 52

3₀(8) → 9

3₀(179) → 180

3₀(11) → 12

3₀(143) → 130

3₀(95) → 96

3₀(167) → 168

3₀(60) → 61

3₀(257) → 258

3₀(43) → 44

3₀(258) → 259

3₀(283) → 284

3₀(176) → 177

3₀(185) → 186

3₀(90) → 91

3₀(263) → 246

3₀(195) → 196

3₀(87) → 74

3₀(82) → 83

3₀(3) → 63

3₀(47) → 265

3₀(164) → 165

3₀(286) → 287

3₀(69) → 70

3₀(184) → 185

3₀(54) → 55

3₀(261) → 262

3₀(72) → 73

3₀(215) → 216

3₀(49) → 50

3₀(135) → 136

3₀(181) → 182

3₀(297) → 280

3₀(5) → 6

3₀(67) → 68

3₀(296) → 297

3₀(10) → 11

3₀(93) → 94

3₀(2) → 247

3₀(229) → 230

3₀(157) → 144

3₀(89) → 90

3₀(186) → 187

3₀(52) → 45

4₀(19) → 20

4₀(46) → 159

4₀(212) → 213

4₀(141) → 142

4₀(92) → 93

4₀(112) → 113

4₀(105) → 106

4₀(3) → 131

4₀(251) → 252

4₀(25) → 26

4₀(224) → 225

4₀(253) → 254

4₀(267) → 268

4₀(66) → 67

4₀(77) → 78

4₀(276) → 277

4₀(8) → 89

4₀(140) → 141

4₀(197) → 198

4₀(133) → 134

4₀(238) → 239

4₀(108) → 109

4₀(56) → 57

4₀(208) → 209

4₀(83) → 84

4₀(198) → 199

4₀(109) → 110

4₀(204) → 205

4₀(284) → 285

4₀(42) → 43

4₀(126) → 127

4₀(233) → 234

4₀(4) → 5

4₀(117) → 145

4₀(160) → 161

4₀(182) → 183

4₀(2) → 8

4₀(168) → 169

4₀(291) → 292

4₀(12) → 7

4₁(305) → 306

4₁(310) → 311

1₀(20) → 21

1₀(2) → 25

1₀(25) → 117

1₀(21) → 22

1₀(175) → 176

1₀(117) → 118

1₀(120) → 121

1₀(188) → 174

1₀(152) → 153

1₀(205) → 206

1₀(129) → 116

1₀(227) → 228

1₀(193) → 194

1₀(110) → 111

1₀(249) → 250

1₀(192) → 193

1₀(59) → 60

1₀(136) → 137

1₀(222) → 223

1₀(165) → 166

1₀(245) → 231

1₀(232) → 233

1₀(260) → 261

1₀(190) → 191

1₀(187) → 188

1₀(210) → 211

1₀(36) → 37

1₀(9) → 10

1₀(99) → 100

1₀(125) → 126

1₀(14) → 15

1₀(128) → 129

1₀(23) → 17

1₀(139) → 140

1₀(169) → 170

1₀(250) → 251

1₀(107) → 108

1₀(236) → 237

1₀(138) → 139

1₀(285) → 286

1₀(39) → 103

1₀(121) → 122

1₀(166) → 167

1₀(3) → 4

1₀(75) → 76

1₀(127) → 128

1₀(94) → 95

1₀(196) → 197

1₀(239) → 240

0₀(2) → 32

0₀(18) → 19

0₀(114) → 115

0₀(28) → 29

0₀(117) → 190

0₀(54) → 232

0₀(202) → 189

0₀(277) → 278

0₀(79) → 80

0₀(80) → 81

0₀(235) → 236

0₀(55) → 56

0₀(247) → 248

0₀(131) → 132

0₀(71) → 72

0₀(25) → 204

0₀(159) → 160

0₀(8) → 54

0₀(37) → 31

0₀(234) → 235

0₀(151) → 152

0₀(76) → 77

0₀(248) → 249

0₀(3) → 39

0₀(6) → 1

0₀(256) → 257

0₀(70) → 71

0₀(221) → 222

0₀(81) → 82

0₀(111) → 112

0₀(173) → 158

0₀(161) → 162

0₀(269) → 270

0₀(228) → 229

0₀(290) → 291

0₀(15) → 16

0₀(35) → 36

0₀(22) → 23

0₀(183) → 184

0₀(39) → 40

0₀(268) → 269

0₀(97) → 98

0₀(154) → 155

0₀(226) → 227

0₀(243) → 244

0₀(266) → 267

0₀(219) → 220

0₀(242) → 243

0₀(106) → 107

0₀(68) → 69

0₀(122) → 123

3₁(306) → 307

3₁(308) → 309

3₁(309) → 310

1₁(307) → 308

2₀(29) → 30

2₀(132) → 133

2₀(8) → 46

2₀(201) → 202

2₀(287) → 288

2₀(47) → 48

2₀(142) → 143

2₀(223) → 224

2₀(279) → 264

2₀(255) → 256

2₀(278) → 279

2₀(281) → 282

2₀(177) → 178

2₀(50) → 51

2₀(211) → 212

2₀(124) → 125

2₀(96) → 97

2₀(241) → 242

2₀(146) → 147

2₀(295) → 296

2₀(270) → 271

2₀(275) → 276

2₀(220) → 221

2₀(209) → 210

2₀(194) → 195

2₀(271) → 272

2₀(119) → 120

2₀(103) → 104

2₀(16) → 13

2₀(3) → 75

2₀(217) → 203

2₀(137) → 138

2₀(65) → 66

2₀(274) → 275

2₀(34) → 35

2₀(150) → 151

2₀(32) → 33

2₀(163) → 164

2₀(85) → 86

2₀(262) → 263

2₀(180) → 181

2₀(134) → 135

2₀(64) → 65

2₀(214) → 215

2₀(104) → 105

2₀(265) → 266

2₀(178) → 179

2₀(2) → 3

2₀(252) → 253

2₀(113) → 114

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