YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 Bounds

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

final states:

{202, 201, 198, 195, 192, 189, 185, 182, 178, 174, 171, 169, 167, 162, 158, 157, 154, 151, 148, 142, 139, 134, 130, 128, 124, 121, 116, 114, 112, 108, 104, 101, 98, 94, 91, 87, 85, 82, 79, 76, 72, 68, 66, 64, 61, 58, 55, 53, 48, 44, 42, 41, 39, 37, 34, 31, 27, 22, 19, 14, 8, 1}

transitions:

157 → 117

61 → 117

128 → 179

128 → 9

87 → 4

167 → 20

167 → 4

41 → 117

39 → 117

134 → 164

134 → 9

37 → 117

34 → 117

55 → 117

130 → 9

31 → 117

1 → 28

1 → 9

1 → 50

1 → 24

8 → 28

8 → 9

139 → 164

139 → 9

44 → 117

58 → 117

121 → 179

121 → 9

171 → 4

116 → 179

116 → 9

22 → 117

124 → 179

124 → 9

53 → 117

66 → 117

114 → 50

114 → 24

114 → 9

14 → 28

14 → 9

112 → 9

169 → 20

169 → 4

42 → 117

64 → 117

162 → 117

158 → 117

48 → 117

154 → 117

154 → 20

154 → 4

68 → 117

148 → 117

142 → 164

142 → 9

19 → 117

27 → 117

151 → 117

3₀(175) → 176

3₀(67) → 66

3₀(65) → 64

3₀(173) → 171

3₀(166) → 162

3₀(78) → 76

3₀(200) → 198

3₀(30) → 27

3₀(105) → 155

3₀(3) → 4

3₀(86) → 85

3₀(33) → 31

3₀(45) → 149

3₀(125) → 126

3₀(77) → 190

3₀(184) → 182

3₀(150) → 148

3₀(26) → 22

3₀(93) → 91

3₀(52) → 48

3₀(111) → 108

3₀(170) → 169

3₀(9) → 117

3₀(118) → 119

3₀(60) → 58

3₀(84) → 82

3₀(75) → 72

3₀(161) → 158

3₀(205) → 202

3₀(97) → 94

3₀(13) → 201

3₀(81) → 79

3₀(107) → 104

3₀(10) → 20

3₀(90) → 87

3₀(63) → 61

3₀(191) → 189

3₀(181) → 178

3₀(28) → 69

3₀(36) → 34

3₀(47) → 44

3₀(57) → 55

3₀(168) → 167

3₀(20) → 122

3₀(194) → 192

3₀(100) → 98

3₀(54) → 53

3₀(103) → 101

3₀(38) → 37

3₀(153) → 151

3₀(188) → 185

1₀(73) → 88

1₀(2) → 3

1₀(78) → 113

1₀(25) → 26

1₀(117) → 118

1₀(160) → 161

1₀(74) → 75

1₀(102) → 103

1₀(152) → 153

1₀(51) → 52

1₀(193) → 194

1₀(32) → 33

1₀(28) → 29

1₀(59) → 60

1₀(46) → 47

1₀(77) → 78

1₀(80) → 81

1₀(165) → 166

1₀(70) → 71

1₀(89) → 90

1₀(190) → 191

1₀(187) → 188

1₀(203) → 204

1₀(199) → 200

1₀(135) → 136

1₀(172) → 173

1₀(92) → 93

1₀(9) → 10

1₀(99) → 100

1₀(125) → 140

1₀(143) → 144

1₀(183) → 184

1₀(163) → 175

1₀(56) → 57

1₀(62) → 170

1₀(69) → 70

1₀(204) → 205

1₀(180) → 181

1₀(38) → 54

1₀(49) → 109

1₀(10) → 105

1₀(29) → 30

1₀(81) → 86

1₀(96) → 97

1₀(149) → 150

1₀(30) → 168

1₀(35) → 36

2₀(73) → 74

2₀(159) → 160

2₀(19) → 41

2₀(156) → 154

2₀(179) → 180

2₀(132) → 133

2₀(34) → 157

2₀(105) → 106

2₀(6) → 7

2₀(43) → 42

2₀(176) → 177

2₀(129) → 128

2₀(88) → 89

2₀(29) → 62

2₀(18) → 14

2₀(28) → 32

2₀(3) → 15

2₀(40) → 43

2₀(164) → 165

2₀(69) → 183

2₀(9) → 49

2₀(196) → 197

2₀(12) → 13

2₀(146) → 147

2₀(80) → 92

2₀(20) → 21

2₀(115) → 114

2₀(62) → 63

2₀(10) → 83

2₀(2) → 23

2₀(24) → 95

2₀(186) → 187

4₀(25) → 199

4₀(106) → 107

4₀(117) → 186

4₀(4) → 131

4₀(118) → 196

4₀(10) → 11

4₀(20) → 193

4₀(83) → 84

4₀(9) → 73

4₀(95) → 96

4₀(110) → 111

4₀(24) → 77

4₀(73) → 203

5₀(77) → 99

5₀(88) → 172

5₀(40) → 39

5₀(73) → 80

5₀(32) → 56

5₀(9) → 163

5₀(23) → 135

5₀(50) → 51

5₀(109) → 110

5₀(71) → 68

5₀(80) → 102

5₀(2) → 143

5₀(26) → 65

5₀(45) → 46

5₀(36) → 67

5₀(28) → 35

5₀(35) → 59

5₀(29) → 38

5₀(10) → 125

f6₀ → 2

0₀(2) → 9

0₀(163) → 164

0₀(177) → 174

0₀(28) → 45

0₀(123) → 121

0₀(117) → 179

0₀(9) → 28

0₀(133) → 130

0₀(10) → 159

0₀(49) → 50

0₀(197) → 195

0₀(113) → 112

0₀(24) → 25

0₀(131) → 132

0₀(4) → 5

0₀(21) → 19

0₀(155) → 156

0₀(138) → 134

0₀(17) → 18

0₀(11) → 12

0₀(147) → 142

0₀(6) → 115

0₀(141) → 139

0₀(136) → 137

0₀(140) → 141

0₀(23) → 24

0₀(137) → 138

0₀(7) → 1

0₀(15) → 16

0₀(127) → 124

0₀(20) → 40

0₀(120) → 116

0₀(126) → 127

0₀(40) → 129

0₀(16) → 17

0₀(109) → 152

0₀(5) → 6

0₀(145) → 146

0₀(144) → 145

0₀(13) → 8

0₀(122) → 123

0₀(119) → 120

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