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

Proof

1 Bounds

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

final states:

{226, 211, 195, 179, 163, 148, 132, 119, 108, 98, 87, 77, 68, 58, 50, 44, 37, 31, 26, 22, 16, 13, 8, 5, 1}

transitions:

87 → 7

87 → 38

98 → 27

98 → 9

211 → 11

211 → 3

119 → 110

119 → 45

119 → 38

226 → 6

50 → 164

50 → 17

108 → 212

108 → 120

108 → 3

5 → 11

5 → 3

37 → 60

37 → 59

31 → 59

1 → 180

1 → 88

1 → 3

8 → 38

13 → 149

13 → 38

44 → 3

179 → 11

179 → 3

26 → 6

58 → 9

22 → 27

22 → 9

16 → 45

16 → 38

77 → 6

250 → 11

68 → 17

148 → 59

132 → 17

195 → 109

195 → 38

24 → 247

163 → 60

163 → 59

f6₀ → 2

4₀(138) → 139

4₀(60) → 61

4₀(137) → 138

4₀(185) → 186

4₀(24) → 25

4₀(32) → 33

4₀(9) → 99

4₀(217) → 218

4₀(42) → 43

4₀(206) → 207

4₀(145) → 146

4₀(186) → 187

4₀(62) → 63

4₀(84) → 85

4₀(76) → 68

4₀(174) → 175

4₀(2) → 9

4₀(3) → 51

4₀(41) → 42

4₀(107) → 98

4₀(149) → 150

4₀(164) → 165

4₀(110) → 111

4₀(115) → 116

4₀(47) → 48

4₀(17) → 27

4₀(39) → 40

4₀(158) → 159

4₀(100) → 101

4₀(25) → 22

4₀(153) → 154

4₀(223) → 224

4₀(154) → 155

4₀(159) → 160

1₀(65) → 66

1₀(123) → 124

1₀(78) → 79

1₀(63) → 64

1₀(59) → 69

1₀(144) → 145

1₀(166) → 167

1₀(212) → 213

1₀(173) → 174

1₀(7) → 227

1₀(207) → 208

1₀(11) → 12

1₀(143) → 144

1₀(38) → 133

1₀(6) → 164

1₀(220) → 221

1₀(134) → 135

1₀(152) → 153

1₀(155) → 156

1₀(55) → 56

1₀(209) → 210

1₀(197) → 198

1₀(29) → 30

1₀(222) → 223

1₀(3) → 4

1₀(175) → 176

1₀(40) → 41

1₀(139) → 140

1₀(64) → 65

1₀(113) → 114

1₀(57) → 50

1₀(191) → 192

1₀(192) → 193

1₀(83) → 84

1₀(215) → 216

1₀(117) → 118

1₀(103) → 104

1₀(67) → 58

1₀(17) → 78

1₀(2) → 17

1₀(141) → 142

3₀(189) → 190

3₀(51) → 52

3₀(130) → 131

3₀(180) → 181

3₀(49) → 44

3₀(95) → 96

3₀(86) → 77

3₀(33) → 34

3₀(125) → 126

3₀(48) → 49

3₀(121) → 122

3₀(61) → 62

3₀(93) → 94

3₀(167) → 168

3₀(228) → 229

3₀(106) → 107

3₀(133) → 134

3₀(111) → 112

3₀(238) → 239

3₀(128) → 129

3₀(18) → 19

3₀(199) → 200

3₀(9) → 10

3₀(59) → 109

3₀(70) → 71

3₀(151) → 152

3₀(6) → 7

3₀(131) → 119

3₀(109) → 110

3₀(236) → 237

3₀(177) → 178

3₀(72) → 73

3₀(15) → 13

3₀(161) → 162

3₀(126) → 127

3₀(233) → 234

3₀(196) → 197

3₀(225) → 211

3₀(182) → 183

3₀(122) → 123

3₀(2) → 38

3₀(17) → 149

3₀(69) → 70

3₀(104) → 105

3₀(54) → 55

3₀(38) → 45

3₀(235) → 236

3₀(218) → 219

3₀(219) → 220

0₁(249) → 250

2₀(2) → 6

2₀(6) → 23

2₀(227) → 228

2₀(201) → 202

2₀(193) → 194

2₀(147) → 132

2₀(88) → 89

2₀(28) → 29

2₀(46) → 47

2₀(165) → 166

2₀(85) → 86

2₀(150) → 151

2₀(89) → 90

2₀(187) → 188

2₀(203) → 204

2₀(176) → 177

2₀(135) → 136

2₀(181) → 182

2₀(183) → 184

2₀(14) → 15

2₀(97) → 87

2₀(156) → 157

2₀(79) → 80

2₀(241) → 242

2₀(38) → 39

2₀(146) → 147

2₀(237) → 238

2₀(3) → 196

2₀(52) → 53

2₀(75) → 76

2₀(81) → 82

2₀(208) → 209

2₀(35) → 36

0₀(2) → 3

0₀(114) → 115

0₀(196) → 212

0₀(56) → 57

0₀(91) → 92

0₀(9) → 14

0₀(224) → 225

0₀(90) → 91

0₀(10) → 11

0₀(184) → 185

0₀(230) → 231

0₀(202) → 203

0₀(213) → 214

0₀(19) → 20

0₀(232) → 233

0₀(71) → 72

0₀(92) → 93

0₀(4) → 1

0₀(21) → 16

0₀(96) → 97

0₀(3) → 32

0₀(214) → 215

0₀(17) → 88

0₀(6) → 120

0₀(118) → 108

0₀(53) → 54

0₀(66) → 67

0₀(140) → 141

0₀(23) → 24

0₀(94) → 95

0₀(216) → 217

0₀(7) → 5

0₀(27) → 28

0₀(101) → 102

0₀(205) → 206

0₀(20) → 21

0₀(142) → 143

0₀(229) → 230

0₀(78) → 180

0₀(242) → 226

0₀(210) → 195

0₀(231) → 232

0₀(194) → 179

0₀(102) → 103

0₀(171) → 172

3₁(248) → 249

2₁(247) → 248

5₀(170) → 171

5₀(17) → 18

5₀(112) → 113

5₀(160) → 161

5₀(120) → 121

5₀(99) → 100

5₀(82) → 83

5₀(172) → 173

5₀(129) → 130

5₀(136) → 137

5₀(124) → 125

5₀(59) → 60

5₀(169) → 170

5₀(36) → 31

5₀(157) → 158

5₀(198) → 199

5₀(43) → 37

5₀(162) → 148

5₀(239) → 240

5₀(234) → 235

5₀(116) → 117

5₀(80) → 81

5₀(74) → 75

5₀(30) → 26

5₀(240) → 241

5₀(190) → 191

5₀(34) → 35

5₀(45) → 46

5₀(12) → 8

5₀(188) → 189

5₀(127) → 128

5₀(204) → 205

5₀(178) → 163

5₀(105) → 106

5₀(2) → 59

5₀(73) → 74

5₀(221) → 222

5₀(168) → 169

5₀(200) → 201

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