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

1.1 Bounds

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

final states:

{163, 159, 155, 150, 145, 143, 141, 138, 134, 129, 127, 125, 123, 119, 114, 109, 104, 100, 96, 94, 90, 88, 86, 80, 76, 71, 68, 64, 59, 56, 54, 52, 48, 47, 43, 38, 36, 33, 29, 23, 18, 17, 15, 13, 11, 7, 1}

transitions:

33 → 81

23 → 81

29 → 24

80 → 81

15 → 81

96 → 44

96 → 24

129 → 19

119 → 19

119 → 81

145 → 44

145 → 24

18 → 81

134 → 24

59 → 24

90 → 72

90 → 81

1 → 19

123 → 19

71 → 44

71 → 24

127 → 24

13 → 81

125 → 81

76 → 91

76 → 19

38 → 19

86 → 81

36 → 81

141 → 81

138 → 19

150 → 19

109 → 81

88 → 82

88 → 24

54 → 81

52 → 81

143 → 24

11 → 81

114 → 24

104 → 19

100 → 81

7 → 81

64 → 81

48 → 81

17 → 81

47 → 24

68 → 81

159 → 19

43 → 19

163 → 81

56 → 19

155 → 91

155 → 19

94 → 24

3₀(74) → 75

3₀(16) → 15

3₀(65) → 66

3₀(53) → 52

3₀(144) → 143

3₀(112) → 113

3₀(3) → 105

3₀(24) → 115

3₀(87) → 86

3₀(9) → 14

3₀(83) → 84

3₀(99) → 96

3₀(6) → 55

3₀(39) → 151

3₀(81) → 146

3₀(107) → 108

3₀(10) → 7

3₀(4) → 5

3₀(124) → 123

3₀(139) → 140

3₀(2) → 39

3₀(57) → 142

3₀(147) → 148

3₀(12) → 11

0₀(73) → 74

0₀(20) → 49

0₀(2) → 3

0₀(25) → 26

0₀(82) → 83

0₀(120) → 121

0₀(19) → 20

0₀(44) → 45

0₀(16) → 124

0₀(24) → 30

0₀(34) → 139

0₀(164) → 165

0₀(8) → 65

0₀(91) → 92

0₀(60) → 61

0₀(106) → 107

0₀(105) → 156

0₀(9) → 10

0₀(57) → 58

0₀(116) → 117

0₀(39) → 40

0₀(146) → 147

0₀(3) → 4

0₀(81) → 110

0₀(22) → 53

0₀(151) → 152

1₀(148) → 149

1₀(41) → 69

1₀(14) → 13

1₀(63) → 59

1₀(85) → 80

1₀(118) → 114

1₀(51) → 48

1₀(8) → 9

1₀(84) → 85

1₀(105) → 106

1₀(77) → 78

1₀(75) → 71

1₀(69) → 126

1₀(140) → 138

1₀(111) → 112

1₀(9) → 12

1₀(50) → 51

1₀(102) → 103

1₀(27) → 28

1₀(21) → 22

1₀(31) → 32

1₀(62) → 63

1₀(5) → 6

1₀(93) → 90

1₀(153) → 154

1₀(44) → 164

1₀(39) → 130

1₀(66) → 67

4₀(101) → 102

4₀(142) → 141

4₀(61) → 62

4₀(117) → 118

4₀(152) → 153

4₀(26) → 27

4₀(4) → 77

4₀(22) → 18

4₀(92) → 93

4₀(20) → 21

4₀(67) → 64

4₀(156) → 157

4₀(49) → 50

4₀(40) → 41

4₀(16) → 87

4₀(3) → 8

4₀(165) → 166

4₀(30) → 31

4₀(133) → 129

4₀(70) → 68

4₀(110) → 111

4₀(121) → 122

4₀(24) → 72

4₀(45) → 46

4₀(130) → 135

4₀(55) → 54

4₀(105) → 120

4₀(2) → 81

5₀(132) → 133

5₀(135) → 136

5₀(16) → 89

5₀(137) → 134

5₀(72) → 73

5₀(79) → 76

5₀(128) → 127

5₀(24) → 25

5₀(34) → 37

5₀(19) → 60

5₀(98) → 99

5₀(7) → 47

5₀(32) → 95

5₀(9) → 57

5₀(69) → 70

5₀(126) → 125

5₀(4) → 101

5₀(14) → 128

5₀(162) → 159

5₀(2) → 24

5₀(41) → 42

5₀(35) → 33

5₀(8) → 97

5₀(149) → 145

5₀(39) → 44

5₀(158) → 155

5₀(81) → 82

5₀(57) → 144

5₀(160) → 161

f6₀ → 2

2₀(2) → 19

2₀(157) → 158

2₀(46) → 43

2₀(28) → 23

2₀(9) → 16

2₀(105) → 160

2₀(95) → 94

2₀(166) → 163

2₀(113) → 109

2₀(30) → 91

2₀(131) → 132

2₀(8) → 34

2₀(37) → 36

2₀(89) → 88

2₀(6) → 1

2₀(14) → 17

2₀(136) → 137

2₀(32) → 29

2₀(161) → 162

2₀(130) → 131

2₀(103) → 100

2₀(42) → 38

2₀(97) → 98

2₀(154) → 150

2₀(108) → 104

2₀(34) → 35

2₀(78) → 79

2₀(58) → 56

2₀(115) → 116

2₀(122) → 119

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