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

Proof

1 String Reversal

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

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

1.1 Bounds

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

final states:

{225, 206, 188, 175, 160, 146, 133, 119, 105, 95, 85, 77, 66, 57, 51, 45, 38, 30, 25, 21, 16, 12, 9, 5, 1}

transitions:

25 → 14

25 → 13

51 → 6

119 → 120

119 → 6

133 → 27

133 → 13

57 → 32

57 → 31

225 → 106

225 → 3

146 → 31

9 → 10

9 → 31

5 → 162

5 → 31

95 → 161

95 → 67

175 → 6

1 → 120

1 → 6

38 → 67

21 → 24

21 → 13

105 → 6

188 → 31

45 → 10

45 → 31

66 → 13

16 → 27

16 → 13

12 → 161

12 → 67

85 → 32

85 → 31

77 → 34

77 → 121

77 → 6

30 → 87

30 → 6

160 → 7

160 → 67

206 → 3

1₀(35) → 36

1₀(11) → 9

1₀(92) → 93

1₀(3) → 106

1₀(240) → 225

1₀(222) → 223

1₀(121) → 122

1₀(123) → 124

1₀(143) → 144

1₀(50) → 45

1₀(87) → 88

1₀(159) → 146

1₀(238) → 239

1₀(138) → 139

1₀(128) → 129

1₀(201) → 202

1₀(198) → 199

1₀(179) → 180

1₀(27) → 28

1₀(60) → 61

1₀(96) → 97

1₀(136) → 137

1₀(71) → 72

1₀(15) → 78

1₀(90) → 91

1₀(202) → 203

1₀(28) → 147

1₀(47) → 48

1₀(182) → 183

1₀(22) → 23

1₀(122) → 123

1₀(2) → 3

1₀(223) → 224

1₀(164) → 165

5₀(72) → 73

5₀(73) → 74

5₀(20) → 16

5₀(2) → 13

5₀(78) → 79

5₀(155) → 156

5₀(177) → 178

5₀(74) → 75

5₀(124) → 125

5₀(113) → 114

5₀(26) → 27

5₀(28) → 29

5₀(209) → 210

5₀(59) → 60

5₀(46) → 176

5₀(173) → 174

5₀(76) → 66

5₀(218) → 219

5₀(165) → 166

5₀(233) → 234

5₀(150) → 151

5₀(185) → 186

5₀(190) → 191

5₀(203) → 204

5₀(55) → 56

5₀(230) → 231

5₀(108) → 109

5₀(172) → 173

5₀(93) → 94

5₀(195) → 196

5₀(23) → 24

5₀(134) → 135

5₀(13) → 14

5₀(219) → 220

5₀(236) → 237

5₀(62) → 63

5₀(216) → 217

5₀(184) → 185

5₀(180) → 181

5₀(15) → 12

5₀(145) → 133

5₀(237) → 238

5₀(130) → 131

5₀(127) → 128

5₀(81) → 82

5₀(158) → 159

5₀(7) → 8

4₀(226) → 227

4₀(98) → 99

4₀(151) → 152

4₀(26) → 161

4₀(14) → 15

4₀(63) → 64

4₀(166) → 167

4₀(142) → 143

4₀(58) → 96

4₀(8) → 5

4₀(174) → 160

4₀(6) → 7

4₀(167) → 168

4₀(43) → 44

4₀(107) → 108

4₀(228) → 229

4₀(88) → 89

4₀(46) → 47

4₀(197) → 198

4₀(29) → 25

4₀(3) → 4

4₀(40) → 41

4₀(139) → 140

4₀(69) → 70

4₀(64) → 65

4₀(234) → 235

4₀(104) → 95

4₀(140) → 141

4₀(232) → 233

4₀(208) → 209

4₀(224) → 206

4₀(83) → 84

4₀(135) → 136

4₀(13) → 86

4₀(53) → 54

4₀(103) → 104

4₀(67) → 68

4₀(17) → 18

4₀(10) → 11

4₀(2) → 67

4₀(141) → 142

4₀(24) → 21

4₀(44) → 38

4₀(39) → 58

2₀(170) → 171

2₀(101) → 102

2₀(186) → 187

2₀(191) → 192

2₀(8) → 226

2₀(171) → 172

2₀(82) → 83

2₀(211) → 212

2₀(94) → 85

2₀(169) → 170

2₀(54) → 55

2₀(7) → 207

2₀(6) → 10

2₀(13) → 22

2₀(162) → 163

2₀(148) → 149

2₀(161) → 162

2₀(156) → 157

2₀(235) → 236

2₀(154) → 155

2₀(189) → 190

2₀(31) → 32

2₀(102) → 103

2₀(65) → 57

2₀(176) → 177

2₀(131) → 132

2₀(114) → 115

2₀(79) → 80

2₀(210) → 211

2₀(212) → 213

2₀(199) → 200

2₀(68) → 189

2₀(111) → 112

2₀(75) → 76

2₀(2) → 31

2₀(221) → 222

2₀(200) → 201

0₀(147) → 148

0₀(99) → 100

0₀(18) → 19

0₀(193) → 194

0₀(68) → 69

0₀(205) → 188

0₀(97) → 98

0₀(34) → 35

0₀(61) → 62

0₀(91) → 92

0₀(181) → 182

0₀(217) → 218

0₀(183) → 184

0₀(194) → 195

0₀(6) → 17

0₀(109) → 110

0₀(192) → 193

0₀(80) → 81

0₀(239) → 240

0₀(89) → 90

0₀(2) → 26

0₀(163) → 164

0₀(26) → 39

0₀(36) → 37

0₀(168) → 169

0₀(1) → 52

0₀(116) → 117

0₀(58) → 59

0₀(115) → 116

0₀(106) → 107

0₀(39) → 40

0₀(207) → 208

0₀(100) → 101

0₀(153) → 154

0₀(204) → 205

0₀(112) → 113

f6₀ → 2

3₀(2) → 6

3₀(157) → 158

3₀(149) → 150

3₀(196) → 197

3₀(56) → 51

3₀(117) → 118

3₀(227) → 228

3₀(49) → 50

3₀(110) → 111

3₀(213) → 214

3₀(48) → 49

3₀(19) → 20

3₀(215) → 216

3₀(152) → 153

3₀(220) → 221

3₀(4) → 1

3₀(37) → 30

3₀(178) → 179

3₀(214) → 215

3₀(84) → 77

3₀(86) → 87

3₀(118) → 105

3₀(70) → 71

3₀(132) → 119

3₀(125) → 126

3₀(32) → 33

3₀(137) → 138

3₀(7) → 46

3₀(33) → 34

3₀(52) → 53

3₀(129) → 130

3₀(22) → 134

3₀(42) → 43

3₀(120) → 121

3₀(126) → 127

3₀(229) → 230

3₀(41) → 42

3₀(187) → 175

3₀(31) → 120

3₀(144) → 145

3₀(231) → 232

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