YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 String Reversal

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

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

1.1 Bounds

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

final states:

{238, 220, 202, 186, 173, 160, 146, 133, 120, 108, 96, 85, 74, 65, 56, 48, 40, 33, 27, 21, 17, 15, 11, 7, 1}

transitions:

33 → 49

33 → 12

202 → 22

15 → 147

15 → 22

96 → 66

96 → 22

133 → 24

133 → 22

120 → 4

120 → 8

108 → 3

65 → 13

1 → 3

40 → 23

40 → 239

21 → 22

186 → 239

220 → 23

220 → 239

11 → 18

11 → 3

85 → 22

48 → 3

17 → 22

160 → 28

160 → 3

74 → 3

27 → 8

56 → 121

56 → 3

238 → 18

238 → 3

4₀(51) → 52

4₀(239) → 240

4₀(203) → 204

4₀(46) → 47

4₀(212) → 213

4₀(73) → 65

4₀(144) → 145

4₀(24) → 25

4₀(134) → 135

4₀(113) → 114

4₀(82) → 83

4₀(208) → 209

4₀(198) → 199

4₀(145) → 133

4₀(247) → 248

4₀(149) → 150

4₀(55) → 48

4₀(196) → 197

4₀(97) → 98

4₀(81) → 82

4₀(10) → 7

4₀(63) → 64

4₀(117) → 118

4₀(225) → 226

4₀(250) → 251

4₀(185) → 173

4₀(192) → 193

4₀(12) → 13

4₀(243) → 244

5₀(72) → 73

5₀(20) → 17

5₀(109) → 110

5₀(2) → 12

5₀(95) → 85

5₀(205) → 206

5₀(26) → 21

5₀(227) → 228

5₀(157) → 158

5₀(88) → 89

5₀(249) → 250

5₀(162) → 163

5₀(98) → 99

5₀(77) → 78

5₀(76) → 77

5₀(140) → 141

5₀(233) → 234

5₀(150) → 151

5₀(12) → 75

5₀(229) → 230

5₀(8) → 9

5₀(89) → 90

5₀(223) → 224

5₀(187) → 188

5₀(191) → 192

5₀(106) → 107

5₀(9) → 221

5₀(68) → 69

5₀(18) → 19

5₀(183) → 184

5₀(13) → 14

5₀(219) → 202

5₀(116) → 117

5₀(244) → 245

5₀(170) → 171

5₀(39) → 33

5₀(204) → 205

5₀(142) → 143

5₀(121) → 122

5₀(86) → 87

5₀(3) → 49

5₀(52) → 53

5₀(75) → 76

1₀(124) → 125

1₀(137) → 138

1₀(148) → 149

1₀(200) → 201

1₀(123) → 124

1₀(42) → 43

1₀(91) → 92

1₀(199) → 200

1₀(35) → 36

1₀(8) → 28

1₀(210) → 211

1₀(257) → 238

1₀(134) → 161

1₀(152) → 153

1₀(155) → 156

1₀(158) → 159

1₀(176) → 177

1₀(131) → 132

1₀(197) → 198

1₀(3) → 18

1₀(172) → 160

1₀(111) → 112

1₀(9) → 10

1₀(232) → 233

1₀(12) → 121

1₀(61) → 62

1₀(193) → 194

1₀(13) → 134

1₀(53) → 54

1₀(5) → 6

1₀(119) → 108

1₀(122) → 123

1₀(2) → 3

1₀(256) → 257

1₀(4) → 5

1₀(214) → 215

1₀(44) → 45

1₀(211) → 212

2₀(87) → 88

2₀(29) → 30

2₀(218) → 219

2₀(58) → 59

2₀(255) → 256

2₀(50) → 51

2₀(230) → 231

2₀(136) → 137

2₀(60) → 61

2₀(242) → 243

2₀(226) → 227

2₀(4) → 203

2₀(28) → 29

2₀(184) → 185

2₀(207) → 208

2₀(234) → 235

2₀(41) → 42

2₀(22) → 147

2₀(147) → 148

2₀(67) → 68

2₀(107) → 96

2₀(139) → 140

2₀(209) → 210

2₀(83) → 84

2₀(159) → 146

2₀(14) → 11

2₀(103) → 104

2₀(16) → 15

2₀(189) → 190

2₀(165) → 166

2₀(80) → 81

2₀(31) → 32

2₀(30) → 31

2₀(102) → 103

2₀(206) → 207

2₀(62) → 63

2₀(224) → 225

2₀(195) → 196

2₀(57) → 58

2₀(163) → 164

2₀(138) → 139

2₀(179) → 180

2₀(175) → 176

2₀(254) → 255

2₀(79) → 80

2₀(38) → 39

2₀(228) → 229

2₀(37) → 38

2₀(23) → 24

2₀(12) → 66

2₀(188) → 189

2₀(178) → 179

2₀(215) → 216

2₀(2) → 22

2₀(221) → 222

3₀(235) → 236

3₀(90) → 91

3₀(59) → 60

3₀(236) → 237

3₀(93) → 94

3₀(99) → 100

3₀(156) → 157

3₀(105) → 106

3₀(128) → 129

3₀(12) → 41

3₀(166) → 167

3₀(118) → 119

3₀(253) → 254

3₀(34) → 35

3₀(94) → 95

3₀(19) → 20

3₀(130) → 131

3₀(125) → 126

3₀(54) → 55

3₀(22) → 23

3₀(181) → 182

3₀(194) → 195

3₀(5) → 97

3₀(251) → 252

3₀(167) → 168

3₀(66) → 67

3₀(127) → 128

3₀(216) → 217

3₀(49) → 50

3₀(177) → 178

3₀(2) → 239

3₀(45) → 46

3₀(168) → 169

3₀(143) → 144

3₀(129) → 130

3₀(28) → 109

3₀(101) → 102

3₀(115) → 116

3₀(13) → 57

3₀(100) → 101

3₀(25) → 26

3₀(154) → 155

3₀(104) → 105

3₀(248) → 249

3₀(141) → 142

3₀(112) → 113

f6₀ → 2

0₀(2) → 8

0₀(114) → 115

0₀(237) → 220

0₀(9) → 16

0₀(110) → 111

0₀(213) → 214

0₀(64) → 56

0₀(246) → 247

0₀(252) → 253

0₀(36) → 37

0₀(71) → 72

0₀(217) → 218

0₀(43) → 44

0₀(92) → 93

0₀(222) → 223

0₀(151) → 152

0₀(3) → 4

0₀(164) → 165

0₀(84) → 74

0₀(135) → 136

0₀(6) → 1

0₀(245) → 246

0₀(70) → 71

0₀(132) → 120

0₀(32) → 27

0₀(241) → 242

0₀(161) → 162

0₀(180) → 181

0₀(240) → 241

0₀(22) → 187

0₀(201) → 186

0₀(126) → 127

0₀(12) → 34

0₀(174) → 175

0₀(78) → 79

0₀(190) → 191

0₀(5) → 174

0₀(231) → 232

0₀(13) → 86

0₀(169) → 170

0₀(47) → 40

0₀(153) → 154

0₀(182) → 183

0₀(171) → 172

0₀(69) → 70

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