YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 String Reversal

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

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

1.1 Bounds

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

final states:

{184, 176, 167, 159, 149, 140, 132, 123, 114, 105, 96, 86, 77, 68, 58, 49, 40, 32, 22, 12, 1}

transitions:

78 → 226

78 → 270

280 → 80

176 → 59

32 → 23

96 → 61

96 → 14

96 → 23

167 → 3

149 → 88

149 → 59

227 → 281

184 → 150

185 → 193

185 → 237

49 → 60

49 → 13

1 → 59

40 → 150

123 → 59

86 → 59

58 → 59

22 → 59

105 → 61

105 → 14

105 → 23

114 → 23

12 → 59

77 → 23

140 → 124

140 → 23

236 → 80

290 → 81

68 → 124

68 → 23

159 → 124

159 → 23

203 → 187

132 → 23

247 → 187

5₁(200) → 201

5₁(231) → 232

5₁(198) → 199

5₁(233) → 234

5₁(194) → 195

5₁(288) → 289

5₁(227) → 228

4₁(228) → 229

4₁(277) → 278

4₁(244) → 245

4₁(232) → 233

4₁(279) → 280

4₁(276) → 277

4₁(238) → 239

4₁(246) → 247

4₁(199) → 200

4₁(243) → 244

4₁(271) → 272

4₁(195) → 196

1₁(281) → 282

1₁(274) → 275

1₁(235) → 236

1₁(242) → 243

1₁(239) → 240

1₁(275) → 276

1₁(202) → 203

1₁(272) → 273

1₁(240) → 241

1₁(273) → 274

1₁(241) → 242

0₁(245) → 246

0₁(229) → 230

0₁(285) → 286

0₁(193) → 194

0₁(196) → 197

0₁(226) → 227

0₁(278) → 279

5₀(115) → 133

5₀(65) → 66

5₀(183) → 176

5₀(78) → 79

5₀(73) → 74

5₀(162) → 163

5₀(158) → 149

5₀(95) → 86

5₀(3) → 4

5₀(7) → 8

5₀(186) → 187

5₀(24) → 25

5₀(50) → 51

5₀(87) → 88

5₀(56) → 57

5₀(9) → 10

5₀(79) → 80

5₀(177) → 178

5₀(47) → 48

5₀(116) → 117

5₀(2) → 59

5₀(23) → 106

5₀(185) → 186

5₀(100) → 101

5₀(188) → 189

4₀(72) → 73

4₀(109) → 110

4₀(2) → 23

4₀(25) → 26

4₀(21) → 12

4₀(120) → 121

4₀(124) → 125

4₀(113) → 105

4₀(26) → 27

4₀(71) → 72

4₀(51) → 52

4₀(19) → 20

4₀(4) → 5

4₀(112) → 113

4₀(173) → 174

4₀(165) → 166

4₀(8) → 9

4₀(60) → 61

4₀(187) → 188

4₀(106) → 107

4₀(135) → 136

4₀(36) → 37

4₀(125) → 126

4₀(143) → 144

4₀(18) → 19

4₀(128) → 129

4₀(23) → 69

4₀(64) → 65

4₀(13) → 14

4₀(97) → 98

4₀(148) → 140

4₀(169) → 170

4₀(118) → 119

4₀(156) → 157

4₀(38) → 39

4₀(121) → 122

4₀(166) → 159

4₀(145) → 146

4₀(146) → 147

4₀(3) → 124

4₀(52) → 53

4₀(104) → 96

4₀(171) → 172

4₀(151) → 152

2₀(33) → 34

2₀(124) → 160

2₀(23) → 24

2₀(70) → 71

2₀(170) → 171

2₀(42) → 43

2₀(144) → 145

2₀(37) → 38

2₀(174) → 175

2₀(6) → 7

2₀(60) → 177

2₀(152) → 153

2₀(92) → 93

2₀(46) → 47

2₀(111) → 112

2₀(163) → 164

2₀(191) → 192

2₀(80) → 81

2₀(13) → 97

2₀(181) → 182

2₀(31) → 22

2₀(10) → 11

2₀(2) → 150

2₀(39) → 32

2₀(157) → 158

2₀(89) → 90

2₀(190) → 191

0₀(87) → 141

0₀(142) → 143

0₀(5) → 6

0₀(122) → 114

0₀(172) → 173

0₀(94) → 95

0₀(117) → 118

0₀(136) → 137

0₀(44) → 45

0₀(27) → 28

0₀(66) → 67

0₀(54) → 55

0₀(4) → 33

0₀(28) → 29

0₀(90) → 91

0₀(20) → 21

0₀(67) → 58

0₀(182) → 183

0₀(62) → 63

0₀(81) → 82

0₀(57) → 49

0₀(110) → 111

0₀(179) → 180

0₀(175) → 167

0₀(134) → 135

0₀(76) → 68

0₀(23) → 185

0₀(115) → 116

0₀(75) → 76

0₀(2) → 3

3₀(59) → 60

3₀(147) → 148

3₀(48) → 40

3₀(137) → 138

3₀(155) → 156

3₀(139) → 132

3₀(34) → 35

3₀(98) → 99

3₀(130) → 131

3₀(91) → 92

3₀(133) → 134

3₀(69) → 70

3₀(126) → 127

3₀(119) → 120

3₀(84) → 85

3₀(127) → 128

3₀(85) → 77

3₀(82) → 83

3₀(43) → 44

3₀(2) → 13

3₀(3) → 50

3₀(45) → 46

3₀(41) → 42

3₀(107) → 108

3₀(35) → 36

3₀(103) → 104

3₀(161) → 162

3₀(13) → 115

3₀(150) → 151

3₀(160) → 161

3₀(141) → 142

f6₀ → 2

1₀(2) → 87

1₀(99) → 100

1₀(30) → 31

1₀(55) → 56

1₀(189) → 190

1₀(131) → 123

1₀(63) → 64

1₀(61) → 62

1₀(138) → 139

1₀(74) → 75

1₀(150) → 168

1₀(178) → 179

1₀(3) → 41

1₀(164) → 165

1₀(17) → 18

1₀(11) → 1

1₀(192) → 184

1₀(14) → 15

1₀(83) → 84

1₀(53) → 54

1₀(23) → 78

1₀(29) → 30

1₀(15) → 16

1₀(180) → 181

1₀(93) → 94

1₀(101) → 102

1₀(129) → 130

1₀(154) → 155

1₀(108) → 109

1₀(16) → 17

1₀(88) → 89

1₀(168) → 169

1₀(153) → 154

1₀(102) → 103

2₁(283) → 284

2₁(234) → 235

2₁(230) → 231

2₁(197) → 198

2₁(287) → 288

2₁(201) → 202

3₁(237) → 238

3₁(270) → 271

3₁(289) → 290

3₁(286) → 287

3₁(284) → 285

3₁(282) → 283

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