0.47/1.20	YES
0.51/1.23	We consider the system theBenchmark.
0.51/1.23	
0.51/1.23	  Alphabet:
0.51/1.23	
0.51/1.23	    0 : [] --> a 
0.51/1.23	    add : [a * a] --> a 
0.51/1.23	    fact : [] --> a -> a 
0.51/1.23	    mult : [] --> a -> a -> a 
0.51/1.23	    rec : [a -> a -> a * a] --> a -> a 
0.51/1.23	    s : [a] --> a 
0.51/1.23	
0.51/1.23	  Rules:
0.51/1.23	
0.51/1.23	    add(0, x) => x 
0.51/1.23	    add(s(x), y) => s(add(x, y)) 
0.51/1.23	    mult 0 x => 0 
0.51/1.23	    mult s(x) y => add(mult x y, y) 
0.51/1.23	    rec(f, x) 0 => x 
0.51/1.23	    rec(f, x) s(y) => f s(y) (rec(f, x) y) 
0.51/1.23	    fact => rec(mult, s(0)) 
0.51/1.23	
0.51/1.23	This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0).
0.51/1.23	
0.51/1.23	We use rule removal, following [Kop12, Theorem 2.23].
0.51/1.23	
0.51/1.23	This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]):
0.51/1.23	
0.51/1.23	  add(0, X) >? X 
0.51/1.23	  add(s(X), Y) >? s(add(X, Y)) 
0.51/1.23	  mult 0 X >? 0 
0.51/1.23	  mult s(X) Y >? add(mult X Y, Y) 
0.51/1.23	  rec(F, X) 0 >? X 
0.51/1.23	  rec(F, X) s(Y) >? F s(Y) (rec(F, X) Y) 
0.51/1.23	  fact >? rec(mult, s(0)) 
0.51/1.23	
0.51/1.23	We use a recursive path ordering as defined in [Kop12, Chapter 5].
0.51/1.23	
0.51/1.23	Argument functions:
0.51/1.23	
0.51/1.23	  [[0]] = _|_ 
0.51/1.23	
0.51/1.23	We choose Lex = {} and Mul = {@_{o -> o -> o}, @_{o -> o}, add, fact, mult, rec, s}, and the following precedence: fact > mult > add > rec > @_{o -> o -> o} > @_{o -> o} > s
0.51/1.23	
0.51/1.23	Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows:
0.51/1.23	
0.51/1.23	  add(_|_, X) > X 
0.51/1.23	  add(s(X), Y) >= s(add(X, Y)) 
0.51/1.23	  @_{o -> o}(@_{o -> o -> o}(mult, _|_), X) >= _|_ 
0.51/1.23	  @_{o -> o}(@_{o -> o -> o}(mult, s(X)), Y) > add(@_{o -> o}(@_{o -> o -> o}(mult, X), Y), Y) 
0.51/1.23	  @_{o -> o}(rec(F, X), _|_) >= X 
0.51/1.23	  @_{o -> o}(rec(F, X), s(Y)) > @_{o -> o}(@_{o -> o -> o}(F, s(Y)), @_{o -> o}(rec(F, X), Y)) 
0.51/1.23	  fact >= rec(mult, s(_|_)) 
0.51/1.23	
0.51/1.23	With these choices, we have:
0.51/1.23	
0.51/1.23	  1] add(_|_, X) > X  because [2], by definition 
0.51/1.23	  2] add*(_|_, X) >= X  because [3], by (Select) 
0.51/1.23	  3] X >= X  by (Meta) 
0.51/1.23	
0.51/1.23	  4] add(s(X), Y) >= s(add(X, Y))  because [5], by (Star) 
0.51/1.23	  5] add*(s(X), Y) >= s(add(X, Y))  because add > s and [6], by (Copy) 
0.51/1.23	  6] add*(s(X), Y) >= add(X, Y)  because add in Mul, [7] and [10], by (Stat) 
0.51/1.23	  7] s(X) > X  because [8], by definition 
0.51/1.23	  8] s*(X) >= X  because [9], by (Select) 
0.51/1.23	  9] X >= X  by (Meta) 
0.51/1.23	  10] Y >= Y  by (Meta) 
0.51/1.23	
0.51/1.23	  11] @_{o -> o}(@_{o -> o -> o}(mult, _|_), X) >= _|_  by (Bot) 
0.51/1.23	
0.51/1.23	  12] @_{o -> o}(@_{o -> o -> o}(mult, s(X)), Y) > add(@_{o -> o}(@_{o -> o -> o}(mult, X), Y), Y)  because [13], by definition 
0.51/1.23	  13] @_{o -> o}*(@_{o -> o -> o}(mult, s(X)), Y) >= add(@_{o -> o}(@_{o -> o -> o}(mult, X), Y), Y)  because [14], by (Select) 
0.51/1.23	  14] @_{o -> o -> o}(mult, s(X)) @_{o -> o}*(@_{o -> o -> o}(mult, s(X)), Y) >= add(@_{o -> o}(@_{o -> o -> o}(mult, X), Y), Y)  because [15] 
0.51/1.23	  15] @_{o -> o -> o}*(mult, s(X), @_{o -> o}*(@_{o -> o -> o}(mult, s(X)), Y)) >= add(@_{o -> o}(@_{o -> o -> o}(mult, X), Y), Y)  because [16], by (Select) 
0.51/1.23	  16] mult @_{o -> o -> o}*(mult, s(X), @_{o -> o}*(@_{o -> o -> o}(mult, s(X)), Y)) @_{o -> o -> o}*(mult, s(X), @_{o -> o}*(@_{o -> o -> o}(mult, s(X)), Y)) >= add(@_{o -> o}(@_{o -> o -> o}(mult, X), Y), Y)  because [17] 
0.51/1.23	  17] mult*(@_{o -> o -> o}*(mult, s(X), @_{o -> o}*(@_{o -> o -> o}(mult, s(X)), Y)), @_{o -> o -> o}*(mult, s(X), @_{o -> o}*(@_{o -> o -> o}(mult, s(X)), Y))) >= add(@_{o -> o}(@_{o -> o -> o}(mult, X), Y), Y)  because mult > add, [18] and [28], by (Copy) 
0.51/1.23	  18] mult*(@_{o -> o -> o}*(mult, s(X), @_{o -> o}*(@_{o -> o -> o}(mult, s(X)), Y)), @_{o -> o -> o}*(mult, s(X), @_{o -> o}*(@_{o -> o -> o}(mult, s(X)), Y))) >= @_{o -> o}(@_{o -> o -> o}(mult, X), Y)  because [19], by (Select) 
0.51/1.23	  19] @_{o -> o -> o}*(mult, s(X), @_{o -> o}*(@_{o -> o -> o}(mult, s(X)), Y)) >= @_{o -> o}(@_{o -> o -> o}(mult, X), Y)  because [20], by (Select) 
0.51/1.23	  20] @_{o -> o}*(@_{o -> o -> o}(mult, s(X)), Y) >= @_{o -> o}(@_{o -> o -> o}(mult, X), Y)  because @_{o -> o} in Mul, [21] and [27], by (Stat) 
0.51/1.23	  21] @_{o -> o -> o}(mult, s(X)) > @_{o -> o -> o}(mult, X)  because [22], by definition 
0.51/1.23	  22] @_{o -> o -> o}*(mult, s(X)) >= @_{o -> o -> o}(mult, X)  because @_{o -> o -> o} in Mul, [23] and [24], by (Stat) 
0.51/1.23	  23] mult >= mult  by (Fun) 
0.51/1.23	  24] s(X) > X  because [25], by definition 
0.51/1.23	  25] s*(X) >= X  because [26], by (Select) 
0.51/1.23	  26] X >= X  by (Meta) 
0.51/1.23	  27] Y >= Y  by (Meta) 
0.51/1.23	  28] mult*(@_{o -> o -> o}*(mult, s(X), @_{o -> o}*(@_{o -> o -> o}(mult, s(X)), Y)), @_{o -> o -> o}*(mult, s(X), @_{o -> o}*(@_{o -> o -> o}(mult, s(X)), Y))) >= Y  because [29], by (Select) 
0.51/1.23	  29] @_{o -> o -> o}*(mult, s(X), @_{o -> o}*(@_{o -> o -> o}(mult, s(X)), Y)) >= Y  because [30], by (Select) 
0.51/1.23	  30] @_{o -> o}*(@_{o -> o -> o}(mult, s(X)), Y) >= Y  because [27], by (Select) 
0.51/1.23	
0.51/1.23	  31] @_{o -> o}(rec(F, X), _|_) >= X  because [32], by (Star) 
0.51/1.23	  32] @_{o -> o}*(rec(F, X), _|_) >= X  because [33], by (Select) 
0.51/1.23	  33] rec(F, X) @_{o -> o}*(rec(F, X), _|_) >= X  because [34] 
0.51/1.23	  34] rec*(F, X, @_{o -> o}*(rec(F, X), _|_)) >= X  because [35], by (Select) 
0.51/1.23	  35] X >= X  by (Meta) 
0.51/1.23	
0.51/1.23	  36] @_{o -> o}(rec(F, X), s(Y)) > @_{o -> o}(@_{o -> o -> o}(F, s(Y)), @_{o -> o}(rec(F, X), Y))  because [37], by definition 
0.51/1.23	  37] @_{o -> o}*(rec(F, X), s(Y)) >= @_{o -> o}(@_{o -> o -> o}(F, s(Y)), @_{o -> o}(rec(F, X), Y))  because [38], by (Select) 
0.51/1.23	  38] rec(F, X) @_{o -> o}*(rec(F, X), s(Y)) >= @_{o -> o}(@_{o -> o -> o}(F, s(Y)), @_{o -> o}(rec(F, X), Y))  because [39] 
0.51/1.23	  39] rec*(F, X, @_{o -> o}*(rec(F, X), s(Y))) >= @_{o -> o}(@_{o -> o -> o}(F, s(Y)), @_{o -> o}(rec(F, X), Y))  because rec > @_{o -> o}, [40] and [49], by (Copy) 
0.51/1.23	  40] rec*(F, X, @_{o -> o}*(rec(F, X), s(Y))) >= @_{o -> o -> o}(F, s(Y))  because rec > @_{o -> o -> o}, [41] and [43], by (Copy) 
0.51/1.23	  41] rec*(F, X, @_{o -> o}*(rec(F, X), s(Y))) >= F  because [42], by (Select) 
0.51/1.23	  42] F >= F  by (Meta) 
0.51/1.23	  43] rec*(F, X, @_{o -> o}*(rec(F, X), s(Y))) >= s(Y)  because rec > s and [44], by (Copy) 
0.51/1.23	  44] rec*(F, X, @_{o -> o}*(rec(F, X), s(Y))) >= Y  because [45], by (Select) 
0.51/1.23	  45] @_{o -> o}*(rec(F, X), s(Y)) >= Y  because [46], by (Select) 
0.51/1.23	  46] s(Y) >= Y  because [47], by (Star) 
0.51/1.23	  47] s*(Y) >= Y  because [48], by (Select) 
0.51/1.23	  48] Y >= Y  by (Meta) 
0.51/1.23	  49] rec*(F, X, @_{o -> o}*(rec(F, X), s(Y))) >= @_{o -> o}(rec(F, X), Y)  because [50], by (Select) 
0.51/1.23	  50] @_{o -> o}*(rec(F, X), s(Y)) >= @_{o -> o}(rec(F, X), Y)  because @_{o -> o} in Mul, [51] and [54], by (Stat) 
0.51/1.23	  51] rec(F, X) >= rec(F, X)  because rec in Mul, [52] and [53], by (Fun) 
0.51/1.23	  52] F >= F  by (Meta) 
0.51/1.23	  53] X >= X  by (Meta) 
0.51/1.23	  54] s(Y) > Y  because [55], by definition 
0.51/1.23	  55] s*(Y) >= Y  because [48], by (Select) 
0.51/1.23	
0.51/1.23	  56] fact >= rec(mult, s(_|_))  because [57], by (Star) 
0.51/1.23	  57] fact* >= rec(mult, s(_|_))  because fact > rec, [58] and [59], by (Copy) 
0.51/1.23	  58] fact* >= mult  because fact > mult, by (Copy) 
0.51/1.23	  59] fact* >= s(_|_)  because fact > s and [60], by (Copy) 
0.51/1.23	  60] fact* >= _|_  by (Bot) 
0.51/1.23	
0.51/1.23	We can thus remove the following rules:
0.51/1.23	
0.51/1.23	  add(0, X) => X 
0.51/1.23	  mult s(X) Y => add(mult X Y, Y) 
0.51/1.23	  rec(F, X) s(Y) => F s(Y) (rec(F, X) Y) 
0.51/1.23	
0.51/1.23	We use rule removal, following [Kop12, Theorem 2.23].
0.51/1.23	
0.51/1.23	This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]):
0.51/1.23	
0.51/1.23	  add(s(X), Y) >? s(add(X, Y)) 
0.51/1.23	  mult 0 X >? 0 
0.51/1.23	  rec(F, X) 0 >? X 
0.51/1.23	  fact >? rec(mult, s(0)) 
0.51/1.23	
0.51/1.23	We orient these requirements with a polynomial interpretation in the natural numbers.
0.51/1.23	
0.51/1.23	The following interpretation satisfies the requirements:
0.51/1.23	
0.51/1.23	  0 = 0 
0.51/1.23	  add = \y0y1.y1 + 3y0 
0.51/1.23	  fact = \y0.3 + 3y0 
0.51/1.23	  mult = \y0y1.0 
0.51/1.23	  rec = \G0y1y2.y1 + G0(0,0) 
0.51/1.23	  s = \y0.y0 
0.51/1.23	
0.51/1.23	Using this interpretation, the requirements translate to:
0.51/1.23	
0.51/1.23	  [[add(s(_x0), _x1)]] = x1 + 3x0 >= x1 + 3x0 = [[s(add(_x0, _x1))]] 
0.51/1.23	  [[mult 0 _x0]] = x0 >= 0 = [[0]] 
0.51/1.23	  [[rec(_F0, _x1) 0]] = x1 + F0(0,0) >= x1 = [[_x1]] 
0.51/1.23	  [[fact]] = \y0.3 + 3y0 > \y0.0 = [[rec(mult, s(0))]] 
0.51/1.23	
0.51/1.23	We can thus remove the following rules:
0.51/1.23	
0.51/1.23	  fact => rec(mult, s(0)) 
0.51/1.23	
0.51/1.23	We use rule removal, following [Kop12, Theorem 2.23].
0.51/1.23	
0.51/1.23	This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]):
0.51/1.23	
0.51/1.23	  add(s(X), Y) >? s(add(X, Y)) 
0.51/1.23	  mult(0, X) >? 0 
0.51/1.23	  rec(F, X, 0) >? X 
0.51/1.23	
0.51/1.23	We orient these requirements with a polynomial interpretation in the natural numbers.
0.51/1.23	
0.51/1.23	The following interpretation satisfies the requirements:
0.51/1.23	
0.51/1.23	  0 = 0 
0.51/1.23	  add = \y0y1.y1 + 3y0 
0.51/1.23	  mult = \y0y1.3 + y1 + 3y0 
0.51/1.23	  rec = \G0y1y2.3 + y1 + y2 + G0(0,0) 
0.51/1.23	  s = \y0.3 + y0 
0.51/1.23	
0.51/1.23	Using this interpretation, the requirements translate to:
0.51/1.23	
0.51/1.23	  [[add(s(_x0), _x1)]] = 9 + x1 + 3x0 > 3 + x1 + 3x0 = [[s(add(_x0, _x1))]] 
0.51/1.23	  [[mult(0, _x0)]] = 3 + x0 > 0 = [[0]] 
0.51/1.23	  [[rec(_F0, _x1, 0)]] = 3 + x1 + F0(0,0) > x1 = [[_x1]] 
0.51/1.23	
0.51/1.23	We can thus remove the following rules:
0.51/1.23	
0.51/1.23	  add(s(X), Y) => s(add(X, Y)) 
0.51/1.23	  mult(0, X) => 0 
0.51/1.23	  rec(F, X, 0) => X 
0.51/1.23	
0.51/1.23	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.51/1.23	
0.51/1.23	
0.51/1.23	+++ Citations +++
0.51/1.23	
0.51/1.23	[Kop12]  C. Kop.  Higher Order Termination.  PhD Thesis, 2012.
0.51/1.23	EOF