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

Proof

1 Bounds

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

final states:

{173, 169, 166, 162, 158, 155, 150, 146, 145, 143, 140, 138, 136, 131, 126, 120, 116, 111, 109, 105, 103, 99, 96, 92, 90, 85, 80, 77, 75, 70, 67, 64, 61, 60, 56, 51, 46, 40, 37, 34, 29, 23, 18, 13, 7, 1}

transitions:

23 → 121

111 → 121

61 → 9

61 → 121

205 → 122

29 → 121

80 → 122

80 → 41

103 → 121

51 → 121

181 → 23

181 → 188

96 → 121

136 → 123

136 → 47

136 → 121

211 → 122

145 → 132

145 → 8

18 → 121

120 → 121

146 → 132

146 → 8

37 → 121

34 → 121

90 → 121

99 → 121

1 → 121

40 → 121

13 → 121

60 → 9

60 → 121

60 → 8

26 → 176

26 → 199

177 → 206

138 → 3

150 → 132

150 → 8

173 → 57

173 → 41

116 → 121

109 → 121

75 → 132

75 → 8

105 → 121

67 → 3

143 → 3

85 → 121

169 → 41

77 → 122

77 → 41

140 → 3

7 → 121

126 → 9

126 → 121

64 → 19

64 → 3

46 → 121

189 → 132

162 → 122

162 → 41

158 → 8

131 → 121

92 → 121

70 → 3

166 → 81

166 → 41

56 → 121

155 → 151

155 → 8

3₁(208) → 209

3₁(204) → 205

3₁(177) → 178

3₁(201) → 202

3₁(179) → 180

5₁(206) → 207

5₁(202) → 203

4₁(210) → 211

1₁(176) → 177

1₁(200) → 201

0₀(31) → 32

0₀(137) → 136

0₀(35) → 36

0₀(11) → 12

0₀(78) → 79

0₀(41) → 47

0₀(95) → 92

0₀(86) → 87

0₀(24) → 86

0₀(93) → 94

0₀(8) → 9

0₀(52) → 53

0₀(134) → 135

0₀(89) → 85

0₀(114) → 115

0₀(119) → 116

0₀(71) → 117

0₀(15) → 16

0₀(101) → 102

0₀(42) → 43

0₀(81) → 82

0₀(107) → 108

0₀(10) → 11

0₀(88) → 89

0₀(5) → 97

0₀(4) → 5

0₀(28) → 23

0₀(14) → 15

0₀(36) → 91

0₀(163) → 164

0₀(122) → 123

0₀(2) → 121

0₀(57) → 58

0₀(154) → 150

0₀(20) → 21

0₀(38) → 39

1₀(2) → 3

1₀(132) → 133

1₀(31) → 156

1₀(117) → 118

1₀(159) → 160

1₀(74) → 70

1₀(102) → 99

1₀(152) → 153

1₀(167) → 168

1₀(71) → 72

1₀(129) → 130

1₀(87) → 88

1₀(4) → 65

1₀(59) → 56

1₀(24) → 25

1₀(115) → 111

1₀(144) → 143

1₀(164) → 165

1₀(47) → 48

1₀(8) → 30

1₀(123) → 124

1₀(36) → 104

1₀(27) → 28

1₀(163) → 174

1₀(54) → 55

1₀(97) → 139

1₀(148) → 149

1₀(118) → 119

1₀(62) → 76

1₀(69) → 67

1₀(39) → 37

1₀(142) → 140

1₀(3) → 19

1₀(52) → 106

1₀(43) → 44

1₀(94) → 95

1₀(171) → 172

1₀(30) → 100

3₀(100) → 101

3₀(170) → 171

3₀(41) → 42

3₀(30) → 31

3₀(19) → 20

3₀(108) → 105

3₀(58) → 59

3₀(35) → 38

3₀(8) → 14

3₀(125) → 120

3₀(168) → 166

3₀(32) → 33

3₀(79) → 77

3₀(55) → 51

3₀(82) → 83

3₀(3) → 4

3₀(47) → 62

3₀(121) → 127

3₀(57) → 163

3₀(9) → 10

3₀(12) → 7

3₀(72) → 73

3₀(135) → 131

3₀(21) → 22

3₀(53) → 54

3₀(48) → 49

3₀(5) → 6

3₀(2) → 24

3₀(153) → 154

3₀(68) → 69

3₀(16) → 17

3₀(52) → 93

4₀(25) → 26

4₀(106) → 107

4₀(112) → 113

4₀(8) → 112

4₀(160) → 161

4₀(97) → 98

4₀(172) → 169

4₀(141) → 142

4₀(44) → 45

4₀(84) → 80

4₀(147) → 148

4₀(83) → 110

4₀(49) → 50

4₀(48) → 141

4₀(165) → 162

4₀(133) → 134

4₀(65) → 66

4₀(76) → 144

4₀(174) → 175

4₀(127) → 128

4₀(113) → 114

5₀(31) → 78

5₀(132) → 170

5₀(121) → 122

5₀(48) → 167

5₀(24) → 71

5₀(175) → 173

5₀(139) → 138

5₀(98) → 96

5₀(73) → 74

5₀(66) → 64

5₀(4) → 35

5₀(151) → 152

5₀(2) → 41

5₀(3) → 81

5₀(36) → 137

5₀(41) → 57

5₀(124) → 125

5₀(35) → 68

5₀(8) → 52

5₀(52) → 159

f6₀ → 2

2₀(2) → 8

2₀(157) → 155

2₀(149) → 146

2₀(156) → 157

2₀(91) → 90

2₀(128) → 129

2₀(110) → 109

2₀(50) → 46

2₀(95) → 145

2₀(36) → 34

2₀(8) → 151

2₀(63) → 61

2₀(26) → 27

2₀(104) → 103

2₀(76) → 75

2₀(17) → 13

2₀(6) → 1

2₀(83) → 84

2₀(62) → 63

2₀(121) → 132

2₀(161) → 158

2₀(1) → 60

2₀(130) → 126

2₀(33) → 29

2₀(45) → 40

2₀(22) → 18

2₀(127) → 147

0₁(207) → 208

0₁(203) → 204

0₁(178) → 179

2₁(199) → 200

2₁(180) → 181

2₁(188) → 189

2₁(209) → 210

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