YES Termination Proof

Termination Proof

by ttt2 (version ttt2 1.15)

Input

The rewrite relation of the following TRS is considered.

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

Proof

1 String Reversal

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

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

1.1 Bounds

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

final states:

{122, 113, 103, 94, 85, 76, 67, 58, 48, 42, 32, 22, 12, 1}

transitions:

32 → 23

103 → 34

103 → 49

122 → 114

122 → 104

1 → 104

76 → 96

76 → 104

58 → 13

22 → 104

67 → 96

67 → 104

12 → 34

12 → 49

85 → 13

113 → 49

42 → 86

42 → 33

48 → 34

48 → 49

94 → 49

5₀(130) → 122

5₀(46) → 47

5₀(92) → 93

5₀(41) → 32

5₀(93) → 85

5₀(29) → 30

5₀(108) → 109

5₀(9) → 10

5₀(59) → 60

5₀(84) → 76

5₀(109) → 110

5₀(62) → 63

5₀(55) → 56

5₀(2) → 23

5₀(23) → 95

5₀(100) → 101

5₀(54) → 55

5₀(38) → 39

4₀(2) → 33

4₀(120) → 121

4₀(16) → 17

4₀(28) → 29

4₀(24) → 25

4₀(47) → 42

4₀(8) → 9

4₀(114) → 115

4₀(14) → 15

4₀(27) → 28

4₀(23) → 86

4₀(97) → 98

4₀(121) → 113

4₀(33) → 68

4₀(81) → 82

1₀(106) → 107

1₀(23) → 24

1₀(123) → 124

1₀(37) → 38

1₀(35) → 36

1₀(34) → 35

1₀(107) → 108

1₀(56) → 57

1₀(36) → 37

1₀(82) → 83

1₀(3) → 123

1₀(104) → 105

1₀(111) → 112

1₀(96) → 97

1₀(128) → 129

1₀(83) → 84

1₀(102) → 94

1₀(15) → 16

1₀(20) → 21

1₀(13) → 14

1₀(21) → 12

1₀(31) → 22

1₀(5) → 6

1₀(10) → 11

1₀(2) → 3

0₀(19) → 20

0₀(125) → 126

0₀(17) → 18

0₀(101) → 102

0₀(112) → 103

0₀(99) → 100

0₀(61) → 62

0₀(86) → 87

0₀(98) → 99

0₀(50) → 51

0₀(69) → 70

0₀(124) → 125

0₀(26) → 27

0₀(4) → 5

0₀(7) → 8

0₀(13) → 59

0₀(116) → 117

0₀(3) → 4

0₀(57) → 48

0₀(95) → 96

0₀(79) → 80

0₀(33) → 114

0₀(68) → 69

0₀(115) → 116

0₀(2) → 104

3₀(90) → 91

3₀(70) → 71

3₀(16) → 43

3₀(87) → 88

3₀(65) → 66

3₀(53) → 54

3₀(88) → 89

3₀(72) → 73

3₀(18) → 19

3₀(40) → 41

3₀(6) → 7

3₀(126) → 127

3₀(119) → 120

3₀(71) → 72

3₀(127) → 128

3₀(49) → 50

3₀(43) → 44

3₀(89) → 90

3₀(2) → 49

3₀(75) → 67

3₀(78) → 79

3₀(33) → 34

3₀(39) → 40

3₀(51) → 52

3₀(25) → 26

f6₀ → 2

2₀(2) → 13

2₀(117) → 118

2₀(91) → 92

2₀(105) → 106

2₀(110) → 111

2₀(64) → 65

2₀(80) → 81

2₀(30) → 31

2₀(63) → 64

2₀(74) → 75

2₀(11) → 1

2₀(118) → 119

2₀(66) → 58

2₀(33) → 77

2₀(52) → 53

2₀(45) → 46

2₀(129) → 130

2₀(73) → 74

2₀(60) → 61

2₀(44) → 45

2₀(77) → 78

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