YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 Bounds

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

final states:

{201, 194, 185, 176, 166, 157, 149, 140, 131, 122, 114, 105, 97, 88, 78, 69, 60, 51, 41, 32, 22, 12, 1}

transitions:

78 → 89

78 → 13

157 → 3

176 → 13

32 → 132

32 → 3

51 → 106

51 → 79

97 → 13

149 → 3

122 → 142

122 → 23

41 → 3

185 → 70

185 → 13

1 → 106

1 → 79

60 → 168

60 → 79

201 → 167

88 → 79

22 → 79

105 → 13

230 → 71

230 → 106

114 → 89

114 → 13

12 → 3

140 → 79

69 → 79

131 → 79

194 → 80

194 → 167

166 → 141

166 → 3

192 → 220

4₁(228) → 229

4₁(225) → 226

5₁(222) → 223

5₁(224) → 225

1₀(190) → 191

1₀(35) → 36

1₀(53) → 54

1₀(19) → 20

1₀(173) → 174

1₀(162) → 163

1₀(86) → 87

1₀(123) → 124

1₀(21) → 12

1₀(143) → 144

1₀(8) → 9

1₀(135) → 136

1₀(89) → 90

1₀(165) → 157

1₀(133) → 134

1₀(64) → 65

1₀(59) → 51

1₀(118) → 119

1₀(151) → 152

1₀(83) → 84

1₀(79) → 132

1₀(109) → 110

1₀(39) → 40

1₀(171) → 172

1₀(55) → 56

1₀(13) → 52

1₀(5) → 6

1₀(124) → 125

1₀(14) → 15

1₀(40) → 32

1₀(2) → 3

1₀(57) → 58

1₀(23) → 141

1₀(147) → 148

1₀(192) → 193

1₀(168) → 169

1₀(156) → 149

1₀(100) → 101

5₀(2) → 23

5₀(82) → 83

5₀(95) → 96

5₀(120) → 121

5₀(74) → 75

5₀(161) → 162

5₀(6) → 7

5₀(26) → 27

5₀(129) → 130

5₀(110) → 111

5₀(42) → 43

5₀(37) → 38

5₀(4) → 5

5₀(24) → 115

5₀(112) → 113

5₀(47) → 48

5₀(203) → 204

5₀(141) → 142

5₀(23) → 61

5₀(107) → 108

5₀(90) → 91

5₀(84) → 85

5₀(15) → 16

5₀(49) → 50

5₀(81) → 82

5₀(208) → 201

5₀(65) → 66

4₀(98) → 99

4₀(33) → 34

4₀(177) → 178

4₀(126) → 127

4₀(23) → 24

4₀(206) → 207

4₀(170) → 171

4₀(42) → 186

4₀(76) → 77

4₀(160) → 161

4₀(108) → 109

4₀(142) → 143

4₀(85) → 86

4₀(7) → 8

4₀(178) → 179

4₀(130) → 122

4₀(174) → 175

4₀(45) → 46

4₀(99) → 100

4₀(134) → 135

4₀(79) → 177

4₀(187) → 188

4₀(152) → 153

4₀(36) → 37

4₀(29) → 30

4₀(172) → 173

4₀(175) → 166

4₀(164) → 165

4₀(104) → 97

4₀(145) → 146

4₀(204) → 205

4₀(94) → 95

4₀(180) → 181

4₀(61) → 62

4₀(72) → 73

4₀(102) → 103

4₀(189) → 190

4₀(13) → 14

4₀(31) → 22

4₀(62) → 63

4₀(48) → 49

4₀(119) → 120

4₀(10) → 11

4₀(2) → 42

4₀(4) → 98

4₀(153) → 154

4₀(188) → 189

4₀(198) → 199

2₀(42) → 70

2₀(17) → 18

2₀(101) → 102

2₀(191) → 192

2₀(46) → 47

2₀(61) → 150

2₀(63) → 64

2₀(169) → 195

2₀(27) → 28

2₀(66) → 67

2₀(96) → 88

2₀(202) → 203

2₀(196) → 197

2₀(184) → 176

2₀(56) → 57

2₀(43) → 44

2₀(20) → 21

2₀(116) → 117

2₀(182) → 183

2₀(193) → 185

2₀(16) → 17

2₀(3) → 89

2₀(80) → 81

2₀(30) → 31

2₀(137) → 138

2₀(34) → 35

2₀(179) → 180

2₀(121) → 114

2₀(18) → 19

2₀(77) → 69

2₀(38) → 39

2₀(199) → 200

2₀(23) → 158

2₀(68) → 60

2₀(91) → 92

2₀(115) → 116

2₀(75) → 76

2₀(2) → 13

2₀(113) → 105

2₀(73) → 74

3₀(138) → 139

3₀(146) → 147

3₀(93) → 94

3₀(197) → 198

3₀(79) → 80

3₀(24) → 25

3₀(169) → 170

3₀(125) → 126

3₀(54) → 55

3₀(181) → 182

3₀(50) → 41

3₀(186) → 187

3₀(71) → 72

3₀(117) → 118

3₀(111) → 112

3₀(2) → 167

3₀(44) → 45

3₀(52) → 53

3₀(13) → 33

3₀(136) → 137

3₀(207) → 208

3₀(158) → 159

3₀(25) → 26

3₀(154) → 155

3₀(195) → 196

f6₀ → 2

0₀(2) → 79

0₀(167) → 168

0₀(163) → 164

0₀(28) → 29

0₀(123) → 202

0₀(9) → 10

0₀(128) → 129

0₀(67) → 68

0₀(92) → 93

0₀(159) → 160

0₀(155) → 156

0₀(150) → 151

0₀(3) → 4

0₀(11) → 1

0₀(87) → 78

0₀(70) → 71

0₀(132) → 133

0₀(139) → 131

0₀(205) → 206

0₀(103) → 104

0₀(127) → 128

0₀(42) → 123

0₀(183) → 184

0₀(58) → 59

0₀(144) → 145

0₀(106) → 107

0₀(13) → 106

0₀(200) → 194

0₀(148) → 140

1₁(220) → 221

1₁(223) → 224

1₁(226) → 227

0₁(229) → 230

0₁(227) → 228

0₁(221) → 222

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