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

Proof

1 String Reversal

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

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

1.1 Bounds

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

final states:

{137, 133, 130, 125, 120, 114, 110, 109, 108, 107, 104, 101, 97, 93, 89, 86, 84, 83, 80, 77, 72, 71, 68, 66, 61, 56, 55, 50, 48, 45, 44, 42, 40, 37, 32, 31, 29, 24, 23, 21, 19, 16, 15, 10, 7, 1}

transitions:

89 → 73

89 → 25

97 → 62

97 → 33

15 → 25

133 → 11

50 → 62

50 → 33

37 → 11

110 → 90

110 → 62

110 → 33

130 → 11

40 → 115

101 → 25

44 → 115

86 → 115

86 → 25

109 → 11

16 → 25

114 → 11

93 → 11

77 → 25

104 → 25

42 → 11

137 → 11

83 → 11

48 → 25

68 → 25

56 → 62

56 → 33

2₀(35) → 46

2₀(53) → 54

2₀(3) → 4

2₀(129) → 125

2₀(98) → 99

2₀(21) → 71

2₀(8) → 22

2₀(135) → 136

2₀(52) → 53

2₀(134) → 135

2₀(128) → 129

2₀(64) → 65

2₀(113) → 110

2₀(27) → 28

2₀(75) → 76

2₀(76) → 72

2₀(13) → 14

2₀(5) → 38

2₀(4) → 8

2₀(117) → 118

2₀(124) → 120

2₀(28) → 24

2₀(116) → 117

2₀(139) → 140

2₀(22) → 30

2₀(122) → 123

2₀(57) → 58

2₀(34) → 35

2₀(54) → 50

2₀(12) → 13

2₀(38) → 85

3₀(2) → 25

3₀(78) → 79

3₀(6) → 15

3₀(58) → 78

3₀(88) → 86

3₀(4) → 17

3₀(136) → 133

3₀(46) → 49

3₀(140) → 141

3₀(70) → 68

3₀(8) → 102

3₀(11) → 73

3₀(92) → 89

3₀(99) → 100

3₀(17) → 18

3₀(118) → 119

3₀(90) → 91

3₀(96) → 93

3₀(30) → 29

3₀(5) → 105

0₀(33) → 34

0₀(126) → 134

0₀(26) → 27

0₀(123) → 124

0₀(14) → 10

0₀(63) → 64

0₀(58) → 59

0₀(51) → 52

0₀(35) → 36

0₀(8) → 20

0₀(34) → 98

0₀(112) → 113

0₀(105) → 106

0₀(11) → 12

0₀(46) → 47

0₀(3) → 57

0₀(121) → 122

0₀(111) → 112

0₀(9) → 7

0₀(127) → 128

0₀(115) → 116

0₀(74) → 75

0₀(62) → 63

0₀(5) → 87

0₀(2) → 3

0₀(4) → 5

0₀(138) → 139

4₀(25) → 26

4₀(17) → 81

4₀(100) → 97

4₀(5) → 69

4₀(94) → 95

4₀(11) → 51

4₀(60) → 56

4₀(6) → 67

4₀(9) → 31

4₀(3) → 62

4₀(102) → 103

4₀(57) → 90

4₀(95) → 96

4₀(126) → 127

4₀(51) → 111

4₀(2) → 33

4₀(73) → 74

5₀(131) → 132

5₀(87) → 88

5₀(60) → 107

5₀(65) → 61

5₀(46) → 55

5₀(5) → 41

5₀(11) → 126

5₀(38) → 39

5₀(43) → 44

5₀(2) → 115

5₀(41) → 40

5₀(103) → 101

5₀(8) → 43

5₀(33) → 138

5₀(47) → 45

5₀(106) → 104

5₀(67) → 108

f6₀ → 2

1₀(2) → 11

1₀(18) → 16

1₀(91) → 92

1₀(49) → 48

1₀(67) → 66

1₀(79) → 77

1₀(36) → 32

1₀(43) → 42

1₀(8) → 9

1₀(21) → 23

1₀(17) → 131

1₀(6) → 1

1₀(141) → 137

1₀(132) → 130

1₀(81) → 82

1₀(22) → 21

1₀(85) → 84

1₀(20) → 19

1₀(82) → 80

1₀(39) → 37

1₀(40) → 109

1₀(57) → 94

1₀(60) → 83

1₀(59) → 60

1₀(5) → 6

1₀(115) → 121

1₀(119) → 114

1₀(69) → 70

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