0.00/0.09	YES
0.00/0.09	We consider the system theBenchmark.
0.00/0.09	
0.00/0.09	  Alphabet:
0.00/0.09	
0.00/0.09	    0 : [] --> nat 
0.00/0.09	    I : [nat] --> nat 
0.00/0.09	    s : [nat] --> nat 
0.00/0.09	
0.00/0.09	  Rules:
0.00/0.09	
0.00/0.09	    I(s(x)) => s((/\f./\y.f (f y)) (/\z.I(z)) x) 
0.00/0.09	    I(0) => 0 
0.00/0.09	
0.00/0.09	This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0).
0.00/0.09	
0.00/0.09	We use the dependency pair framework as described in [Kop12, Ch. 6/7], with dynamic dependency pairs.
0.00/0.09	
0.00/0.09	We thus obtain the following dependency pair problem (P_0, R_0, minimal, formative):
0.00/0.09	
0.00/0.09	  Dependency Pairs P_0:
0.00/0.09	
0.00/0.09	    0] I#(s(X)) =#> I#(x)   
0.00/0.09	    1] I#(s(X)) =#> I#(X)   
0.00/0.09	    2] I#(s(X)) =#> I#((/\x.I(x)) X)   
0.00/0.09	    3] I#(s(X)) =#> I#(X)   
0.00/0.09	
0.00/0.09	  Rules R_0:
0.00/0.09	
0.00/0.09	    I(s(X)) => s((/\f./\x.f (f x)) (/\y.I(y)) X) 
0.00/0.09	    I(0) => 0 
0.00/0.09	
0.00/0.09	Thus, the original system is terminating if (P_0, R_0, minimal, formative) is finite.
0.00/0.09	
0.00/0.09	We consider the dependency pair problem (P_0, R_0, minimal, formative).
0.00/0.09	
0.00/0.09	We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows:
0.00/0.09	
0.00/0.09	    * 0 :  
0.00/0.09	    * 1 : 0, 1, 2, 3 
0.00/0.09	    * 2 : 0, 1, 2, 3 
0.00/0.09	    * 3 : 0, 1, 2, 3 
0.00/0.09	
0.00/0.09	This graph has the following strongly connected components:
0.00/0.09	
0.00/0.09	  P_1:
0.00/0.09	
0.00/0.09	    I#(s(X)) =#> I#(X)   
0.00/0.09	    I#(s(X)) =#> I#((/\x.I(x)) X)   
0.00/0.09	    I#(s(X)) =#> I#(X)   
0.00/0.09	
0.00/0.09	By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_0, R_0, m, f) by (P_1, R_0, m, f).
0.00/0.09	
0.00/0.09	Thus, the original system is terminating if (P_1, R_0, minimal, formative) is finite.
0.00/0.09	
0.00/0.09	We consider the dependency pair problem (P_1, R_0, minimal, formative).
0.00/0.09	
0.00/0.09	The formative rules of (P_1, R_0) are R_1 ::=
0.00/0.09	
0.00/0.09	  I(s(X)) => s((/\f./\x.f (f x)) (/\y.I(y)) X) 
0.00/0.09	
0.00/0.09	By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_1, R_0, minimal, formative) by (P_1, R_1, minimal, formative).
0.00/0.09	
0.00/0.09	Thus, the original system is terminating if (P_1, R_1, minimal, formative) is finite.
0.00/0.09	
0.00/0.09	We consider the dependency pair problem (P_1, R_1, minimal, formative).
0.00/0.09	
0.00/0.09	We will use the reduction pair processor [Kop12, Thm. 7.16].  It suffices to find a standard reduction pair [Kop12, Def. 6.69].  Thus, we must orient:
0.00/0.09	
0.00/0.09	  I#(s(X)) >? I#(X) 
0.00/0.09	  I#(s(X)) >? I#((/\x.I(x)) X) 
0.00/0.09	  I#(s(X)) >? I#(X) 
0.00/0.09	  I(s(X)) >= s((/\f./\x.f (f x)) (/\y.I(y)) X) 
0.00/0.09	
0.00/0.09	We orient these requirements with a polynomial interpretation in the natural numbers.
0.00/0.09	
0.00/0.09	The following interpretation satisfies the requirements:
0.00/0.09	
0.00/0.09	  I = \y0.y0 
0.00/0.09	  I# = \y0.3y0 
0.00/0.09	  s = \y0.3 + 3y0 
0.00/0.09	
0.00/0.09	Using this interpretation, the requirements translate to:
0.00/0.09	
0.00/0.09	  [[I#(s(_x0))]] = 9 + 9x0 > 3x0 = [[I#(_x0)]] 
0.00/0.09	  [[I#(s(_x0))]] = 9 + 9x0 > 3x0 = [[I#((/\x.I(x)) _x0)]] 
0.00/0.09	  [[I#(s(_x0))]] = 9 + 9x0 > 3x0 = [[I#(_x0)]] 
0.00/0.09	  [[I(s(_x0))]] = 3 + 3x0 >= 3 + 3x0 = [[s((/\f./\x.f (f x)) (/\y.I(y)) _x0)]] 
0.00/0.09	
0.00/0.09	By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace a dependency pair problem (P_1, R_1) by ({}, R_1).  By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed.
0.00/0.09	
0.00/0.09	As all dependency pair problems were succesfully simplified with sound (and complete) processors until nothing remained, we conclude termination.
0.00/0.09	
0.00/0.09	
0.00/0.09	+++ Citations +++
0.00/0.09	
0.00/0.09	[Kop12]  C. Kop.  Higher Order Termination.  PhD Thesis, 2012.
0.00/0.09	EOF