YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 Bounds

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

final states:

{245, 229, 214, 198, 182, 166, 153, 138, 125, 112, 99, 89, 80, 70, 61, 53, 47, 40, 32, 26, 19, 13, 10, 6, 1}

transitions:

61 → 90

61 → 14

32 → 15

32 → 33

89 → 62

89 → 100

80 → 14

214 → 20

229 → 62

229 → 100

10 → 3

273 → 158

99 → 3

1 → 34

1 → 33

40 → 14

13 → 4

13 → 7

26 → 113

26 → 100

125 → 33

138 → 20

6 → 7

153 → 34

153 → 33

124 → 279

283 → 73

53 → 231

53 → 14

112 → 15

112 → 33

182 → 21

182 → 20

198 → 71

198 → 7

245 → 33

47 → 167

47 → 14

154 → 269

19 → 20

70 → 3

166 → 7

f6₀ → 2

5₀(31) → 26

5₀(236) → 237

5₀(65) → 66

5₀(79) → 70

5₀(118) → 119

5₀(34) → 35

5₀(98) → 89

5₀(188) → 189

5₀(238) → 239

5₀(202) → 203

5₀(211) → 212

5₀(91) → 92

5₀(114) → 115

5₀(217) → 218

5₀(183) → 246

5₀(199) → 200

5₀(5) → 81

5₀(119) → 120

5₀(74) → 75

5₀(14) → 62

5₀(63) → 64

5₀(111) → 99

5₀(113) → 215

5₀(2) → 100

5₀(3) → 41

5₀(221) → 222

5₀(37) → 38

5₀(129) → 130

5₀(161) → 162

5₀(244) → 229

5₀(259) → 260

5₀(100) → 113

5₀(249) → 250

1₀(33) → 71

1₀(227) → 228

1₀(219) → 220

1₀(124) → 112

1₀(73) → 74

1₀(239) → 240

1₀(260) → 261

1₀(123) → 124

1₀(252) → 253

1₀(250) → 251

1₀(147) → 148

1₀(86) → 87

1₀(108) → 109

1₀(142) → 143

1₀(7) → 139

1₀(51) → 52

1₀(45) → 46

1₀(210) → 211

1₀(34) → 54

1₀(105) → 106

1₀(168) → 169

1₀(38) → 39

1₀(60) → 53

1₀(220) → 221

1₀(257) → 258

1₀(213) → 198

1₀(110) → 111

1₀(155) → 156

1₀(90) → 91

1₀(195) → 196

1₀(87) → 88

1₀(18) → 13

1₀(28) → 29

1₀(3) → 4

1₀(243) → 244

1₀(97) → 98

1₀(234) → 235

1₀(154) → 155

1₀(116) → 117

1₀(9) → 6

1₀(163) → 164

1₀(235) → 236

1₀(145) → 146

1₀(191) → 192

1₀(196) → 197

1₀(50) → 51

1₀(180) → 181

1₀(224) → 225

1₀(102) → 103

1₀(117) → 118

1₀(181) → 166

1₀(246) → 247

1₀(2) → 7

1₀(68) → 69

1₀(186) → 187

1₀(190) → 191

3₀(130) → 131

3₀(169) → 170

3₀(78) → 79

3₀(120) → 121

3₀(193) → 194

3₀(3) → 27

3₀(7) → 8

3₀(240) → 241

3₀(77) → 78

3₀(58) → 59

3₀(143) → 144

3₀(140) → 141

3₀(133) → 134

3₀(170) → 171

3₀(113) → 114

3₀(248) → 249

3₀(131) → 132

3₀(84) → 85

3₀(187) → 188

3₀(75) → 76

3₀(177) → 178

3₀(62) → 63

3₀(42) → 154

3₀(149) → 150

3₀(126) → 127

3₀(233) → 234

3₀(55) → 56

3₀(81) → 82

3₀(4) → 126

3₀(43) → 44

3₀(22) → 23

3₀(2) → 3

3₀(57) → 58

3₀(185) → 186

3₀(17) → 18

3₀(192) → 193

3₀(104) → 105

3₀(152) → 138

3₀(54) → 55

3₀(226) → 227

3₀(103) → 104

3₀(12) → 10

3₀(255) → 256

3₀(218) → 219

2₁(271) → 272

2₁(281) → 282

2₁(272) → 273

2₁(282) → 283

4₀(2) → 14

4₀(132) → 133

4₀(21) → 22

4₀(175) → 176

4₀(205) → 206

4₀(88) → 80

4₀(247) → 248

4₀(162) → 163

4₀(42) → 43

4₀(59) → 60

4₀(24) → 25

4₀(136) → 137

4₀(46) → 40

4₀(173) → 174

4₀(174) → 175

4₀(85) → 86

4₀(232) → 233

4₀(176) → 177

4₀(230) → 231

4₀(11) → 12

4₀(172) → 173

4₀(92) → 93

4₀(253) → 254

4₀(36) → 37

4₀(93) → 94

4₀(251) → 252

4₀(183) → 184

4₀(56) → 57

4₀(148) → 149

4₀(262) → 263

4₀(216) → 217

4₀(197) → 182

4₀(189) → 190

4₀(3) → 167

4₀(52) → 47

4₀(29) → 30

4₀(127) → 128

4₀(94) → 95

4₀(215) → 216

4₀(7) → 90

2₀(2) → 20

2₀(237) → 238

2₀(263) → 245

2₀(184) → 185

2₀(146) → 147

2₀(95) → 96

2₀(225) → 226

2₀(30) → 31

2₀(107) → 108

2₀(25) → 19

2₀(4) → 5

2₀(8) → 9

2₀(21) → 199

2₀(222) → 223

2₀(151) → 152

2₀(150) → 151

2₀(223) → 224

2₀(83) → 84

2₀(100) → 101

2₀(141) → 142

2₀(66) → 67

2₀(203) → 204

2₀(256) → 257

2₀(23) → 24

2₀(241) → 242

2₀(139) → 140

2₀(208) → 209

2₀(228) → 214

2₀(15) → 16

2₀(27) → 28

2₀(35) → 36

2₀(20) → 21

2₀(82) → 83

2₀(41) → 42

2₀(44) → 45

2₀(242) → 243

2₀(5) → 1

2₀(231) → 232

2₀(106) → 107

2₀(200) → 201

2₀(158) → 159

2₀(115) → 116

2₀(194) → 195

2₀(171) → 172

1₁(280) → 281

1₁(270) → 271

3₁(279) → 280

3₁(269) → 270

0₀(101) → 102

0₀(8) → 11

0₀(201) → 202

0₀(160) → 161

0₀(135) → 136

0₀(164) → 165

0₀(122) → 123

0₀(69) → 61

0₀(96) → 97

0₀(157) → 158

0₀(128) → 129

0₀(207) → 208

0₀(39) → 32

0₀(41) → 48

0₀(20) → 183

0₀(67) → 68

0₀(167) → 168

0₀(209) → 210

0₀(156) → 157

0₀(49) → 50

0₀(72) → 73

0₀(159) → 160

0₀(14) → 15

0₀(16) → 17

0₀(48) → 49

0₀(165) → 153

0₀(206) → 207

0₀(261) → 262

0₀(137) → 125

0₀(179) → 180

0₀(121) → 122

0₀(254) → 255

0₀(144) → 145

0₀(134) → 135

0₀(109) → 110

0₀(64) → 65

0₀(76) → 77

0₀(33) → 34

0₀(212) → 213

0₀(204) → 205

0₀(178) → 179

0₀(71) → 72

0₀(2) → 33

0₀(113) → 230

0₀(258) → 259

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