YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 String Reversal

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

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

1.1 Bounds

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

final states:

{215, 198, 182, 168, 155, 143, 131, 120, 107, 94, 83, 75, 65, 57, 50, 43, 38, 31, 24, 19, 14, 12, 8, 5, 1}

transitions:

239 → 218

120 → 9

3 → 236

50 → 20

50 → 108

57 → 84

5 → 95

37 → 250

65 → 11

65 → 108

243 → 138

107 → 237

107 → 236

107 → 3

31 → 216

31 → 25

1 → 95

8 → 84

135 → 240

38 → 108

251 → 237

75 → 9

143 → 236

143 → 3

14 → 236

14 → 3

12 → 66

12 → 108

182 → 9

83 → 95

198 → 6

198 → 84

168 → 236

168 → 3

215 → 237

215 → 236

215 → 3

131 → 95

24 → 85

24 → 25

19 → 66

19 → 108

43 → 95

155 → 236

155 → 3

94 → 96

94 → 108

f6₀ → 2

0₀(132) → 156

0₀(135) → 136

0₀(87) → 88

0₀(96) → 144

0₀(72) → 73

0₀(128) → 129

0₀(139) → 140

0₀(169) → 170

0₀(32) → 33

0₀(61) → 62

0₀(140) → 141

0₀(133) → 134

0₀(199) → 200

0₀(212) → 213

0₀(84) → 85

0₀(66) → 169

0₀(127) → 128

0₀(76) → 77

0₀(89) → 90

0₀(2) → 25

0₀(3) → 216

0₀(30) → 24

0₀(37) → 31

0₀(108) → 109

0₀(110) → 111

0₀(33) → 34

0₀(178) → 179

0₀(158) → 159

0₀(25) → 32

0₀(204) → 205

0₀(160) → 161

0₀(209) → 210

0₀(141) → 142

0₀(112) → 113

4₀(226) → 227

4₀(148) → 149

4₀(206) → 207

4₀(150) → 151

4₀(170) → 171

4₀(42) → 38

4₀(76) → 199

4₀(59) → 60

4₀(166) → 167

4₀(7) → 5

4₀(58) → 59

4₀(207) → 208

4₀(35) → 36

4₀(45) → 46

4₀(132) → 133

4₀(125) → 126

4₀(105) → 106

4₀(32) → 44

4₀(99) → 100

4₀(95) → 96

4₀(6) → 7

4₀(60) → 61

4₀(203) → 204

4₀(134) → 135

4₀(187) → 188

4₀(222) → 223

4₀(28) → 29

4₀(3) → 4

4₀(47) → 48

4₀(172) → 173

4₀(113) → 114

4₀(111) → 112

4₀(116) → 117

4₀(9) → 20

4₀(25) → 66

4₀(54) → 55

4₀(180) → 181

4₀(224) → 225

4₀(102) → 103

4₀(15) → 16

4₀(27) → 28

4₀(223) → 224

4₀(20) → 21

4₀(115) → 116

4₀(62) → 63

4₀(103) → 104

4₀(67) → 68

4₀(10) → 11

4₀(2) → 108

4₀(188) → 189

4₀(229) → 230

4₀(157) → 158

4₀(22) → 23

3₀(51) → 183

3₀(183) → 184

3₀(73) → 74

3₀(146) → 147

3₀(210) → 211

3₀(93) → 83

3₀(80) → 81

3₀(167) → 155

3₀(18) → 14

3₀(151) → 152

3₀(145) → 146

3₀(119) → 107

3₀(39) → 40

3₀(161) → 162

3₀(126) → 127

3₀(55) → 56

3₀(205) → 206

3₀(97) → 98

3₀(4) → 58

3₀(181) → 168

3₀(225) → 226

3₀(40) → 41

3₀(2) → 3

3₀(213) → 214

3₀(85) → 86

3₀(17) → 18

3₀(192) → 193

3₀(156) → 157

3₀(100) → 101

3₀(218) → 219

1₁(242) → 243

1₁(238) → 239

5₀(109) → 110

5₀(2) → 84

5₀(231) → 215

5₀(25) → 26

5₀(177) → 178

5₀(124) → 125

5₀(186) → 187

5₀(51) → 52

5₀(227) → 228

5₀(201) → 202

5₀(193) → 194

5₀(44) → 45

5₀(147) → 148

5₀(202) → 203

5₀(32) → 132

5₀(144) → 145

5₀(46) → 47

5₀(173) → 174

5₀(165) → 166

5₀(164) → 165

5₀(70) → 71

5₀(91) → 92

5₀(123) → 124

5₀(214) → 198

5₀(11) → 8

5₀(92) → 93

5₀(36) → 37

5₀(9) → 10

5₀(68) → 69

5₀(195) → 196

5₀(23) → 19

5₀(64) → 57

5₀(13) → 12

5₀(118) → 119

5₀(69) → 70

5₀(15) → 51

5₀(189) → 190

5₀(3) → 6

5₀(52) → 53

5₀(29) → 30

5₀(104) → 105

5₀(171) → 172

5₀(196) → 197

5₀(153) → 154

1₀(2) → 9

1₀(9) → 15

1₀(90) → 91

1₀(184) → 185

1₀(230) → 231

1₀(175) → 176

1₀(197) → 182

1₀(79) → 80

1₀(152) → 153

1₀(220) → 221

1₀(71) → 72

1₀(4) → 1

1₀(74) → 65

1₀(96) → 97

1₀(86) → 87

1₀(211) → 212

1₀(176) → 177

1₀(136) → 137

1₀(216) → 217

1₀(121) → 122

1₀(221) → 222

1₀(81) → 82

1₀(228) → 229

1₀(130) → 120

1₀(101) → 102

1₀(129) → 130

1₀(82) → 75

1₀(142) → 131

1₀(41) → 42

1₀(185) → 186

1₀(106) → 94

1₀(200) → 201

1₀(88) → 89

4₁(241) → 242

4₁(237) → 238

3₁(250) → 251

3₁(240) → 241

3₁(236) → 237

2₀(21) → 22

2₀(191) → 192

2₀(78) → 79

2₀(122) → 123

2₀(98) → 99

2₀(208) → 209

2₀(63) → 64

2₀(53) → 54

2₀(117) → 118

2₀(26) → 27

2₀(11) → 13

2₀(66) → 67

2₀(56) → 50

2₀(162) → 163

2₀(20) → 39

2₀(149) → 150

2₀(194) → 195

2₀(49) → 43

2₀(159) → 160

2₀(154) → 143

2₀(16) → 17

2₀(48) → 49

2₀(3) → 76

2₀(217) → 218

2₀(137) → 138

2₀(190) → 191

2₀(34) → 35

2₀(219) → 220

2₀(32) → 121

2₀(163) → 164

2₀(138) → 139

2₀(179) → 180

2₀(114) → 115

2₀(77) → 78

2₀(174) → 175

2₀(2) → 95

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