YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 Bounds

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

final states:

{263, 246, 228, 211, 193, 175, 156, 139, 125, 110, 96, 81, 67, 59, 52, 44, 38, 34, 29, 25, 21, 15, 10, 6, 1}

transitions:

25 → 39

25 → 264

29 → 3

263 → 212

263 → 3

81 → 17

81 → 264

10 → 264

15 → 53

15 → 68

96 → 140

96 → 16

211 → 60

211 → 16

59 → 140

59 → 16

110 → 27

110 → 264

34 → 18

34 → 11

175 → 68

193 → 26

193 → 68

246 → 26

246 → 68

1 → 68

139 → 264

44 → 140

44 → 16

125 → 39

125 → 264

38 → 17

38 → 264

21 → 11

6 → 11

52 → 142

52 → 4

52 → 264

67 → 68

228 → 264

156 → 3

3₀(189) → 190

3₀(74) → 75

3₀(16) → 17

3₀(180) → 181

3₀(203) → 204

3₀(245) → 228

3₀(141) → 142

3₀(278) → 279

3₀(200) → 201

3₀(146) → 147

3₀(3) → 4

3₀(7) → 39

3₀(280) → 281

3₀(240) → 241

3₀(224) → 225

3₀(32) → 33

3₀(207) → 208

3₀(66) → 59

3₀(231) → 232

3₀(58) → 52

3₀(121) → 122

3₀(61) → 62

3₀(275) → 276

3₀(26) → 27

3₀(93) → 94

3₀(135) → 136

3₀(134) → 135

3₀(138) → 125

3₀(142) → 143

3₀(155) → 139

3₀(18) → 19

3₀(208) → 209

3₀(70) → 71

3₀(60) → 61

3₀(145) → 146

3₀(119) → 120

3₀(84) → 85

3₀(262) → 246

3₀(136) → 137

3₀(126) → 127

3₀(233) → 234

3₀(191) → 192

3₀(122) → 123

3₀(2) → 264

3₀(226) → 227

3₀(153) → 154

3₀(218) → 219

3₀(188) → 189

4₀(2) → 3

4₀(186) → 187

4₀(88) → 89

4₀(16) → 82

4₀(50) → 51

4₀(234) → 235

4₀(4) → 176

4₀(115) → 116

4₀(112) → 113

4₀(174) → 156

4₀(76) → 77

4₀(140) → 141

4₀(232) → 233

4₀(150) → 151

4₀(89) → 90

4₀(260) → 261

4₀(258) → 259

4₀(214) → 215

4₀(172) → 173

4₀(253) → 254

4₀(183) → 184

4₀(163) → 164

4₀(154) → 155

4₀(79) → 80

4₀(131) → 132

4₀(221) → 222

4₀(39) → 40

4₀(168) → 169

4₀(259) → 260

4₀(206) → 207

4₀(166) → 167

4₀(271) → 272

4₀(33) → 29

4₀(3) → 212

4₀(252) → 253

4₀(75) → 76

4₀(101) → 102

4₀(40) → 41

2₀(227) → 211

2₀(151) → 152

2₀(124) → 110

2₀(148) → 149

2₀(23) → 24

2₀(73) → 74

2₀(225) → 226

2₀(239) → 240

2₀(165) → 166

2₀(279) → 280

2₀(91) → 92

2₀(159) → 160

2₀(212) → 213

2₀(178) → 179

2₀(217) → 218

2₀(51) → 44

2₀(105) → 106

2₀(11) → 111

2₀(167) → 168

2₀(220) → 221

2₀(277) → 278

2₀(247) → 248

2₀(43) → 38

2₀(107) → 108

2₀(77) → 78

2₀(187) → 188

2₀(152) → 153

2₀(120) → 121

2₀(201) → 202

2₀(176) → 177

2₀(202) → 203

2₀(209) → 210

2₀(268) → 269

2₀(195) → 196

2₀(274) → 275

2₀(3) → 140

2₀(249) → 250

2₀(64) → 65

2₀(264) → 265

2₀(113) → 114

2₀(111) → 194

2₀(12) → 13

2₀(161) → 162

2₀(94) → 95

2₀(80) → 67

2₀(215) → 216

2₀(27) → 28

2₀(223) → 224

2₀(117) → 118

2₀(181) → 182

2₀(71) → 72

2₀(133) → 134

2₀(103) → 104

2₀(2) → 16

2₀(269) → 270

2₀(4) → 5

2₀(237) → 238

2₀(68) → 97

2₀(254) → 255

2₀(157) → 158

2₀(16) → 60

1₀(87) → 88

1₀(238) → 239

1₀(17) → 18

1₀(171) → 172

1₀(78) → 79

1₀(82) → 83

1₀(169) → 170

1₀(11) → 12

1₀(242) → 243

1₀(241) → 242

1₀(198) → 199

1₀(196) → 197

1₀(4) → 35

1₀(7) → 30

1₀(90) → 91

1₀(162) → 163

1₀(147) → 148

1₀(248) → 249

1₀(9) → 6

1₀(149) → 150

1₀(194) → 195

1₀(251) → 252

1₀(273) → 274

1₀(16) → 22

1₀(31) → 32

1₀(197) → 198

1₀(158) → 159

1₀(57) → 58

1₀(24) → 21

1₀(205) → 206

1₀(130) → 131

1₀(37) → 34

1₀(127) → 128

1₀(265) → 266

1₀(2) → 11

1₀(272) → 273

1₀(266) → 267

5₀(184) → 185

5₀(235) → 236

5₀(123) → 124

5₀(132) → 133

5₀(236) → 237

5₀(261) → 262

5₀(16) → 45

5₀(60) → 157

5₀(229) → 230

5₀(65) → 66

5₀(137) → 138

5₀(53) → 54

5₀(185) → 186

5₀(72) → 73

5₀(55) → 56

5₀(128) → 129

5₀(68) → 69

5₀(97) → 98

5₀(95) → 81

5₀(270) → 271

5₀(19) → 20

5₀(98) → 99

5₀(92) → 93

5₀(250) → 251

5₀(190) → 191

5₀(243) → 244

5₀(222) → 223

5₀(199) → 200

5₀(69) → 70

5₀(42) → 43

5₀(109) → 96

5₀(11) → 126

5₀(62) → 63

5₀(213) → 214

5₀(85) → 86

5₀(4) → 229

5₀(14) → 10

5₀(256) → 257

5₀(111) → 112

5₀(177) → 178

5₀(2) → 7

5₀(30) → 31

5₀(170) → 171

5₀(129) → 130

5₀(35) → 36

5₀(116) → 117

5₀(8) → 9

5₀(210) → 193

5₀(164) → 165

5₀(102) → 103

5₀(158) → 247

5₀(86) → 87

5₀(204) → 205

5₀(160) → 161

5₀(257) → 258

f6₀ → 2

0₀(2) → 68

0₀(114) → 115

0₀(46) → 47

0₀(28) → 25

0₀(56) → 57

0₀(230) → 231

0₀(49) → 50

0₀(54) → 55

0₀(48) → 49

0₀(99) → 100

0₀(255) → 256

0₀(36) → 37

0₀(63) → 64

0₀(104) → 105

0₀(244) → 245

0₀(281) → 263

0₀(3) → 26

0₀(11) → 53

0₀(192) → 175

0₀(83) → 84

0₀(100) → 101

0₀(118) → 119

0₀(216) → 217

0₀(173) → 174

0₀(7) → 8

0₀(267) → 268

0₀(45) → 46

0₀(22) → 23

0₀(20) → 15

0₀(276) → 277

0₀(143) → 144

0₀(108) → 109

0₀(41) → 42

0₀(219) → 220

0₀(5) → 1

0₀(144) → 145

0₀(106) → 107

0₀(179) → 180

0₀(13) → 14

0₀(47) → 48

0₀(182) → 183

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