YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 String Reversal

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

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

1.1 Bounds

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

final states:

{112, 107, 103, 98, 92, 87, 83, 77, 73, 68, 65, 60, 54, 50, 45, 42, 36, 32, 27, 23, 19, 13, 8, 1}

transitions:

23 → 78

32 → 3

87 → 3

103 → 9

103 → 55

98 → 37

129 → 24

129 → 56

145 → 124

50 → 37

65 → 4

65 → 14

65 → 124

107 → 93

1 → 93

8 → 93

13 → 93

60 → 4

60 → 14

60 → 124

73 → 93

36 → 78

54 → 3

105 → 144

143 → 15

2 → 123

45 → 78

63 → 137

112 → 93

77 → 4

77 → 14

77 → 124

42 → 78

83 → 37

68 → 93

92 → 37

19 → 15

19 → 14

19 → 124

27 → 56

27 → 93

f6₀ → 2

5₀(55) → 88

5₀(95) → 96

5₀(61) → 62

5₀(14) → 28

5₀(2) → 37

5₀(44) → 42

5₀(102) → 98

5₀(15) → 16

5₀(57) → 66

1₁(142) → 143

1₁(140) → 141

1₁(141) → 142

1₁(144) → 145

1₁(123) → 124

0₁(137) → 138

2₀(106) → 103

2₀(86) → 83

2₀(84) → 85

2₀(109) → 110

2₀(88) → 89

2₀(28) → 104

2₀(3) → 9

2₀(69) → 70

2₀(9) → 20

2₀(53) → 50

2₀(48) → 49

2₀(5) → 6

2₀(93) → 99

2₀(2) → 55

2₀(4) → 33

2₀(66) → 67

2₀(16) → 17

2₁(138) → 139

2₁(139) → 140

4₀(31) → 27

4₀(74) → 75

4₀(115) → 112

4₀(30) → 31

4₀(37) → 46

4₀(41) → 36

4₀(25) → 26

4₀(58) → 59

4₀(26) → 23

4₀(111) → 107

4₀(18) → 13

4₀(9) → 24

4₀(59) → 54

4₀(79) → 80

4₀(94) → 95

4₀(110) → 111

4₀(71) → 72

4₀(15) → 51

4₀(55) → 56

4₀(97) → 92

4₀(81) → 82

4₀(10) → 11

4₀(4) → 5

4₀(28) → 29

4₀(40) → 41

4₀(2) → 93

4₀(57) → 58

4₀(100) → 101

4₀(12) → 8

4₀(38) → 39

4₁(125) → 126

4₁(127) → 128

4₁(128) → 129

1₀(20) → 21

1₀(2) → 14

1₀(78) → 79

1₀(82) → 77

1₀(21) → 22

1₀(28) → 113

1₀(37) → 38

1₀(76) → 73

1₀(70) → 71

1₀(89) → 90

1₀(91) → 87

1₀(55) → 61

1₀(9) → 10

1₀(99) → 100

1₀(93) → 94

1₀(14) → 15

1₀(56) → 74

1₀(64) → 60

1₀(62) → 63

1₀(90) → 91

1₀(39) → 40

1₀(33) → 34

1₀(3) → 4

1₀(10) → 43

1₀(104) → 105

1₀(96) → 97

1₀(22) → 19

3₀(2) → 78

3₀(51) → 52

3₀(114) → 115

3₀(56) → 57

3₀(49) → 45

3₀(67) → 65

3₀(80) → 81

3₀(24) → 25

3₀(17) → 18

3₀(11) → 12

3₀(6) → 7

3₀(29) → 30

3₀(7) → 1

3₀(52) → 53

3₀(35) → 32

3₀(101) → 102

3₀(75) → 76

3₀(85) → 86

3₀(108) → 109

3₀(72) → 68

3₀(47) → 48

3₁(126) → 127

5₁(124) → 125

0₀(46) → 47

0₀(63) → 64

0₀(43) → 44

0₀(14) → 108

0₀(34) → 35

0₀(79) → 84

0₀(55) → 69

0₀(105) → 106

0₀(2) → 3

0₀(113) → 114

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