0.00/0.32 YES 0.00/0.33 We consider the system theBenchmark. 0.00/0.33 0.00/0.33 Alphabet: 0.00/0.33 0.00/0.33 cons : [a * c] --> c 0.00/0.33 false : [] --> b 0.00/0.33 filter : [a -> b * c] --> c 0.00/0.33 if : [b * c * c] --> c 0.00/0.33 nil : [] --> c 0.00/0.33 true : [] --> b 0.00/0.33 0.00/0.33 Rules: 0.00/0.33 0.00/0.33 if(true, x, y) => x 0.00/0.33 if(false, x, y) => y 0.00/0.33 filter(f, nil) => nil 0.00/0.33 filter(f, cons(x, y)) => if(f x, cons(x, filter(f, y)), filter(f, y)) 0.00/0.33 0.00/0.33 This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0). 0.00/0.33 0.00/0.33 We use rule removal, following [Kop12, Theorem 2.23]. 0.00/0.33 0.00/0.33 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0.00/0.33 0.00/0.33 if(true, X, Y) >? X 0.00/0.33 if(false, X, Y) >? Y 0.00/0.33 filter(F, nil) >? nil 0.00/0.33 filter(F, cons(X, Y)) >? if(F X, cons(X, filter(F, Y)), filter(F, Y)) 0.00/0.33 0.00/0.33 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 0.00/0.33 0.00/0.33 Argument functions: 0.00/0.33 0.00/0.33 [[nil]] = _|_ 0.00/0.33 0.00/0.33 We choose Lex = {} and Mul = {@_{o -> o}, cons, false, filter, if, true}, and the following precedence: false > filter > @_{o -> o} > cons > if > true 0.00/0.33 0.00/0.33 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 0.00/0.33 0.00/0.33 if(true, X, Y) >= X 0.00/0.33 if(false, X, Y) >= Y 0.00/0.33 filter(F, _|_) > _|_ 0.00/0.33 filter(F, cons(X, Y)) >= if(@_{o -> o}(F, X), cons(X, filter(F, Y)), filter(F, Y)) 0.00/0.33 0.00/0.33 With these choices, we have: 0.00/0.33 0.00/0.33 1] if(true, X, Y) >= X because [2], by (Star) 0.00/0.33 2] if*(true, X, Y) >= X because [3], by (Select) 0.00/0.33 3] X >= X by (Meta) 0.00/0.33 0.00/0.33 4] if(false, X, Y) >= Y because [5], by (Star) 0.00/0.33 5] if*(false, X, Y) >= Y because [6], by (Select) 0.00/0.33 6] Y >= Y by (Meta) 0.00/0.33 0.00/0.33 7] filter(F, _|_) > _|_ because [8], by definition 0.00/0.33 8] filter*(F, _|_) >= _|_ by (Bot) 0.00/0.33 0.00/0.33 9] filter(F, cons(X, Y)) >= if(@_{o -> o}(F, X), cons(X, filter(F, Y)), filter(F, Y)) because [10], by (Star) 0.00/0.33 10] filter*(F, cons(X, Y)) >= if(@_{o -> o}(F, X), cons(X, filter(F, Y)), filter(F, Y)) because filter > if, [11], [18] and [19], by (Copy) 0.00/0.33 11] filter*(F, cons(X, Y)) >= @_{o -> o}(F, X) because filter > @_{o -> o}, [12] and [14], by (Copy) 0.00/0.33 12] filter*(F, cons(X, Y)) >= F because [13], by (Select) 0.00/0.33 13] F >= F by (Meta) 0.00/0.33 14] filter*(F, cons(X, Y)) >= X because [15], by (Select) 0.00/0.33 15] cons(X, Y) >= X because [16], by (Star) 0.00/0.33 16] cons*(X, Y) >= X because [17], by (Select) 0.00/0.33 17] X >= X by (Meta) 0.00/0.33 18] filter*(F, cons(X, Y)) >= cons(X, filter(F, Y)) because filter > cons, [14] and [19], by (Copy) 0.00/0.33 19] filter*(F, cons(X, Y)) >= filter(F, Y) because filter in Mul, [20] and [21], by (Stat) 0.00/0.33 20] F >= F by (Meta) 0.00/0.33 21] cons(X, Y) > Y because [22], by definition 0.00/0.33 22] cons*(X, Y) >= Y because [23], by (Select) 0.00/0.33 23] Y >= Y by (Meta) 0.00/0.33 0.00/0.33 We can thus remove the following rules: 0.00/0.33 0.00/0.33 filter(F, nil) => nil 0.00/0.33 0.00/0.33 We use rule removal, following [Kop12, Theorem 2.23]. 0.00/0.33 0.00/0.33 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0.00/0.33 0.00/0.33 if(true, X, Y) >? X 0.00/0.33 if(false, X, Y) >? Y 0.00/0.33 filter(F, cons(X, Y)) >? if(F X, cons(X, filter(F, Y)), filter(F, Y)) 0.00/0.33 0.00/0.33 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 0.00/0.33 0.00/0.33 We choose Lex = {} and Mul = {@_{o -> o}, cons, false, filter, if, true}, and the following precedence: false > filter > @_{o -> o} > if > cons > true 0.00/0.33 0.00/0.33 With these choices, we have: 0.00/0.33 0.00/0.33 1] if(true, X, Y) >= X because [2], by (Star) 0.00/0.33 2] if*(true, X, Y) >= X because [3], by (Select) 0.00/0.33 3] X >= X by (Meta) 0.00/0.33 0.00/0.33 4] if(false, X, Y) > Y because [5], by definition 0.00/0.33 5] if*(false, X, Y) >= Y because [6], by (Select) 0.00/0.33 6] Y >= Y by (Meta) 0.00/0.33 0.00/0.33 7] filter(F, cons(X, Y)) >= if(@_{o -> o}(F, X), cons(X, filter(F, Y)), filter(F, Y)) because [8], by (Star) 0.00/0.33 8] filter*(F, cons(X, Y)) >= if(@_{o -> o}(F, X), cons(X, filter(F, Y)), filter(F, Y)) because filter > if, [9], [16] and [17], by (Copy) 0.00/0.33 9] filter*(F, cons(X, Y)) >= @_{o -> o}(F, X) because filter > @_{o -> o}, [10] and [12], by (Copy) 0.00/0.33 10] filter*(F, cons(X, Y)) >= F because [11], by (Select) 0.00/0.33 11] F >= F by (Meta) 0.00/0.33 12] filter*(F, cons(X, Y)) >= X because [13], by (Select) 0.00/0.33 13] cons(X, Y) >= X because [14], by (Star) 0.00/0.33 14] cons*(X, Y) >= X because [15], by (Select) 0.00/0.33 15] X >= X by (Meta) 0.00/0.33 16] filter*(F, cons(X, Y)) >= cons(X, filter(F, Y)) because filter > cons, [12] and [17], by (Copy) 0.00/0.33 17] filter*(F, cons(X, Y)) >= filter(F, Y) because filter in Mul, [18] and [19], by (Stat) 0.00/0.33 18] F >= F by (Meta) 0.00/0.33 19] cons(X, Y) > Y because [20], by definition 0.00/0.33 20] cons*(X, Y) >= Y because [21], by (Select) 0.00/0.33 21] Y >= Y by (Meta) 0.00/0.33 0.00/0.33 We can thus remove the following rules: 0.00/0.33 0.00/0.33 if(false, X, Y) => Y 0.00/0.33 0.00/0.33 We use rule removal, following [Kop12, Theorem 2.23]. 0.00/0.33 0.00/0.33 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 0.00/0.33 0.00/0.33 if(true, X, Y) >? X 0.00/0.33 filter(F, cons(X, Y)) >? if(F X, cons(X, filter(F, Y)), filter(F, Y)) 0.00/0.33 0.00/0.33 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 0.00/0.33 0.00/0.33 We choose Lex = {} and Mul = {@_{o -> o}, cons, filter, if, true}, and the following precedence: filter > @_{o -> o} > if > cons > true 0.00/0.33 0.00/0.33 With these choices, we have: 0.00/0.33 0.00/0.33 1] if(true, X, Y) > X because [2], by definition 0.00/0.33 2] if*(true, X, Y) >= X because [3], by (Select) 0.00/0.33 3] X >= X by (Meta) 0.00/0.33 0.00/0.33 4] filter(F, cons(X, Y)) > if(@_{o -> o}(F, X), cons(X, filter(F, Y)), filter(F, Y)) because [5], by definition 0.00/0.33 5] filter*(F, cons(X, Y)) >= if(@_{o -> o}(F, X), cons(X, filter(F, Y)), filter(F, Y)) because filter > if, [6], [13] and [14], by (Copy) 0.00/0.33 6] filter*(F, cons(X, Y)) >= @_{o -> o}(F, X) because filter > @_{o -> o}, [7] and [9], by (Copy) 0.00/0.33 7] filter*(F, cons(X, Y)) >= F because [8], by (Select) 0.00/0.33 8] F >= F by (Meta) 0.00/0.33 9] filter*(F, cons(X, Y)) >= X because [10], by (Select) 0.00/0.33 10] cons(X, Y) >= X because [11], by (Star) 0.00/0.33 11] cons*(X, Y) >= X because [12], by (Select) 0.00/0.33 12] X >= X by (Meta) 0.00/0.33 13] filter*(F, cons(X, Y)) >= cons(X, filter(F, Y)) because filter > cons, [9] and [14], by (Copy) 0.00/0.33 14] filter*(F, cons(X, Y)) >= filter(F, Y) because filter in Mul, [15] and [16], by (Stat) 0.00/0.33 15] F >= F by (Meta) 0.00/0.33 16] cons(X, Y) > Y because [17], by definition 0.00/0.33 17] cons*(X, Y) >= Y because [18], by (Select) 0.00/0.33 18] Y >= Y by (Meta) 0.00/0.33 0.00/0.33 We can thus remove the following rules: 0.00/0.33 0.00/0.33 if(true, X, Y) => X 0.00/0.33 filter(F, cons(X, Y)) => if(F X, cons(X, filter(F, Y)), filter(F, Y)) 0.00/0.33 0.00/0.33 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.33 0.00/0.33 0.00/0.33 +++ Citations +++ 0.00/0.33 0.00/0.33 [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. 0.00/0.33 EOF