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

1.1 Bounds

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

final states:

{234, 215, 196, 179, 163, 147, 132, 116, 106, 95, 85, 76, 67, 59, 51, 46, 40, 34, 30, 24, 19, 16, 11, 6, 1}

transitions:

51 → 68

51 → 12

147 → 3

95 → 21

95 → 197

95 → 35

59 → 180

59 → 35

34 → 3

1 → 36

1 → 12

40 → 60

40 → 25

179 → 26

179 → 35

76 → 26

76 → 35

6 → 7

116 → 216

67 → 180

67 → 35

11 → 7

106 → 3

16 → 86

16 → 12

85 → 3

234 → 25

30 → 12

46 → 35

215 → 1

132 → 180

132 → 35

24 → 20

24 → 12

19 → 25

163 → 197

163 → 35

196 → 25

f6₀ → 2

4₀(176) → 177

4₀(48) → 49

4₀(60) → 96

4₀(229) → 230

4₀(189) → 190

4₀(137) → 138

4₀(128) → 129

4₀(68) → 69

4₀(232) → 233

4₀(22) → 23

4₀(222) → 223

4₀(50) → 46

4₀(214) → 196

4₀(109) → 110

4₀(252) → 234

4₀(151) → 152

4₀(240) → 241

4₀(83) → 84

4₀(2) → 25

4₀(41) → 107

4₀(75) → 67

4₀(27) → 28

4₀(37) → 38

4₀(124) → 125

4₀(143) → 144

4₀(8) → 17

4₀(52) → 53

4₀(108) → 109

4₀(13) → 14

4₀(25) → 60

4₀(150) → 151

4₀(104) → 105

4₀(209) → 210

4₀(220) → 221

2₀(126) → 127

2₀(170) → 171

2₀(41) → 47

2₀(14) → 133

2₀(63) → 64

2₀(212) → 213

2₀(142) → 143

2₀(118) → 119

2₀(169) → 170

2₀(7) → 180

2₀(205) → 206

2₀(84) → 76

2₀(210) → 211

2₀(168) → 169

2₀(231) → 232

2₀(247) → 248

2₀(213) → 214

2₀(187) → 188

2₀(120) → 121

2₀(242) → 243

2₀(88) → 89

2₀(195) → 179

2₀(238) → 239

2₀(3) → 4

2₀(243) → 244

2₀(97) → 98

2₀(154) → 155

2₀(140) → 141

2₀(221) → 222

2₀(235) → 236

2₀(25) → 26

2₀(184) → 185

2₀(12) → 197

2₀(248) → 249

2₀(146) → 132

2₀(208) → 209

2₀(224) → 225

2₀(102) → 103

2₀(20) → 21

2₀(21) → 22

2₀(74) → 75

2₀(181) → 182

2₀(103) → 104

2₀(2) → 35

2₀(4) → 5

2₀(188) → 189

2₀(66) → 59

0₀(175) → 176

0₀(239) → 240

0₀(180) → 181

0₀(53) → 54

0₀(173) → 174

0₀(73) → 74

0₀(200) → 201

0₀(227) → 228

0₀(158) → 159

0₀(41) → 77

0₀(7) → 31

0₀(44) → 45

0₀(98) → 99

0₀(207) → 208

0₀(91) → 92

0₀(123) → 124

0₀(8) → 9

0₀(165) → 166

0₀(197) → 198

0₀(133) → 134

0₀(64) → 65

0₀(9) → 10

0₀(249) → 250

0₀(60) → 235

0₀(119) → 120

0₀(110) → 111

0₀(71) → 72

0₀(42) → 43

0₀(149) → 150

0₀(81) → 82

0₀(160) → 161

0₀(182) → 183

0₀(122) → 123

0₀(2) → 3

0₀(164) → 165

0₀(156) → 157

0₀(38) → 39

0₀(218) → 219

5₀(2) → 7

5₀(45) → 40

5₀(117) → 118

5₀(159) → 160

5₀(167) → 168

5₀(26) → 27

5₀(186) → 187

5₀(211) → 212

5₀(193) → 194

5₀(202) → 203

5₀(162) → 147

5₀(28) → 29

5₀(192) → 193

5₀(115) → 106

5₀(174) → 175

5₀(245) → 246

5₀(70) → 71

5₀(12) → 13

5₀(203) → 204

5₀(230) → 231

5₀(199) → 200

5₀(141) → 142

5₀(105) → 95

5₀(36) → 37

5₀(251) → 252

5₀(14) → 15

5₀(23) → 19

5₀(54) → 55

5₀(56) → 57

5₀(134) → 135

5₀(148) → 164

5₀(17) → 18

5₀(57) → 58

5₀(219) → 220

5₀(241) → 242

5₀(121) → 122

5₀(15) → 11

5₀(145) → 146

5₀(226) → 227

5₀(237) → 238

5₀(3) → 52

5₀(10) → 6

5₀(43) → 44

5₀(246) → 247

5₀(153) → 154

5₀(65) → 66

5₀(7) → 117

3₀(2) → 12

3₀(157) → 158

3₀(18) → 16

3₀(177) → 178

3₀(250) → 251

3₀(191) → 192

3₀(79) → 80

3₀(80) → 81

3₀(225) → 226

3₀(55) → 56

3₀(107) → 108

3₀(217) → 218

3₀(92) → 93

3₀(233) → 215

3₀(244) → 245

3₀(178) → 163

3₀(96) → 97

3₀(206) → 207

3₀(3) → 20

3₀(86) → 87

3₀(100) → 101

3₀(136) → 137

3₀(62) → 63

3₀(94) → 85

3₀(216) → 217

3₀(125) → 126

3₀(112) → 113

3₀(29) → 24

3₀(228) → 229

3₀(130) → 131

3₀(7) → 86

3₀(35) → 36

3₀(129) → 130

3₀(183) → 184

3₀(39) → 34

3₀(12) → 68

3₀(60) → 61

3₀(41) → 42

3₀(58) → 51

3₀(5) → 1

3₀(185) → 186

3₀(148) → 149

3₀(72) → 73

3₀(47) → 48

3₀(171) → 172

1₀(87) → 88

1₀(25) → 41

1₀(101) → 102

1₀(201) → 202

1₀(135) → 136

1₀(78) → 79

1₀(99) → 100

1₀(82) → 83

1₀(223) → 224

1₀(172) → 173

1₀(61) → 62

1₀(152) → 153

1₀(69) → 70

1₀(198) → 199

1₀(236) → 237

1₀(7) → 8

1₀(90) → 91

1₀(93) → 94

1₀(166) → 167

1₀(161) → 162

1₀(139) → 140

1₀(89) → 90

1₀(155) → 156

1₀(194) → 195

1₀(49) → 50

1₀(35) → 148

1₀(31) → 32

1₀(190) → 191

1₀(32) → 33

1₀(138) → 139

1₀(144) → 145

1₀(131) → 116

1₀(114) → 115

1₀(77) → 78

1₀(33) → 30

1₀(12) → 216

1₀(111) → 112

1₀(127) → 128

1₀(204) → 205

1₀(113) → 114

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