YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 String Reversal

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

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

1.1 Bounds

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

final states:

{252, 235, 216, 198, 180, 164, 149, 134, 121, 109, 100, 90, 80, 70, 63, 55, 48, 41, 35, 27, 20, 16, 10, 6, 1}

transitions:

80 → 199

10 → 7

149 → 4

149 → 3

41 → 28

134 → 28

55 → 91

55 → 199

90 → 122

90 → 7

20 → 217

20 → 7

1 → 28

235 → 182

235 → 81

235 → 199

121 → 28

6 → 42

6 → 150

6 → 3

109 → 3

180 → 111

180 → 150

180 → 3

252 → 165

252 → 11

16 → 150

16 → 3

63 → 201

63 → 28

100 → 21

216 → 200

216 → 199

35 → 181

35 → 28

48 → 200

48 → 199

198 → 49

198 → 21

164 → 11

27 → 110

27 → 7

70 → 17

70 → 11

f6₀ → 2

5₀(224) → 225

5₀(31) → 32

5₀(146) → 147

5₀(263) → 264

5₀(189) → 190

5₀(233) → 234

5₀(185) → 186

5₀(72) → 73

5₀(21) → 217

5₀(169) → 170

5₀(188) → 189

5₀(46) → 47

5₀(145) → 146

5₀(186) → 187

5₀(126) → 127

5₀(71) → 72

5₀(76) → 77

5₀(85) → 86

5₀(201) → 202

5₀(240) → 241

5₀(256) → 257

5₀(218) → 219

5₀(2) → 7

5₀(3) → 122

5₀(26) → 20

5₀(221) → 222

5₀(170) → 171

5₀(37) → 38

5₀(168) → 169

5₀(28) → 29

5₀(33) → 34

5₀(13) → 14

5₀(15) → 10

5₀(81) → 110

5₀(104) → 105

5₀(209) → 210

5₀(141) → 142

2₀(151) → 152

2₀(219) → 220

2₀(177) → 178

2₀(23) → 24

2₀(239) → 240

2₀(165) → 166

2₀(270) → 252

2₀(250) → 251

2₀(144) → 145

2₀(19) → 16

2₀(156) → 157

2₀(262) → 263

2₀(34) → 27

2₀(143) → 144

2₀(43) → 44

2₀(213) → 214

2₀(79) → 70

2₀(258) → 259

2₀(56) → 57

2₀(197) → 180

2₀(29) → 30

2₀(82) → 83

2₀(28) → 165

2₀(3) → 17

2₀(266) → 267

2₀(40) → 35

2₀(97) → 98

2₀(64) → 65

2₀(255) → 256

2₀(113) → 114

2₀(9) → 6

2₀(163) → 149

2₀(25) → 26

2₀(232) → 233

2₀(204) → 205

2₀(192) → 193

2₀(83) → 84

2₀(21) → 56

2₀(74) → 75

2₀(119) → 120

2₀(17) → 135

2₀(2) → 11

2₀(4) → 5

2₀(153) → 154

2₀(44) → 45

2₀(39) → 40

2₀(66) → 67

2₀(52) → 53

4₀(51) → 52

4₀(244) → 245

4₀(175) → 176

4₀(190) → 191

4₀(130) → 131

4₀(53) → 54

4₀(78) → 79

4₀(127) → 128

4₀(30) → 31

4₀(210) → 211

4₀(227) → 228

4₀(120) → 109

4₀(158) → 159

4₀(112) → 113

4₀(95) → 96

4₀(3) → 4

4₀(7) → 150

4₀(222) → 223

4₀(125) → 126

4₀(207) → 208

4₀(61) → 62

4₀(184) → 185

4₀(21) → 22

4₀(228) → 229

4₀(140) → 141

4₀(29) → 42

4₀(111) → 112

4₀(128) → 129

4₀(56) → 253

4₀(68) → 69

4₀(59) → 60

4₀(84) → 85

4₀(110) → 111

4₀(62) → 55

4₀(101) → 102

4₀(42) → 43

4₀(214) → 215

4₀(261) → 262

4₀(5) → 236

4₀(117) → 118

4₀(124) → 125

4₀(28) → 71

4₀(265) → 266

4₀(259) → 260

4₀(2) → 3

4₀(147) → 148

4₀(257) → 258

4₀(223) → 224

4₀(17) → 18

4₀(243) → 244

0₀(2) → 199

0₀(132) → 133

0₀(45) → 46

0₀(155) → 156

0₀(161) → 162

0₀(225) → 226

0₀(205) → 206

0₀(58) → 59

0₀(157) → 158

0₀(32) → 33

0₀(162) → 163

0₀(28) → 81

0₀(133) → 121

0₀(115) → 116

0₀(245) → 246

0₀(220) → 221

0₀(8) → 9

0₀(89) → 80

0₀(260) → 261

0₀(114) → 115

0₀(123) → 124

0₀(187) → 188

0₀(191) → 192

0₀(203) → 204

0₀(199) → 200

0₀(105) → 106

0₀(172) → 173

0₀(92) → 93

0₀(181) → 182

0₀(251) → 235

0₀(14) → 15

0₀(195) → 196

0₀(212) → 213

0₀(139) → 140

0₀(57) → 58

0₀(107) → 108

0₀(236) → 237

0₀(131) → 132

0₀(38) → 39

0₀(49) → 50

0₀(75) → 76

0₀(81) → 82

0₀(196) → 197

0₀(208) → 209

0₀(246) → 247

0₀(122) → 123

0₀(22) → 23

0₀(7) → 91

3₀(2) → 28

3₀(18) → 19

3₀(65) → 66

3₀(54) → 48

3₀(202) → 203

3₀(98) → 99

3₀(67) → 68

3₀(166) → 167

3₀(24) → 25

3₀(217) → 218

3₀(159) → 160

3₀(21) → 181

3₀(138) → 139

3₀(178) → 179

3₀(87) → 88

3₀(211) → 212

3₀(176) → 177

3₀(118) → 119

3₀(238) → 239

3₀(136) → 137

3₀(173) → 174

3₀(93) → 94

3₀(129) → 130

3₀(22) → 36

3₀(103) → 104

3₀(183) → 184

3₀(12) → 13

3₀(73) → 74

3₀(268) → 269

3₀(60) → 61

3₀(229) → 230

3₀(242) → 243

3₀(5) → 1

3₀(231) → 232

3₀(106) → 107

3₀(200) → 201

3₀(182) → 183

3₀(102) → 103

3₀(171) → 172

1₀(108) → 100

1₀(21) → 64

1₀(160) → 161

1₀(47) → 41

1₀(142) → 143

1₀(135) → 136

1₀(99) → 90

1₀(86) → 87

1₀(88) → 89

1₀(237) → 238

1₀(50) → 51

1₀(230) → 231

1₀(94) → 95

1₀(152) → 153

1₀(69) → 63

1₀(269) → 270

1₀(11) → 12

1₀(96) → 97

1₀(226) → 227

1₀(36) → 37

1₀(241) → 242

1₀(28) → 49

1₀(7) → 8

1₀(234) → 216

1₀(148) → 134

1₀(167) → 168

1₀(248) → 249

1₀(116) → 117

1₀(194) → 195

1₀(249) → 250

1₀(72) → 101

1₀(193) → 194

1₀(154) → 155

1₀(267) → 268

1₀(206) → 207

1₀(137) → 138

1₀(150) → 151

1₀(179) → 164

1₀(254) → 255

1₀(247) → 248

1₀(77) → 78

1₀(174) → 175

1₀(91) → 92

1₀(264) → 265

1₀(253) → 254

1₀(215) → 198

1₀(2) → 21

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