YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 Bounds

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

final states:

{270, 263, 256, 247, 241, 232, 223, 215, 207, 199, 191, 182, 173, 164, 155, 146, 136, 127, 117, 109, 101, 92, 83, 74, 67, 58, 50, 40, 30, 22, 12, 1}

transitions:

223 → 224

223 → 31

263 → 118

136 → 224

136 → 31

50 → 13

146 → 119

146 → 13

298 → 59

199 → 31

241 → 3

1 → 84

1 → 13

40 → 224

40 → 31

127 → 111

127 → 31

101 → 59

101 → 13

309 → 84

58 → 84

58 → 13

207 → 31

173 → 233

173 → 3

109 → 208

109 → 137

22 → 31

270 → 118

67 → 31

117 → 118

232 → 84

232 → 13

12 → 31

182 → 118

30 → 224

30 → 31

256 → 174

256 → 118

83 → 31

245 → 299

164 → 137

215 → 31

74 → 31

92 → 224

92 → 31

19 → 288

155 → 15

155 → 137

191 → 93

191 → 41

247 → 174

247 → 118

2₁(291) → 292

2₁(301) → 302

2₁(295) → 296

2₁(296) → 297

2₁(307) → 308

4₁(299) → 300

1₁(303) → 304

5₁(290) → 291

5₁(304) → 305

5₀(244) → 245

5₀(190) → 182

5₀(78) → 79

5₀(73) → 67

5₀(37) → 38

5₀(3) → 156

5₀(7) → 8

5₀(86) → 87

5₀(273) → 274

5₀(275) → 276

5₀(268) → 269

5₀(135) → 127

5₀(140) → 141

5₀(18) → 19

5₀(68) → 69

5₀(82) → 74

5₀(201) → 202

5₀(248) → 249

5₀(249) → 250

5₀(119) → 200

5₀(84) → 85

5₀(177) → 178

5₀(62) → 63

5₀(148) → 149

5₀(42) → 51

5₀(269) → 263

5₀(233) → 234

5₀(13) → 174

5₀(107) → 108

5₀(261) → 262

5₀(14) → 23

5₀(2) → 118

5₀(23) → 24

5₀(194) → 195

5₀(152) → 153

5₀(218) → 219

1₀(2) → 31

1₀(231) → 223

1₀(31) → 32

1₀(45) → 46

1₀(159) → 160

1₀(6) → 7

1₀(19) → 20

1₀(110) → 111

1₀(88) → 89

1₀(32) → 33

1₀(98) → 99

1₀(103) → 104

1₀(42) → 43

1₀(266) → 267

1₀(192) → 193

1₀(133) → 134

1₀(144) → 145

1₀(46) → 47

1₀(174) → 175

1₀(224) → 225

1₀(47) → 48

1₀(260) → 261

1₀(60) → 257

1₀(187) → 188

1₀(61) → 242

1₀(203) → 204

1₀(214) → 207

1₀(230) → 231

1₀(210) → 211

1₀(253) → 254

1₀(128) → 129

1₀(195) → 196

1₀(134) → 135

1₀(200) → 271

1₀(265) → 266

1₀(13) → 14

1₀(169) → 170

1₀(118) → 224

1₀(262) → 256

1₀(197) → 198

1₀(138) → 139

1₀(184) → 185

1₀(39) → 30

1₀(38) → 39

1₀(206) → 199

1₀(226) → 227

1₀(252) → 253

1₀(81) → 82

1₀(171) → 172

1₀(239) → 240

1₀(208) → 209

1₀(65) → 66

2₀(33) → 34

2₀(227) → 228

2₀(137) → 138

2₀(245) → 246

2₀(251) → 252

2₀(108) → 101

2₀(166) → 167

2₀(118) → 119

2₀(51) → 52

2₀(179) → 180

2₀(132) → 133

2₀(112) → 113

2₀(105) → 106

2₀(143) → 144

2₀(168) → 169

2₀(60) → 61

2₀(158) → 159

2₀(55) → 56

2₀(129) → 130

2₀(56) → 57

2₀(3) → 84

2₀(104) → 105

2₀(255) → 247

2₀(154) → 146

2₀(161) → 162

2₀(72) → 73

2₀(102) → 103

2₀(189) → 190

2₀(193) → 194

2₀(15) → 16

2₀(21) → 12

2₀(31) → 59

2₀(119) → 120

2₀(10) → 11

2₀(2) → 13

2₀(4) → 5

2₀(153) → 154

2₀(24) → 25

2₀(89) → 90

2₀(186) → 187

4₀(125) → 126

4₀(17) → 18

4₀(246) → 241

4₀(142) → 143

4₀(99) → 100

4₀(123) → 124

4₀(237) → 238

4₀(222) → 215

4₀(44) → 45

4₀(36) → 37

4₀(4) → 110

4₀(28) → 29

4₀(20) → 21

4₀(181) → 173

4₀(149) → 150

4₀(3) → 147

4₀(80) → 81

4₀(31) → 233

4₀(70) → 71

4₀(137) → 165

4₀(229) → 230

4₀(150) → 151

4₀(163) → 155

4₀(175) → 176

4₀(121) → 122

4₀(185) → 186

4₀(250) → 251

4₀(131) → 132

4₀(204) → 205

4₀(2) → 3

4₀(272) → 273

4₀(221) → 222

4₀(225) → 226

3₀(267) → 268

3₀(235) → 236

3₀(90) → 91

3₀(59) → 60

3₀(48) → 49

3₀(93) → 94

3₀(16) → 17

3₀(96) → 97

3₀(137) → 183

3₀(53) → 54

3₀(79) → 80

3₀(200) → 201

3₀(118) → 128

3₀(97) → 98

3₀(95) → 96

3₀(157) → 158

3₀(94) → 95

3₀(120) → 121

3₀(61) → 62

3₀(91) → 83

3₀(243) → 244

3₀(114) → 115

3₀(183) → 184

3₀(212) → 213

3₀(84) → 208

3₀(14) → 15

3₀(63) → 64

3₀(49) → 40

3₀(162) → 163

3₀(111) → 112

3₀(2) → 137

3₀(228) → 229

3₀(26) → 27

3₀(41) → 75

3₀(170) → 171

3₀(122) → 123

3₀(35) → 36

3₀(116) → 109

3₀(264) → 265

3₀(29) → 22

3₀(276) → 270

3₀(259) → 260

3₀(115) → 116

3₀(178) → 179

3₀(219) → 220

3₀(100) → 92

3₀(209) → 210

3₀(220) → 221

f6₀ → 2

0₀(2) → 41

0₀(167) → 168

0₀(274) → 275

0₀(196) → 197

0₀(156) → 157

0₀(9) → 10

0₀(257) → 258

0₀(258) → 259

0₀(271) → 272

0₀(175) → 264

0₀(54) → 55

0₀(202) → 203

0₀(213) → 214

0₀(64) → 65

0₀(113) → 114

0₀(71) → 72

0₀(25) → 26

0₀(217) → 218

0₀(43) → 44

0₀(8) → 9

0₀(124) → 125

0₀(234) → 235

0₀(236) → 237

0₀(151) → 152

0₀(76) → 77

0₀(254) → 255

0₀(3) → 4

0₀(11) → 1

0₀(147) → 148

0₀(14) → 192

0₀(87) → 88

0₀(211) → 212

0₀(176) → 177

0₀(141) → 142

0₀(66) → 58

0₀(238) → 239

0₀(198) → 191

0₀(23) → 68

0₀(216) → 217

0₀(139) → 140

0₀(130) → 131

0₀(180) → 181

0₀(27) → 28

0₀(165) → 166

0₀(52) → 53

0₀(240) → 232

0₀(205) → 206

0₀(172) → 164

0₀(42) → 102

0₀(75) → 76

0₀(85) → 86

0₀(126) → 117

0₀(57) → 50

0₀(34) → 35

0₀(41) → 42

0₀(242) → 243

0₀(188) → 189

0₀(31) → 93

0₀(5) → 6

0₀(145) → 136

0₀(106) → 107

0₀(77) → 78

0₀(13) → 248

0₀(160) → 161

0₀(119) → 216

0₀(69) → 70

3₁(293) → 294

0₁(308) → 309

0₁(305) → 306

0₁(306) → 307

0₁(300) → 301

0₁(294) → 295

0₁(289) → 290

0₁(292) → 293

0₁(297) → 298

0₁(302) → 303

0₁(288) → 289

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