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))))	→	0(0(1(3(2(x0)))))
0(1(2(2(x0))))	→	0(3(2(2(1(x0)))))
0(2(1(1(x0))))	→	0(1(1(1(3(2(x0))))))
0(2(3(2(x0))))	→	0(3(0(3(2(2(x0))))))
0(2(4(4(x0))))	→	3(0(4(2(4(x0)))))
0(4(0(2(x0))))	→	3(0(0(4(2(x0)))))
0(4(0(2(x0))))	→	3(0(0(0(4(2(x0))))))
0(4(5(1(x0))))	→	0(0(0(4(1(5(x0))))))
0(5(1(1(x0))))	→	0(1(1(3(5(x0)))))
0(5(1(1(x0))))	→	0(1(3(1(5(x0)))))
0(5(1(4(x0))))	→	0(3(3(4(1(5(x0))))))
0(5(3(2(x0))))	→	0(3(0(5(5(2(x0))))))
0(5(3(2(x0))))	→	3(0(3(5(5(2(x0))))))
0(5(4(1(x0))))	→	0(3(1(5(4(x0)))))
0(5(4(1(x0))))	→	0(0(4(1(1(5(x0))))))
0(5(4(4(x0))))	→	4(0(4(3(5(x0)))))
2(0(2(4(x0))))	→	2(2(4(0(0(x0)))))
2(0(5(1(x0))))	→	0(0(0(5(2(1(x0))))))
2(0(5(1(x0))))	→	5(0(3(5(2(1(x0))))))
2(0(5(1(x0))))	→	5(3(0(5(2(1(x0))))))
2(0(5(4(x0))))	→	2(4(0(3(5(x0)))))
5(1(0(2(x0))))	→	2(5(0(3(1(x0)))))
5(3(2(4(x0))))	→	2(3(4(3(5(x0)))))
5(4(0(2(x0))))	→	5(0(3(0(4(2(x0))))))
0(0(2(1(1(x0)))))	→	0(3(0(1(2(1(x0))))))
0(1(5(1(4(x0)))))	→	0(4(3(1(1(5(x0))))))
0(1(5(4(1(x0)))))	→	4(0(1(1(3(5(x0))))))
0(2(0(2(4(x0)))))	→	0(0(2(1(2(4(x0))))))
0(2(0(5(1(x0)))))	→	5(0(0(0(2(1(x0))))))
0(2(1(3(2(x0)))))	→	3(0(3(1(2(2(x0))))))
0(2(1(5(1(x0)))))	→	0(5(2(1(1(0(x0))))))
0(2(3(5(1(x0)))))	→	5(2(1(0(0(3(x0))))))
0(4(0(4(2(x0)))))	→	3(0(0(4(4(2(x0))))))
0(5(0(2(4(x0)))))	→	0(4(0(5(2(4(x0))))))
0(5(1(3(2(x0)))))	→	0(3(4(1(5(2(x0))))))
0(5(4(3(2(x0)))))	→	0(0(3(4(2(5(x0))))))
0(5(5(4(2(x0)))))	→	4(0(3(5(5(2(x0))))))
2(0(1(2(4(x0)))))	→	2(2(1(3(4(0(x0))))))
2(0(5(1(1(x0)))))	→	5(0(2(3(1(1(x0))))))
2(5(5(1(1(x0)))))	→	5(5(2(1(1(3(x0))))))
3(4(2(1(1(x0)))))	→	3(4(3(1(1(2(x0))))))
3(5(0(2(1(x0)))))	→	1(2(5(0(3(3(x0))))))
4(1(2(1(1(x0)))))	→	3(4(1(1(2(1(x0))))))
4(1(2(4(1(x0)))))	→	4(3(4(1(1(2(x0))))))
4(3(5(1(1(x0)))))	→	3(4(1(1(1(5(x0))))))
5(0(1(5(1(x0)))))	→	5(0(3(1(1(5(x0))))))
5(0(5(0(2(x0)))))	→	2(0(0(0(5(5(x0))))))
5(1(4(5(1(x0)))))	→	5(0(1(1(5(4(x0))))))
5(1(4(5(1(x0)))))	→	5(3(4(1(1(5(x0))))))
5(3(1(5(4(x0)))))	→	5(3(4(1(3(5(x0))))))

Proof

1 Bounds

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

final states:

{187, 185, 182, 177, 175, 172, 169, 166, 161, 156, 151, 146, 141, 140, 135, 131, 127, 123, 117, 112, 108, 104, 100, 99, 96, 92, 89, 87, 83, 80, 78, 75, 71, 66, 63, 59, 55, 52, 47, 44, 41, 37, 31, 29, 25, 20, 15, 12, 7, 1}

transitions:

78 → 3

25 → 67

29 → 67

89 → 56

89 → 32

87 → 32

80 → 3

15 → 67

96 → 67

41 → 67

146 → 3

187 → 32

108 → 105

108 → 67

37 → 67

59 → 67

185 → 32

55 → 67

175 → 32

20 → 67

99 → 67

31 → 67

1 → 67

123 → 67

71 → 3

127 → 67

44 → 67

135 → 67

161 → 38

161 → 118

177 → 32

141 → 3

172 → 64

172 → 21

52 → 67

75 → 3

117 → 67

66 → 3

63 → 67

12 → 105

12 → 67

112 → 105

112 → 67

169 → 21

104 → 67

140 → 179

140 → 67

100 → 67

7 → 67

182 → 32

83 → 32

47 → 67

131 → 67

92 → 106

92 → 68

92 → 67

166 → 21

151 → 136

151 → 3

156 → 118

f6₀ → 2

5₀(184) → 182

5₀(176) → 175

5₀(48) → 49

5₀(77) → 75

5₀(189) → 187

5₀(155) → 151

5₀(79) → 78

5₀(21) → 56

5₀(32) → 178

5₀(91) → 89

5₀(22) → 128

5₀(9) → 72

5₀(186) → 185

5₀(85) → 86

5₀(2) → 32

5₀(163) → 164

5₀(3) → 48

5₀(107) → 104

5₀(122) → 117

5₀(115) → 116

5₀(154) → 155

5₀(150) → 146

1₀(33) → 60

1₀(165) → 161

1₀(42) → 43

1₀(118) → 152

1₀(8) → 147

1₀(143) → 144

1₀(32) → 33

1₀(38) → 39

1₀(60) → 173

1₀(152) → 153

1₀(120) → 121

1₀(56) → 57

1₀(3) → 157

1₀(113) → 114

1₀(57) → 183

1₀(9) → 93

1₀(13) → 14

1₀(48) → 132

1₀(5) → 13

1₀(67) → 113

1₀(93) → 167

1₀(2) → 8

1₀(4) → 5

1₀(39) → 40

1₀(157) → 158

1₀(22) → 101

1₀(16) → 109

3₀(137) → 138

3₀(16) → 17

3₀(73) → 79

3₀(30) → 29

3₀(49) → 53

3₀(158) → 159

3₀(174) → 172

3₀(3) → 4

3₀(33) → 42

3₀(45) → 46

3₀(32) → 38

3₀(24) → 20

3₀(61) → 186

3₀(50) → 51

3₀(8) → 84

3₀(133) → 134

3₀(111) → 108

3₀(170) → 171

3₀(142) → 143

3₀(18) → 19

3₀(64) → 88

3₀(118) → 162

3₀(27) → 90

3₀(94) → 95

3₀(60) → 97

3₀(109) → 110

3₀(72) → 76

3₀(126) → 123

3₀(10) → 11

3₀(28) → 25

3₀(160) → 156

3₀(2) → 118

3₀(57) → 58

3₀(147) → 148

3₀(34) → 45

3₀(168) → 166

3₀(54) → 52

3₀(188) → 189

2₀(2) → 3

2₀(82) → 80

2₀(21) → 22

2₀(88) → 87

2₀(32) → 136

2₀(144) → 145

2₀(164) → 165

2₀(70) → 66

2₀(8) → 9

2₀(114) → 115

2₀(9) → 10

2₀(181) → 177

2₀(148) → 149

2₀(69) → 70

2₀(121) → 122

2₀(145) → 141

2₀(86) → 83

2₀(3) → 16

2₀(101) → 102

2₀(153) → 154

0₀(2) → 67

0₀(51) → 47

0₀(149) → 150

0₀(46) → 44

0₀(28) → 30

0₀(9) → 105

0₀(90) → 91

0₀(128) → 129

0₀(134) → 131

0₀(49) → 50

0₀(105) → 106

0₀(110) → 111

0₀(98) → 96

0₀(95) → 92

0₀(64) → 65

0₀(67) → 68

0₀(19) → 15

0₀(36) → 31

0₀(43) → 41

0₀(124) → 125

0₀(61) → 62

0₀(26) → 27

0₀(76) → 77

0₀(138) → 139

0₀(74) → 71

0₀(178) → 179

0₀(38) → 81

0₀(17) → 18

0₀(11) → 7

0₀(84) → 85

0₀(6) → 1

0₀(14) → 12

0₀(118) → 119

0₀(53) → 54

0₀(62) → 59

0₀(23) → 24

0₀(125) → 126

0₀(139) → 135

0₀(130) → 127

0₀(180) → 181

0₀(27) → 28

0₀(35) → 36

0₀(93) → 94

0₀(103) → 100

0₀(183) → 184

0₀(40) → 37

0₀(73) → 74

0₀(97) → 176

0₀(162) → 163

0₀(34) → 35

0₀(58) → 55

0₀(5) → 6

0₀(106) → 107

0₀(179) → 180

0₀(72) → 73

0₀(116) → 112

0₀(119) → 120

0₀(102) → 103

4₀(132) → 133

4₀(171) → 169

4₀(97) → 98

4₀(129) → 130

4₀(136) → 137

4₀(26) → 124

4₀(60) → 61

4₀(54) → 140

4₀(39) → 188

4₀(22) → 23

4₀(67) → 142

4₀(167) → 168

4₀(159) → 160

4₀(3) → 26

4₀(65) → 63

4₀(158) → 170

4₀(81) → 82

4₀(173) → 174

4₀(38) → 64

4₀(33) → 34

4₀(37) → 99

4₀(68) → 69

4₀(2) → 21

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