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(x0))))	→	0(0(1(x0)))
1(2(3(3(4(5(x0))))))	→	4(0(0(1(5(x0)))))
4(4(3(4(3(1(3(x0)))))))	→	0(1(3(1(4(4(x0))))))
5(2(5(2(5(1(1(x0)))))))	→	5(4(5(5(1(x0)))))
1(0(5(5(5(3(4(1(x0))))))))	→	4(3(0(3(4(3(0(5(0(x0)))))))))
3(4(3(0(4(0(3(2(x0))))))))	→	5(1(5(4(2(x0)))))
0(5(3(2(3(1(5(4(4(x0)))))))))	→	0(0(4(4(1(0(3(4(x0))))))))
1(0(4(3(5(2(1(0(1(x0)))))))))	→	1(4(2(0(1(1(3(4(1(x0)))))))))
5(3(2(1(1(2(1(5(3(x0)))))))))	→	5(1(4(3(3(5(0(4(x0))))))))
1(2(4(4(4(5(5(0(2(2(x0))))))))))	→	4(4(1(1(0(5(5(5(0(x0)))))))))
2(1(3(1(5(5(5(1(1(1(x0))))))))))	→	5(4(2(3(5(4(2(2(1(x0)))))))))
2(0(3(1(1(0(2(5(3(3(2(3(x0))))))))))))	→	5(4(0(4(4(4(1(4(0(3(x0))))))))))
3(4(1(1(4(0(1(2(2(4(5(3(2(x0)))))))))))))	→	5(3(1(3(4(5(4(0(3(0(1(x0)))))))))))
1(2(0(3(1(0(4(3(3(0(3(0(5(3(x0))))))))))))))	→	4(2(0(5(3(3(4(4(3(1(5(0(4(x0)))))))))))))
1(5(4(4(3(2(4(0(1(5(2(0(5(2(x0))))))))))))))	→	1(5(5(2(2(2(4(0(0(5(3(3(2(2(2(0(x0))))))))))))))))
3(5(0(1(4(0(0(1(3(5(4(1(0(2(x0))))))))))))))	→	1(1(4(1(1(5(0(3(0(0(4(5(0(x0)))))))))))))
3(2(3(4(3(5(5(3(4(0(5(4(3(5(2(x0)))))))))))))))	→	3(5(5(0(1(4(3(4(1(1(5(1(0(x0)))))))))))))
0(0(2(2(5(0(3(0(4(0(4(0(2(3(1(5(x0))))))))))))))))	→	0(4(2(5(2(5(3(0(4(3(2(0(2(4(5(x0)))))))))))))))
2(1(3(0(5(1(2(2(5(5(1(0(2(1(3(2(x0))))))))))))))))	→	5(5(2(3(2(4(5(0(2(0(3(3(4(1(1(x0)))))))))))))))
2(4(4(1(5(2(3(3(2(0(4(5(3(5(0(2(x0))))))))))))))))	→	0(5(1(4(5(2(4(1(1(5(4(3(3(x0)))))))))))))
1(5(0(0(1(4(5(3(5(4(1(0(1(2(1(2(0(x0)))))))))))))))))	→	1(4(0(1(3(5(3(3(4(1(0(4(3(3(0(5(1(0(x0))))))))))))))))))
4(0(4(4(2(1(4(2(0(3(1(2(5(5(5(5(3(1(2(x0)))))))))))))))))))	→	3(5(4(4(2(0(4(4(4(0(1(0(2(4(0(4(1(5(x0))))))))))))))))))
1(1(0(1(1(4(5(0(4(1(3(0(4(4(0(5(5(0(2(0(x0))))))))))))))))))))	→	4(0(5(3(5(3(2(2(5(3(5(1(2(4(2(4(5(0(5(5(x0))))))))))))))))))))
3(1(2(1(3(1(1(4(3(5(2(0(3(3(2(3(1(3(0(1(x0))))))))))))))))))))	→	0(4(3(5(1(4(2(4(0(5(3(2(4(1(5(5(1(x0)))))))))))))))))
5(0(1(3(4(2(1(3(1(4(2(0(0(2(3(2(5(2(2(4(x0))))))))))))))))))))	→	5(4(1(5(5(0(1(3(1(2(1(1(2(4(3(2(5(x0)))))))))))))))))

Proof

1 Bounds

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

final states:

{242, 228, 209, 193, 178, 166, 152, 138, 126, 115, 100, 90, 81, 71, 63, 56, 49, 41, 34, 29, 20, 16, 10, 5, 1}

transitions:

29 → 35

29 → 72

81 → 155

81 → 43

81 → 35

81 → 72

152 → 64

152 → 30

10 → 12

10 → 11

41 → 127

41 → 3

5 → 3

209 → 153

209 → 3

34 → 21

90 → 3

20 → 127

20 → 3

193 → 11

49 → 6

1 → 4

1 → 21

71 → 101

71 → 30

138 → 21

178 → 7

178 → 3

16 → 6

63 → 64

63 → 30

100 → 7

100 → 3

126 → 72

115 → 72

242 → 22

242 → 6

166 → 30

56 → 3

228 → 72

f6₀ → 2

2₀(64) → 65

2₀(235) → 236

2₀(147) → 148

2₀(230) → 231

2₀(68) → 69

2₀(172) → 173

2₀(21) → 101

2₀(139) → 140

2₀(157) → 158

2₀(98) → 99

2₀(46) → 47

2₀(215) → 216

2₀(6) → 243

2₀(109) → 110

2₀(213) → 214

2₀(245) → 246

2₀(111) → 112

2₀(2) → 30

2₀(163) → 164

2₀(3) → 64

2₀(221) → 222

2₀(149) → 150

2₀(101) → 102

2₀(161) → 162

2₀(110) → 111

2₀(196) → 197

2₀(102) → 103

2₀(204) → 205

2₀(248) → 249

2₀(141) → 142

2₀(220) → 221

1₀(114) → 100

1₀(124) → 125

1₀(170) → 171

1₀(216) → 217

1₀(14) → 15

1₀(251) → 252

1₀(183) → 184

1₀(59) → 60

1₀(169) → 170

1₀(51) → 91

1₀(125) → 115

1₀(32) → 33

1₀(6) → 7

1₀(60) → 61

1₀(247) → 248

1₀(43) → 44

1₀(129) → 130

1₀(36) → 37

1₀(87) → 88

1₀(18) → 229

1₀(3) → 153

1₀(249) → 250

1₀(175) → 176

1₀(121) → 122

1₀(255) → 256

1₀(54) → 55

1₀(12) → 13

1₀(128) → 129

1₀(192) → 178

1₀(189) → 190

1₀(21) → 127

1₀(74) → 75

1₀(48) → 41

1₀(133) → 134

1₀(246) → 247

1₀(122) → 123

1₀(2) → 3

1₀(237) → 238

1₀(44) → 45

1₀(198) → 199

4₀(244) → 245

4₀(130) → 131

4₀(65) → 66

4₀(53) → 54

4₀(11) → 12

4₀(229) → 230

4₀(212) → 213

4₀(73) → 74

4₀(92) → 93

4₀(200) → 201

4₀(234) → 235

4₀(30) → 31

4₀(37) → 38

4₀(227) → 209

4₀(174) → 175

4₀(3) → 42

4₀(7) → 194

4₀(240) → 241

4₀(195) → 196

4₀(77) → 78

4₀(24) → 25

4₀(123) → 124

4₀(61) → 62

4₀(184) → 185

4₀(143) → 144

4₀(150) → 151

4₀(93) → 94

4₀(167) → 168

4₀(256) → 257

4₀(206) → 207

4₀(108) → 109

4₀(18) → 19

4₀(9) → 5

4₀(83) → 84

4₀(99) → 90

4₀(201) → 202

4₀(6) → 139

4₀(79) → 80

4₀(236) → 237

4₀(75) → 76

4₀(62) → 56

4₀(171) → 172

4₀(76) → 77

4₀(214) → 215

4₀(205) → 206

4₀(191) → 192

4₀(181) → 182

4₀(202) → 203

4₀(28) → 20

4₀(160) → 161

4₀(47) → 48

4₀(22) → 116

4₀(2) → 11

4₀(85) → 86

4₀(69) → 70

4₀(38) → 39

4₀(153) → 154

4₀(132) → 133

5₀(2) → 6

5₀(31) → 32

5₀(21) → 22

5₀(159) → 160

5₀(120) → 121

5₀(6) → 210

5₀(225) → 226

5₀(113) → 114

5₀(211) → 212

5₀(19) → 16

5₀(50) → 51

5₀(136) → 137

5₀(112) → 113

5₀(173) → 174

5₀(80) → 71

5₀(254) → 255

5₀(165) → 152

5₀(232) → 233

5₀(164) → 165

5₀(70) → 63

5₀(89) → 81

5₀(223) → 224

5₀(207) → 208

5₀(187) → 188

5₀(176) → 177

5₀(55) → 49

5₀(105) → 106

5₀(135) → 136

5₀(253) → 254

5₀(238) → 239

5₀(217) → 218

5₀(148) → 149

5₀(17) → 18

5₀(57) → 58

5₀(219) → 220

5₀(257) → 242

5₀(84) → 85

5₀(66) → 67

5₀(168) → 169

5₀(33) → 29

5₀(146) → 147

5₀(3) → 17

5₀(127) → 128

5₀(96) → 97

5₀(22) → 57

0₀(2) → 21

0₀(177) → 166

0₀(156) → 157

0₀(117) → 118

0₀(128) → 179

0₀(134) → 135

0₀(197) → 198

0₀(252) → 253

0₀(107) → 108

0₀(4) → 1

0₀(8) → 9

0₀(233) → 234

0₀(26) → 27

0₀(151) → 138

0₀(3) → 4

0₀(11) → 50

0₀(203) → 204

0₀(140) → 141

0₀(241) → 228

0₀(7) → 8

0₀(15) → 10

0₀(35) → 36

0₀(45) → 46

0₀(22) → 23

0₀(82) → 83

0₀(39) → 40

0₀(40) → 34

0₀(97) → 98

0₀(226) → 227

0₀(78) → 79

0₀(190) → 191

0₀(58) → 59

0₀(210) → 211

0₀(144) → 145

0₀(106) → 107

0₀(199) → 200

0₀(158) → 159

0₀(72) → 73

0₀(116) → 117

0₀(194) → 195

0₀(119) → 120

0₀(182) → 183

3₀(25) → 26

3₀(42) → 43

3₀(186) → 187

3₀(218) → 219

3₀(142) → 143

3₀(86) → 87

3₀(88) → 89

3₀(208) → 193

3₀(222) → 223

3₀(94) → 95

3₀(11) → 35

3₀(27) → 28

3₀(4) → 82

3₀(13) → 14

3₀(162) → 163

3₀(239) → 240

3₀(118) → 119

3₀(67) → 68

3₀(155) → 156

3₀(72) → 167

3₀(52) → 53

3₀(154) → 155

3₀(103) → 104

3₀(145) → 146

3₀(137) → 126

3₀(224) → 225

3₀(95) → 96

3₀(179) → 180

3₀(185) → 186

3₀(250) → 251

3₀(131) → 132

3₀(180) → 181

3₀(51) → 52

3₀(23) → 24

3₀(91) → 92

3₀(104) → 105

3₀(188) → 189

3₀(231) → 232

3₀(2) → 72

3₀(243) → 244

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