0.00/0.17 YES 0.00/0.18 We consider the system theBenchmark. 0.00/0.18 0.00/0.18 Alphabet: 0.00/0.18 0.00/0.18 0 : [] --> a 0.00/0.18 eq : [a * a] --> c 0.00/0.18 false : [] --> c 0.00/0.18 fork : [b * a * b] --> b 0.00/0.18 if : [c * c * c] --> c 0.00/0.18 lt : [a * a] --> c 0.00/0.18 member : [a * b] --> c 0.00/0.18 null : [] --> b 0.00/0.18 s : [a] --> a 0.00/0.18 true : [] --> c 0.00/0.18 0.00/0.18 Rules: 0.00/0.18 0.00/0.18 lt(s(x), s(y)) => lt(x, y) 0.00/0.18 lt(0, s(x)) => true 0.00/0.18 lt(x, 0) => false 0.00/0.18 eq(x, x) => true 0.00/0.18 eq(s(x), 0) => false 0.00/0.18 eq(0, s(x)) => false 0.00/0.18 member(x, null) => false 0.00/0.18 member(x, fork(y, z, u)) => if(lt(x, z), member(x, y), if(eq(x, z), true, member(x, u))) 0.00/0.18 0.00/0.18 This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0). 0.00/0.18 0.00/0.18 We use rule removal, following [Kop12, Theorem 2.23]. 0.00/0.18 0.00/0.18 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0.00/0.18 0.00/0.18 lt(s(X), s(Y)) >? lt(X, Y) 0.00/0.18 lt(0, s(X)) >? true 0.00/0.18 lt(X, 0) >? false 0.00/0.18 eq(X, X) >? true 0.00/0.18 eq(s(X), 0) >? false 0.00/0.18 eq(0, s(X)) >? false 0.00/0.18 member(X, null) >? false 0.00/0.18 member(X, fork(Y, Z, U)) >? if(lt(X, Z), member(X, Y), if(eq(X, Z), true, member(X, U))) 0.00/0.18 0.00/0.18 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 0.00/0.18 0.00/0.18 Argument functions: 0.00/0.18 0.00/0.18 [[false]] = _|_ 0.00/0.18 [[true]] = _|_ 0.00/0.18 0.00/0.18 We choose Lex = {} and Mul = {0, eq, fork, if, lt, member, null, s}, and the following precedence: fork > null > s > eq = lt = member > 0 > if 0.00/0.18 0.00/0.18 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 0.00/0.18 0.00/0.18 lt(s(X), s(Y)) >= lt(X, Y) 0.00/0.18 lt(0, s(X)) >= _|_ 0.00/0.18 lt(X, 0) >= _|_ 0.00/0.18 eq(X, X) > _|_ 0.00/0.18 eq(s(X), 0) >= _|_ 0.00/0.18 eq(0, s(X)) >= _|_ 0.00/0.18 member(X, null) >= _|_ 0.00/0.18 member(X, fork(Y, Z, U)) > if(lt(X, Z), member(X, Y), if(eq(X, Z), _|_, member(X, U))) 0.00/0.18 0.00/0.18 With these choices, we have: 0.00/0.18 0.00/0.18 1] lt(s(X), s(Y)) >= lt(X, Y) because [2], by (Star) 0.00/0.18 2] lt*(s(X), s(Y)) >= lt(X, Y) because lt in Mul, [3] and [6], by (Stat) 0.00/0.18 3] s(X) >= X because [4], by (Star) 0.00/0.18 4] s*(X) >= X because [5], by (Select) 0.00/0.18 5] X >= X by (Meta) 0.00/0.18 6] s(Y) > Y because [7], by definition 0.00/0.18 7] s*(Y) >= Y because [8], by (Select) 0.00/0.18 8] Y >= Y by (Meta) 0.00/0.18 0.00/0.18 9] lt(0, s(X)) >= _|_ by (Bot) 0.00/0.18 0.00/0.18 10] lt(X, 0) >= _|_ by (Bot) 0.00/0.18 0.00/0.18 11] eq(X, X) > _|_ because [12], by definition 0.00/0.18 12] eq*(X, X) >= _|_ by (Bot) 0.00/0.18 0.00/0.18 13] eq(s(X), 0) >= _|_ by (Bot) 0.00/0.18 0.00/0.18 14] eq(0, s(X)) >= _|_ by (Bot) 0.00/0.18 0.00/0.18 15] member(X, null) >= _|_ by (Bot) 0.00/0.18 0.00/0.18 16] member(X, fork(Y, Z, U)) > if(lt(X, Z), member(X, Y), if(eq(X, Z), _|_, member(X, U))) because [17], by definition 0.00/0.18 17] member*(X, fork(Y, Z, U)) >= if(lt(X, Z), member(X, Y), if(eq(X, Z), _|_, member(X, U))) because member > if, [18], [23] and [27], by (Copy) 0.00/0.18 18] member*(X, fork(Y, Z, U)) >= lt(X, Z) because member = lt, member in Mul, [19] and [20], by (Stat) 0.00/0.18 19] X >= X by (Meta) 0.00/0.18 20] fork(Y, Z, U) > Z because [21], by definition 0.00/0.18 21] fork*(Y, Z, U) >= Z because [22], by (Select) 0.00/0.18 22] Z >= Z by (Meta) 0.00/0.18 23] member*(X, fork(Y, Z, U)) >= member(X, Y) because member in Mul, [19] and [24], by (Stat) 0.00/0.18 24] fork(Y, Z, U) > Y because [25], by definition 0.00/0.18 25] fork*(Y, Z, U) >= Y because [26], by (Select) 0.00/0.18 26] Y >= Y by (Meta) 0.00/0.18 27] member*(X, fork(Y, Z, U)) >= if(eq(X, Z), _|_, member(X, U)) because member > if, [28], [29] and [30], by (Copy) 0.00/0.18 28] member*(X, fork(Y, Z, U)) >= eq(X, Z) because member = eq, member in Mul, [19] and [20], by (Stat) 0.00/0.18 29] member*(X, fork(Y, Z, U)) >= _|_ by (Bot) 0.00/0.18 30] member*(X, fork(Y, Z, U)) >= member(X, U) because member in Mul, [19] and [31], by (Stat) 0.00/0.18 31] fork(Y, Z, U) > U because [32], by definition 0.00/0.18 32] fork*(Y, Z, U) >= U because [33], by (Select) 0.00/0.18 33] U >= U by (Meta) 0.00/0.18 0.00/0.18 We can thus remove the following rules: 0.00/0.18 0.00/0.18 eq(X, X) => true 0.00/0.18 member(X, fork(Y, Z, U)) => if(lt(X, Z), member(X, Y), if(eq(X, Z), true, member(X, U))) 0.00/0.18 0.00/0.18 We use rule removal, following [Kop12, Theorem 2.23]. 0.00/0.18 0.00/0.18 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0.00/0.18 0.00/0.18 lt(s(X), s(Y)) >? lt(X, Y) 0.00/0.18 lt(0, s(X)) >? true 0.00/0.18 lt(X, 0) >? false 0.00/0.18 eq(s(X), 0) >? false 0.00/0.18 eq(0, s(X)) >? false 0.00/0.18 member(X, null) >? false 0.00/0.18 0.00/0.18 We orient these requirements with a polynomial interpretation in the natural numbers. 0.00/0.18 0.00/0.18 The following interpretation satisfies the requirements: 0.00/0.18 0.00/0.18 0 = 3 0.00/0.18 eq = \y0y1.3 + 3y0 + 3y1 0.00/0.18 false = 0 0.00/0.18 lt = \y0y1.3 + y0 + y1 0.00/0.18 member = \y0y1.3 + y0 + 3y1 0.00/0.18 null = 3 0.00/0.18 s = \y0.3 + 3y0 0.00/0.18 true = 0 0.00/0.18 0.00/0.18 Using this interpretation, the requirements translate to: 0.00/0.18 0.00/0.18 [[lt(s(_x0), s(_x1))]] = 9 + 3x0 + 3x1 > 3 + x0 + x1 = [[lt(_x0, _x1)]] 0.00/0.18 [[lt(0, s(_x0))]] = 9 + 3x0 > 0 = [[true]] 0.00/0.18 [[lt(_x0, 0)]] = 6 + x0 > 0 = [[false]] 0.00/0.18 [[eq(s(_x0), 0)]] = 21 + 9x0 > 0 = [[false]] 0.00/0.18 [[eq(0, s(_x0))]] = 21 + 9x0 > 0 = [[false]] 0.00/0.18 [[member(_x0, null)]] = 12 + x0 > 0 = [[false]] 0.00/0.18 0.00/0.18 We can thus remove the following rules: 0.00/0.18 0.00/0.18 lt(s(X), s(Y)) => lt(X, Y) 0.00/0.18 lt(0, s(X)) => true 0.00/0.18 lt(X, 0) => false 0.00/0.18 eq(s(X), 0) => false 0.00/0.18 eq(0, s(X)) => false 0.00/0.18 member(X, null) => false 0.00/0.18 0.00/0.18 All rules were succesfully removed. Thus, termination of the original system has been reduced to termination of the beta-rule, which is well-known to hold. 0.00/0.18 0.00/0.18 0.00/0.18 +++ Citations +++ 0.00/0.18 0.00/0.18 [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. 0.00/0.18 EOF