YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 Bounds

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

final states:

{195, 178, 161, 143, 124, 107, 91, 75, 62, 50, 39, 28, 19, 10, 1}

transitions:

10 → 11

39 → 29

50 → 51

50 → 3

107 → 11

62 → 29

1 → 11

91 → 20

161 → 29

124 → 196

143 → 40

143 → 29

28 → 144

28 → 20

195 → 3

19 → 197

19 → 29

5₀(51) → 52

5₀(211) → 212

5₀(35) → 36

5₀(173) → 174

5₀(78) → 79

5₀(92) → 162

5₀(162) → 163

5₀(37) → 38

5₀(3) → 144

5₀(7) → 8

5₀(98) → 99

5₀(32) → 33

5₀(58) → 59

5₀(21) → 22

5₀(93) → 94

5₀(206) → 207

5₀(106) → 91

5₀(29) → 30

5₀(201) → 202

5₀(179) → 180

5₀(96) → 97

5₀(84) → 85

5₀(71) → 72

5₀(160) → 143

5₀(2) → 20

5₀(85) → 86

5₀(172) → 173

5₀(20) → 63

5₀(54) → 55

5₀(38) → 28

5₀(153) → 154

5₀(188) → 189

3₀(72) → 73

3₀(20) → 92

3₀(132) → 133

3₀(159) → 160

3₀(177) → 161

3₀(113) → 114

3₀(167) → 168

3₀(147) → 148

3₀(24) → 25

3₀(34) → 35

3₀(77) → 78

3₀(83) → 84

3₀(119) → 120

3₀(70) → 71

3₀(190) → 191

3₀(203) → 204

3₀(141) → 142

3₀(92) → 93

3₀(125) → 126

3₀(128) → 129

3₀(139) → 140

3₀(13) → 14

3₀(79) → 80

3₀(90) → 75

3₀(131) → 132

3₀(67) → 68

3₀(15) → 16

3₀(189) → 190

3₀(194) → 178

3₀(30) → 31

3₀(158) → 159

3₀(40) → 41

3₀(5) → 6

3₀(65) → 66

4₀(151) → 152

4₀(126) → 127

4₀(148) → 149

4₀(150) → 151

4₀(170) → 171

4₀(81) → 82

4₀(14) → 15

4₀(59) → 60

4₀(156) → 157

4₀(130) → 131

4₀(207) → 208

4₀(136) → 137

4₀(8) → 9

4₀(210) → 211

4₀(11) → 125

4₀(168) → 169

4₀(99) → 100

4₀(95) → 96

4₀(43) → 44

4₀(213) → 195

4₀(187) → 188

4₀(110) → 111

4₀(152) → 153

4₀(176) → 177

4₀(209) → 210

4₀(109) → 110

4₀(3) → 51

4₀(164) → 165

4₀(121) → 122

4₀(154) → 155

4₀(163) → 164

4₀(102) → 103

4₀(49) → 39

4₀(135) → 136

4₀(48) → 49

4₀(2) → 3

4₀(4) → 5

4₀(68) → 69

4₀(89) → 90

1₀(87) → 88

1₀(29) → 108

1₀(108) → 109

1₀(142) → 124

1₀(97) → 98

1₀(82) → 83

1₀(192) → 193

1₀(53) → 54

1₀(94) → 95

1₀(11) → 12

1₀(27) → 19

1₀(66) → 67

1₀(202) → 203

1₀(146) → 147

1₀(157) → 158

1₀(184) → 185

1₀(118) → 119

1₀(41) → 42

1₀(20) → 21

1₀(166) → 167

1₀(181) → 182

1₀(116) → 117

1₀(182) → 183

1₀(193) → 194

1₀(145) → 146

1₀(165) → 166

1₀(144) → 145

1₀(114) → 115

1₀(45) → 46

1₀(33) → 34

1₀(23) → 24

1₀(115) → 116

1₀(104) → 105

1₀(2) → 196

2₀(138) → 139

2₀(60) → 61

2₀(20) → 76

2₀(137) → 138

2₀(185) → 186

2₀(197) → 198

2₀(169) → 170

2₀(120) → 121

2₀(46) → 47

2₀(199) → 200

2₀(186) → 187

2₀(11) → 40

2₀(212) → 213

2₀(76) → 77

2₀(63) → 64

2₀(171) → 172

2₀(111) → 112

2₀(174) → 175

2₀(2) → 29

2₀(36) → 37

2₀(122) → 123

2₀(208) → 209

2₀(149) → 150

2₀(134) → 135

2₀(196) → 197

2₀(47) → 48

2₀(100) → 101

2₀(25) → 26

f6₀ → 2

0₀(2) → 11

0₀(18) → 10

0₀(56) → 57

0₀(123) → 107

0₀(117) → 118

0₀(9) → 1

0₀(133) → 134

0₀(204) → 205

0₀(175) → 176

0₀(105) → 106

0₀(191) → 192

0₀(64) → 65

0₀(80) → 81

0₀(55) → 56

0₀(61) → 50

0₀(26) → 27

0₀(155) → 156

0₀(74) → 62

0₀(3) → 4

0₀(17) → 18

0₀(86) → 87

0₀(6) → 7

0₀(140) → 141

0₀(198) → 199

0₀(112) → 113

0₀(180) → 181

0₀(52) → 53

0₀(101) → 102

0₀(129) → 130

0₀(22) → 23

0₀(205) → 206

0₀(103) → 104

0₀(127) → 128

0₀(42) → 43

0₀(183) → 184

0₀(126) → 179

0₀(12) → 13

0₀(73) → 74

0₀(57) → 58

0₀(44) → 45

0₀(16) → 17

0₀(31) → 32

0₀(200) → 201

0₀(88) → 89

0₀(69) → 70

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