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

Proof

1 String Reversal

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

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

1.1 Bounds

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

final states:

{156, 151, 149, 145, 140, 136, 133, 132, 128, 124, 121, 116, 115, 110, 105, 102, 100, 96, 91, 88, 84, 80, 77, 72, 68, 62, 57, 54, 52, 51, 50, 46, 43, 39, 38, 34, 29, 28, 26, 22, 17, 12, 11, 9, 8, 6, 1}

transitions:

102 → 30

29 → 40

29 → 30

128 → 23

128 → 3

80 → 30

51 → 3

96 → 97

96 → 14

96 → 3

84 → 30

136 → 30

149 → 142

149 → 47

149 → 3

145 → 47

145 → 3

133 → 30

39 → 30

50 → 30

57 → 40

57 → 30

9 → 23

9 → 3

9 → 141

110 → 30

34 → 141

34 → 3

62 → 141

62 → 3

1 → 23

1 → 3

8 → 23

8 → 3

26 → 13

91 → 97

91 → 14

91 → 3

72 → 111

72 → 63

121 → 30

6 → 23

6 → 3

116 → 13

88 → 30

54 → 23

54 → 3

52 → 13

22 → 23

22 → 3

105 → 30

124 → 23

124 → 3

11 → 23

11 → 3

28 → 30

28 → 13

106 → 164

12 → 23

12 → 3

169 → 124

77 → 30

140 → 23

140 → 3

100 → 30

46 → 13

35 → 141

35 → 3

17 → 23

17 → 3

68 → 13

132 → 30

43 → 30

151 → 3

156 → 3

f6₀ → 2

5₀(64) → 146

5₀(59) → 60

5₀(87) → 84

5₀(139) → 136

5₀(34) → 115

5₀(46) → 132

5₀(69) → 70

5₀(76) → 72

5₀(14) → 81

5₀(63) → 152

5₀(2) → 30

5₀(3) → 40

5₀(122) → 157

5₀(1) → 28

5₀(103) → 104

5₀(29) → 50

5₀(78) → 79

5₀(101) → 100

5₀(106) → 107

2₁(165) → 166

2₁(164) → 165

0₀(1) → 27

0₀(41) → 53

0₀(63) → 92

0₀(144) → 140

0₀(147) → 148

0₀(85) → 86

0₀(7) → 6

0₀(58) → 69

0₀(99) → 96

0₀(56) → 54

0₀(90) → 88

0₀(36) → 37

0₀(18) → 19

0₀(82) → 83

0₀(64) → 65

0₀(94) → 95

0₀(127) → 124

0₀(15) → 16

0₀(74) → 75

0₀(31) → 32

0₀(48) → 49

0₀(119) → 120

0₀(10) → 9

0₀(2) → 13

0₀(4) → 5

0₀(24) → 25

0₀(44) → 89

0₀(138) → 139

1₀(130) → 131

1₀(35) → 36

1₀(67) → 62

1₀(73) → 74

1₀(92) → 93

1₀(30) → 31

1₀(112) → 113

1₀(3) → 4

1₀(45) → 43

1₀(125) → 126

1₀(142) → 143

1₀(60) → 61

1₀(71) → 68

1₀(15) → 55

1₀(42) → 39

1₀(97) → 98

1₀(13) → 58

1₀(81) → 82

1₀(107) → 134

1₀(63) → 64

1₀(117) → 137

1₀(14) → 15

1₀(47) → 48

1₀(40) → 41

1₀(2) → 18

1₀(23) → 24

1₀(20) → 21

1₀(104) → 102

1₀(152) → 153

3₁(168) → 169

2₀(109) → 105

2₀(2) → 3

2₀(45) → 51

2₀(21) → 17

2₀(95) → 91

2₀(155) → 151

2₀(129) → 130

2₀(157) → 156

2₀(44) → 45

2₀(85) → 103

2₀(150) → 149

2₀(89) → 90

2₀(114) → 110

2₀(123) → 121

2₀(61) → 57

2₀(106) → 125

2₀(141) → 142

2₀(126) → 127

2₀(135) → 133

2₀(92) → 97

2₀(18) → 23

2₀(64) → 129

2₀(13) → 14

2₀(148) → 145

2₀(118) → 119

2₀(79) → 77

2₀(63) → 141

2₀(66) → 67

2₀(33) → 29

2₀(146) → 147

2₀(86) → 87

2₀(3) → 47

2₀(30) → 117

2₀(122) → 123

3₀(18) → 106

3₀(65) → 66

3₀(134) → 135

3₀(49) → 46

3₀(98) → 99

3₀(19) → 85

3₀(113) → 114

3₀(55) → 56

3₀(131) → 128

3₀(25) → 22

3₀(4) → 7

3₀(37) → 34

3₀(83) → 80

3₀(53) → 52

3₀(32) → 33

3₀(137) → 138

3₀(27) → 26

3₀(93) → 94

3₀(75) → 76

3₀(120) → 116

3₀(143) → 144

3₀(16) → 12

3₀(31) → 44

3₀(58) → 59

3₀(5) → 1

3₀(153) → 154

0₁(167) → 168

1₁(166) → 167

4₀(19) → 20

4₀(108) → 109

4₀(117) → 118

4₀(44) → 122

4₀(59) → 78

4₀(7) → 10

4₀(6) → 8

4₀(41) → 42

4₀(107) → 108

4₀(9) → 11

4₀(154) → 155

4₀(3) → 35

4₀(30) → 111

4₀(70) → 71

4₀(18) → 73

4₀(45) → 150

4₀(33) → 101

4₀(12) → 38

4₀(111) → 112

4₀(2) → 63

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