YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 String Reversal

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

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

1.1 Bounds

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

final states:

{184, 180, 175, 174, 169, 166, 162, 159, 155, 150, 146, 142, 139, 136, 131, 127, 124, 122, 118, 114, 110, 105, 101, 96, 92, 87, 83, 78, 74, 69, 64, 58, 55, 49, 44, 42, 38, 35, 33, 29, 27, 22, 21, 19, 14, 10, 7, 1}

transitions:

78 → 36

78 → 3

33 → 23

200 → 175

29 → 23

89 → 216

87 → 97

87 → 30

229 → 117

10 → 23

96 → 11

96 → 30

136 → 23

122 → 23

184 → 23

146 → 23

108 → 244

110 → 23

55 → 70

55 → 39

175 → 23

49 → 23

1 → 23

127 → 23

222 → 87

101 → 11

101 → 30

139 → 39

44 → 23

38 → 23

79 → 223

58 → 23

177 → 195

21 → 23

150 → 23

172 → 272

121 → 258

22 → 23

105 → 39

124 → 23

174 → 23

264 → 120

204 → 175

180 → 70

180 → 39

118 → 11

118 → 30

114 → 4

114 → 3

14 → 23

169 → 23

7 → 23

69 → 65

69 → 39

42 → 23

64 → 23

162 → 23

35 → 23

278 → 24

83 → 11

83 → 30

198 → 201

250 → 40

159 → 11

159 → 30

142 → 39

131 → 23

74 → 75

74 → 3

92 → 23

19 → 23

27 → 36

27 → 3

166 → 23

155 → 23

f6₀ → 2

5₀(138) → 136

5₀(59) → 185

5₀(132) → 133

5₀(48) → 44

5₀(65) → 140

5₀(20) → 43

5₀(53) → 54

5₀(61) → 62

5₀(46) → 56

5₀(183) → 180

5₀(50) → 151

5₀(145) → 142

5₀(113) → 110

5₀(2) → 39

5₀(3) → 70

5₀(45) → 128

5₀(41) → 160

5₀(30) → 65

5₀(107) → 108

5₀(37) → 167

5₀(47) → 48

5₀(106) → 143

5₀(57) → 55

0₁(195) → 196

0₁(245) → 246

0₁(217) → 218

0₁(273) → 274

0₁(224) → 225

0₁(259) → 260

0₁(196) → 197

1₀(182) → 183

1₀(126) → 124

1₀(148) → 149

1₀(26) → 22

1₀(41) → 38

1₀(76) → 77

1₀(59) → 106

1₀(37) → 35

1₀(108) → 109

1₀(130) → 127

1₀(179) → 175

1₀(34) → 33

1₀(112) → 113

1₀(168) → 166

1₀(32) → 29

1₀(167) → 168

1₀(134) → 135

1₀(79) → 115

1₀(158) → 155

1₀(56) → 123

1₀(88) → 89

1₀(46) → 47

1₀(172) → 173

1₀(121) → 118

1₀(154) → 150

1₀(9) → 7

1₀(163) → 164

1₀(54) → 49

1₀(94) → 95

1₀(15) → 20

1₀(20) → 19

1₀(13) → 10

1₀(31) → 32

1₀(62) → 63

1₀(5) → 6

1₀(103) → 104

1₀(93) → 94

1₀(2) → 23

1₀(141) → 139

1₀(188) → 184

1₀(66) → 67

1₀(16) → 17

1₀(89) → 90

1₁(223) → 224

1₁(216) → 217

1₁(272) → 273

1₁(203) → 204

1₁(198) → 199

1₁(258) → 259

1₁(244) → 245

2₀(51) → 52

2₀(137) → 138

2₀(65) → 66

2₀(19) → 21

2₀(11) → 12

2₀(73) → 69

2₀(30) → 31

2₀(157) → 158

2₀(120) → 121

2₀(144) → 145

2₀(3) → 15

2₀(25) → 26

2₀(129) → 130

2₀(45) → 46

2₀(125) → 126

2₀(50) → 79

2₀(140) → 141

2₀(106) → 107

2₀(29) → 34

2₀(111) → 112

2₀(128) → 129

2₀(18) → 14

2₀(151) → 152

2₀(60) → 61

2₀(84) → 85

2₀(187) → 188

2₀(75) → 76

2₀(71) → 72

2₀(102) → 103

2₀(39) → 132

2₀(161) → 159

2₀(97) → 98

2₀(5) → 8

2₀(4) → 5

2₀(181) → 182

2₀(28) → 27

2₀(36) → 37

2₀(40) → 41

2₀(2) → 59

2₀(23) → 170

2₀(147) → 148

2₀(164) → 165

2₀(176) → 177

2₀(100) → 96

2₀(12) → 13

2₀(153) → 154

2₁(261) → 262

2₁(277) → 278

2₁(249) → 250

2₁(263) → 264

2₁(219) → 220

2₁(247) → 248

2₁(275) → 276

2₁(228) → 229

2₁(201) → 202

2₁(221) → 222

2₁(197) → 198

2₁(226) → 227

0₀(2) → 3

0₀(45) → 163

0₀(117) → 114

0₀(95) → 92

0₀(177) → 178

0₀(186) → 187

0₀(98) → 99

0₀(50) → 51

0₀(59) → 75

0₀(77) → 74

0₀(80) → 81

0₀(119) → 120

0₀(70) → 71

0₀(91) → 87

0₀(123) → 122

0₀(135) → 131

0₀(23) → 24

0₀(116) → 117

0₀(39) → 40

0₀(178) → 179

0₀(3) → 4

0₀(81) → 82

0₀(104) → 174

0₀(30) → 36

0₀(40) → 181

3₀(2) → 50

3₀(149) → 146

3₀(56) → 57

3₀(156) → 157

3₀(133) → 134

3₀(67) → 68

3₀(99) → 100

3₀(170) → 171

3₀(30) → 176

3₀(36) → 102

3₀(24) → 25

3₀(43) → 42

3₀(4) → 84

3₀(8) → 9

3₀(63) → 58

3₀(104) → 101

3₀(3) → 45

3₀(6) → 1

3₀(70) → 125

3₀(15) → 16

3₀(165) → 162

3₀(52) → 53

3₀(82) → 78

3₀(59) → 88

3₀(31) → 93

3₀(68) → 64

3₀(171) → 172

4₁(248) → 249

4₁(276) → 277

4₁(262) → 263

4₁(220) → 221

4₁(227) → 228

3₁(199) → 200

3₁(225) → 226

3₁(202) → 203

3₁(274) → 275

3₁(218) → 219

3₁(246) → 247

3₁(260) → 261

4₀(143) → 144

4₀(17) → 18

4₀(106) → 137

4₀(132) → 156

4₀(160) → 161

4₀(86) → 83

4₀(152) → 153

4₀(26) → 28

4₀(59) → 60

4₀(90) → 91

4₀(39) → 147

4₀(15) → 111

4₀(72) → 73

4₀(3) → 11

4₀(30) → 119

4₀(173) → 169

4₀(185) → 186

4₀(85) → 86

4₀(79) → 80

4₀(109) → 105

4₀(23) → 97

4₀(115) → 116

4₀(2) → 30

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