/export/starexec/sandbox/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files


--------------------------------------------------------------------------------


YES
We consider the system theBenchmark.

We are asked to determine termination of the following first-order TRS.

  1 : [] --> o 
  a : [o * o] --> o 
  lambda : [o] --> o 
  t : [] --> o 

  a(lambda(X), Y) => lambda(a(X, 1)) 
  a(lambda(X), Y) => lambda(a(X, a(Y, t))) 
  a(a(X, Y), Z) => a(X, a(Y, Z)) 
  lambda(X) => X 
  a(X, Y) => X 
  a(X, Y) => Y 

We use rule removal, following [Kop12, Theorem 2.23].

This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]):

  a(lambda(X), Y) >? lambda(a(X, 1)) 
  a(lambda(X), Y) >? lambda(a(X, a(Y, t))) 
  a(a(X, Y), Z) >? a(X, a(Y, Z)) 
  lambda(X) >? X 
  a(X, Y) >? X 
  a(X, Y) >? Y 

We orient these requirements with a polynomial interpretation in the natural numbers.

The following interpretation satisfies the requirements:

  1 = 0 
  a = \y0y1.y0 + y1 
  lambda = \y0.2 + y0 
  t = 0 

Using this interpretation, the requirements translate to:

  [[a(lambda(_x0), _x1)]] = 2 + x0 + x1 >= 2 + x0 = [[lambda(a(_x0, 1))]] 
  [[a(lambda(_x0), _x1)]] = 2 + x0 + x1 >= 2 + x0 + x1 = [[lambda(a(_x0, a(_x1, t)))]] 
  [[a(a(_x0, _x1), _x2)]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[a(_x0, a(_x1, _x2))]] 
  [[lambda(_x0)]] = 2 + x0 > x0 = [[_x0]] 
  [[a(_x0, _x1)]] = x0 + x1 >= x0 = [[_x0]] 
  [[a(_x0, _x1)]] = x0 + x1 >= x1 = [[_x1]] 

We can thus remove the following rules:

  lambda(X) => X 

We use the dependency pair framework as described in [Kop12, Ch. 6/7], with static dependency pairs (see [KusIsoSakBla09] and the adaptation for AFSMs in [Kop12, Ch. 7.8]).

We thus obtain the following dependency pair problem (P_0, R_0, minimal, formative):

  Dependency Pairs P_0:

    0] a#(lambda(X), Y) =#> a#(X, 1)   
    1] a#(lambda(X), Y) =#> a#(X, a(Y, t))   
    2] a#(lambda(X), Y) =#> a#(Y, t)   
    3] a#(a(X, Y), Z) =#> a#(X, a(Y, Z))   
    4] a#(a(X, Y), Z) =#> a#(Y, Z)   

  Rules R_0:

    a(lambda(X), Y) => lambda(a(X, 1)) 
    a(lambda(X), Y) => lambda(a(X, a(Y, t))) 
    a(a(X, Y), Z) => a(X, a(Y, Z)) 
    a(X, Y) => X 
    a(X, Y) => Y 

Thus, the original system is terminating if (P_0, R_0, minimal, formative) is finite.

We consider the dependency pair problem (P_0, R_0, minimal, formative).

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:

  a#(lambda(X), Y) >? a#(X, 1) 
  a#(lambda(X), Y) >? a#(X, a(Y, t)) 
  a#(lambda(X), Y) >? a#(Y, t) 
  a#(a(X, Y), Z) >? a#(X, a(Y, Z)) 
  a#(a(X, Y), Z) >? a#(Y, Z) 
  a(lambda(X), Y) >= lambda(a(X, 1)) 
  a(lambda(X), Y) >= lambda(a(X, a(Y, t))) 
  a(a(X, Y), Z) >= a(X, a(Y, Z)) 
  a(X, Y) >= X 
  a(X, Y) >= Y 

We orient these requirements with a polynomial interpretation in the natural numbers.

The following interpretation satisfies the requirements:

  1 = 0 
  a = \y0y1.y0 + y1 
  a# = \y0y1.y0 + y1 
  lambda = \y0.2 + y0 
  t = 0 

Using this interpretation, the requirements translate to:

  [[a#(lambda(_x0), _x1)]] = 2 + x0 + x1 > x0 = [[a#(_x0, 1)]] 
  [[a#(lambda(_x0), _x1)]] = 2 + x0 + x1 > x0 + x1 = [[a#(_x0, a(_x1, t))]] 
  [[a#(lambda(_x0), _x1)]] = 2 + x0 + x1 > x1 = [[a#(_x1, t)]] 
  [[a#(a(_x0, _x1), _x2)]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[a#(_x0, a(_x1, _x2))]] 
  [[a#(a(_x0, _x1), _x2)]] = x0 + x1 + x2 >= x1 + x2 = [[a#(_x1, _x2)]] 
  [[a(lambda(_x0), _x1)]] = 2 + x0 + x1 >= 2 + x0 = [[lambda(a(_x0, 1))]] 
  [[a(lambda(_x0), _x1)]] = 2 + x0 + x1 >= 2 + x0 + x1 = [[lambda(a(_x0, a(_x1, t)))]] 
  [[a(a(_x0, _x1), _x2)]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[a(_x0, a(_x1, _x2))]] 
  [[a(_x0, _x1)]] = x0 + x1 >= x0 = [[_x0]] 
  [[a(_x0, _x1)]] = x0 + x1 >= x1 = [[_x1]] 

By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_0, R_0, minimal, formative) by (P_1, R_0, minimal, formative), where P_1 consists of:

  a#(a(X, Y), Z) =#> a#(X, a(Y, Z))   
  a#(a(X, Y), Z) =#> a#(Y, Z)   

Thus, the original system is terminating if (P_1, R_0, minimal, formative) is finite.

We consider the dependency pair problem (P_1, R_0, minimal, formative).

We apply the subterm criterion with the following projection function:

  nu(a#) = 1 

Thus, we can orient the dependency pairs as follows:

  nu(a#(a(X, Y), Z)) = a(X, Y) |> X = nu(a#(X, a(Y, Z))) 
  nu(a#(a(X, Y), Z)) = a(X, Y) |> Y = nu(a#(Y, Z)) 

By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_1, R_0, minimal, f) by ({}, R_0, minimal, f).  By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed.

As all dependency pair problems were succesfully simplified with sound (and complete) processors until nothing remained, we conclude termination.


+++ Citations +++

[Kop12]  C. Kop.  Higher Order Termination.  PhD Thesis, 2012.
[KusIsoSakBla09]  K. Kusakari, Y. Isogai, M. Sakai, and F. Blanqui.  Static Dependency Pair Method Based On Strong Computability for Higher-Order Rewrite Systems.  In volume 92(10) of IEICE Transactions on Information and Systems.  2007--2015, 2009.