YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 Bounds

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

final states:

{165, 160, 156, 153, 150, 146, 141, 136, 132, 127, 122, 121, 117, 114, 110, 108, 105, 101, 98, 93, 88, 84, 79, 75, 71, 70, 68, 64, 60, 59, 34, 56, 55, 52, 46, 42, 38, 35, 31, 28, 24, 21, 16, 10, 6, 1}

transitions:

223 → 123

111 → 183

98 → 128

98 → 17

10 → 17

96 → 236

129 → 188

129 → 204

84 → 17

136 → 128

136 → 17

211 → 191

122 → 17

227 → 220

187 → 110

146 → 128

146 → 17

108 → 123

108 → 61

209 → 127

59 → 123

59 → 61

110 → 123

110 → 61

34 → 17

55 → 17

243 → 220

99 → 242

31 → 17

1 → 17

71 → 17

165 → 85

165 → 61

127 → 17

101 → 128

101 → 17

60 → 61

73 → 234

125 → 246

38 → 17

235 → 220

79 → 17

21 → 17

141 → 128

141 → 17

150 → 128

150 → 17

172 → 108

121 → 89

121 → 17

6 → 17

153 → 123

153 → 61

88 → 17

52 → 17

22 → 226

75 → 17

105 → 128

105 → 17

237 → 220

249 → 169

117 → 85

117 → 61

28 → 17

16 → 17

114 → 85

114 → 61

93 → 128

93 → 17

63 → 168

12 → 230

42 → 17

64 → 61

46 → 17

35 → 17

231 → 220

160 → 80

160 → 61

68 → 61

148 → 248

132 → 17

24 → 17

19 → 219

70 → 17

56 → 17

191 → 210

192 → 127

156 → 80

156 → 61

247 → 169

4₁(210) → 211

2₁(220) → 221

2₁(188) → 189

2₁(169) → 170

2₁(184) → 185

2₁(207) → 208

0₁(221) → 222

0₁(185) → 186

0₁(208) → 209

0₁(170) → 171

5₁(222) → 223

5₁(204) → 205

5₁(186) → 187

5₁(171) → 172

5₁(189) → 190

1₀(137) → 138

1₀(65) → 66

1₀(19) → 20

1₀(11) → 57

1₀(73) → 74

1₀(7) → 8

1₀(129) → 130

1₀(125) → 126

1₀(32) → 36

1₀(61) → 142

1₀(87) → 84

1₀(159) → 156

1₀(29) → 72

1₀(111) → 112

1₀(83) → 79

1₀(99) → 100

1₀(27) → 24

1₀(96) → 97

1₀(148) → 149

1₀(39) → 133

1₀(161) → 162

1₀(63) → 60

1₀(43) → 44

1₀(47) → 137

1₀(22) → 23

1₀(2) → 3

1₀(154) → 155

1₀(69) → 68

1₀(12) → 13

3₀(2) → 7

3₀(82) → 83

3₀(26) → 27

3₀(147) → 148

3₀(76) → 77

3₀(12) → 22

3₀(47) → 65

3₀(91) → 92

3₀(123) → 124

3₀(11) → 29

3₀(18) → 19

3₀(62) → 63

3₀(49) → 50

3₀(130) → 131

3₀(29) → 43

3₀(94) → 95

3₀(158) → 159

3₀(7) → 39

2₀(106) → 107

2₀(151) → 152

2₀(144) → 145

2₀(142) → 143

2₀(8) → 9

2₀(11) → 118

2₀(32) → 33

2₀(134) → 135

2₀(155) → 153

2₀(92) → 88

2₀(131) → 127

2₀(109) → 108

2₀(36) → 37

2₀(29) → 30

2₀(3) → 4

2₀(47) → 85

2₀(40) → 41

2₀(139) → 140

2₀(164) → 160

2₀(113) → 110

2₀(57) → 58

2₀(116) → 114

2₀(54) → 52

2₀(50) → 51

2₀(162) → 163

2₀(61) → 80

2₀(72) → 166

2₀(13) → 14

2₀(62) → 157

2₀(103) → 104

2₀(119) → 120

2₀(17) → 123

2₀(2) → 61

2₀(44) → 45

2₀(39) → 115

2₀(66) → 67

4₀(19) → 53

4₀(25) → 26

4₀(17) → 18

4₀(47) → 111

4₀(86) → 87

4₀(63) → 69

4₀(53) → 54

4₀(124) → 125

4₀(11) → 12

4₀(4) → 76

4₀(7) → 32

4₀(90) → 91

4₀(39) → 40

4₀(89) → 90

4₀(72) → 73

4₀(48) → 49

4₀(102) → 103

4₀(81) → 82

4₀(95) → 96

4₀(138) → 139

4₀(18) → 25

4₀(85) → 147

4₀(2) → 11

5₀(166) → 167

5₀(118) → 119

5₀(19) → 99

5₀(7) → 102

5₀(61) → 62

5₀(133) → 134

5₀(5) → 59

5₀(11) → 94

5₀(167) → 165

5₀(66) → 151

5₀(2) → 47

5₀(3) → 161

5₀(143) → 144

5₀(1) → 70

5₀(115) → 116

5₀(47) → 48

5₀(39) → 106

f6₀ → 2

0₀(2) → 17

0₀(157) → 158

0₀(163) → 164

0₀(51) → 46

0₀(149) → 146

0₀(9) → 6

0₀(128) → 129

0₀(67) → 64

0₀(80) → 81

0₀(30) → 28

0₀(152) → 150

0₀(107) → 105

0₀(4) → 5

0₀(37) → 35

0₀(104) → 101

0₀(74) → 71

0₀(17) → 89

0₀(135) → 132

0₀(14) → 15

0₀(100) → 98

0₀(140) → 136

0₀(23) → 21

0₀(112) → 113

0₀(33) → 34

0₀(15) → 10

0₀(45) → 42

0₀(85) → 86

0₀(20) → 16

0₀(120) → 117

0₀(126) → 122

0₀(97) → 93

0₀(60) → 109

0₀(34) → 31

0₀(41) → 38

0₀(78) → 75

0₀(109) → 121

0₀(58) → 56

0₀(5) → 1

0₀(145) → 141

0₀(77) → 78

0₀(13) → 55

0₀(72) → 154

0₀(47) → 128

3₁(205) → 206

3₁(190) → 191

1₁(246) → 247

1₁(183) → 184

1₁(248) → 249

1₁(219) → 220

1₁(191) → 192

1₁(236) → 237

1₁(168) → 169

1₁(230) → 231

1₁(234) → 235

1₁(242) → 243

1₁(226) → 227

1₁(206) → 207

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