YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 Bounds

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

final states:

{283, 274, 266, 257, 248, 241, 232, 223, 214, 206, 198, 189, 180, 171, 163, 155, 147, 140, 131, 122, 112, 104, 94, 85, 76, 66, 57, 48, 39, 32, 22, 12, 1}

transitions:

223 → 67

32 → 23

214 → 67

274 → 23

122 → 68

122 → 95

39 → 13

57 → 190

57 → 3

147 → 49

147 → 3

241 → 67

1 → 67

76 → 14

76 → 67

248 → 233

248 → 67

257 → 113

171 → 3

22 → 67

283 → 23

180 → 172

180 → 3

232 → 67

66 → 190

66 → 3

12 → 164

12 → 3

85 → 215

85 → 113

112 → 23

104 → 86

104 → 113

140 → 13

189 → 164

189 → 3

48 → 13

198 → 3

206 → 190

206 → 3

131 → 258

131 → 13

266 → 215

266 → 113

163 → 49

163 → 3

155 → 49

155 → 3

94 → 215

94 → 113

f6₀ → 2

4₀(31) → 22

4₀(179) → 171

4₀(263) → 264

4₀(261) → 262

4₀(16) → 17

4₀(96) → 97

4₀(20) → 21

4₀(265) → 257

4₀(273) → 266

4₀(227) → 228

4₀(95) → 96

4₀(34) → 35

4₀(258) → 259

4₀(250) → 251

4₀(61) → 62

4₀(242) → 243

4₀(173) → 174

4₀(114) → 115

4₀(183) → 184

4₀(23) → 249

4₀(269) → 270

4₀(84) → 76

4₀(182) → 183

4₀(216) → 217

4₀(239) → 240

4₀(82) → 83

4₀(111) → 104

4₀(2) → 95

4₀(3) → 181

4₀(45) → 46

4₀(41) → 42

4₀(75) → 66

4₀(208) → 209

4₀(115) → 141

4₀(272) → 273

4₀(226) → 227

4₀(254) → 255

4₀(67) → 68

4₀(100) → 101

4₀(81) → 82

4₀(159) → 160

3₀(33) → 34

3₀(151) → 152

3₀(126) → 127

3₀(23) → 77

3₀(165) → 166

3₀(260) → 261

3₀(218) → 219

3₀(123) → 124

3₀(91) → 92

3₀(252) → 253

3₀(30) → 31

3₀(289) → 290

3₀(108) → 109

3₀(7) → 8

3₀(281) → 282

3₀(51) → 52

3₀(8) → 9

3₀(132) → 133

3₀(210) → 211

3₀(262) → 263

3₀(99) → 100

3₀(38) → 32

3₀(167) → 168

3₀(60) → 61

3₀(187) → 188

3₀(149) → 150

3₀(158) → 159

3₀(176) → 177

3₀(185) → 186

3₀(88) → 89

3₀(90) → 91

3₀(282) → 274

3₀(3) → 40

3₀(249) → 250

3₀(47) → 39

3₀(271) → 272

3₀(175) → 176

3₀(40) → 41

3₀(286) → 287

3₀(121) → 112

3₀(113) → 114

3₀(288) → 289

3₀(101) → 102

3₀(83) → 84

3₀(275) → 276

3₀(15) → 16

3₀(287) → 288

3₀(13) → 275

3₀(62) → 63

3₀(5) → 33

3₀(2) → 23

3₀(233) → 234

3₀(290) → 283

3₀(237) → 238

3₀(68) → 69

3₀(211) → 212

3₀(89) → 90

3₀(52) → 53

1₀(244) → 245

1₀(137) → 138

1₀(169) → 170

1₀(209) → 210

1₀(193) → 194

1₀(195) → 196

1₀(125) → 126

1₀(77) → 156

1₀(231) → 223

1₀(24) → 284

1₀(50) → 51

1₀(128) → 129

1₀(113) → 233

1₀(59) → 60

1₀(6) → 7

1₀(247) → 241

1₀(161) → 162

1₀(97) → 98

1₀(13) → 14

1₀(2) → 67

1₀(23) → 58

1₀(69) → 70

5₀(109) → 110

5₀(2) → 13

5₀(95) → 258

5₀(120) → 121

5₀(102) → 103

5₀(152) → 153

5₀(113) → 123

5₀(186) → 187

5₀(201) → 202

5₀(157) → 158

5₀(103) → 94

5₀(87) → 88

5₀(192) → 193

5₀(4) → 5

5₀(46) → 47

5₀(77) → 78

5₀(243) → 244

5₀(280) → 281

5₀(150) → 151

5₀(70) → 71

5₀(207) → 242

5₀(270) → 271

5₀(106) → 107

5₀(181) → 182

5₀(238) → 239

5₀(23) → 24

5₀(217) → 218

5₀(56) → 48

5₀(200) → 201

5₀(139) → 131

5₀(107) → 108

5₀(63) → 64

5₀(236) → 237

5₀(116) → 117

5₀(184) → 185

5₀(259) → 260

5₀(166) → 167

5₀(49) → 50

5₀(146) → 140

5₀(130) → 122

5₀(86) → 148

5₀(29) → 30

5₀(194) → 195

5₀(5) → 6

5₀(153) → 154

2₀(2) → 113

2₀(177) → 178

2₀(9) → 10

2₀(224) → 225

2₀(133) → 134

2₀(134) → 135

2₀(10) → 11

2₀(230) → 231

2₀(197) → 189

2₀(105) → 106

2₀(54) → 55

2₀(110) → 111

2₀(277) → 278

2₀(98) → 99

2₀(213) → 206

2₀(95) → 215

2₀(64) → 65

2₀(19) → 20

2₀(225) → 226

2₀(255) → 256

2₀(113) → 224

2₀(36) → 37

2₀(215) → 216

2₀(235) → 236

2₀(55) → 56

2₀(220) → 221

2₀(71) → 72

2₀(43) → 44

2₀(92) → 93

2₀(21) → 12

2₀(124) → 125

2₀(26) → 27

2₀(37) → 38

2₀(222) → 214

2₀(74) → 75

2₀(178) → 179

2₀(96) → 267

2₀(3) → 4

2₀(264) → 265

2₀(17) → 18

2₀(11) → 1

2₀(245) → 246

2₀(118) → 119

2₀(141) → 142

2₀(136) → 137

2₀(132) → 207

2₀(221) → 222

2₀(27) → 28

2₀(35) → 36

2₀(267) → 268

2₀(205) → 198

2₀(127) → 128

2₀(40) → 105

2₀(276) → 277

2₀(143) → 144

2₀(142) → 143

2₀(212) → 213

2₀(44) → 45

2₀(253) → 254

2₀(285) → 286

2₀(219) → 220

2₀(190) → 191

2₀(145) → 146

2₀(144) → 145

2₀(199) → 200

2₀(13) → 86

2₀(115) → 116

2₀(160) → 161

2₀(207) → 208

2₀(119) → 120

2₀(168) → 169

0₀(170) → 163

0₀(25) → 26

0₀(42) → 43

0₀(191) → 192

0₀(246) → 247

0₀(135) → 136

0₀(78) → 79

0₀(279) → 280

0₀(58) → 59

0₀(164) → 165

0₀(278) → 279

0₀(203) → 204

0₀(172) → 173

0₀(86) → 87

0₀(53) → 54

0₀(129) → 130

0₀(117) → 118

0₀(96) → 199

0₀(202) → 203

0₀(196) → 197

0₀(28) → 29

0₀(13) → 190

0₀(284) → 285

0₀(162) → 155

0₀(93) → 85

0₀(234) → 235

0₀(148) → 149

0₀(156) → 157

0₀(72) → 73

0₀(251) → 252

0₀(154) → 147

0₀(14) → 15

0₀(256) → 248

0₀(3) → 49

0₀(80) → 81

0₀(240) → 232

0₀(65) → 57

0₀(229) → 230

0₀(138) → 139

0₀(18) → 19

0₀(79) → 80

0₀(24) → 25

0₀(228) → 229

0₀(23) → 172

0₀(174) → 175

0₀(68) → 164

0₀(268) → 269

0₀(188) → 180

0₀(204) → 205

0₀(2) → 3

0₀(113) → 132

0₀(73) → 74

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