YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 Bounds

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

final states:

{217, 201, 186, 172, 155, 143, 133, 121, 112, 100, 89, 80, 70, 63, 55, 47, 42, 34, 28, 23, 18, 13, 9, 5, 1}

transitions:

23 → 6

89 → 187

89 → 24

80 → 29

80 → 14

133 → 71

133 → 10

18 → 10

9 → 6

5 → 122

5 → 6

34 → 3

55 → 101

55 → 24

1 → 6

13 → 20

13 → 4

13 → 3

201 → 156

201 → 3

186 → 10

172 → 48

172 → 24

172 → 101

121 → 3

143 → 35

28 → 35

63 → 24

112 → 49

112 → 3

100 → 25

100 → 6

217 → 6

42 → 24

47 → 7

47 → 35

70 → 14

155 → 3

f6₀ → 2

4₀(138) → 139

4₀(147) → 148

4₀(20) → 21

4₀(72) → 73

4₀(79) → 70

4₀(227) → 228

4₀(24) → 56

4₀(120) → 112

4₀(7) → 134

4₀(202) → 203

4₀(225) → 226

4₀(194) → 195

4₀(145) → 146

4₀(167) → 168

4₀(38) → 39

4₀(117) → 118

4₀(14) → 15

4₀(49) → 50

4₀(177) → 178

4₀(174) → 175

4₀(2) → 14

4₀(3) → 29

4₀(30) → 173

4₀(44) → 45

4₀(35) → 218

4₀(58) → 59

4₀(29) → 202

4₀(164) → 165

4₀(78) → 79

4₀(161) → 162

4₀(10) → 81

4₀(33) → 28

4₀(226) → 227

4₀(196) → 197

4₀(158) → 159

1₀(114) → 115

1₀(106) → 107

1₀(137) → 138

1₀(150) → 151

1₀(81) → 82

1₀(218) → 219

1₀(216) → 201

1₀(14) → 19

1₀(30) → 31

1₀(19) → 20

1₀(166) → 167

1₀(212) → 213

1₀(118) → 119

1₀(130) → 131

1₀(51) → 52

1₀(84) → 85

1₀(32) → 33

1₀(6) → 156

1₀(231) → 232

1₀(134) → 135

1₀(149) → 150

1₀(228) → 229

1₀(185) → 172

1₀(90) → 91

1₀(29) → 30

1₀(222) → 223

1₀(3) → 4

1₀(40) → 41

1₀(139) → 140

1₀(64) → 65

1₀(204) → 205

1₀(146) → 147

1₀(61) → 62

1₀(102) → 103

1₀(189) → 190

1₀(215) → 216

1₀(71) → 72

1₀(31) → 32

1₀(48) → 49

1₀(103) → 104

1₀(17) → 13

1₀(2) → 3

1₀(4) → 64

1₀(229) → 230

1₀(211) → 212

1₀(157) → 158

1₀(66) → 67

0₀(35) → 122

0₀(173) → 174

0₀(127) → 128

0₀(234) → 217

0₀(210) → 211

0₀(37) → 38

0₀(95) → 96

0₀(125) → 126

0₀(207) → 208

0₀(24) → 25

0₀(8) → 5

0₀(87) → 88

0₀(52) → 53

0₀(159) → 160

0₀(111) → 100

0₀(59) → 60

0₀(208) → 209

0₀(151) → 152

0₀(179) → 180

0₀(27) → 23

0₀(94) → 95

0₀(60) → 61

0₀(96) → 97

0₀(75) → 76

0₀(62) → 55

0₀(39) → 40

0₀(171) → 155

0₀(233) → 234

0₀(107) → 108

0₀(43) → 44

0₀(163) → 164

0₀(122) → 123

0₀(2) → 6

0₀(85) → 86

0₀(168) → 169

0₀(104) → 105

0₀(152) → 153

0₀(12) → 9

0₀(188) → 189

5₀(41) → 34

5₀(213) → 214

5₀(2) → 10

5₀(25) → 144

5₀(82) → 83

5₀(45) → 46

5₀(113) → 114

5₀(162) → 163

5₀(209) → 210

5₀(192) → 193

5₀(136) → 137

5₀(144) → 145

5₀(77) → 78

5₀(119) → 120

5₀(220) → 221

5₀(232) → 233

5₀(190) → 191

5₀(91) → 92

5₀(203) → 204

5₀(176) → 177

5₀(199) → 200

5₀(105) → 106

5₀(11) → 113

5₀(108) → 109

5₀(135) → 136

5₀(92) → 93

5₀(36) → 37

5₀(14) → 71

5₀(195) → 196

5₀(200) → 186

5₀(156) → 157

5₀(219) → 220

5₀(197) → 198

5₀(67) → 68

5₀(221) → 222

5₀(142) → 133

5₀(10) → 11

5₀(101) → 102

5₀(22) → 18

5₀(7) → 8

3₀(2) → 24

3₀(46) → 42

3₀(65) → 66

3₀(128) → 129

3₀(175) → 176

3₀(110) → 111

3₀(99) → 89

3₀(24) → 48

3₀(131) → 132

3₀(4) → 1

3₀(26) → 27

3₀(74) → 75

3₀(181) → 182

3₀(223) → 224

3₀(206) → 207

3₀(3) → 187

3₀(214) → 215

3₀(11) → 12

3₀(6) → 101

3₀(53) → 54

3₀(140) → 141

3₀(29) → 43

3₀(180) → 181

3₀(165) → 166

3₀(35) → 36

3₀(205) → 206

3₀(57) → 58

3₀(97) → 98

3₀(116) → 117

3₀(153) → 154

3₀(69) → 63

2₀(170) → 171

2₀(25) → 26

2₀(21) → 22

2₀(191) → 192

2₀(132) → 121

2₀(160) → 161

2₀(123) → 124

2₀(86) → 87

2₀(88) → 80

2₀(98) → 99

2₀(141) → 142

2₀(50) → 51

2₀(230) → 231

2₀(129) → 130

2₀(124) → 125

2₀(169) → 170

2₀(198) → 199

2₀(54) → 47

2₀(184) → 185

2₀(56) → 57

2₀(6) → 7

2₀(93) → 94

2₀(148) → 149

2₀(15) → 16

2₀(83) → 84

2₀(182) → 183

2₀(193) → 194

2₀(154) → 143

2₀(14) → 90

2₀(16) → 17

2₀(224) → 225

2₀(183) → 184

2₀(126) → 127

2₀(109) → 110

2₀(76) → 77

2₀(68) → 69

2₀(115) → 116

2₀(178) → 179

2₀(187) → 188

2₀(2) → 35

2₀(73) → 74

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