2.29/1.96	YES
2.37/2.02	We consider the system theBenchmark.
2.37/2.02	
2.37/2.02	  Alphabet:
2.37/2.02	
2.37/2.02	    0 : [] --> nat 
2.37/2.02	    find0 : [nat -> nat * nat * nat] --> nat 
2.37/2.02	    if : [nat * nat * nat] --> nat 
2.37/2.02	    min : [nat * nat] --> nat 
2.37/2.02	    nul : [nat -> nat * nat] --> nat 
2.37/2.02	    s : [nat] --> nat 
2.37/2.02	
2.37/2.02	  Rules:
2.37/2.02	
2.37/2.02	    min(s(x), s(y)) => min(x, y) 
2.37/2.02	    min(x, 0) => 0 
2.37/2.02	    min(0, x) => 0 
2.37/2.02	    min(nul(f, x), y) => nul(f, min(x, y)) 
2.37/2.02	    nul(f, x) => find0(f, 0, x) 
2.37/2.02	    find0(f, x, 0) => x 
2.37/2.02	    find0(f, x, s(y)) => if(f x, find0(f, s(x), y), x) 
2.37/2.02	    if(s(x), y, z) => y 
2.37/2.02	    if(0, x, y) => y 
2.37/2.02	
2.37/2.02	This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0).
2.37/2.02	
2.37/2.02	We observe that the rules contain a first-order subset:
2.37/2.02	
2.37/2.02	  if(s(X), Y, Z) => Y 
2.37/2.02	  if(0, X, Y) => Y 
2.37/2.02	
2.37/2.02	Moreover, the system is finitely branching.  Thus, by [Kop12, Thm. 7.55], we may omit all first-order dependency pairs from the dependency pair problem (DP(R), R) if this first-order part is Ce-terminating when seen as a many-sorted first-order TRS.
2.37/2.02	
2.37/2.02	According to the external first-order termination prover, this system is indeed Ce-terminating:
2.37/2.02	
2.37/2.02	 || proof of resources/system.trs
2.37/2.02	 || # AProVE Commit ID: d84c10301d352dfd14de2104819581f4682260f5 fuhs 20130616
2.37/2.02	 || 
2.37/2.02	 || 
2.37/2.02	 || Termination w.r.t. Q of the given QTRS could be proven:
2.37/2.02	 || 
2.37/2.02	 || (0) QTRS
2.37/2.02	 || (1) QTRSRRRProof [EQUIVALENT]
2.37/2.02	 || (2) QTRS
2.37/2.02	 || (3) RisEmptyProof [EQUIVALENT]
2.37/2.02	 || (4) YES
2.37/2.02	 || 
2.37/2.02	 || 
2.37/2.02	 || ----------------------------------------
2.37/2.02	 || 
2.37/2.02	 || (0)
2.37/2.02	 || Obligation:
2.37/2.02	 || Q restricted rewrite system:
2.37/2.02	 || The TRS R consists of the following rules:
2.37/2.02	 || 
2.37/2.02	 ||    if(s(%X), %Y, %Z) -> %Y
2.37/2.02	 ||    if(0, %X, %Y) -> %Y
2.37/2.02	 ||    ~PAIR(%X, %Y) -> %X
2.37/2.02	 ||    ~PAIR(%X, %Y) -> %Y
2.37/2.02	 || 
2.37/2.02	 || Q is empty.
2.37/2.02	 || 
2.37/2.02	 || ----------------------------------------
2.37/2.02	 || 
2.37/2.02	 || (1) QTRSRRRProof (EQUIVALENT)
2.37/2.02	 || Used ordering:
2.37/2.02	 || if/3(YES,YES,YES)
2.37/2.02	 || s/1)YES(
2.37/2.02	 || 0/0)
2.37/2.02	 || ~PAIR/2(YES,YES)
2.37/2.02	 || 
2.37/2.02	 || Quasi precedence:
2.37/2.02	 || trivial
2.37/2.02	 || 
2.37/2.02	 || 
2.37/2.02	 || Status:
2.37/2.02	 || if_3: multiset status
2.37/2.02	 || 0: multiset status
2.37/2.02	 || ~PAIR_2: multiset status
2.37/2.02	 || 
2.37/2.02	 || With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
2.37/2.02	 || 
2.37/2.02	 ||    if(s(%X), %Y, %Z) -> %Y
2.37/2.02	 ||    if(0, %X, %Y) -> %Y
2.37/2.02	 ||    ~PAIR(%X, %Y) -> %X
2.37/2.02	 ||    ~PAIR(%X, %Y) -> %Y
2.37/2.02	 || 
2.37/2.02	 || 
2.37/2.02	 || 
2.37/2.02	 || 
2.37/2.02	 || ----------------------------------------
2.37/2.02	 || 
2.37/2.02	 || (2)
2.37/2.02	 || Obligation:
2.37/2.02	 || Q restricted rewrite system:
2.37/2.02	 || R is empty.
2.37/2.02	 || Q is empty.
2.37/2.02	 || 
2.37/2.02	 || ----------------------------------------
2.37/2.02	 || 
2.37/2.02	 || (3) RisEmptyProof (EQUIVALENT)
2.37/2.02	 || The TRS R is empty. Hence, termination is trivially proven.
2.37/2.02	 || ----------------------------------------
2.37/2.02	 || 
2.37/2.02	 || (4)
2.37/2.02	 || YES
2.37/2.02	 || 
2.37/2.02	We use the dependency pair framework as described in [Kop12, Ch. 6/7], with dynamic dependency pairs.
2.37/2.02	
2.37/2.02	After applying [Kop12, Thm. 7.22] to denote collapsing dependency pairs in an extended form, we thus obtain the following dependency pair problem (P_0, R_0, minimal, formative):
2.37/2.02	
2.37/2.02	  Dependency Pairs P_0:
2.37/2.02	
2.37/2.02	    0] min#(s(X), s(Y)) =#> min#(X, Y)   
2.37/2.02	    1] min#(nul(F, X), Y) =#> nul#(F, min(X, Y))   
2.37/2.02	    2] min#(nul(F, X), Y) =#> min#(X, Y)   
2.37/2.02	    3] nul#(F, X) =#> find0#(F, 0, X)   
2.37/2.02	    4] find0#(F, X, s(Y)) =#> if#(F X, find0(F, s(X), Y), X)   
2.37/2.02	    5] find0#(F, X, s(Y)) =#> F(X)   
2.37/2.02	    6] find0#(F, X, s(Y)) =#> find0#(F, s(X), Y)   
2.37/2.02	
2.37/2.02	  Rules R_0:
2.37/2.02	
2.37/2.02	    min(s(X), s(Y)) => min(X, Y) 
2.37/2.02	    min(X, 0) => 0 
2.37/2.02	    min(0, X) => 0 
2.37/2.02	    min(nul(F, X), Y) => nul(F, min(X, Y)) 
2.37/2.02	    nul(F, X) => find0(F, 0, X) 
2.37/2.02	    find0(F, X, 0) => X 
2.37/2.02	    find0(F, X, s(Y)) => if(F X, find0(F, s(X), Y), X) 
2.37/2.02	    if(s(X), Y, Z) => Y 
2.37/2.02	    if(0, X, Y) => Y 
2.37/2.02	
2.37/2.02	Thus, the original system is terminating if (P_0, R_0, minimal, formative) is finite.
2.37/2.02	
2.37/2.02	We consider the dependency pair problem (P_0, R_0, minimal, formative).
2.37/2.02	
2.37/2.02	We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows:
2.37/2.02	
2.37/2.02	    * 0 : 0, 1, 2 
2.37/2.02	    * 1 : 3 
2.37/2.02	    * 2 : 0, 1, 2 
2.37/2.02	    * 3 : 4, 5, 6 
2.37/2.02	    * 4 :  
2.37/2.02	    * 5 : 0, 1, 2, 3, 4, 5, 6 
2.37/2.02	    * 6 : 4, 5, 6 
2.37/2.02	
2.37/2.02	This graph has the following strongly connected components:
2.37/2.02	
2.37/2.02	  P_1:
2.37/2.02	
2.37/2.02	    min#(s(X), s(Y)) =#> min#(X, Y)   
2.37/2.02	    min#(nul(F, X), Y) =#> nul#(F, min(X, Y))   
2.37/2.02	    min#(nul(F, X), Y) =#> min#(X, Y)   
2.37/2.02	    nul#(F, X) =#> find0#(F, 0, X)   
2.37/2.02	    find0#(F, X, s(Y)) =#> F(X)   
2.37/2.02	    find0#(F, X, s(Y)) =#> find0#(F, s(X), Y)   
2.37/2.02	
2.37/2.02	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).
2.37/2.02	
2.37/2.02	Thus, the original system is terminating if (P_1, R_0, minimal, formative) is finite.
2.37/2.02	
2.37/2.02	We consider the dependency pair problem (P_1, R_0, minimal, formative).
2.37/2.02	
2.37/2.02	We will use the reduction pair processor [Kop12, Thm. 7.16].  As the system is abstraction-simple and the formative flag is set, it suffices to find a tagged reduction pair [Kop12, Def. 6.70].  Thus, we must orient:
2.37/2.02	
2.37/2.02	  min#(s(X), s(Y)) >? min#(X, Y) 
2.37/2.02	  min#(nul(F, X), Y) >? nul#(F, min(X, Y)) 
2.37/2.02	  min#(nul(F, X), Y) >? min#(X, Y) 
2.37/2.02	  nul#(F, X) >? find0#(F, 0, X) 
2.37/2.02	  find0#(F, X, s(Y)) >? F(X) 
2.37/2.02	  find0#(F, X, s(Y)) >? find0#(F, s(X), Y) 
2.37/2.02	  min(s(X), s(Y)) >= min(X, Y) 
2.37/2.02	  min(X, 0) >= 0 
2.37/2.02	  min(0, X) >= 0 
2.37/2.02	  min(nul(F, X), Y) >= nul(F, min(X, Y)) 
2.37/2.02	  nul(F, X) >= find0(F, 0, X) 
2.37/2.02	  find0(F, X, 0) >= X 
2.37/2.02	  find0(F, X, s(Y)) >= if(F X, find0(F, s(X), Y), X) 
2.37/2.02	  if(s(X), Y, Z) >= Y 
2.37/2.02	  if(0, X, Y) >= Y 
2.37/2.02	
2.37/2.02	We apply [Kop12, Thm. 6.75] and use the following argument functions:
2.37/2.02	
2.37/2.02	  pi( nul#(F, X) ) = #argfun-nul##(find0#(F, 0, X)) 
2.37/2.02	
2.37/2.02	Since this representation is not advantageous for the higher-order recursive path ordering, we present the strict requirements in their unextended form, which is not problematic since for any F, s and substituion gamma: (F s)gamma beta-reduces to F(s)gamma.)
2.37/2.02	
2.37/2.02	We use a recursive path ordering as defined in [Kop12, Chapter 5].
2.37/2.02	
2.37/2.02	Argument functions:
2.37/2.02	
2.37/2.02	  [[0]] = _|_ 
2.37/2.02	  [[find0(x_1, x_2, x_3)]] = find0(x_3, x_2, x_1) 
2.37/2.02	  [[find0#(x_1, x_2, x_3)]] = find0#(x_3, x_2, x_1) 
2.37/2.02	  [[min(x_1, x_2)]] = x_1 
2.37/2.02	
2.37/2.02	We choose Lex = {find0, find0#} and Mul = {#argfun-nul##, @_{o -> o}, if, min#, nul, nul#, s}, and the following precedence: min# > #argfun-nul## > nul > find0 > find0# > @_{o -> o} > if > nul# > s
2.37/2.02	
2.37/2.02	Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows:
2.37/2.02	
2.37/2.02	  min#(s(X), s(Y)) >= min#(X, Y) 
2.37/2.02	  min#(nul(F, X), Y) >= #argfun-nul##(find0#(F, _|_, X)) 
2.37/2.02	  min#(nul(F, X), Y) >= min#(X, Y) 
2.37/2.02	  #argfun-nul##(find0#(F, _|_, X)) >= find0#(F, _|_, X) 
2.37/2.02	  find0#(F, X, s(Y)) >= @_{o -> o}(F, X) 
2.37/2.02	  find0#(F, X, s(Y)) > find0#(F, s(X), Y) 
2.37/2.02	  s(X) >= X 
2.37/2.02	  X >= _|_ 
2.37/2.02	  _|_ >= _|_ 
2.37/2.02	  nul(F, X) >= nul(F, X) 
2.37/2.02	  nul(F, X) >= find0(F, _|_, X) 
2.37/2.02	  find0(F, X, _|_) >= X 
2.37/2.02	  find0(F, X, s(Y)) >= if(@_{o -> o}(F, X), find0(F, s(X), Y), X) 
2.37/2.02	  if(s(X), Y, Z) >= Y 
2.37/2.02	  if(_|_, X, Y) >= Y 
2.37/2.02	
2.37/2.02	With these choices, we have:
2.37/2.02	
2.37/2.02	  1] min#(s(X), s(Y)) >= min#(X, Y)  because [2], by (Star) 
2.37/2.02	  2] min#*(s(X), s(Y)) >= min#(X, Y)  because min# in Mul, [3] and [6], by (Stat) 
2.37/2.02	  3] s(X) >= X  because [4], by (Star) 
2.37/2.02	  4] s*(X) >= X  because [5], by (Select) 
2.37/2.02	  5] X >= X  by (Meta) 
2.37/2.02	  6] s(Y) > Y  because [7], by definition 
2.37/2.02	  7] s*(Y) >= Y  because [8], by (Select) 
2.37/2.02	  8] Y >= Y  by (Meta) 
2.37/2.02	
2.37/2.02	  9] min#(nul(F, X), Y) >= #argfun-nul##(find0#(F, _|_, X))  because [10], by (Star) 
2.37/2.02	  10] min#*(nul(F, X), Y) >= #argfun-nul##(find0#(F, _|_, X))  because min# > #argfun-nul## and [11], by (Copy) 
2.37/2.02	  11] min#*(nul(F, X), Y) >= find0#(F, _|_, X)  because [12], by (Select) 
2.37/2.02	  12] nul(F, X) >= find0#(F, _|_, X)  because [13], by (Star) 
2.37/2.02	  13] nul*(F, X) >= find0#(F, _|_, X)  because nul > find0#, [14], [16] and [17], by (Copy) 
2.37/2.02	  14] nul*(F, X) >= F  because [15], by (Select) 
2.37/2.02	  15] F >= F  by (Meta) 
2.37/2.02	  16] nul*(F, X) >= _|_  by (Bot) 
2.37/2.02	  17] nul*(F, X) >= X  because [18], by (Select) 
2.37/2.02	  18] X >= X  by (Meta) 
2.37/2.02	
2.37/2.02	  19] min#(nul(F, X), Y) >= min#(X, Y)  because [20], by (Star) 
2.37/2.02	  20] min#*(nul(F, X), Y) >= min#(X, Y)  because min# in Mul, [21] and [22], by (Stat) 
2.37/2.02	  21] nul(F, X) > X  because [17], by definition 
2.37/2.02	  22] Y >= Y  by (Meta) 
2.37/2.02	
2.37/2.02	  23] #argfun-nul##(find0#(F, _|_, X)) >= find0#(F, _|_, X)  because [24], by (Star) 
2.37/2.02	  24] #argfun-nul##*(find0#(F, _|_, X)) >= find0#(F, _|_, X)  because [25], by (Select) 
2.37/2.02	  25] find0#(F, _|_, X) >= find0#(F, _|_, X)  because [26], [27] and [28], by (Fun) 
2.37/2.02	  26] F >= F  by (Meta) 
2.37/2.02	  27] _|_ >= _|_  by (Bot) 
2.37/2.02	  28] X >= X  by (Meta) 
2.37/2.02	
2.37/2.02	  29] find0#(F, X, s(Y)) >= @_{o -> o}(F, X)  because [30], by (Star) 
2.37/2.02	  30] find0#*(F, X, s(Y)) >= @_{o -> o}(F, X)  because find0# > @_{o -> o}, [31] and [33], by (Copy) 
2.37/2.02	  31] find0#*(F, X, s(Y)) >= F  because [32], by (Select) 
2.37/2.02	  32] F >= F  by (Meta) 
2.37/2.02	  33] find0#*(F, X, s(Y)) >= X  because [34], by (Select) 
2.37/2.02	  34] X >= X  by (Meta) 
2.37/2.02	
2.37/2.02	  35] find0#(F, X, s(Y)) > find0#(F, s(X), Y)  because [36], by definition 
2.37/2.02	  36] find0#*(F, X, s(Y)) >= find0#(F, s(X), Y)  because [37], [31], [40] and [41], by (Stat) 
2.37/2.02	  37] s(Y) > Y  because [38], by definition 
2.37/2.02	  38] s*(Y) >= Y  because [39], by (Select) 
2.37/2.02	  39] Y >= Y  by (Meta) 
2.37/2.02	  40] find0#*(F, X, s(Y)) >= s(X)  because find0# > s and [33], by (Copy) 
2.37/2.02	  41] find0#*(F, X, s(Y)) >= Y  because [42], by (Select) 
2.37/2.02	  42] s(Y) >= Y  because [38], by (Star) 
2.37/2.02	
2.37/2.02	  43] s(X) >= X  because [4], by (Star) 
2.37/2.02	
2.37/2.02	  44] X >= _|_  by (Bot) 
2.37/2.02	
2.37/2.02	  45] _|_ >= _|_  by (Bot) 
2.37/2.02	
2.37/2.02	  46] nul(F, X) >= nul(F, X)  because nul in Mul, [47] and [48], by (Fun) 
2.37/2.02	  47] F >= F  by (Meta) 
2.37/2.02	  48] X >= X  by (Meta) 
2.37/2.02	
2.37/2.02	  49] nul(F, X) >= find0(F, _|_, X)  because [50], by (Star) 
2.37/2.02	  50] nul*(F, X) >= find0(F, _|_, X)  because nul > find0, [51], [52] and [53], by (Copy) 
2.37/2.02	  51] nul*(F, X) >= F  because [26], by (Select) 
2.37/2.02	  52] nul*(F, X) >= _|_  by (Bot) 
2.37/2.02	  53] nul*(F, X) >= X  because [28], by (Select) 
2.37/2.02	
2.37/2.02	  54] find0(F, X, _|_) >= X  because [55], by (Star) 
2.37/2.02	  55] find0*(F, X, _|_) >= X  because [56], by (Select) 
2.37/2.02	  56] X >= X  by (Meta) 
2.37/2.02	
2.37/2.02	  57] find0(F, X, s(Y)) >= if(@_{o -> o}(F, X), find0(F, s(X), Y), X)  because [58], by (Star) 
2.37/2.02	  58] find0*(F, X, s(Y)) >= if(@_{o -> o}(F, X), find0(F, s(X), Y), X)  because find0 > if, [59], [62] and [61], by (Copy) 
2.37/2.02	  59] find0*(F, X, s(Y)) >= @_{o -> o}(F, X)  because find0 > @_{o -> o}, [60] and [61], by (Copy) 
2.37/2.02	  60] find0*(F, X, s(Y)) >= F  because [32], by (Select) 
2.37/2.02	  61] find0*(F, X, s(Y)) >= X  because [34], by (Select) 
2.37/2.02	  62] find0*(F, X, s(Y)) >= find0(F, s(X), Y)  because [37], [60], [63] and [64], by (Stat) 
2.37/2.02	  63] find0*(F, X, s(Y)) >= s(X)  because find0 > s and [61], by (Copy) 
2.37/2.02	  64] find0*(F, X, s(Y)) >= Y  because [42], by (Select) 
2.37/2.02	
2.37/2.02	  65] if(s(X), Y, Z) >= Y  because [66], by (Star) 
2.37/2.02	  66] if*(s(X), Y, Z) >= Y  because [67], by (Select) 
2.37/2.02	  67] Y >= Y  by (Meta) 
2.37/2.02	
2.37/2.02	  68] if(_|_, X, Y) >= Y  because [69], by (Star) 
2.37/2.02	  69] if*(_|_, X, Y) >= Y  because [70], by (Select) 
2.37/2.02	  70] Y >= Y  by (Meta) 
2.37/2.02	
2.37/2.02	By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_1, R_0, minimal, formative) by (P_2, R_0, minimal, formative), where P_2 consists of:
2.37/2.02	
2.37/2.02	  min#(s(X), s(Y)) =#> min#(X, Y)   
2.37/2.02	  min#(nul(F, X), Y) =#> nul#(F, min(X, Y))   
2.37/2.02	  min#(nul(F, X), Y) =#> min#(X, Y)   
2.37/2.02	  nul#(F, X) =#> find0#(F, 0, X)   
2.37/2.02	  find0#(F, X, s(Y)) =#> F(X)   
2.37/2.02	
2.37/2.02	Thus, the original system is terminating if (P_2, R_0, minimal, formative) is finite.
2.37/2.02	
2.37/2.02	We consider the dependency pair problem (P_2, R_0, minimal, formative).
2.37/2.02	
2.37/2.02	We will use the reduction pair processor [Kop12, Thm. 7.16].  As the system is abstraction-simple and the formative flag is set, it suffices to find a tagged reduction pair [Kop12, Def. 6.70].  Thus, we must orient:
2.37/2.02	
2.37/2.02	  min#(s(X), s(Y)) >? min#(X, Y) 
2.37/2.02	  min#(nul(F, X), Y) >? nul#(F, min(X, Y)) 
2.37/2.02	  min#(nul(F, X), Y) >? min#(X, Y) 
2.37/2.02	  nul#(F, X) >? find0#(F, 0, X) 
2.37/2.02	  find0#(F, X, s(Y)) >? F(X) 
2.37/2.02	  min(s(X), s(Y)) >= min(X, Y) 
2.37/2.02	  min(X, 0) >= 0 
2.37/2.02	  min(0, X) >= 0 
2.37/2.02	  min(nul(F, X), Y) >= nul(F, min(X, Y)) 
2.37/2.02	  nul(F, X) >= find0(F, 0, X) 
2.37/2.02	  find0(F, X, 0) >= X 
2.37/2.02	  find0(F, X, s(Y)) >= if(F X, find0(F, s(X), Y), X) 
2.37/2.02	  if(s(X), Y, Z) >= Y 
2.37/2.02	  if(0, X, Y) >= Y 
2.37/2.02	
2.37/2.02	We apply [Kop12, Thm. 6.75] and use the following argument functions:
2.37/2.02	
2.37/2.02	  pi( nul#(F, X) ) = #argfun-nul##(find0#(F, 0, X)) 
2.37/2.02	
2.37/2.02	Since this representation is not advantageous for the higher-order recursive path ordering, we present the strict requirements in their unextended form, which is not problematic since for any F, s and substituion gamma: (F s)gamma beta-reduces to F(s)gamma.)
2.37/2.02	
2.37/2.02	We use a recursive path ordering as defined in [Kop12, Chapter 5].
2.37/2.02	
2.37/2.02	Argument functions:
2.37/2.02	
2.37/2.02	  [[0]] = _|_ 
2.37/2.02	  [[find0(x_1, x_2, x_3)]] = find0(x_3, x_1, x_2) 
2.37/2.02	  [[if(x_1, x_2, x_3)]] = if(x_2, x_3) 
2.37/2.02	  [[min(x_1, x_2)]] = x_1 
2.37/2.02	
2.37/2.02	We choose Lex = {find0} and Mul = {#argfun-nul##, @_{o -> o}, find0#, if, min#, nul, nul#, s}, and the following precedence: min# > nul > #argfun-nul## > nul# > find0# > find0 > if > @_{o -> o} > s
2.37/2.02	
2.37/2.02	Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows:
2.37/2.02	
2.37/2.02	  min#(s(X), s(Y)) > min#(X, Y) 
2.37/2.02	  min#(nul(F, X), Y) >= #argfun-nul##(find0#(F, _|_, X)) 
2.37/2.02	  min#(nul(F, X), Y) >= min#(X, Y) 
2.37/2.02	  #argfun-nul##(find0#(F, _|_, X)) > find0#(F, _|_, X) 
2.37/2.02	  find0#(F, X, s(Y)) > @_{o -> o}(F, X) 
2.37/2.02	  s(X) >= X 
2.37/2.02	  X >= _|_ 
2.37/2.02	  _|_ >= _|_ 
2.37/2.02	  nul(F, X) >= nul(F, X) 
2.37/2.02	  nul(F, X) >= find0(F, _|_, X) 
2.37/2.02	  find0(F, X, _|_) >= X 
2.37/2.02	  find0(F, X, s(Y)) >= if(find0(F, s(X), Y), X) 
2.37/2.02	  if(X, Y) >= X 
2.37/2.02	  if(X, Y) >= Y 
2.37/2.02	
2.37/2.02	With these choices, we have:
2.37/2.02	
2.37/2.02	  1] min#(s(X), s(Y)) > min#(X, Y)  because [2], by definition 
2.37/2.02	  2] min#*(s(X), s(Y)) >= min#(X, Y)  because min# in Mul, [3] and [6], by (Stat) 
2.37/2.02	  3] s(X) >= X  because [4], by (Star) 
2.37/2.02	  4] s*(X) >= X  because [5], by (Select) 
2.37/2.02	  5] X >= X  by (Meta) 
2.37/2.02	  6] s(Y) > Y  because [7], by definition 
2.37/2.02	  7] s*(Y) >= Y  because [8], by (Select) 
2.37/2.02	  8] Y >= Y  by (Meta) 
2.37/2.02	
2.37/2.02	  9] min#(nul(F, X), Y) >= #argfun-nul##(find0#(F, _|_, X))  because [10], by (Star) 
2.37/2.02	  10] min#*(nul(F, X), Y) >= #argfun-nul##(find0#(F, _|_, X))  because min# > #argfun-nul## and [11], by (Copy) 
2.37/2.02	  11] min#*(nul(F, X), Y) >= find0#(F, _|_, X)  because [12], by (Select) 
2.37/2.02	  12] nul(F, X) >= find0#(F, _|_, X)  because [13], by (Star) 
2.37/2.02	  13] nul*(F, X) >= find0#(F, _|_, X)  because nul > find0#, [14], [16] and [17], by (Copy) 
2.37/2.02	  14] nul*(F, X) >= F  because [15], by (Select) 
2.37/2.02	  15] F >= F  by (Meta) 
2.37/2.02	  16] nul*(F, X) >= _|_  by (Bot) 
2.37/2.02	  17] nul*(F, X) >= X  because [18], by (Select) 
2.37/2.02	  18] X >= X  by (Meta) 
2.37/2.02	
2.37/2.02	  19] min#(nul(F, X), Y) >= min#(X, Y)  because min# in Mul, [20] and [21], by (Fun) 
2.37/2.02	  20] nul(F, X) >= X  because [17], by (Star) 
2.37/2.02	  21] Y >= Y  by (Meta) 
2.37/2.02	
2.37/2.02	  22] #argfun-nul##(find0#(F, _|_, X)) > find0#(F, _|_, X)  because [23], by definition 
2.37/2.02	  23] #argfun-nul##*(find0#(F, _|_, X)) >= find0#(F, _|_, X)  because [24], by (Select) 
2.37/2.02	  24] find0#(F, _|_, X) >= find0#(F, _|_, X)  because find0# in Mul, [25], [26] and [27], by (Fun) 
2.37/2.02	  25] F >= F  by (Meta) 
2.37/2.02	  26] _|_ >= _|_  by (Bot) 
2.37/2.02	  27] X >= X  by (Meta) 
2.37/2.02	
2.37/2.02	  28] find0#(F, X, s(Y)) > @_{o -> o}(F, X)  because [29], by definition 
2.37/2.02	  29] find0#*(F, X, s(Y)) >= @_{o -> o}(F, X)  because find0# > @_{o -> o}, [30] and [32], by (Copy) 
2.37/2.02	  30] find0#*(F, X, s(Y)) >= F  because [31], by (Select) 
2.37/2.02	  31] F >= F  by (Meta) 
2.37/2.02	  32] find0#*(F, X, s(Y)) >= X  because [33], by (Select) 
2.37/2.02	  33] X >= X  by (Meta) 
2.37/2.02	
2.37/2.02	  34] s(X) >= X  because [4], by (Star) 
2.37/2.02	
2.37/2.02	  35] X >= _|_  by (Bot) 
2.37/2.02	
2.37/2.02	  36] _|_ >= _|_  by (Bot) 
2.37/2.02	
2.37/2.02	  37] nul(F, X) >= nul(F, X)  because nul in Mul, [38] and [39], by (Fun) 
2.37/2.02	  38] F >= F  by (Meta) 
2.37/2.02	  39] X >= X  by (Meta) 
2.37/2.02	
2.37/2.02	  40] nul(F, X) >= find0(F, _|_, X)  because [41], by (Star) 
2.37/2.02	  41] nul*(F, X) >= find0(F, _|_, X)  because nul > find0, [42], [43] and [44], by (Copy) 
2.37/2.02	  42] nul*(F, X) >= F  because [25], by (Select) 
2.37/2.02	  43] nul*(F, X) >= _|_  by (Bot) 
2.37/2.02	  44] nul*(F, X) >= X  because [27], by (Select) 
2.37/2.02	
2.37/2.02	  45] find0(F, X, _|_) >= X  because [46], by (Star) 
2.37/2.02	  46] find0*(F, X, _|_) >= X  because [47], by (Select) 
2.37/2.02	  47] X >= X  by (Meta) 
2.37/2.02	
2.37/2.02	  48] find0(F, X, s(Y)) >= if(find0(F, s(X), Y), X)  because [49], by (Star) 
2.37/2.02	  49] find0*(F, X, s(Y)) >= if(find0(F, s(X), Y), X)  because find0 > if, [50] and [56], by (Copy) 
2.37/2.02	  50] find0*(F, X, s(Y)) >= find0(F, s(X), Y)  because [51], [54], [55] and [57], by (Stat) 
2.37/2.02	  51] s(Y) > Y  because [52], by definition 
2.37/2.02	  52] s*(Y) >= Y  because [53], by (Select) 
2.37/2.02	  53] Y >= Y  by (Meta) 
2.37/2.02	  54] find0*(F, X, s(Y)) >= F  because [31], by (Select) 
2.37/2.02	  55] find0*(F, X, s(Y)) >= s(X)  because find0 > s and [56], by (Copy) 
2.37/2.02	  56] find0*(F, X, s(Y)) >= X  because [33], by (Select) 
2.37/2.02	  57] find0*(F, X, s(Y)) >= Y  because [58], by (Select) 
2.37/2.02	  58] s(Y) >= Y  because [52], by (Star) 
2.37/2.02	
2.37/2.02	  59] if(X, Y) >= X  because [60], by (Star) 
2.37/2.02	  60] if*(X, Y) >= X  because [61], by (Select) 
2.37/2.02	  61] X >= X  by (Meta) 
2.37/2.02	
2.37/2.02	  62] if(X, Y) >= Y  because [63], by (Star) 
2.37/2.02	  63] if*(X, Y) >= Y  because [64], by (Select) 
2.37/2.02	  64] Y >= Y  by (Meta) 
2.37/2.02	
2.37/2.02	By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_2, R_0, minimal, formative) by (P_3, R_0, minimal, formative), where P_3 consists of:
2.37/2.02	
2.37/2.02	  min#(nul(F, X), Y) =#> nul#(F, min(X, Y))   
2.37/2.02	  min#(nul(F, X), Y) =#> min#(X, Y)   
2.37/2.02	
2.37/2.02	Thus, the original system is terminating if (P_3, R_0, minimal, formative) is finite.
2.37/2.02	
2.37/2.02	We consider the dependency pair problem (P_3, R_0, minimal, formative).
2.37/2.02	
2.37/2.02	We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows:
2.37/2.02	
2.37/2.02	    * 0 :  
2.37/2.02	    * 1 : 0, 1 
2.37/2.02	
2.37/2.02	This graph has the following strongly connected components:
2.37/2.02	
2.37/2.02	  P_4:
2.37/2.02	
2.37/2.02	    min#(nul(F, X), Y) =#> min#(X, Y)   
2.37/2.02	
2.37/2.02	By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_3, R_0, m, f) by (P_4, R_0, m, f).
2.37/2.02	
2.37/2.02	Thus, the original system is terminating if (P_4, R_0, minimal, formative) is finite.
2.37/2.02	
2.37/2.02	We consider the dependency pair problem (P_4, R_0, minimal, formative).
2.37/2.02	
2.37/2.02	We apply the subterm criterion with the following projection function:
2.37/2.02	
2.37/2.02	  nu(min#) = 1 
2.37/2.02	
2.37/2.02	Thus, we can orient the dependency pairs as follows:
2.37/2.02	
2.37/2.02	  nu(min#(nul(F, X), Y)) = nul(F, X) |> X = nu(min#(X, Y)) 
2.37/2.02	
2.37/2.02	By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_4, R_0, minimal, f) by ({}, R_0, minimal, f).  By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed.
2.37/2.02	
2.37/2.02	As all dependency pair problems were succesfully simplified with sound (and complete) processors until nothing remained, we conclude termination.
2.37/2.02	
2.37/2.02	
2.37/2.02	+++ Citations +++
2.37/2.02	
2.37/2.02	[Kop12]  C. Kop.  Higher Order Termination.  PhD Thesis, 2012.
2.37/2.02	EOF