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(1(x0)))))	→	0(0(1(1(x0))))
4(5(2(3(5(x0)))))	→	4(4(0(5(x0))))
5(3(2(4(3(2(x0))))))	→	5(3(0(5(4(x0)))))
2(2(5(5(2(2(1(x0)))))))	→	3(2(3(3(1(0(x0))))))
4(5(2(1(1(3(4(x0)))))))	→	1(1(0(5(0(x0)))))
0(2(2(3(3(2(5(0(4(x0)))))))))	→	0(2(2(1(3(4(1(4(x0))))))))
2(3(0(4(0(0(5(2(4(x0)))))))))	→	3(2(2(2(3(0(4(0(4(x0)))))))))
2(4(3(3(3(5(0(1(3(x0)))))))))	→	0(1(0(0(5(0(5(x0)))))))
2(3(5(3(3(4(1(5(1(2(x0))))))))))	→	2(0(3(5(2(5(1(3(4(2(x0))))))))))
3(0(1(2(4(0(0(3(3(4(x0))))))))))	→	3(1(5(0(4(2(0(2(5(4(x0))))))))))
1(1(4(0(4(2(1(2(4(5(3(x0)))))))))))	→	1(1(0(1(5(2(2(0(2(4(x0))))))))))
3(1(2(4(0(0(3(3(1(4(5(x0)))))))))))	→	2(3(1(1(4(0(4(2(2(2(5(x0)))))))))))
4(3(0(4(1(0(4(1(5(0(3(x0)))))))))))	→	0(4(2(3(0(0(1(5(5(1(x0))))))))))
0(5(1(0(1(1(2(2(1(1(2(2(2(2(x0))))))))))))))	→	0(3(0(5(3(1(3(0(3(4(2(3(3(1(4(x0)))))))))))))))
0(5(2(1(1(4(2(5(2(0(1(3(3(3(x0))))))))))))))	→	0(4(0(4(4(4(5(0(2(4(0(3(2(2(x0))))))))))))))
3(0(2(3(2(0(3(3(2(1(2(2(0(1(3(x0)))))))))))))))	→	2(1(5(3(2(1(2(2(0(4(0(1(3(1(x0))))))))))))))
0(5(2(3(4(0(5(3(2(4(2(2(4(0(3(4(x0))))))))))))))))	→	0(0(0(5(1(3(2(2(3(0(1(3(2(1(x0))))))))))))))
4(4(2(5(3(3(1(1(3(1(1(0(5(3(1(4(x0))))))))))))))))	→	4(2(4(4(4(2(1(5(5(4(3(3(0(5(1(5(4(x0)))))))))))))))))
5(3(5(1(1(5(4(2(2(4(1(5(0(5(4(3(x0))))))))))))))))	→	0(0(4(2(2(1(3(2(1(0(5(1(1(1(x0))))))))))))))
2(2(0(1(4(3(5(4(2(2(5(1(0(5(0(5(4(5(2(x0)))))))))))))))))))	→	3(3(4(2(0(4(5(2(5(2(0(0(4(4(3(5(1(4(5(2(x0))))))))))))))))))))
2(5(3(4(1(3(2(5(3(1(1(2(2(1(0(2(4(3(3(x0)))))))))))))))))))	→	0(3(5(2(3(1(1(0(3(4(3(4(0(0(5(2(2(3(x0))))))))))))))))))
5(3(1(5(0(1(4(4(2(4(3(2(5(0(4(1(0(4(4(x0)))))))))))))))))))	→	5(2(2(4(1(1(5(2(3(4(2(5(2(0(2(0(2(5(4(x0)))))))))))))))))))
2(3(0(3(2(3(1(1(4(2(5(3(4(2(5(2(5(0(2(3(1(x0)))))))))))))))))))))	→	3(2(4(3(2(1(3(3(1(0(1(1(3(3(0(3(0(5(1(x0)))))))))))))))))))
3(1(2(1(3(1(2(2(4(1(1(3(2(4(4(3(2(0(3(4(5(x0)))))))))))))))))))))	→	2(5(5(1(1(2(1(0(1(3(1(0(5(2(4(1(1(5(x0))))))))))))))))))
5(4(3(1(3(4(5(3(0(1(3(4(0(2(2(4(3(3(0(5(3(x0)))))))))))))))))))))	→	5(5(1(1(5(2(4(0(0(1(0(1(2(0(5(1(3(5(x0))))))))))))))))))

Proof

1 Bounds

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

final states:

{255, 238, 221, 207, 189, 170, 158, 143, 130, 117, 104, 91, 82, 72, 63, 55, 45, 40, 32, 25, 21, 15, 10, 6, 1}

transitions:

221 → 191

221 → 46

25 → 16

32 → 191

32 → 46

10 → 7

15 → 74

15 → 105

15 → 46

276 → 120

55 → 190

255 → 12

255 → 7

130 → 8

130 → 16

1 → 16

40 → 64

40 → 46

287 → 171

79 → 272

233 → 282

91 → 222

91 → 8

91 → 16

170 → 105

170 → 46

21 → 172

21 → 11

72 → 118

72 → 190

207 → 7

6 → 172

6 → 11

82 → 11

143 → 11

117 → 190

45 → 191

45 → 46

63 → 4

63 → 3

104 → 8

104 → 16

189 → 73

189 → 46

158 → 7

238 → 118

238 → 190

1₁(273) → 274

1₁(272) → 273

4₁(282) → 283

3₁(285) → 286

4₀(211) → 212

4₀(175) → 176

4₀(115) → 116

4₀(46) → 47

4₀(183) → 184

4₀(157) → 143

4₀(120) → 121

4₀(112) → 113

4₀(186) → 187

4₀(240) → 241

4₀(195) → 196

4₀(33) → 34

4₀(77) → 78

4₀(58) → 59

4₀(26) → 27

4₀(8) → 9

4₀(167) → 168

4₀(89) → 90

4₀(197) → 198

4₀(111) → 112

4₀(155) → 156

4₀(113) → 114

4₀(9) → 6

4₀(94) → 95

4₀(75) → 76

4₀(148) → 149

4₀(171) → 172

4₀(107) → 108

4₀(265) → 266

4₀(2) → 11

4₀(176) → 177

4₀(154) → 155

4₀(217) → 218

4₀(153) → 154

4₀(235) → 236

5₀(2) → 7

5₀(159) → 160

5₀(51) → 52

5₀(110) → 111

5₀(16) → 22

5₀(209) → 210

5₀(192) → 193

5₀(144) → 145

5₀(46) → 171

5₀(173) → 174

5₀(100) → 101

5₀(83) → 84

5₀(220) → 207

5₀(242) → 243

5₀(267) → 268

5₀(150) → 151

5₀(8) → 41

5₀(60) → 61

5₀(214) → 215

5₀(270) → 271

5₀(11) → 12

5₀(253) → 254

5₀(14) → 10

5₀(139) → 140

5₀(257) → 258

5₀(182) → 183

5₀(67) → 68

5₀(204) → 205

5₀(180) → 181

5₀(49) → 50

5₀(271) → 255

5₀(3) → 83

5₀(252) → 253

5₀(127) → 128

5₀(149) → 150

1₀(226) → 227

1₀(244) → 245

1₀(98) → 99

1₀(227) → 228

1₀(151) → 152

1₀(124) → 125

1₀(23) → 24

1₀(70) → 71

1₀(239) → 240

1₀(260) → 261

1₀(200) → 201

1₀(78) → 79

1₀(216) → 217

1₀(250) → 251

1₀(251) → 252

1₀(118) → 119

1₀(7) → 239

1₀(84) → 85

1₀(132) → 133

1₀(262) → 263

1₀(11) → 26

1₀(43) → 44

1₀(79) → 80

1₀(201) → 202

1₀(268) → 269

1₀(28) → 29

1₀(3) → 4

1₀(172) → 173

1₀(164) → 165

1₀(232) → 233

1₀(12) → 144

1₀(161) → 162

1₀(248) → 249

1₀(128) → 129

1₀(61) → 62

1₀(215) → 216

1₀(71) → 63

1₀(48) → 49

1₀(246) → 247

1₀(2) → 3

1₀(269) → 270

1₀(256) → 257

1₀(4) → 159

1₀(24) → 21

1₀(68) → 69

1₀(229) → 230

1₀(138) → 139

1₀(16) → 17

3₀(87) → 88

3₀(17) → 18

3₀(47) → 48

3₀(97) → 98

3₀(99) → 100

3₀(237) → 221

3₀(222) → 223

3₀(230) → 231

3₀(26) → 92

3₀(27) → 28

3₀(202) → 203

3₀(146) → 147

3₀(198) → 199

3₀(196) → 197

3₀(7) → 256

3₀(13) → 14

3₀(234) → 235

3₀(39) → 32

3₀(147) → 148

3₀(92) → 93

3₀(20) → 15

3₀(52) → 53

3₀(35) → 36

3₀(3) → 118

3₀(80) → 81

3₀(102) → 103

3₀(62) → 55

3₀(137) → 138

3₀(224) → 225

3₀(163) → 164

3₀(95) → 96

3₀(18) → 19

3₀(131) → 132

3₀(126) → 127

3₀(134) → 135

3₀(205) → 206

3₀(212) → 213

3₀(174) → 175

3₀(188) → 170

3₀(231) → 232

3₀(187) → 188

3₀(245) → 246

3₀(105) → 106

3₀(2) → 190

3₀(225) → 226

2₀(179) → 180

2₀(123) → 124

2₀(135) → 136

2₀(236) → 237

2₀(93) → 94

2₀(156) → 157

2₀(65) → 66

2₀(266) → 267

2₀(233) → 234

2₀(88) → 89

2₀(185) → 186

2₀(152) → 153

2₀(12) → 56

2₀(166) → 167

2₀(19) → 20

2₀(7) → 73

2₀(125) → 126

2₀(54) → 45

2₀(73) → 74

2₀(46) → 105

2₀(190) → 191

2₀(181) → 182

2₀(191) → 192

2₀(50) → 51

2₀(165) → 166

2₀(11) → 64

2₀(213) → 214

2₀(66) → 67

2₀(38) → 39

2₀(241) → 242

2₀(74) → 75

2₀(162) → 163

2₀(218) → 219

2₀(2) → 46

2₀(3) → 131

2₀(36) → 37

2₀(30) → 31

2₀(37) → 38

2₀(129) → 117

2₀(122) → 123

2₀(208) → 209

2₀(29) → 30

2₀(210) → 211

2₀(108) → 109

2₀(259) → 260

2₀(136) → 137

2₀(254) → 238

2₀(219) → 220

2₀(81) → 72

2₀(57) → 58

2₀(203) → 204

2₀(249) → 250

f6₀ → 2

0₀(2) → 16

0₀(114) → 115

0₀(177) → 178

0₀(56) → 57

0₀(263) → 264

0₀(90) → 82

0₀(133) → 134

0₀(258) → 259

0₀(184) → 185

0₀(64) → 65

0₀(247) → 248

0₀(4) → 5

0₀(76) → 77

0₀(178) → 179

0₀(96) → 97

0₀(223) → 224

0₀(206) → 189

0₀(264) → 265

0₀(11) → 33

0₀(86) → 87

0₀(83) → 222

0₀(53) → 54

0₀(141) → 142

0₀(140) → 141

0₀(121) → 122

0₀(228) → 229

0₀(7) → 8

0₀(101) → 102

0₀(22) → 23

0₀(103) → 91

0₀(42) → 43

0₀(85) → 86

0₀(12) → 13

0₀(142) → 130

0₀(243) → 244

0₀(34) → 35

0₀(41) → 42

0₀(44) → 40

0₀(261) → 262

0₀(59) → 60

0₀(109) → 110

0₀(31) → 25

0₀(58) → 208

0₀(5) → 1

0₀(145) → 146

0₀(106) → 107

0₀(199) → 200

0₀(193) → 194

0₀(169) → 158

0₀(160) → 161

0₀(116) → 104

0₀(194) → 195

0₀(119) → 120

0₀(168) → 169

0₀(69) → 70

5₁(283) → 284

5₁(286) → 287

0₁(275) → 276

0₁(274) → 275

0₁(284) → 285

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