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

Proof

1 Bounds

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

final states:

{291, 274, 256, 237, 222, 206, 190, 175, 161, 148, 137, 126, 115, 104, 93, 84, 74, 64, 56, 48, 41, 35, 30, 24, 20, 17, 13, 9, 6, 1}

transitions:

274 → 43

274 → 3

84 → 7

145 → 324

41 → 152

41 → 36

41 → 25

9 → 10

319 → 116

175 → 75

175 → 7

20 → 10

1 → 116

1 → 3

13 → 10

222 → 25

161 → 10

6 → 163

54 → 315

237 → 162

93 → 25

104 → 66

104 → 7

30 → 11

30 → 3

137 → 3

64 → 42

64 → 7

35 → 238

35 → 7

115 → 10

256 → 14

256 → 25

48 → 150

48 → 10

17 → 10

190 → 43

190 → 3

148 → 292

148 → 191

148 → 7

74 → 7

24 → 139

24 → 25

56 → 149

56 → 162

327 → 94

291 → 25

f6₀ → 2

5₀(31) → 32

5₀(138) → 139

5₀(132) → 133

5₀(180) → 181

5₀(236) → 222

5₀(261) → 262

5₀(305) → 306

5₀(297) → 298

5₀(155) → 156

5₀(18) → 19

5₀(198) → 199

5₀(273) → 256

5₀(68) → 69

5₀(172) → 173

5₀(278) → 279

5₀(118) → 119

5₀(205) → 190

5₀(188) → 189

5₀(7) → 14

5₀(73) → 64

5₀(22) → 23

5₀(173) → 174

5₀(199) → 200

5₀(214) → 215

5₀(6) → 275

5₀(11) → 12

5₀(127) → 128

5₀(216) → 217

5₀(239) → 240

5₀(49) → 50

5₀(279) → 280

5₀(151) → 152

5₀(162) → 257

5₀(218) → 219

5₀(43) → 44

5₀(2) → 25

5₀(45) → 46

5₀(36) → 37

5₀(170) → 171

5₀(37) → 38

5₀(28) → 29

5₀(29) → 24

5₀(78) → 79

5₀(10) → 36

5₀(47) → 41

5₀(207) → 208

5₀(187) → 188

5₀(100) → 101

5₀(203) → 204

5₀(257) → 258

1₁(325) → 326

2₀(219) → 220

2₀(241) → 242

2₀(23) → 20

2₀(26) → 27

2₀(306) → 307

2₀(123) → 124

2₀(42) → 57

2₀(76) → 77

2₀(14) → 21

2₀(63) → 56

2₀(289) → 290

2₀(59) → 60

2₀(159) → 160

2₀(147) → 137

2₀(86) → 87

2₀(108) → 109

2₀(169) → 170

2₀(58) → 59

2₀(130) → 131

2₀(281) → 282

2₀(217) → 218

2₀(105) → 106

2₀(220) → 221

2₀(134) → 135

2₀(247) → 248

2₀(79) → 80

2₀(152) → 153

2₀(201) → 202

2₀(131) → 132

2₀(109) → 110

2₀(185) → 186

2₀(46) → 47

2₀(268) → 269

2₀(3) → 4

2₀(284) → 285

2₀(121) → 122

2₀(234) → 235

2₀(163) → 164

2₀(25) → 26

2₀(304) → 305

2₀(192) → 193

2₀(80) → 81

2₀(215) → 216

2₀(27) → 28

2₀(21) → 22

2₀(181) → 182

2₀(62) → 63

2₀(133) → 134

2₀(10) → 149

2₀(2) → 162

2₀(302) → 303

2₀(233) → 234

2₀(153) → 154

2₀(157) → 158

4₁(324) → 325

3₀(221) → 206

3₀(51) → 52

3₀(16) → 13

3₀(212) → 213

3₀(209) → 210

3₀(162) → 163

3₀(146) → 147

3₀(210) → 211

3₀(120) → 121

3₀(3) → 94

3₀(251) → 252

3₀(7) → 105

3₀(44) → 45

3₀(129) → 130

3₀(98) → 99

3₀(125) → 115

3₀(32) → 33

3₀(267) → 268

3₀(66) → 67

3₀(8) → 6

3₀(89) → 90

3₀(288) → 289

3₀(238) → 239

3₀(114) → 104

3₀(128) → 129

3₀(82) → 83

3₀(60) → 61

3₀(145) → 146

3₀(136) → 126

3₀(110) → 111

3₀(75) → 76

3₀(204) → 205

3₀(269) → 270

3₀(171) → 172

3₀(81) → 82

3₀(10) → 65

3₀(4) → 49

3₀(191) → 192

3₀(124) → 125

3₀(283) → 284

3₀(225) → 226

3₀(202) → 203

3₀(14) → 15

3₀(116) → 117

3₀(139) → 140

3₀(298) → 299

3₀(85) → 86

3₀(277) → 278

3₀(294) → 295

3₀(282) → 283

3₀(226) → 227

3₀(243) → 244

3₀(232) → 233

0₁(318) → 319

0₁(317) → 318

0₁(315) → 316

1₀(72) → 73

1₀(111) → 112

1₀(228) → 229

1₀(2) → 10

1₀(255) → 237

1₀(295) → 296

1₀(193) → 194

1₀(19) → 17

1₀(249) → 250

1₀(112) → 113

1₀(140) → 141

1₀(242) → 243

1₀(164) → 165

1₀(150) → 151

1₀(12) → 9

1₀(176) → 177

1₀(55) → 48

1₀(270) → 271

1₀(106) → 107

1₀(135) → 136

1₀(296) → 297

1₀(143) → 144

1₀(14) → 31

1₀(265) → 266

1₀(97) → 98

1₀(57) → 58

1₀(107) → 108

1₀(182) → 183

1₀(244) → 245

1₀(197) → 198

1₀(67) → 68

1₀(184) → 185

1₀(39) → 40

1₀(168) → 169

1₀(142) → 143

1₀(178) → 179

1₀(15) → 16

1₀(33) → 34

1₀(248) → 249

1₀(301) → 302

1₀(149) → 150

1₀(196) → 197

1₀(158) → 159

1₀(122) → 123

1₀(7) → 8

0₀(2) → 3

0₀(167) → 168

0₀(177) → 178

0₀(299) → 300

0₀(90) → 91

0₀(10) → 11

0₀(230) → 231

0₀(105) → 138

0₀(54) → 55

0₀(260) → 261

0₀(95) → 96

0₀(99) → 100

0₀(67) → 223

0₀(166) → 167

0₀(252) → 253

0₀(303) → 304

0₀(71) → 72

0₀(25) → 207

0₀(4) → 5

0₀(8) → 18

0₀(61) → 62

0₀(96) → 97

0₀(264) → 265

0₀(11) → 116

0₀(245) → 246

0₀(53) → 54

0₀(141) → 142

0₀(70) → 71

0₀(290) → 274

0₀(52) → 53

0₀(259) → 260

0₀(101) → 102

0₀(195) → 196

0₀(103) → 93

0₀(293) → 294

0₀(42) → 43

0₀(75) → 127

0₀(183) → 184

0₀(174) → 161

0₀(276) → 277

0₀(154) → 155

0₀(186) → 187

0₀(162) → 176

0₀(34) → 30

0₀(266) → 267

0₀(5) → 1

0₀(231) → 232

0₀(77) → 78

0₀(286) → 287

0₀(200) → 201

0₀(194) → 195

0₀(102) → 103

0₀(69) → 70

2₁(316) → 317

3₁(326) → 327

4₀(87) → 88

4₀(238) → 292

4₀(246) → 247

4₀(160) → 148

4₀(287) → 288

4₀(223) → 224

4₀(227) → 228

4₀(88) → 89

4₀(208) → 209

4₀(263) → 264

4₀(50) → 51

4₀(211) → 212

4₀(94) → 95

4₀(117) → 118

4₀(26) → 85

4₀(7) → 191

4₀(275) → 276

4₀(162) → 238

4₀(280) → 281

4₀(10) → 42

4₀(92) → 84

4₀(285) → 286

4₀(156) → 157

4₀(83) → 74

4₀(235) → 236

4₀(307) → 308

4₀(271) → 272

4₀(119) → 120

4₀(40) → 35

4₀(189) → 175

4₀(3) → 75

4₀(165) → 166

4₀(240) → 241

4₀(308) → 309

4₀(224) → 225

4₀(65) → 66

4₀(229) → 230

4₀(292) → 293

4₀(179) → 180

4₀(254) → 255

4₀(250) → 251

4₀(144) → 145

4₀(262) → 263

4₀(38) → 39

4₀(300) → 301

4₀(91) → 92

4₀(253) → 254

4₀(2) → 7

4₀(113) → 114

4₀(272) → 273

4₀(258) → 259

4₀(213) → 214

4₀(309) → 291

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