YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 String Reversal

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

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

1.1 Bounds

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

final states:

{241, 232, 224, 217, 209, 200, 191, 181, 173, 165, 156, 147, 139, 129, 122, 113, 104, 95, 86, 76, 67, 58, 49, 41, 32, 22, 12, 1}

transitions:

200 → 182

32 → 130

181 → 182

129 → 130

122 → 77

41 → 77

147 → 13

209 → 14

209 → 3

95 → 13

241 → 77

224 → 130

49 → 4

49 → 130

1 → 130

165 → 130

139 → 87

139 → 182

76 → 13

86 → 148

86 → 77

58 → 182

173 → 130

22 → 77

67 → 77

232 → 157

232 → 23

12 → 182

104 → 77

217 → 182

113 → 13

191 → 182

156 → 13

1₀(211) → 212

1₀(130) → 131

1₀(115) → 218

1₀(245) → 246

1₀(157) → 158

1₀(24) → 25

1₀(121) → 113

1₀(150) → 151

1₀(87) → 88

1₀(215) → 216

1₀(155) → 147

1₀(9) → 10

1₀(79) → 80

1₀(96) → 174

1₀(187) → 188

1₀(236) → 237

1₀(177) → 178

1₀(62) → 63

1₀(15) → 16

1₀(101) → 102

1₀(39) → 40

1₀(205) → 206

1₀(160) → 161

1₀(2) → 13

1₀(164) → 156

1₀(17) → 18

1₀(69) → 70

1₀(226) → 227

1₀(38) → 39

5₀(2) → 182

5₀(132) → 133

5₀(117) → 118

5₀(120) → 121

5₀(74) → 75

5₀(6) → 7

5₀(179) → 180

5₀(193) → 194

5₀(19) → 20

5₀(202) → 203

5₀(247) → 248

5₀(162) → 163

5₀(28) → 29

5₀(59) → 60

5₀(136) → 137

5₀(46) → 47

5₀(34) → 35

5₀(77) → 192

5₀(174) → 175

5₀(80) → 81

5₀(198) → 199

5₀(8) → 9

5₀(207) → 208

5₀(203) → 204

5₀(214) → 215

5₀(55) → 56

5₀(106) → 107

5₀(199) → 191

5₀(210) → 211

5₀(108) → 109

5₀(68) → 210

5₀(23) → 33

5₀(212) → 213

5₀(134) → 135

5₀(137) → 138

5₀(13) → 87

5₀(148) → 149

5₀(169) → 170

5₀(131) → 132

5₀(84) → 85

5₀(138) → 129

5₀(237) → 238

5₀(75) → 67

5₀(171) → 172

5₀(96) → 97

5₀(208) → 200

5₀(158) → 159

5₀(246) → 247

4₀(33) → 34

4₀(219) → 220

4₀(124) → 125

4₀(23) → 68

4₀(170) → 171

4₀(123) → 124

4₀(78) → 79

4₀(216) → 209

4₀(91) → 92

4₀(30) → 31

4₀(230) → 231

4₀(166) → 167

4₀(85) → 76

4₀(7) → 8

4₀(178) → 179

4₀(130) → 233

4₀(35) → 36

4₀(168) → 169

4₀(99) → 100

4₀(60) → 61

4₀(77) → 105

4₀(152) → 153

4₀(149) → 150

4₀(176) → 177

4₀(194) → 195

4₀(92) → 93

4₀(87) → 166

4₀(238) → 239

4₀(18) → 19

4₀(3) → 50

4₀(97) → 98

4₀(140) → 141

4₀(116) → 117

4₀(163) → 164

4₀(102) → 103

4₀(27) → 28

4₀(115) → 116

4₀(13) → 14

4₀(5) → 123

4₀(103) → 95

4₀(119) → 120

4₀(10) → 11

4₀(93) → 94

4₀(2) → 3

4₀(68) → 69

4₀(186) → 187

0₀(29) → 30

0₀(42) → 43

0₀(244) → 245

0₀(227) → 228

0₀(151) → 152

0₀(63) → 64

0₀(50) → 51

0₀(222) → 223

0₀(94) → 86

0₀(196) → 197

0₀(234) → 235

0₀(235) → 236

0₀(182) → 183

0₀(3) → 4

0₀(197) → 198

0₀(144) → 145

0₀(109) → 110

0₀(228) → 229

0₀(23) → 59

0₀(231) → 224

0₀(2) → 130

2₀(64) → 65

2₀(146) → 139

2₀(135) → 136

2₀(48) → 41

2₀(105) → 106

2₀(20) → 21

2₀(53) → 54

2₀(185) → 186

2₀(72) → 73

2₀(24) → 242

2₀(172) → 165

2₀(118) → 119

2₀(40) → 32

2₀(125) → 126

2₀(54) → 55

2₀(73) → 74

2₀(61) → 62

2₀(190) → 181

2₀(114) → 115

2₀(23) → 114

2₀(145) → 146

2₀(71) → 72

2₀(127) → 128

2₀(192) → 193

2₀(148) → 225

2₀(240) → 232

2₀(82) → 83

2₀(83) → 84

2₀(89) → 90

2₀(2) → 77

2₀(3) → 148

2₀(26) → 27

2₀(45) → 46

2₀(142) → 143

2₀(161) → 162

2₀(51) → 52

2₀(25) → 26

2₀(81) → 82

2₀(195) → 196

2₀(57) → 49

2₀(248) → 241

2₀(112) → 104

f6₀ → 2

3₀(2) → 23

3₀(167) → 168

3₀(56) → 57

3₀(90) → 91

3₀(65) → 66

3₀(128) → 122

3₀(133) → 134

3₀(204) → 205

3₀(184) → 185

3₀(175) → 176

3₀(110) → 111

3₀(98) → 99

3₀(213) → 214

3₀(50) → 140

3₀(225) → 226

3₀(36) → 37

3₀(220) → 221

3₀(189) → 190

3₀(239) → 240

3₀(107) → 108

3₀(43) → 44

3₀(4) → 5

3₀(159) → 160

3₀(21) → 12

3₀(233) → 234

3₀(37) → 38

3₀(223) → 217

3₀(206) → 207

3₀(3) → 201

3₀(11) → 1

3₀(14) → 15

3₀(218) → 219

3₀(100) → 101

3₀(141) → 142

3₀(66) → 58

3₀(70) → 71

3₀(23) → 24

3₀(221) → 222

3₀(111) → 112

3₀(130) → 157

3₀(33) → 42

3₀(180) → 173

3₀(52) → 53

3₀(183) → 184

3₀(201) → 202

3₀(126) → 127

3₀(143) → 144

3₀(154) → 155

3₀(229) → 230

3₀(243) → 244

3₀(44) → 45

3₀(16) → 17

3₀(242) → 243

3₀(188) → 189

3₀(31) → 22

3₀(5) → 6

3₀(77) → 78

3₀(13) → 96

3₀(88) → 89

3₀(47) → 48

3₀(153) → 154

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