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

Proof

1 Bounds

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

final states:

{274, 255, 237, 218, 201, 181, 167, 152, 140, 124, 113, 101, 89, 78, 68, 60, 50, 40, 31, 26, 18, 12, 9, 5, 1}

transitions:

78 → 41

89 → 71

89 → 61

89 → 3

152 → 6

274 → 4

274 → 6

181 → 79

167 → 80

167 → 6

18 → 219

18 → 51

50 → 51

218 → 182

218 → 41

9 → 4

9 → 6

5 → 202

5 → 3

255 → 41

20 → 297

31 → 51

1 → 41

40 → 125

40 → 41

101 → 79

60 → 51

26 → 13

201 → 13

124 → 79

237 → 90

237 → 79

300 → 24

12 → 3

140 → 13

113 → 13

68 → 79

f6₀ → 2

4₀(146) → 147

4₀(59) → 50

4₀(123) → 113

4₀(132) → 133

4₀(147) → 148

4₀(77) → 68

4₀(79) → 90

4₀(198) → 199

4₀(172) → 173

4₀(278) → 279

4₀(232) → 233

4₀(98) → 99

4₀(169) → 170

4₀(92) → 93

4₀(238) → 275

4₀(211) → 212

4₀(114) → 115

4₀(6) → 69

4₀(109) → 110

4₀(252) → 253

4₀(66) → 67

4₀(71) → 72

4₀(76) → 77

4₀(63) → 64

4₀(148) → 149

4₀(240) → 241

4₀(177) → 178

4₀(2) → 79

4₀(170) → 171

4₀(231) → 232

4₀(271) → 272

4₀(168) → 169

4₀(129) → 130

4₀(122) → 123

4₀(28) → 29

4₀(208) → 209

4₀(108) → 109

4₀(161) → 162

4₀(276) → 277

4₀(134) → 135

4₀(33) → 34

4₀(234) → 235

4₀(15) → 16

4₀(25) → 18

4₀(57) → 58

4₀(209) → 210

4₀(141) → 142

4₀(112) → 101

2₀(244) → 245

2₀(219) → 220

2₀(241) → 242

2₀(126) → 127

2₀(206) → 207

2₀(150) → 151

2₀(272) → 273

2₀(41) → 42

2₀(216) → 217

2₀(270) → 271

2₀(250) → 251

2₀(251) → 252

2₀(160) → 161

2₀(37) → 38

2₀(19) → 153

2₀(86) → 87

2₀(118) → 119

2₀(130) → 131

2₀(174) → 175

2₀(45) → 46

2₀(267) → 268

2₀(105) → 106

2₀(11) → 9

2₀(143) → 144

2₀(203) → 204

2₀(79) → 80

2₀(187) → 188

2₀(120) → 121

2₀(242) → 243

2₀(258) → 259

2₀(194) → 195

2₀(185) → 186

2₀(90) → 91

2₀(282) → 283

2₀(238) → 239

2₀(3) → 4

2₀(249) → 250

2₀(243) → 244

2₀(284) → 285

2₀(69) → 114

2₀(264) → 265

2₀(111) → 112

2₀(163) → 164

2₀(145) → 146

2₀(184) → 185

2₀(196) → 197

2₀(192) → 193

2₀(83) → 84

2₀(102) → 141

2₀(27) → 28

2₀(20) → 21

2₀(115) → 116

2₀(135) → 136

2₀(13) → 19

2₀(74) → 75

2₀(53) → 54

2₀(246) → 247

2₀(2) → 6

2₀(4) → 32

2₀(214) → 215

2₀(186) → 187

2₀(52) → 256

3₀(51) → 238

3₀(175) → 176

3₀(137) → 138

3₀(46) → 47

3₀(166) → 152

3₀(292) → 274

3₀(210) → 211

3₀(158) → 159

3₀(3) → 61

3₀(280) → 281

3₀(121) → 122

3₀(8) → 5

3₀(80) → 81

3₀(87) → 88

3₀(285) → 286

3₀(215) → 216

3₀(228) → 229

3₀(29) → 30

3₀(133) → 134

3₀(142) → 143

3₀(64) → 65

3₀(82) → 83

3₀(70) → 71

3₀(99) → 100

3₀(248) → 249

3₀(6) → 7

3₀(79) → 202

3₀(136) → 137

3₀(72) → 73

3₀(102) → 103

3₀(269) → 270

3₀(171) → 172

3₀(233) → 234

3₀(55) → 56

3₀(97) → 98

3₀(13) → 14

3₀(10) → 11

3₀(220) → 221

3₀(117) → 118

3₀(283) → 284

3₀(225) → 226

3₀(14) → 15

3₀(182) → 183

3₀(2) → 3

3₀(263) → 264

3₀(164) → 165

3₀(85) → 86

3₀(176) → 177

3₀(266) → 267

3₀(17) → 12

3₀(69) → 70

3₀(156) → 157

3₀(100) → 89

3₀(38) → 39

3₀(153) → 154

3₀(188) → 189

0₁(299) → 300

1₀(2) → 51

1₀(235) → 236

1₀(21) → 22

1₀(95) → 96

1₀(6) → 219

1₀(261) → 262

1₀(51) → 52

1₀(157) → 158

1₀(202) → 203

1₀(32) → 33

1₀(247) → 248

1₀(103) → 104

1₀(24) → 25

1₀(119) → 120

1₀(190) → 191

1₀(223) → 224

1₀(106) → 107

1₀(287) → 288

1₀(279) → 280

1₀(253) → 254

1₀(36) → 37

1₀(125) → 126

1₀(183) → 184

1₀(128) → 129

1₀(195) → 196

1₀(212) → 213

1₀(200) → 181

1₀(139) → 124

1₀(107) → 108

1₀(257) → 258

1₀(262) → 263

1₀(197) → 198

1₀(138) → 139

1₀(67) → 60

1₀(39) → 31

1₀(204) → 205

1₀(189) → 190

1₀(94) → 95

1₀(7) → 8

1₀(35) → 36

0₀(2) → 41

0₀(56) → 57

0₀(91) → 92

0₀(224) → 225

0₀(288) → 289

0₀(65) → 66

0₀(49) → 40

0₀(48) → 49

0₀(191) → 192

0₀(19) → 20

0₀(291) → 292

0₀(131) → 132

0₀(43) → 168

0₀(4) → 1

0₀(159) → 160

0₀(236) → 218

0₀(104) → 105

0₀(254) → 237

0₀(178) → 179

0₀(281) → 282

0₀(3) → 182

0₀(14) → 102

0₀(245) → 246

0₀(256) → 257

0₀(62) → 63

0₀(23) → 24

0₀(81) → 82

0₀(290) → 291

0₀(52) → 53

0₀(93) → 94

0₀(22) → 23

0₀(205) → 206

0₀(75) → 76

0₀(289) → 290

0₀(73) → 74

0₀(268) → 269

0₀(229) → 230

0₀(16) → 17

0₀(144) → 145

0₀(286) → 287

0₀(179) → 180

0₀(13) → 125

0₀(88) → 78

0₀(273) → 255

0₀(116) → 117

2₁(298) → 299

3₁(297) → 298

5₀(42) → 43

5₀(277) → 278

5₀(47) → 48

5₀(58) → 59

5₀(227) → 228

5₀(151) → 140

5₀(61) → 62

5₀(222) → 223

5₀(230) → 231

5₀(44) → 45

5₀(260) → 261

5₀(96) → 97

5₀(226) → 227

5₀(54) → 55

5₀(84) → 85

5₀(43) → 44

5₀(275) → 276

5₀(207) → 208

5₀(162) → 163

5₀(239) → 240

5₀(10) → 27

5₀(155) → 156

5₀(149) → 150

5₀(193) → 194

5₀(154) → 155

5₀(3) → 10

5₀(165) → 166

5₀(217) → 201

5₀(30) → 26

5₀(34) → 35

5₀(110) → 111

5₀(173) → 174

5₀(180) → 167

5₀(199) → 200

5₀(259) → 260

5₀(127) → 128

5₀(265) → 266

5₀(2) → 13

5₀(221) → 222

5₀(213) → 214

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