YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 Bounds

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

final states:

{255, 236, 218, 201, 185, 171, 157, 144, 133, 120, 108, 99, 87, 77, 68, 59, 50, 42, 34, 27, 19, 12, 8, 5, 1}

transitions:

157 → 28

25 → 318

87 → 88

289 → 147

133 → 172

133 → 88

120 → 13

50 → 88

218 → 20

108 → 219

108 → 88

5 → 88

59 → 13

34 → 21

34 → 28

185 → 88

255 → 88

99 → 88

293 → 56

246 → 302

1 → 60

1 → 28

8 → 20

305 → 249

323 → 307

309 → 172

170 → 322

201 → 20

178 → 274

277 → 181

171 → 20

53 → 290

2 → 306

12 → 51

12 → 13

77 → 88

236 → 124

236 → 89

236 → 3

42 → 88

68 → 88

19 → 89

19 → 3

144 → 7

144 → 308

144 → 6

144 → 307

43 → 286

27 → 20

321 → 60

5₁(322) → 323

5₁(306) → 307

5₁(303) → 304

5₁(307) → 308

5₁(302) → 303

1₁(319) → 320

1₁(290) → 291

1₁(318) → 319

1₁(275) → 276

1₁(287) → 288

1₁(291) → 292

1₁(286) → 287

1₁(274) → 275

4₀(211) → 212

4₀(190) → 191

4₀(115) → 116

4₀(67) → 59

4₀(65) → 66

4₀(30) → 31

4₀(49) → 42

4₀(37) → 38

4₀(193) → 194

4₀(7) → 5

4₀(240) → 241

4₀(224) → 225

4₀(21) → 22

4₀(268) → 269

4₀(167) → 168

4₀(134) → 135

4₀(142) → 143

4₀(18) → 12

4₀(113) → 114

4₀(6) → 51

4₀(131) → 132

4₀(79) → 80

4₀(94) → 95

4₀(96) → 97

4₀(262) → 263

4₀(247) → 248

4₀(204) → 205

4₀(71) → 72

4₀(72) → 73

4₀(101) → 102

4₀(39) → 40

4₀(205) → 206

4₀(88) → 186

4₀(90) → 134

4₀(28) → 35

4₀(14) → 15

4₀(36) → 37

4₀(160) → 161

4₀(163) → 164

4₀(116) → 117

4₀(22) → 23

4₀(2) → 13

4₀(164) → 165

4₀(192) → 193

4₀(100) → 101

4₀(132) → 120

5₀(73) → 74

5₀(109) → 110

5₀(228) → 229

5₀(2) → 6

5₀(78) → 79

5₀(235) → 218

5₀(175) → 176

5₀(269) → 270

5₀(188) → 189

5₀(6) → 7

5₀(124) → 125

5₀(88) → 121

5₀(28) → 29

5₀(209) → 210

5₀(174) → 175

5₀(80) → 81

5₀(245) → 246

5₀(267) → 268

5₀(229) → 230

5₀(223) → 224

5₀(258) → 259

5₀(114) → 115

5₀(270) → 271

5₀(141) → 142

5₀(105) → 106

5₀(253) → 254

5₀(154) → 155

5₀(265) → 266

5₀(13) → 14

5₀(17) → 18

5₀(169) → 170

5₀(257) → 258

5₀(244) → 245

5₀(259) → 260

5₀(38) → 39

5₀(206) → 207

5₀(226) → 227

5₀(29) → 30

5₀(35) → 36

1₀(182) → 183

1₀(177) → 178

1₀(126) → 127

1₀(150) → 151

1₀(239) → 240

1₀(26) → 19

1₀(123) → 124

1₀(76) → 68

1₀(14) → 78

1₀(250) → 251

1₀(159) → 160

1₀(212) → 213

1₀(156) → 144

1₀(178) → 179

1₀(179) → 180

1₀(112) → 113

1₀(125) → 126

1₀(168) → 169

1₀(95) → 96

1₀(6) → 256

1₀(203) → 204

1₀(231) → 232

1₀(43) → 145

1₀(152) → 153

1₀(202) → 203

1₀(56) → 57

1₀(88) → 89

1₀(222) → 223

1₀(3) → 4

1₀(234) → 235

1₀(9) → 10

1₀(25) → 26

1₀(145) → 146

1₀(191) → 192

1₀(54) → 55

1₀(161) → 162

1₀(162) → 163

1₀(102) → 103

1₀(189) → 190

1₀(15) → 16

1₀(13) → 158

1₀(53) → 54

1₀(2) → 3

1₀(233) → 234

1₀(153) → 154

1₀(254) → 236

1₀(89) → 90

3₀(106) → 107

3₀(82) → 83

3₀(58) → 50

3₀(122) → 123

3₀(86) → 77

3₀(98) → 87

3₀(237) → 238

3₀(230) → 231

3₀(136) → 137

3₀(60) → 61

3₀(242) → 243

3₀(198) → 199

3₀(7) → 69

3₀(43) → 219

3₀(6) → 9

3₀(147) → 148

3₀(92) → 93

3₀(166) → 167

3₀(107) → 99

3₀(248) → 249

3₀(181) → 182

3₀(155) → 156

3₀(194) → 195

3₀(249) → 250

3₀(52) → 53

3₀(251) → 252

3₀(35) → 172

3₀(256) → 257

3₀(165) → 166

3₀(74) → 75

3₀(62) → 63

3₀(195) → 196

3₀(138) → 139

3₀(183) → 184

3₀(24) → 25

3₀(51) → 237

3₀(199) → 200

3₀(104) → 105

3₀(127) → 128

3₀(2) → 88

3₀(252) → 253

3₀(213) → 214

3₀(225) → 226

0₀(31) → 32

0₀(146) → 147

0₀(176) → 177

0₀(70) → 71

0₀(180) → 181

0₀(263) → 264

0₀(121) → 122

0₀(135) → 136

0₀(48) → 49

0₀(93) → 94

0₀(16) → 17

0₀(60) → 100

0₀(20) → 21

0₀(137) → 138

0₀(197) → 198

0₀(55) → 56

0₀(200) → 185

0₀(128) → 129

0₀(273) → 255

0₀(227) → 228

0₀(232) → 233

0₀(139) → 140

0₀(40) → 41

0₀(32) → 33

0₀(61) → 62

0₀(46) → 47

0₀(91) → 92

0₀(260) → 261

0₀(243) → 244

0₀(173) → 174

0₀(217) → 201

0₀(23) → 24

0₀(140) → 141

0₀(214) → 215

0₀(215) → 216

0₀(186) → 202

0₀(119) → 108

0₀(66) → 67

0₀(148) → 149

0₀(111) → 112

0₀(83) → 84

0₀(2) → 28

0₀(3) → 60

0₀(45) → 46

0₀(221) → 222

0₀(170) → 157

0₀(271) → 272

0₀(28) → 109

0₀(264) → 265

0₀(103) → 104

0₀(110) → 111

0₀(196) → 197

0₀(47) → 48

0₀(207) → 208

0₀(158) → 159

0₀(51) → 52

0₀(81) → 82

0₀(57) → 58

0₀(246) → 247

0₀(220) → 221

f6₀ → 2

2₀(2) → 20

2₀(149) → 150

2₀(28) → 43

2₀(117) → 118

2₀(90) → 91

2₀(10) → 11

2₀(184) → 171

2₀(64) → 65

2₀(43) → 44

2₀(4) → 1

2₀(63) → 64

2₀(151) → 152

2₀(272) → 273

2₀(11) → 8

2₀(84) → 85

2₀(118) → 119

2₀(238) → 239

2₀(216) → 217

2₀(241) → 242

2₀(208) → 209

2₀(130) → 131

2₀(33) → 27

2₀(129) → 130

2₀(172) → 173

2₀(75) → 76

2₀(85) → 86

2₀(143) → 133

2₀(97) → 98

2₀(186) → 187

2₀(41) → 34

2₀(44) → 45

2₀(266) → 267

2₀(187) → 188

2₀(219) → 220

2₀(261) → 262

2₀(210) → 211

2₀(69) → 70

2₁(292) → 293

2₁(276) → 277

2₁(288) → 289

2₁(320) → 321

4₁(308) → 309

4₁(304) → 305

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