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

Proof

1 Bounds

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

final states:

{272, 252, 235, 214, 199, 185, 169, 154, 141, 128, 115, 104, 93, 81, 72, 63, 54, 46, 40, 33, 25, 19, 14, 8, 1}

transitions:

272 → 55

33 → 15

25 → 16

25 → 26

128 → 155

128 → 41

128 → 215

81 → 10

81 → 15

214 → 41

214 → 215

199 → 3

185 → 55

1 → 27

1 → 26

40 → 3

8 → 216

8 → 9

235 → 216

235 → 9

72 → 16

72 → 26

141 → 57

141 → 215

54 → 15

252 → 18

252 → 55

14 → 55

93 → 73

93 → 215

63 → 55

169 → 26

104 → 215

46 → 170

46 → 26

115 → 253

115 → 26

154 → 9

19 → 15

3₀(221) → 222

3₀(279) → 280

3₀(244) → 245

3₀(175) → 176

3₀(74) → 75

3₀(180) → 181

3₀(11) → 12

3₀(183) → 184

3₀(209) → 210

3₀(157) → 200

3₀(41) → 42

3₀(193) → 194

3₀(222) → 223

3₀(91) → 92

3₀(275) → 276

3₀(26) → 94

3₀(50) → 51

3₀(268) → 269

3₀(286) → 287

3₀(256) → 257

3₀(215) → 216

3₀(238) → 239

3₀(142) → 143

3₀(155) → 156

3₀(64) → 65

3₀(9) → 47

3₀(118) → 119

3₀(70) → 71

3₀(83) → 84

3₀(198) → 185

3₀(60) → 61

3₀(96) → 97

3₀(136) → 137

3₀(126) → 127

3₀(4) → 5

3₀(2) → 9

3₀(23) → 24

3₀(147) → 148

3₀(223) → 224

3₀(192) → 193

3₀(34) → 35

3₀(264) → 265

3₀(219) → 220

4₀(213) → 199

4₀(2) → 3

4₀(78) → 79

4₀(231) → 232

4₀(225) → 226

4₀(152) → 153

4₀(157) → 158

4₀(88) → 89

4₀(202) → 203

4₀(249) → 250

4₀(162) → 163

4₀(98) → 99

4₀(87) → 88

4₀(112) → 113

4₀(283) → 284

4₀(267) → 268

4₀(260) → 261

4₀(230) → 231

4₀(9) → 82

4₀(143) → 144

4₀(277) → 278

4₀(27) → 28

4₀(163) → 164

4₀(217) → 218

4₀(56) → 105

4₀(134) → 135

4₀(200) → 201

4₀(265) → 266

4₀(97) → 98

4₀(276) → 277

4₀(257) → 258

4₀(116) → 117

4₀(131) → 132

4₀(170) → 171

4₀(66) → 67

4₀(38) → 39

4₀(206) → 207

4₀(178) → 179

4₀(49) → 50

4₀(130) → 131

4₀(86) → 87

4₀(3) → 4

4₀(43) → 44

4₀(246) → 247

4₀(5) → 186

4₀(35) → 36

2₀(106) → 107

2₀(280) → 281

2₀(151) → 152

2₀(124) → 125

2₀(177) → 178

2₀(165) → 166

2₀(26) → 41

2₀(42) → 43

2₀(76) → 77

2₀(30) → 31

2₀(59) → 60

2₀(160) → 161

2₀(37) → 38

2₀(108) → 109

2₀(281) → 282

2₀(205) → 206

2₀(174) → 175

2₀(132) → 133

2₀(210) → 211

2₀(262) → 263

2₀(105) → 106

2₀(168) → 154

2₀(187) → 188

2₀(110) → 111

2₀(120) → 121

2₀(176) → 177

2₀(194) → 195

2₀(55) → 56

2₀(56) → 57

2₀(263) → 264

2₀(82) → 83

2₀(3) → 129

2₀(243) → 244

2₀(234) → 214

2₀(140) → 128

2₀(9) → 64

2₀(232) → 233

2₀(191) → 192

2₀(236) → 237

2₀(208) → 209

2₀(102) → 103

2₀(15) → 73

2₀(27) → 155

2₀(135) → 136

2₀(53) → 46

2₀(117) → 118

2₀(31) → 32

2₀(5) → 6

2₀(67) → 68

2₀(10) → 11

2₀(2) → 215

2₀(233) → 234

2₀(153) → 141

2₀(229) → 230

2₀(254) → 255

2₀(171) → 172

2₀(22) → 23

2₀(52) → 53

2₀(190) → 191

5₀(125) → 126

5₀(17) → 18

5₀(47) → 142

5₀(58) → 59

5₀(237) → 238

5₀(211) → 212

5₀(129) → 130

5₀(282) → 283

5₀(69) → 70

5₀(36) → 37

5₀(241) → 242

5₀(146) → 147

5₀(84) → 85

5₀(90) → 91

5₀(13) → 8

5₀(220) → 221

5₀(285) → 286

5₀(167) → 168

5₀(181) → 182

5₀(89) → 90

5₀(9) → 34

5₀(182) → 183

5₀(189) → 190

5₀(240) → 241

5₀(133) → 134

5₀(261) → 262

5₀(224) → 225

5₀(158) → 159

5₀(173) → 174

5₀(18) → 14

5₀(247) → 248

5₀(85) → 86

5₀(109) → 110

5₀(212) → 213

5₀(12) → 13

5₀(253) → 254

5₀(2) → 55

5₀(73) → 116

5₀(266) → 267

1₀(274) → 275

1₀(123) → 124

1₀(121) → 122

1₀(16) → 17

1₀(99) → 100

1₀(77) → 78

1₀(156) → 157

1₀(20) → 21

1₀(137) → 138

1₀(79) → 80

1₀(68) → 69

1₀(24) → 19

1₀(166) → 167

1₀(172) → 173

1₀(21) → 22

1₀(95) → 96

1₀(139) → 140

1₀(270) → 271

1₀(92) → 81

1₀(258) → 259

1₀(73) → 74

1₀(250) → 251

1₀(61) → 62

1₀(242) → 243

1₀(9) → 10

1₀(114) → 104

1₀(251) → 235

1₀(145) → 146

1₀(186) → 187

1₀(62) → 54

1₀(119) → 120

1₀(71) → 63

1₀(239) → 240

1₀(148) → 149

1₀(245) → 246

1₀(113) → 114

1₀(2) → 15

1₀(45) → 40

1₀(271) → 252

1₀(44) → 45

1₀(287) → 288

1₀(29) → 30

1₀(149) → 150

1₀(164) → 165

1₀(101) → 102

1₀(288) → 289

1₀(226) → 227

1₀(196) → 197

1₀(39) → 33

1₀(195) → 196

1₀(150) → 151

1₀(159) → 160

1₀(203) → 204

1₀(248) → 249

f6₀ → 2

0₀(2) → 26

0₀(51) → 52

0₀(28) → 29

0₀(227) → 228

0₀(9) → 253

0₀(65) → 66

0₀(204) → 205

0₀(10) → 273

0₀(184) → 169

0₀(197) → 198

0₀(48) → 49

0₀(80) → 72

0₀(255) → 256

0₀(107) → 108

0₀(4) → 236

0₀(26) → 27

0₀(138) → 139

0₀(3) → 20

0₀(284) → 285

0₀(6) → 7

0₀(218) → 219

0₀(100) → 101

0₀(94) → 95

0₀(216) → 217

0₀(32) → 25

0₀(111) → 112

0₀(161) → 162

0₀(269) → 270

0₀(228) → 229

0₀(7) → 1

0₀(15) → 16

0₀(259) → 260

0₀(129) → 170

0₀(103) → 93

0₀(127) → 115

0₀(75) → 76

0₀(201) → 202

0₀(289) → 272

0₀(57) → 58

0₀(278) → 279

0₀(188) → 189

0₀(144) → 145

0₀(179) → 180

0₀(273) → 274

0₀(207) → 208

0₀(122) → 123

0₀(47) → 48

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