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

Proof

1 String Reversal

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

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

1.1 Bounds

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

final states:

{249, 229, 210, 194, 176, 158, 145, 129, 116, 104, 93, 83, 71, 61, 55, 46, 38, 31, 25, 19, 15, 12, 8, 5, 1}

transitions:

176 → 3

25 → 17

25 → 16

61 → 3

229 → 20

15 → 195

15 → 6

129 → 9

145 → 16

5 → 130

5 → 9

55 → 13

55 → 16

31 → 3

1 → 3

8 → 20

71 → 20

38 → 105

38 → 6

116 → 6

249 → 20

270 → 195

93 → 7

93 → 9

12 → 9

104 → 212

104 → 211

46 → 230

46 → 16

158 → 9

83 → 3

19 → 20

210 → 117

210 → 9

194 → 72

194 → 211

156 → 266

f6₀ → 2

5₀(236) → 237

5₀(48) → 49

5₀(16) → 17

5₀(77) → 78

5₀(60) → 55

5₀(20) → 230

5₀(137) → 138

5₀(88) → 89

5₀(79) → 80

5₀(97) → 98

5₀(157) → 145

5₀(40) → 41

5₀(125) → 126

5₀(54) → 46

5₀(73) → 74

5₀(202) → 203

5₀(9) → 10

5₀(222) → 223

5₀(191) → 192

5₀(50) → 51

5₀(214) → 215

5₀(42) → 43

5₀(251) → 252

5₀(206) → 207

5₀(6) → 26

5₀(84) → 94

5₀(241) → 242

5₀(216) → 217

5₀(63) → 64

5₀(148) → 149

5₀(245) → 246

5₀(171) → 172

5₀(43) → 44

5₀(2) → 16

5₀(3) → 13

5₀(107) → 108

5₀(231) → 232

5₀(124) → 125

5₀(122) → 123

5₀(35) → 36

5₀(103) → 93

5₀(58) → 59

5₀(29) → 30

5₀(164) → 165

5₀(33) → 34

5₀(226) → 227

5₀(102) → 103

5₀(257) → 258

5₀(141) → 142

0₀(227) → 228

0₀(126) → 127

0₀(78) → 79

0₀(159) → 160

0₀(147) → 148

0₀(160) → 161

0₀(142) → 143

0₀(7) → 5

0₀(130) → 131

0₀(136) → 137

0₀(205) → 206

0₀(105) → 106

0₀(99) → 100

0₀(6) → 72

0₀(167) → 168

0₀(247) → 248

0₀(131) → 132

0₀(197) → 198

0₀(87) → 88

0₀(28) → 29

0₀(172) → 173

0₀(139) → 140

0₀(64) → 65

0₀(111) → 112

0₀(96) → 97

0₀(94) → 95

0₀(127) → 128

0₀(15) → 56

0₀(20) → 21

0₀(115) → 104

0₀(21) → 22

0₀(53) → 54

0₀(117) → 118

0₀(119) → 120

0₀(17) → 18

0₀(10) → 84

0₀(2) → 211

0₀(237) → 238

0₀(138) → 139

0₀(211) → 212

0₀(198) → 199

0₀(22) → 23

1₀(189) → 190

1₀(244) → 245

1₀(260) → 261

1₀(175) → 158

1₀(74) → 75

1₀(16) → 117

1₀(190) → 191

1₀(67) → 68

1₀(203) → 204

1₀(173) → 174

1₀(166) → 167

1₀(209) → 194

1₀(234) → 235

1₀(120) → 121

1₀(144) → 129

1₀(252) → 253

1₀(86) → 87

1₀(240) → 241

1₀(98) → 99

1₀(32) → 33

1₀(253) → 254

1₀(207) → 208

1₀(135) → 136

1₀(80) → 81

1₀(256) → 257

1₀(133) → 134

1₀(170) → 171

1₀(155) → 156

1₀(56) → 57

1₀(68) → 69

1₀(113) → 114

1₀(9) → 130

1₀(118) → 119

1₀(201) → 202

1₀(179) → 180

1₀(6) → 7

1₀(72) → 73

1₀(258) → 259

1₀(233) → 234

1₀(81) → 82

1₀(220) → 221

1₀(2) → 9

1₀(23) → 24

1₀(178) → 250

1₀(154) → 155

1₀(168) → 169

1₀(156) → 157

1₀(100) → 101

1₀(264) → 265

1₀(188) → 189

3₁(269) → 270

3₀(20) → 177

3₀(2) → 6

3₀(255) → 256

3₀(45) → 38

3₀(26) → 27

3₀(51) → 52

3₀(110) → 111

3₀(16) → 62

3₀(192) → 193

3₀(34) → 35

3₀(224) → 225

3₀(218) → 219

3₀(140) → 141

3₀(165) → 166

3₀(243) → 244

3₀(123) → 124

3₀(199) → 200

3₀(92) → 83

3₀(36) → 37

3₀(9) → 159

3₀(18) → 15

3₀(183) → 184

3₀(128) → 116

3₀(212) → 213

3₀(265) → 249

3₀(118) → 195

3₀(250) → 251

3₀(84) → 85

3₀(184) → 185

3₀(204) → 205

3₀(259) → 260

3₀(121) → 122

3₀(49) → 50

3₀(3) → 105

3₀(239) → 240

3₀(208) → 209

3₀(65) → 66

2₀(2) → 3

2₀(163) → 164

2₀(114) → 115

2₀(149) → 150

2₀(91) → 92

2₀(263) → 264

2₀(90) → 91

2₀(134) → 135

2₀(146) → 147

2₀(213) → 214

2₀(95) → 96

2₀(30) → 25

2₀(215) → 216

2₀(152) → 153

2₀(235) → 236

2₀(217) → 218

2₀(4) → 1

2₀(37) → 31

2₀(178) → 179

2₀(181) → 182

2₀(89) → 90

2₀(3) → 4

2₀(14) → 12

2₀(66) → 67

2₀(70) → 61

2₀(221) → 222

2₀(27) → 28

2₀(52) → 53

2₀(101) → 102

2₀(195) → 196

2₀(186) → 187

2₀(162) → 163

2₀(41) → 42

2₀(44) → 45

2₀(187) → 188

2₀(219) → 220

2₀(261) → 262

2₀(59) → 60

2₀(185) → 186

2₀(106) → 107

2₀(13) → 14

2₀(200) → 201

2₀(193) → 176

2₀(169) → 170

2₀(47) → 48

2₀(153) → 154

2₀(69) → 70

0₁(268) → 269

5₁(266) → 267

5₁(267) → 268

4₀(108) → 109

4₀(143) → 144

4₀(238) → 239

4₀(17) → 47

4₀(112) → 113

4₀(246) → 247

4₀(132) → 133

4₀(82) → 71

4₀(223) → 224

4₀(151) → 152

4₀(5) → 146

4₀(177) → 178

4₀(230) → 231

4₀(11) → 8

4₀(242) → 243

4₀(196) → 197

4₀(10) → 11

4₀(39) → 40

4₀(20) → 32

4₀(161) → 162

4₀(248) → 229

4₀(232) → 233

4₀(182) → 183

4₀(16) → 39

4₀(62) → 63

4₀(57) → 58

4₀(150) → 151

4₀(254) → 255

4₀(85) → 86

4₀(24) → 19

4₀(262) → 263

4₀(180) → 181

4₀(109) → 110

4₀(76) → 77

4₀(228) → 210

4₀(174) → 175

4₀(75) → 76

4₀(2) → 20

4₀(225) → 226

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