YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 String Reversal

Since only unary symbols occur, one can reverse all terms and obtains the TRS

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

1.1 Bounds

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

final states:

{256, 250, 241, 232, 224, 217, 208, 199, 192, 183, 175, 167, 159, 151, 142, 133, 124, 115, 106, 97, 88, 79, 69, 59, 49, 39, 29, 21, 12, 1}

transitions:

239 → 309

29 → 70

97 → 60

167 → 30

133 → 60

39 → 70

219 → 265

59 → 70

199 → 70

275 → 221

319 → 232

241 → 71

241 → 30

175 → 60

224 → 60

49 → 70

1 → 70

183 → 70

79 → 3

208 → 61

208 → 40

21 → 60

88 → 50

308 → 264

124 → 134

124 → 3

232 → 185

232 → 125

232 → 60

106 → 70

12 → 70

217 → 233

217 → 60

69 → 60

115 → 13

115 → 50

256 → 50

250 → 50

159 → 61

159 → 40

142 → 70

151 → 60

262 → 298

192 → 70

1₁(313) → 314

1₁(316) → 317

1₁(306) → 307

1₁(299) → 300

1₁(311) → 312

1₁(305) → 306

1₁(266) → 267

1₁(317) → 318

1₁(273) → 274

1₁(267) → 268

1₁(269) → 270

1₁(310) → 311

1₁(302) → 303

1₁(300) → 301

1₁(272) → 273

5₁(309) → 310

5₁(265) → 266

5₁(298) → 299

0₁(268) → 269

0₁(312) → 313

0₁(301) → 302

3₀(137) → 138

3₀(35) → 36

3₀(203) → 204

3₀(166) → 159

3₀(169) → 170

3₀(73) → 74

3₀(30) → 31

3₀(144) → 145

3₀(174) → 167

3₀(3) → 13

3₀(7) → 8

3₀(129) → 130

3₀(45) → 46

3₀(125) → 126

3₀(66) → 67

3₀(50) → 116

3₀(80) → 81

3₀(140) → 141

3₀(238) → 239

3₀(170) → 171

3₀(155) → 156

3₀(82) → 251

3₀(179) → 180

3₀(249) → 241

3₀(60) → 80

3₀(204) → 205

3₀(102) → 103

3₀(15) → 16

3₀(55) → 56

3₀(214) → 215

3₀(205) → 206

3₀(160) → 161

3₀(2) → 50

3₀(57) → 58

3₀(23) → 24

3₀(246) → 247

3₀(213) → 214

3₀(17) → 18

3₀(194) → 195

3₀(104) → 105

3₀(235) → 236

3₀(264) → 256

0₀(41) → 42

0₀(2) → 30

0₀(231) → 224

0₀(31) → 32

0₀(117) → 118

0₀(225) → 226

0₀(26) → 27

0₀(71) → 72

0₀(201) → 202

0₀(19) → 20

0₀(110) → 111

0₀(44) → 45

0₀(162) → 163

0₀(50) → 51

0₀(37) → 38

0₀(4) → 22

0₀(46) → 47

0₀(100) → 101

0₀(83) → 84

0₀(222) → 223

0₀(165) → 166

0₀(70) → 71

0₀(185) → 186

0₀(229) → 230

0₀(258) → 259

0₀(60) → 89

0₀(61) → 152

0₀(176) → 177

0₀(126) → 127

0₀(172) → 173

0₀(92) → 93

0₀(253) → 254

0₀(143) → 144

0₀(128) → 129

0₀(139) → 140

0₀(13) → 14

0₀(62) → 63

0₀(197) → 198

0₀(221) → 222

0₀(259) → 260

0₀(121) → 122

0₀(53) → 54

0₀(146) → 147

0₀(3) → 98

0₀(252) → 253

0₀(81) → 82

0₀(122) → 123

0₀(5) → 6

1₀(226) → 227

1₀(182) → 175

1₀(206) → 207

1₀(70) → 184

1₀(123) → 115

1₀(216) → 208

1₀(14) → 15

1₀(30) → 257

1₀(147) → 148

1₀(86) → 87

1₀(108) → 109

1₀(207) → 199

1₀(136) → 137

1₀(210) → 211

1₀(34) → 35

1₀(112) → 113

1₀(143) → 168

1₀(32) → 33

1₀(6) → 7

1₀(60) → 61

1₀(43) → 44

1₀(152) → 153

1₀(149) → 150

1₀(209) → 210

1₀(131) → 132

1₀(109) → 110

1₀(56) → 57

1₀(75) → 76

1₀(195) → 196

1₀(28) → 21

1₀(3) → 4

1₀(47) → 48

1₀(40) → 41

1₀(234) → 235

1₀(255) → 250

1₀(111) → 112

1₀(9) → 10

1₀(236) → 237

1₀(96) → 88

1₀(101) → 102

1₀(248) → 249

1₀(261) → 262

1₀(94) → 95

1₀(72) → 73

1₀(189) → 190

1₀(135) → 136

1₀(31) → 160

1₀(10) → 11

1₀(2) → 40

1₀(141) → 133

1₀(4) → 5

1₀(157) → 158

1₀(22) → 23

1₀(89) → 90

1₀(52) → 53

5₀(25) → 26

5₀(191) → 183

5₀(171) → 172

5₀(218) → 219

5₀(120) → 121

5₀(177) → 178

5₀(153) → 154

5₀(237) → 238

5₀(50) → 200

5₀(211) → 212

5₀(152) → 193

5₀(36) → 37

5₀(202) → 203

5₀(198) → 192

5₀(90) → 91

5₀(118) → 119

5₀(20) → 12

5₀(67) → 68

5₀(161) → 162

5₀(119) → 120

5₀(40) → 242

5₀(103) → 104

5₀(3) → 143

5₀(70) → 134

5₀(138) → 139

5₀(85) → 86

5₀(114) → 106

5₀(24) → 25

5₀(180) → 181

5₀(134) → 135

5₀(38) → 29

5₀(228) → 229

5₀(212) → 213

5₀(130) → 131

5₀(68) → 59

5₀(91) → 92

5₀(188) → 189

5₀(178) → 179

5₀(2) → 3

5₀(113) → 114

5₀(243) → 244

5₀(168) → 218

4₀(64) → 65

4₀(184) → 185

4₀(16) → 17

4₀(99) → 100

4₀(156) → 157

4₀(105) → 97

4₀(230) → 231

4₀(65) → 66

4₀(233) → 234

4₀(200) → 201

4₀(193) → 194

4₀(227) → 228

4₀(40) → 125

4₀(54) → 55

4₀(181) → 182

4₀(242) → 243

4₀(173) → 174

4₀(50) → 233

4₀(215) → 216

4₀(251) → 252

4₀(186) → 187

4₀(127) → 128

4₀(76) → 77

4₀(63) → 64

4₀(148) → 149

4₀(245) → 246

4₀(82) → 83

4₀(2) → 60

4₀(163) → 164

4₀(30) → 107

4₀(27) → 28

4₀(143) → 225

4₀(116) → 117

4₀(78) → 69

4₀(244) → 245

4₀(33) → 34

4₀(158) → 151

4₀(223) → 217

4₀(154) → 155

f6₀ → 2

2₀(2) → 70

2₀(51) → 52

2₀(18) → 19

2₀(196) → 197

2₀(263) → 264

2₀(257) → 258

2₀(98) → 99

2₀(48) → 39

2₀(260) → 261

2₀(95) → 96

2₀(220) → 221

2₀(247) → 248

2₀(239) → 240

2₀(107) → 108

2₀(8) → 9

2₀(61) → 62

2₀(254) → 255

2₀(74) → 75

2₀(150) → 142

2₀(164) → 165

2₀(11) → 1

2₀(84) → 85

2₀(87) → 79

2₀(132) → 124

2₀(262) → 263

2₀(93) → 94

2₀(240) → 232

2₀(42) → 43

2₀(40) → 209

2₀(187) → 188

2₀(219) → 220

2₀(190) → 191

2₀(58) → 49

2₀(145) → 146

2₀(77) → 78

2₀(116) → 176

2₀(168) → 169

3₁(303) → 304

3₁(314) → 315

3₁(270) → 271

2₁(318) → 319

2₁(271) → 272

2₁(307) → 308

2₁(274) → 275

2₁(304) → 305

2₁(315) → 316

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