YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 Bounds

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

final states:

{192, 189, 185, 180, 176, 171, 167, 165, 162, 160, 155, 151, 148, 144, 140, 136, 132, 127, 122, 120, 115, 113, 108, 105, 100, 95, 90, 86, 81, 75, 70, 65, 60, 55, 54, 49, 43, 40, 37, 32, 29, 26, 22, 17, 12, 7, 1}

transitions:

176 → 128

176 → 44

32 → 18

29 → 18

81 → 66

81 → 18

136 → 61

136 → 13

167 → 128

167 → 44

122 → 18

120 → 18

108 → 18

37 → 18

95 → 18

65 → 66

65 → 18

185 → 56

185 → 44

55 → 18

90 → 18

49 → 18

1 → 18

40 → 18

165 → 128

165 → 44

127 → 87

127 → 61

127 → 13

60 → 66

60 → 18

26 → 18

86 → 18

171 → 128

171 → 44

54 → 18

22 → 18

75 → 66

75 → 18

105 → 18

180 → 128

180 → 44

12 → 18

140 → 168

140 → 116

140 → 13

100 → 18

7 → 18

113 → 18

189 → 56

189 → 44

162 → 128

162 → 44

115 → 18

17 → 18

160 → 128

160 → 44

148 → 82

148 → 76

132 → 61

132 → 13

144 → 82

144 → 76

43 → 18

70 → 66

70 → 18

151 → 128

151 → 44

155 → 128

155 → 44

192 → 56

192 → 44

f6₀ → 2

5₀(184) → 180

5₀(31) → 161

5₀(121) → 120

5₀(18) → 128

5₀(128) → 152

5₀(166) → 165

5₀(172) → 173

5₀(98) → 99

5₀(188) → 185

5₀(91) → 92

5₀(181) → 182

5₀(119) → 115

5₀(63) → 114

5₀(83) → 84

5₀(2) → 44

5₀(142) → 143

5₀(143) → 140

5₀(8) → 56

5₀(164) → 162

5₀(13) → 123

5₀(187) → 188

0₀(106) → 107

0₀(137) → 138

0₀(170) → 167

0₀(78) → 79

0₀(91) → 186

0₀(14) → 30

0₀(183) → 184

0₀(19) → 20

0₀(85) → 81

0₀(118) → 119

0₀(58) → 59

0₀(51) → 52

0₀(35) → 36

0₀(8) → 91

0₀(45) → 177

0₀(125) → 126

0₀(38) → 39

0₀(79) → 80

0₀(158) → 159

0₀(131) → 127

0₀(46) → 47

0₀(18) → 66

0₀(3) → 23

0₀(175) → 171

0₀(97) → 98

0₀(64) → 60

0₀(111) → 112

0₀(57) → 58

0₀(96) → 97

0₀(101) → 102

0₀(94) → 90

0₀(102) → 103

0₀(193) → 194

0₀(15) → 16

0₀(74) → 70

0₀(71) → 72

0₀(62) → 63

0₀(5) → 6

0₀(10) → 11

0₀(2) → 18

0₀(141) → 142

0₀(153) → 154

0₀(24) → 163

0₀(190) → 191

3₀(130) → 131

3₀(173) → 174

3₀(73) → 74

3₀(30) → 31

3₀(157) → 158

3₀(174) → 175

3₀(3) → 71

3₀(186) → 187

3₀(44) → 45

3₀(195) → 192

3₀(45) → 46

3₀(66) → 67

3₀(123) → 137

3₀(61) → 62

3₀(50) → 51

3₀(80) → 75

3₀(89) → 86

3₀(159) → 155

3₀(128) → 129

3₀(56) → 57

3₀(18) → 19

3₀(9) → 10

3₀(84) → 85

3₀(110) → 111

3₀(109) → 110

3₀(15) → 38

3₀(101) → 141

3₀(149) → 150

3₀(76) → 96

3₀(13) → 101

3₀(5) → 106

3₀(4) → 5

3₀(117) → 118

3₀(124) → 125

3₀(14) → 15

3₀(182) → 183

3₀(2) → 8

3₀(23) → 24

3₀(154) → 151

3₀(34) → 35

3₀(168) → 190

3₀(20) → 41

3₀(194) → 195

3₀(152) → 153

1₀(41) → 42

1₀(20) → 21

1₀(2) → 13

1₀(6) → 166

1₀(129) → 130

1₀(44) → 116

1₀(103) → 104

1₀(133) → 134

1₀(24) → 25

1₀(47) → 48

1₀(8) → 9

1₀(135) → 132

1₀(92) → 93

1₀(99) → 95

1₀(93) → 94

1₀(68) → 69

1₀(18) → 61

1₀(27) → 28

1₀(163) → 164

1₀(56) → 168

1₀(134) → 135

1₀(139) → 136

1₀(13) → 33

1₀(156) → 157

1₀(66) → 87

1₀(67) → 68

1₀(146) → 147

1₀(3) → 4

1₀(52) → 53

2₀(2) → 3

2₀(114) → 113

2₀(28) → 26

2₀(48) → 43

2₀(191) → 189

2₀(19) → 133

2₀(36) → 32

2₀(107) → 105

2₀(25) → 22

2₀(21) → 17

2₀(63) → 64

2₀(104) → 100

2₀(76) → 172

2₀(138) → 139

2₀(11) → 7

2₀(147) → 144

2₀(6) → 1

2₀(87) → 149

2₀(53) → 49

2₀(112) → 108

2₀(33) → 34

2₀(42) → 40

2₀(82) → 83

2₀(39) → 37

2₀(126) → 122

2₀(44) → 156

2₀(16) → 12

2₀(59) → 55

2₀(31) → 29

2₀(77) → 78

2₀(179) → 176

2₀(13) → 14

2₀(88) → 89

2₀(169) → 170

2₀(116) → 193

2₀(47) → 54

2₀(69) → 65

4₀(19) → 27

4₀(87) → 88

4₀(47) → 121

4₀(123) → 124

4₀(177) → 178

4₀(44) → 50

4₀(13) → 109

4₀(161) → 160

4₀(116) → 117

4₀(72) → 73

4₀(145) → 146

4₀(3) → 181

4₀(150) → 148

4₀(18) → 82

4₀(76) → 77

4₀(91) → 145

4₀(178) → 179

4₀(2) → 76

4₀(168) → 169

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