YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 Bounds

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

final states:

{189, 185, 182, 179, 174, 169, 168, 164, 160, 156, 153, 148, 144, 140, 135, 130, 127, 123, 122, 119, 115, 113, 109, 104, 98, 96, 91, 87, 82, 80, 75, 72, 67, 65, 63, 58, 54, 48, 45, 26, 42, 38, 33, 27, 21, 17, 13, 8, 1}

transitions:

33 → 49

87 → 28

80 → 28

98 → 28

96 → 28

119 → 49

122 → 49

65 → 10

65 → 28

185 → 99

130 → 49

1 → 10

1 → 28

123 → 49

8 → 28

127 → 49

13 → 28

135 → 49

179 → 99

26 → 49

38 → 49

91 → 28

58 → 10

58 → 28

21 → 28

72 → 28

153 → 49

109 → 49

54 → 10

54 → 28

75 → 28

174 → 99

67 → 10

67 → 28

82 → 28

45 → 49

63 → 10

63 → 28

169 → 99

104 → 23

104 → 9

140 → 49

113 → 49

182 → 99

42 → 49

189 → 92

189 → 99

115 → 49

48 → 10

48 → 28

17 → 28

160 → 100

160 → 22

164 → 116

164 → 170

164 → 99

168 → 170

168 → 99

148 → 49

144 → 49

27 → 49

156 → 22

f6₀ → 2

5₀(20) → 97

5₀(18) → 186

5₀(68) → 69

5₀(24) → 120

5₀(34) → 161

5₀(22) → 92

5₀(9) → 149

5₀(23) → 165

5₀(42) → 168

5₀(145) → 154

5₀(126) → 123

5₀(2) → 99

5₀(28) → 170

5₀(35) → 180

5₀(10) → 116

5₀(17) → 122

1₀(100) → 101

1₀(165) → 166

1₀(170) → 171

1₀(81) → 80

1₀(76) → 77

1₀(14) → 55

1₀(183) → 184

1₀(59) → 60

1₀(159) → 156

1₀(136) → 137

1₀(84) → 85

1₀(132) → 133

1₀(34) → 35

1₀(105) → 141

1₀(99) → 175

1₀(6) → 7

1₀(107) → 108

1₀(92) → 93

1₀(29) → 30

1₀(28) → 29

1₀(3) → 4

1₀(139) → 135

1₀(69) → 70

1₀(64) → 63

1₀(57) → 54

1₀(9) → 131

1₀(161) → 162

1₀(50) → 51

1₀(49) → 50

1₀(20) → 66

1₀(62) → 58

1₀(2) → 9

1₀(171) → 172

1₀(16) → 13

1₀(22) → 23

1₀(186) → 187

3₀(31) → 32

3₀(180) → 181

3₀(46) → 47

3₀(11) → 12

3₀(166) → 167

3₀(78) → 79

3₀(141) → 142

3₀(73) → 74

3₀(162) → 163

3₀(157) → 158

3₀(120) → 121

3₀(3) → 83

3₀(86) → 82

3₀(129) → 127

3₀(24) → 25

3₀(184) → 182

3₀(89) → 90

3₀(133) → 134

3₀(111) → 112

3₀(138) → 139

3₀(114) → 113

3₀(18) → 19

3₀(68) → 124

3₀(9) → 105

3₀(70) → 71

3₀(151) → 152

3₀(131) → 132

3₀(94) → 95

3₀(60) → 61

3₀(145) → 146

3₀(177) → 178

3₀(102) → 103

3₀(55) → 56

3₀(4) → 5

3₀(117) → 118

3₀(191) → 192

3₀(14) → 15

3₀(36) → 37

3₀(43) → 44

3₀(40) → 41

3₀(2) → 49

3₀(23) → 88

3₀(147) → 144

3₀(154) → 155

3₀(172) → 173

3₀(188) → 185

2₀(2) → 3

2₀(175) → 176

2₀(51) → 52

2₀(110) → 111

2₀(88) → 89

2₀(28) → 76

2₀(150) → 151

2₀(108) → 104

2₀(9) → 18

2₀(93) → 94

2₀(68) → 145

2₀(23) → 24

2₀(137) → 138

2₀(116) → 117

2₀(66) → 65

2₀(39) → 73

2₀(3) → 59

2₀(10) → 11

2₀(29) → 43

2₀(101) → 183

2₀(22) → 34

0₀(2) → 28

0₀(167) → 164

0₀(163) → 160

0₀(149) → 150

0₀(56) → 57

0₀(9) → 10

0₀(90) → 87

0₀(128) → 129

0₀(134) → 130

0₀(146) → 147

0₀(105) → 106

0₀(95) → 91

0₀(79) → 75

0₀(19) → 20

0₀(152) → 148

0₀(71) → 67

0₀(25) → 26

0₀(124) → 125

0₀(61) → 62

0₀(26) → 21

0₀(37) → 33

0₀(155) → 153

0₀(74) → 72

0₀(178) → 174

0₀(181) → 179

0₀(192) → 189

0₀(6) → 114

0₀(83) → 84

0₀(118) → 115

0₀(53) → 48

0₀(125) → 126

0₀(32) → 27

0₀(121) → 119

0₀(173) → 169

0₀(112) → 109

0₀(7) → 1

0₀(15) → 16

0₀(52) → 53

0₀(103) → 98

0₀(85) → 86

0₀(12) → 8

0₀(97) → 96

0₀(41) → 38

0₀(44) → 42

0₀(16) → 81

0₀(5) → 6

0₀(88) → 128

0₀(68) → 110

0₀(158) → 159

0₀(47) → 45

4₀(143) → 140

4₀(101) → 102

4₀(106) → 107

4₀(142) → 143

4₀(99) → 100

4₀(4) → 39

4₀(43) → 46

4₀(6) → 64

4₀(39) → 40

4₀(20) → 17

4₀(9) → 68

4₀(49) → 136

4₀(35) → 36

4₀(3) → 14

4₀(30) → 31

4₀(190) → 191

4₀(176) → 177

4₀(175) → 190

4₀(77) → 78

4₀(68) → 157

4₀(187) → 188

4₀(2) → 22

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