YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 String Reversal

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

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

1.1 Bounds

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

final states:

{247, 229, 212, 193, 177, 162, 150, 133, 119, 107, 99, 89, 78, 68, 56, 47, 39, 33, 29, 23, 20, 15, 11, 7, 1}

transitions:

78 → 79

78 → 57

33 → 16

23 → 57

29 → 12

89 → 48

89 → 8

229 → 8

15 → 24

15 → 12

119 → 134

119 → 57

133 → 230

133 → 194

39 → 134

39 → 57

20 → 79

20 → 57

193 → 135

193 → 230

193 → 194

99 → 230

99 → 194

107 → 134

107 → 57

1 → 194

177 → 90

177 → 16

150 → 57

11 → 57

212 → 8

7 → 57

162 → 135

162 → 230

162 → 194

47 → 26

47 → 58

47 → 12

68 → 79

68 → 57

56 → 12

247 → 57

f6₀ → 2

5₀(131) → 132

5₀(59) → 60

5₀(121) → 122

5₀(16) → 24

5₀(96) → 97

5₀(152) → 153

5₀(12) → 13

5₀(21) → 22

5₀(205) → 206

5₀(253) → 254

5₀(139) → 140

5₀(125) → 126

5₀(258) → 259

5₀(32) → 29

5₀(190) → 191

5₀(242) → 243

5₀(173) → 174

5₀(182) → 183

5₀(85) → 86

5₀(4) → 21

5₀(63) → 64

5₀(256) → 257

5₀(2) → 12

5₀(163) → 164

5₀(228) → 212

5₀(30) → 31

5₀(231) → 232

5₀(101) → 102

5₀(13) → 14

5₀(67) → 56

5₀(25) → 26

5₀(154) → 155

5₀(57) → 58

5₀(141) → 142

3₀(106) → 99

3₀(65) → 66

3₀(245) → 246

3₀(81) → 82

3₀(160) → 161

3₀(108) → 109

3₀(178) → 179

3₀(130) → 131

3₀(132) → 119

3₀(262) → 247

3₀(143) → 144

3₀(168) → 169

3₀(220) → 221

3₀(134) → 135

3₀(79) → 178

3₀(187) → 188

3₀(149) → 133

3₀(176) → 162

3₀(88) → 78

3₀(195) → 196

3₀(87) → 88

3₀(172) → 173

3₀(57) → 230

3₀(9) → 30

3₀(232) → 233

3₀(128) → 129

3₀(224) → 225

3₀(189) → 190

3₀(74) → 75

3₀(5) → 6

3₀(17) → 18

3₀(2) → 194

3₀(4) → 5

3₀(24) → 34

3₀(237) → 238

3₀(44) → 45

3₀(211) → 193

3₀(198) → 199

3₀(66) → 67

3₀(52) → 53

1₀(221) → 222

1₀(254) → 255

1₀(244) → 245

1₀(175) → 176

1₀(31) → 32

1₀(16) → 48

1₀(19) → 15

1₀(166) → 167

1₀(183) → 184

1₀(234) → 235

1₀(144) → 145

1₀(95) → 96

1₀(105) → 106

1₀(3) → 4

1₀(98) → 89

1₀(26) → 27

1₀(93) → 94

1₀(8) → 9

1₀(135) → 136

1₀(167) → 168

1₀(215) → 216

1₀(165) → 166

1₀(197) → 198

1₀(9) → 10

1₀(151) → 152

1₀(201) → 202

1₀(27) → 28

1₀(79) → 80

1₀(60) → 61

1₀(109) → 110

1₀(236) → 237

1₀(75) → 76

1₀(204) → 205

1₀(148) → 149

1₀(42) → 43

1₀(126) → 127

1₀(233) → 234

1₀(55) → 47

1₀(196) → 197

1₀(117) → 118

1₀(202) → 203

1₀(250) → 251

1₀(36) → 37

1₀(40) → 41

1₀(22) → 20

1₀(122) → 123

1₀(2) → 8

1₀(246) → 229

1₀(164) → 165

1₀(243) → 244

1₀(218) → 219

0₀(111) → 112

0₀(213) → 214

0₀(2) → 3

0₀(155) → 156

0₀(261) → 262

0₀(113) → 114

0₀(71) → 72

0₀(129) → 130

0₀(227) → 228

0₀(16) → 69

0₀(115) → 116

0₀(34) → 100

0₀(174) → 175

0₀(76) → 77

0₀(83) → 84

0₀(91) → 92

0₀(223) → 224

0₀(123) → 124

0₀(207) → 208

0₀(199) → 200

0₀(92) → 93

0₀(181) → 182

0₀(238) → 239

0₀(134) → 163

0₀(13) → 108

0₀(156) → 157

0₀(219) → 220

0₀(90) → 91

0₀(170) → 171

0₀(216) → 217

0₀(184) → 185

0₀(69) → 70

0₀(142) → 143

0₀(53) → 54

0₀(145) → 146

0₀(240) → 241

0₀(3) → 40

0₀(10) → 7

0₀(127) → 128

0₀(94) → 95

0₀(171) → 172

0₀(194) → 195

0₀(208) → 209

0₀(158) → 159

0₀(153) → 154

0₀(22) → 151

4₀(2) → 57

4₀(157) → 158

4₀(28) → 23

4₀(257) → 258

4₀(134) → 248

4₀(230) → 231

4₀(49) → 50

4₀(191) → 192

4₀(64) → 65

4₀(80) → 81

4₀(225) → 226

4₀(252) → 253

4₀(255) → 256

4₀(235) → 236

4₀(24) → 25

4₀(217) → 218

4₀(159) → 160

4₀(222) → 223

4₀(104) → 105

4₀(138) → 139

4₀(3) → 79

4₀(86) → 87

4₀(6) → 1

4₀(136) → 137

4₀(140) → 141

4₀(62) → 63

4₀(161) → 150

4₀(251) → 252

4₀(103) → 104

4₀(12) → 134

4₀(73) → 74

4₀(186) → 187

4₀(209) → 210

4₀(185) → 186

4₀(200) → 201

4₀(72) → 73

4₀(116) → 117

4₀(194) → 213

2₀(112) → 113

2₀(100) → 101

2₀(97) → 98

2₀(120) → 121

2₀(82) → 83

2₀(58) → 59

2₀(192) → 177

2₀(46) → 39

2₀(203) → 204

2₀(61) → 62

2₀(50) → 51

2₀(124) → 125

2₀(169) → 170

2₀(260) → 261

2₀(226) → 227

2₀(241) → 242

2₀(146) → 147

2₀(54) → 55

2₀(84) → 85

2₀(43) → 44

2₀(239) → 240

2₀(118) → 107

2₀(41) → 42

2₀(147) → 148

2₀(248) → 249

2₀(249) → 250

2₀(14) → 11

2₀(16) → 17

2₀(48) → 49

2₀(35) → 36

2₀(3) → 90

2₀(102) → 103

2₀(206) → 207

2₀(70) → 71

2₀(137) → 138

2₀(34) → 35

2₀(57) → 120

2₀(110) → 111

2₀(179) → 180

2₀(18) → 19

2₀(114) → 115

2₀(210) → 211

2₀(45) → 46

2₀(180) → 181

2₀(51) → 52

2₀(77) → 68

2₀(38) → 33

2₀(214) → 215

2₀(37) → 38

2₀(259) → 260

2₀(188) → 189

2₀(2) → 16

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