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

Proof

1 String Reversal

Since only unary symbols occur, one can reverse all terms and obtains the TRS

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

1.1 Bounds

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

final states:

{181, 165, 152, 138, 123, 109, 96, 84, 72, 60, 51, 42, 34, 25, 16, 10, 6, 1}

transitions:

25 → 26

25 → 17

152 → 17

10 → 61

10 → 3

51 → 18

51 → 85

181 → 11

181 → 73

96 → 124

96 → 73

84 → 17

34 → 97

1 → 7

123 → 35

123 → 85

165 → 4

165 → 17

60 → 85

72 → 3

138 → 166

138 → 97

6 → 3

109 → 125

109 → 73

16 → 73

42 → 3

2₀(74) → 75

2₀(35) → 43

2₀(180) → 165

2₀(19) → 20

2₀(46) → 47

2₀(11) → 12

2₀(173) → 174

2₀(146) → 147

2₀(30) → 31

2₀(44) → 45

2₀(45) → 46

2₀(32) → 33

2₀(24) → 16

2₀(121) → 122

2₀(93) → 94

2₀(8) → 9

2₀(167) → 168

2₀(87) → 88

2₀(140) → 141

2₀(170) → 171

2₀(56) → 57

2₀(64) → 65

2₀(199) → 181

2₀(83) → 72

2₀(198) → 199

2₀(79) → 80

2₀(145) → 146

2₀(148) → 149

2₀(39) → 40

2₀(149) → 150

2₀(196) → 197

2₀(88) → 89

2₀(47) → 48

2₀(139) → 140

2₀(2) → 7

2₀(104) → 105

2₀(54) → 55

2₀(12) → 13

3₀(2) → 73

3₀(31) → 32

3₀(82) → 83

3₀(21) → 22

3₀(188) → 189

3₀(124) → 125

3₀(179) → 180

3₀(113) → 114

3₀(58) → 59

3₀(98) → 99

3₀(37) → 38

3₀(136) → 137

3₀(144) → 145

3₀(119) → 120

3₀(85) → 124

3₀(89) → 90

3₀(187) → 188

3₀(61) → 62

3₀(55) → 56

3₀(141) → 142

3₀(126) → 127

3₀(105) → 106

3₀(68) → 69

3₀(14) → 15

3₀(57) → 58

3₀(107) → 108

3₀(69) → 70

3₀(142) → 143

3₀(53) → 54

3₀(49) → 50

3₀(52) → 53

3₀(94) → 95

3₀(101) → 102

3₀(122) → 109

3₀(7) → 11

3₀(65) → 66

3₀(35) → 36

0₀(73) → 139

0₀(100) → 101

0₀(159) → 160

0₀(156) → 157

0₀(169) → 170

0₀(7) → 8

0₀(132) → 133

0₀(43) → 44

0₀(131) → 132

0₀(36) → 37

0₀(28) → 29

0₀(164) → 152

0₀(9) → 6

0₀(184) → 185

0₀(50) → 42

0₀(162) → 163

0₀(115) → 116

0₀(117) → 118

0₀(17) → 61

0₀(2) → 3

0₀(4) → 5

0₀(190) → 191

5₀(112) → 113

5₀(186) → 187

5₀(160) → 161

5₀(97) → 98

5₀(135) → 136

5₀(78) → 79

5₀(99) → 100

5₀(192) → 193

5₀(151) → 138

5₀(172) → 173

5₀(7) → 182

5₀(90) → 91

5₀(13) → 14

5₀(41) → 34

5₀(20) → 21

5₀(166) → 167

5₀(67) → 68

5₀(194) → 195

5₀(182) → 183

5₀(103) → 104

5₀(189) → 190

5₀(3) → 110

5₀(133) → 134

5₀(70) → 71

5₀(150) → 151

5₀(163) → 164

5₀(18) → 52

5₀(85) → 166

5₀(130) → 131

5₀(23) → 24

5₀(75) → 76

5₀(178) → 179

5₀(2) → 97

5₀(73) → 74

5₀(168) → 169

4₀(59) → 51

4₀(48) → 49

4₀(137) → 123

4₀(197) → 198

4₀(155) → 156

4₀(18) → 19

4₀(128) → 129

4₀(40) → 41

4₀(7) → 35

4₀(125) → 126

4₀(92) → 93

4₀(114) → 115

4₀(183) → 184

4₀(62) → 63

4₀(66) → 67

4₀(71) → 60

4₀(76) → 77

4₀(38) → 39

4₀(80) → 81

4₀(111) → 112

4₀(174) → 175

4₀(2) → 85

4₀(26) → 27

4₀(29) → 30

4₀(108) → 96

4₀(161) → 162

4₀(110) → 111

4₀(17) → 18

4₀(153) → 154

4₀(195) → 196

f6₀ → 2

1₀(2) → 17

1₀(157) → 158

1₀(177) → 178

1₀(91) → 92

1₀(134) → 135

1₀(175) → 176

1₀(95) → 84

1₀(191) → 192

1₀(36) → 153

1₀(63) → 64

1₀(3) → 4

1₀(17) → 26

1₀(86) → 87

1₀(147) → 148

1₀(176) → 177

1₀(118) → 119

1₀(81) → 82

1₀(33) → 25

1₀(15) → 10

1₀(27) → 28

1₀(129) → 130

1₀(22) → 23

1₀(127) → 128

1₀(85) → 86

1₀(120) → 121

1₀(143) → 144

1₀(154) → 155

1₀(5) → 1

1₀(185) → 186

1₀(106) → 107

1₀(77) → 78

1₀(193) → 194

1₀(158) → 159

1₀(116) → 117

1₀(102) → 103

1₀(171) → 172

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