YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 Bounds

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

final states:

{159, 156, 155, 151, 147, 142, 137, 133, 127, 126, 123, 121, 120, 118, 115, 111, 109, 105, 104, 99, 96, 91, 90, 86, 83, 81, 77, 73, 71, 67, 61, 58, 54, 51, 50, 44, 40, 36, 31, 30, 25, 20, 18, 16, 11, 9, 7, 1}

transitions:

111 → 100

111 → 12

25 → 12

200 → 180

61 → 62

51 → 62

96 → 12

84 → 199

18 → 12

120 → 62

184 → 93

9 → 12

5 → 179

59 → 205

90 → 12

20 → 12

193 → 183

99 → 100

99 → 12

31 → 12

1 → 12

40 → 12

123 → 62

71 → 93

127 → 93

13 → 62

183 → 185

44 → 12

38 → 189

86 → 12

91 → 12

58 → 62

36 → 12

186 → 183

172 → 144

121 → 62

109 → 100

109 → 12

54 → 62

105 → 100

105 → 12

67 → 93

2 → 168

11 → 12

118 → 12

16 → 12

104 → 144

104 → 100

104 → 12

7 → 100

7 → 12

126 → 93

30 → 12

115 → 12

83 → 12

206 → 190

f6₀ → 2

5₀(146) → 142

5₀(70) → 67

5₀(131) → 132

5₀(132) → 127

5₀(135) → 136

5₀(16) → 126

5₀(87) → 97

5₀(72) → 71

5₀(68) → 152

5₀(21) → 37

5₀(7) → 30

5₀(125) → 123

5₀(92) → 93

5₀(66) → 61

5₀(76) → 73

5₀(4) → 52

5₀(49) → 44

5₀(82) → 81

5₀(43) → 40

5₀(89) → 86

5₀(3) → 138

5₀(26) → 78

5₀(122) → 121

5₀(35) → 31

5₀(161) → 162

5₀(47) → 48

5₀(15) → 11

5₀(158) → 156

5₀(154) → 151

5₀(150) → 147

5₀(160) → 161

2₁(191) → 192

2₁(168) → 169

2₁(185) → 186

2₁(180) → 181

1₁(182) → 183

1₁(190) → 191

1₀(65) → 66

1₀(148) → 149

1₀(23) → 24

1₀(100) → 101

1₀(26) → 55

1₀(41) → 42

1₀(78) → 79

1₀(144) → 145

1₀(37) → 38

1₀(45) → 74

1₀(95) → 91

1₀(79) → 80

1₀(152) → 153

1₀(129) → 130

1₀(46) → 148

1₀(29) → 25

1₀(87) → 88

1₀(3) → 21

1₀(47) → 84

1₀(97) → 98

1₀(69) → 70

1₀(12) → 92

1₀(102) → 103

1₀(48) → 49

1₀(5) → 19

1₀(2) → 128

1₀(4) → 5

1₀(68) → 134

1₀(138) → 139

1₀(157) → 158

1₀(52) → 59

5₁(183) → 184

2₀(74) → 75

2₀(92) → 106

2₀(3) → 26

2₀(33) → 34

2₀(45) → 46

2₀(98) → 96

2₀(32) → 33

2₀(93) → 94

2₀(59) → 60

2₀(70) → 72

2₀(62) → 63

2₀(13) → 14

2₀(63) → 64

2₀(139) → 140

2₀(2) → 3

2₀(12) → 68

4₁(171) → 172

4₀(2) → 62

4₀(21) → 160

4₀(124) → 125

4₀(26) → 112

4₀(110) → 109

4₀(103) → 99

4₀(28) → 29

4₀(85) → 83

4₀(8) → 7

4₀(114) → 111

4₀(60) → 58

4₀(55) → 56

4₀(108) → 105

4₀(139) → 157

4₀(13) → 41

4₀(57) → 54

4₀(116) → 117

4₀(66) → 120

4₀(53) → 51

4₀(3) → 32

4₀(5) → 10

4₀(22) → 23

0₀(2) → 12

0₀(149) → 150

0₀(46) → 47

0₀(56) → 122

0₀(117) → 115

0₀(134) → 135

0₀(10) → 9

0₀(49) → 90

0₀(64) → 65

0₀(113) → 114

0₀(24) → 20

0₀(63) → 87

0₀(26) → 27

0₀(38) → 39

0₀(3) → 4

0₀(17) → 16

0₀(84) → 85

0₀(6) → 1

0₀(14) → 15

0₀(140) → 141

0₀(94) → 95

0₀(130) → 131

0₀(7) → 82

0₀(101) → 102

0₀(45) → 100

0₀(42) → 43

0₀(75) → 76

0₀(85) → 104

0₀(143) → 144

0₀(34) → 35

0₀(59) → 119

0₀(5) → 6

0₀(145) → 146

0₀(106) → 107

0₀(88) → 89

0₀(68) → 69

3₁(170) → 171

3₁(205) → 206

3₁(189) → 190

0₁(179) → 180

0₁(199) → 200

0₁(169) → 170

0₁(181) → 182

0₁(192) → 193

3₀(19) → 18

3₀(21) → 22

3₀(112) → 113

3₀(78) → 124

3₀(5) → 17

3₀(153) → 154

3₀(141) → 137

3₀(117) → 155

3₀(136) → 133

3₀(27) → 28

3₀(128) → 129

3₀(4) → 8

3₀(7) → 50

3₀(56) → 57

3₀(162) → 159

3₀(39) → 36

3₀(107) → 108

3₀(15) → 110

3₀(52) → 53

3₀(119) → 118

3₀(3) → 143

3₀(80) → 77

3₀(37) → 116

3₀(12) → 13

3₀(2) → 45

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