YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 Bounds

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

final states:

{187, 183, 178, 175, 173, 171, 167, 162, 158, 154, 150, 148, 144, 140, 136, 133, 128, 124, 119, 115, 110, 106, 101, 97, 94, 93, 88, 84, 83, 81, 78, 75, 71, 66, 62, 57, 53, 49, 44, 38, 33, 29, 25, 19, 15, 12, 7, 1}

transitions:

78 → 35

78 → 67

33 → 8

25 → 130

25 → 8

29 → 130

29 → 8

128 → 8

81 → 35

81 → 67

97 → 67

15 → 8

84 → 35

84 → 67

136 → 8

167 → 35

167 → 67

119 → 111

119 → 3

145 → 204

133 → 8

57 → 8

187 → 67

209 → 9

110 → 67

34 → 198

175 → 67

62 → 8

49 → 8

1 → 9

1 → 3

1 → 67

71 → 35

71 → 67

101 → 67

183 → 67

44 → 8

38 → 8

150 → 67

178 → 67

173 → 35

173 → 67

171 → 35

171 → 67

88 → 35

88 → 67

75 → 35

75 → 67

124 → 111

124 → 3

53 → 8

66 → 8

106 → 67

93 → 35

93 → 67

12 → 8

140 → 8

7 → 8

162 → 35

162 → 67

158 → 35

158 → 67

115 → 129

115 → 3

83 → 35

83 → 67

154 → 188

154 → 67

148 → 67

203 → 81

19 → 8

144 → 8

94 → 35

94 → 67

f6₀ → 2

5₀(185) → 186

5₀(72) → 79

5₀(68) → 145

5₀(21) → 151

5₀(34) → 58

5₀(40) → 54

5₀(130) → 131

5₀(190) → 191

5₀(114) → 110

5₀(69) → 70

5₀(113) → 114

5₀(2) → 39

5₀(26) → 125

5₀(58) → 59

5₀(134) → 135

5₀(67) → 179

5₀(104) → 105

2₁(199) → 200

2₁(205) → 206

0₀(177) → 175

0₀(23) → 24

0₀(73) → 74

0₀(123) → 119

0₀(76) → 77

0₀(91) → 92

0₀(159) → 160

0₀(160) → 161

0₀(86) → 87

0₀(108) → 109

0₀(156) → 157

0₀(8) → 9

0₀(132) → 128

0₀(34) → 163

0₀(125) → 126

0₀(168) → 169

0₀(99) → 100

0₀(107) → 108

0₀(79) → 80

0₀(152) → 153

0₀(120) → 121

0₀(155) → 156

0₀(3) → 102

0₀(116) → 176

0₀(9) → 10

0₀(191) → 187

0₀(146) → 147

0₀(72) → 73

0₀(102) → 103

0₀(20) → 129

0₀(13) → 14

0₀(21) → 137

0₀(117) → 118

0₀(181) → 182

0₀(31) → 149

0₀(5) → 6

0₀(67) → 111

0₀(2) → 3

0₀(4) → 16

0₀(39) → 63

0₀(22) → 23

0₀(89) → 141

1₀(31) → 32

1₀(73) → 82

1₀(30) → 31

1₀(37) → 33

1₀(129) → 130

1₀(32) → 29

1₀(48) → 44

1₀(121) → 122

1₀(61) → 57

1₀(21) → 22

1₀(143) → 140

1₀(52) → 49

1₀(89) → 90

1₀(165) → 166

1₀(138) → 139

1₀(56) → 53

1₀(18) → 15

1₀(68) → 69

1₀(27) → 28

1₀(72) → 76

1₀(126) → 127

1₀(63) → 64

1₀(5) → 13

1₀(4) → 5

1₀(14) → 12

1₀(36) → 37

1₀(43) → 38

1₀(40) → 168

1₀(139) → 136

1₀(2) → 8

1₀(147) → 144

1₀(34) → 89

1₀(20) → 21

3₁(208) → 209

3₁(202) → 203

2₀(2) → 20

2₀(95) → 96

2₀(188) → 189

2₀(113) → 174

2₀(26) → 27

2₀(58) → 107

2₀(186) → 183

2₀(51) → 52

2₀(42) → 43

2₀(28) → 25

2₀(87) → 84

2₀(4) → 30

2₀(34) → 72

2₀(112) → 113

2₀(164) → 165

2₀(47) → 48

2₀(60) → 61

2₀(55) → 56

2₀(105) → 101

2₀(11) → 7

2₀(137) → 138

2₀(156) → 172

2₀(116) → 117

2₀(182) → 178

2₀(90) → 91

2₀(170) → 167

2₀(67) → 68

2₀(39) → 98

2₀(142) → 143

2₀(145) → 146

2₀(3) → 4

2₀(127) → 124

2₀(40) → 116

2₀(65) → 62

2₀(35) → 36

3₀(2) → 67

3₀(157) → 154

3₀(163) → 164

3₀(149) → 148

3₀(46) → 47

3₀(10) → 11

3₀(54) → 55

3₀(98) → 99

3₀(50) → 51

3₀(64) → 65

3₀(67) → 188

3₀(166) → 162

3₀(80) → 78

3₀(24) → 19

3₀(92) → 88

3₀(26) → 85

3₀(151) → 152

3₀(74) → 71

3₀(3) → 26

3₀(17) → 18

3₀(6) → 1

3₀(176) → 177

3₀(100) → 97

3₀(118) → 115

3₀(141) → 142

3₀(111) → 112

3₀(161) → 158

3₀(103) → 104

3₀(172) → 171

3₀(85) → 95

3₀(82) → 81

3₀(40) → 41

3₀(34) → 35

3₀(41) → 42

3₀(78) → 93

3₀(16) → 17

3₀(59) → 60

3₀(109) → 106

3₀(5) → 134

3₀(77) → 75

3₀(169) → 170

3₀(122) → 123

3₀(153) → 150

3₀(102) → 184

0₁(198) → 199

0₁(207) → 208

0₁(204) → 205

0₁(201) → 202

1₁(206) → 207

1₁(200) → 201

4₀(135) → 133

4₀(120) → 159

4₀(96) → 94

4₀(28) → 83

4₀(184) → 185

4₀(39) → 40

4₀(20) → 120

4₀(40) → 50

4₀(189) → 190

4₀(70) → 66

4₀(34) → 45

4₀(179) → 180

4₀(131) → 132

4₀(85) → 86

4₀(45) → 46

4₀(180) → 181

4₀(174) → 173

4₀(68) → 155

4₀(2) → 34

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