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

Proof

1 String Reversal

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

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

1.1 Bounds

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

final states:

{168, 165, 161, 157, 152, 147, 144, 138, 135, 131, 126, 121, 120, 115, 110, 108, 103, 100, 97, 93, 88, 85, 84, 80, 78, 76, 73, 68, 63, 62, 57, 53, 50, 48, 46, 42, 38, 35, 31, 26, 24, 19, 14, 12, 8, 1}

transitions:

78 → 43

78 → 58

157 → 27

80 → 139

103 → 59

103 → 27

152 → 3

97 → 3

50 → 3

57 → 3

108 → 33

108 → 4

108 → 27

147 → 27

110 → 3

62 → 3

31 → 3

1 → 27

8 → 64

8 → 139

165 → 3

135 → 21

135 → 27

73 → 27

26 → 3

76 → 64

76 → 139

38 → 3

161 → 64

161 → 139

138 → 4

138 → 27

121 → 4

121 → 27

88 → 4

88 → 27

53 → 58

4 → 58

14 → 4

14 → 27

93 → 3

63 → 3

12 → 58

12 → 3

85 → 27

100 → 3

126 → 89

126 → 3

42 → 3

64 → 3

46 → 27

35 → 3

115 → 27

48 → 3

168 → 58

68 → 58

131 → 3

24 → 58

19 → 4

19 → 27

144 → 3

1₀(51) → 145

1₀(74) → 75

1₀(127) → 162

1₀(37) → 35

1₀(95) → 96

1₀(3) → 9

1₀(44) → 45

1₀(33) → 34

1₀(58) → 127

1₀(21) → 22

1₀(143) → 138

1₀(150) → 151

1₀(140) → 141

1₀(133) → 134

1₀(64) → 65

1₀(151) → 147

1₀(27) → 28

1₀(94) → 101

1₀(119) → 115

1₀(75) → 73

1₀(71) → 72

1₀(5) → 86

1₀(4) → 5

1₀(28) → 158

1₀(47) → 46

1₀(40) → 41

1₀(139) → 169

1₀(122) → 123

1₀(2) → 15

1₀(20) → 111

1₀(104) → 105

1₀(153) → 154

2₀(72) → 68

2₀(20) → 21

2₀(2) → 27

2₀(132) → 133

2₀(117) → 118

2₀(58) → 59

2₀(44) → 47

2₀(32) → 33

2₀(87) → 85

2₀(89) → 94

2₀(91) → 92

2₀(114) → 110

2₀(92) → 88

2₀(36) → 37

2₀(18) → 14

2₀(137) → 135

2₀(139) → 140

2₀(118) → 119

2₀(62) → 84

2₀(39) → 40

2₀(33) → 74

2₀(146) → 144

2₀(3) → 4

2₀(43) → 44

2₀(81) → 82

2₀(149) → 150

3₀(98) → 99

3₀(65) → 66

3₀(123) → 124

3₀(30) → 109

3₀(59) → 60

3₀(169) → 170

3₀(105) → 106

3₀(32) → 36

3₀(6) → 7

3₀(158) → 159

3₀(29) → 30

3₀(82) → 83

3₀(28) → 29

3₀(3) → 69

3₀(111) → 112

3₀(116) → 117

3₀(9) → 10

3₀(163) → 164

3₀(101) → 102

3₀(128) → 129

3₀(127) → 128

3₀(15) → 16

3₀(20) → 39

3₀(13) → 79

3₀(5) → 6

3₀(17) → 25

3₀(2) → 20

3₀(141) → 142

3₀(22) → 23

3₀(16) → 54

3₀(89) → 90

4₀(58) → 148

4₀(86) → 87

4₀(136) → 137

4₀(26) → 120

4₀(11) → 8

4₀(27) → 104

4₀(162) → 163

4₀(15) → 116

4₀(156) → 152

4₀(40) → 49

4₀(145) → 146

4₀(3) → 64

4₀(34) → 31

4₀(134) → 131

4₀(51) → 52

4₀(2) → 139

5₀(64) → 81

5₀(90) → 91

5₀(70) → 71

5₀(16) → 17

5₀(60) → 61

5₀(96) → 93

5₀(20) → 43

5₀(55) → 56

5₀(79) → 78

5₀(94) → 95

5₀(40) → 136

5₀(125) → 121

5₀(54) → 55

5₀(167) → 165

5₀(66) → 77

5₀(148) → 149

5₀(171) → 172

5₀(113) → 114

5₀(2) → 58

5₀(170) → 171

5₀(27) → 122

5₀(58) → 153

5₀(29) → 166

5₀(10) → 13

5₀(13) → 62

5₀(102) → 100

5₀(106) → 107

5₀(51) → 98

5₀(154) → 155

5₀(159) → 160

f6₀ → 2

0₀(2) → 3

0₀(56) → 53

0₀(10) → 11

0₀(49) → 48

0₀(67) → 63

0₀(99) → 97

0₀(166) → 167

0₀(30) → 26

0₀(107) → 103

0₀(25) → 24

0₀(124) → 125

0₀(61) → 57

0₀(155) → 156

0₀(3) → 89

0₀(164) → 161

0₀(17) → 18

0₀(83) → 80

0₀(66) → 67

0₀(23) → 19

0₀(32) → 132

0₀(112) → 113

0₀(130) → 126

0₀(7) → 1

0₀(52) → 50

0₀(45) → 42

0₀(129) → 130

0₀(172) → 168

0₀(20) → 32

0₀(142) → 143

0₀(41) → 38

0₀(16) → 51

0₀(109) → 108

0₀(77) → 76

0₀(13) → 12

0₀(160) → 157

0₀(69) → 70

78	→	43
78	→	58
157	→	27
80	→	139
103	→	59
103	→	27
152	→	3
97	→	3
50	→	3
57	→	3
108	→	33
108	→	4
108	→	27
147	→	27
110	→	3
62	→	3
31	→	3
1	→	27
8	→	64
8	→	139
165	→	3
135	→	21
135	→	27
73	→	27
26	→	3
76	→	64
76	→	139
38	→	3
161	→	64
161	→	139
138	→	4
138	→	27
121	→	4
121	→	27
88	→	4
88	→	27
53	→	58
4	→	58
14	→	4
14	→	27
93	→	3
63	→	3
12	→	58
12	→	3
85	→	27
100	→	3
126	→	89
126	→	3
42	→	3
64	→	3
46	→	27
35	→	3
115	→	27
48	→	3
168	→	58
68	→	58
131	→	3
24	→	58
19	→	4
19	→	27
144	→	3
1₀(51)	→	145
1₀(74)	→	75
1₀(127)	→	162
1₀(37)	→	35
1₀(95)	→	96
1₀(3)	→	9
1₀(44)	→	45
1₀(33)	→	34
1₀(58)	→	127
1₀(21)	→	22
1₀(143)	→	138
1₀(150)	→	151
1₀(140)	→	141
1₀(133)	→	134
1₀(64)	→	65
1₀(151)	→	147
1₀(27)	→	28
1₀(94)	→	101
1₀(119)	→	115
1₀(75)	→	73
1₀(71)	→	72
1₀(5)	→	86
1₀(4)	→	5
1₀(28)	→	158
1₀(47)	→	46
1₀(40)	→	41
1₀(139)	→	169
1₀(122)	→	123
1₀(2)	→	15
1₀(20)	→	111
1₀(104)	→	105
1₀(153)	→	154
2₀(72)	→	68
2₀(20)	→	21
2₀(2)	→	27
2₀(132)	→	133
2₀(117)	→	118
2₀(58)	→	59
2₀(44)	→	47
2₀(32)	→	33
2₀(87)	→	85
2₀(89)	→	94
2₀(91)	→	92
2₀(114)	→	110
2₀(92)	→	88
2₀(36)	→	37
2₀(18)	→	14
2₀(137)	→	135
2₀(139)	→	140
2₀(118)	→	119
2₀(62)	→	84
2₀(39)	→	40
2₀(33)	→	74
2₀(146)	→	144
2₀(3)	→	4
2₀(43)	→	44
2₀(81)	→	82
2₀(149)	→	150
3₀(98)	→	99
3₀(65)	→	66
3₀(123)	→	124
3₀(30)	→	109
3₀(59)	→	60
3₀(169)	→	170
3₀(105)	→	106
3₀(32)	→	36
3₀(6)	→	7
3₀(158)	→	159
3₀(29)	→	30
3₀(82)	→	83
3₀(28)	→	29
3₀(3)	→	69
3₀(111)	→	112
3₀(116)	→	117
3₀(9)	→	10
3₀(163)	→	164
3₀(101)	→	102
3₀(128)	→	129
3₀(127)	→	128
3₀(15)	→	16
3₀(20)	→	39
3₀(13)	→	79
3₀(5)	→	6
3₀(17)	→	25
3₀(2)	→	20
3₀(141)	→	142
3₀(22)	→	23
3₀(16)	→	54
3₀(89)	→	90
4₀(58)	→	148
4₀(86)	→	87
4₀(136)	→	137
4₀(26)	→	120
4₀(11)	→	8
4₀(27)	→	104
4₀(162)	→	163
4₀(15)	→	116
4₀(156)	→	152
4₀(40)	→	49
4₀(145)	→	146
4₀(3)	→	64
4₀(34)	→	31
4₀(134)	→	131
4₀(51)	→	52
4₀(2)	→	139
5₀(64)	→	81
5₀(90)	→	91
5₀(70)	→	71
5₀(16)	→	17
5₀(60)	→	61
5₀(96)	→	93
5₀(20)	→	43
5₀(55)	→	56
5₀(79)	→	78
5₀(94)	→	95
5₀(40)	→	136
5₀(125)	→	121
5₀(54)	→	55
5₀(167)	→	165
5₀(66)	→	77
5₀(148)	→	149
5₀(171)	→	172
5₀(113)	→	114
5₀(2)	→	58
5₀(170)	→	171
5₀(27)	→	122
5₀(58)	→	153
5₀(29)	→	166
5₀(10)	→	13
5₀(13)	→	62
5₀(102)	→	100
5₀(106)	→	107
5₀(51)	→	98
5₀(154)	→	155
5₀(159)	→	160
f6₀	→	2
0₀(2)	→	3
0₀(56)	→	53
0₀(10)	→	11
0₀(49)	→	48
0₀(67)	→	63
0₀(99)	→	97
0₀(166)	→	167
0₀(30)	→	26
0₀(107)	→	103
0₀(25)	→	24
0₀(124)	→	125
0₀(61)	→	57
0₀(155)	→	156
0₀(3)	→	89
0₀(164)	→	161
0₀(17)	→	18
0₀(83)	→	80
0₀(66)	→	67
0₀(23)	→	19
0₀(32)	→	132
0₀(112)	→	113
0₀(130)	→	126
0₀(7)	→	1
0₀(52)	→	50
0₀(45)	→	42
0₀(129)	→	130
0₀(172)	→	168
0₀(20)	→	32
0₀(142)	→	143
0₀(41)	→	38
0₀(16)	→	51
0₀(109)	→	108
0₀(77)	→	76
0₀(13)	→	12
0₀(160)	→	157
0₀(69)	→	70