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


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


YES
We consider the system theBenchmark.

  Alphabet:

    0 : [] --> nat 
    cons : [nat * list] --> list 
    foldr : [nat -> nat -> nat * nat * list] --> nat 
    length : [list] --> nat 
    nil : [] --> list 
    s : [nat] --> nat 

  Rules:

    foldr(f, x, nil) => x 
    foldr(f, x, cons(y, z)) => f y foldr(f, x, z) 
    length(x) => foldr(/\y./\z.s(z), 0, x) 

This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0).

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

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

  foldr(F, X, nil) >? X 
  foldr(F, X, cons(Y, Z)) >? F Y foldr(F, X, Z) 
  length(X) >? foldr(/\x./\y.s(y), 0, X) 

about to try horpo

We use a recursive path ordering as defined in [Kop12, Chapter 5].

Argument functions:

  [[0]] = _|_ 
  [[s(x_1)]] = x_1 

We choose Lex = {} and Mul = {@_{o -> o -> o}, @_{o -> o}, cons, foldr, length, nil}, and the following precedence: length > foldr > @_{o -> o} > @_{o -> o -> o} > cons > nil

Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows:

  foldr(F, X, nil) >= X 
  foldr(F, X, cons(Y, Z)) > @_{o -> o}(@_{o -> o -> o}(F, Y), foldr(F, X, Z)) 
  length(X) >= foldr(/\x./\y.y, _|_, X) 

With these choices, we have:

  1] foldr(F, X, nil) >= X  because [2], by (Star) 
  2] foldr*(F, X, nil) >= X  because [3], by (Select) 
  3] X >= X  by (Meta) 

  4] foldr(F, X, cons(Y, Z)) > @_{o -> o}(@_{o -> o -> o}(F, Y), foldr(F, X, Z))  because [5], by definition 
  5] foldr*(F, X, cons(Y, Z)) >= @_{o -> o}(@_{o -> o -> o}(F, Y), foldr(F, X, Z))  because foldr > @_{o -> o}, [6] and [13], by (Copy) 
  6] foldr*(F, X, cons(Y, Z)) >= @_{o -> o -> o}(F, Y)  because foldr > @_{o -> o -> o}, [7] and [9], by (Copy) 
  7] foldr*(F, X, cons(Y, Z)) >= F  because [8], by (Select) 
  8] F >= F  by (Meta) 
  9] foldr*(F, X, cons(Y, Z)) >= Y  because [10], by (Select) 
  10] cons(Y, Z) >= Y  because [11], by (Star) 
  11] cons*(Y, Z) >= Y  because [12], by (Select) 
  12] Y >= Y  by (Meta) 
  13] foldr*(F, X, cons(Y, Z)) >= foldr(F, X, Z)  because foldr in Mul, [14], [15] and [16], by (Stat) 
  14] F >= F  by (Meta) 
  15] X >= X  by (Meta) 
  16] cons(Y, Z) > Z  because [17], by definition 
  17] cons*(Y, Z) >= Z  because [18], by (Select) 
  18] Z >= Z  by (Meta) 

  19] length(X) >= foldr(/\x./\y.y, _|_, X)  because [20], by (Star) 
  20] length*(X) >= foldr(/\x./\y.y, _|_, X)  because length > foldr, [21], [25] and [26], by (Copy) 
  21] length*(X) >= /\y./\z.z  because [22], by (F-Abs) 
  22] length*(X, x) >= /\z.z  because [23], by (F-Abs) 
  23] length*(X, x, y) >= y  because [24], by (Select) 
  24] y >= y  by (Var) 
  25] length*(X) >= _|_  by (Bot) 
  26] length*(X) >= X  because [27], by (Select) 
  27] X >= X  by (Meta) 

We can thus remove the following rules:

  foldr(F, X, cons(Y, Z)) => F Y foldr(F, X, Z) 

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

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

  foldr(F, X, nil) >? X 
  length(X) >? foldr(/\x./\y.s(y), 0, X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  foldr = \G0y1y2.y1 + y2 + G0(0,0) 
  length = \y0.3 + 3y0 
  nil = 3 
  s = \y0.y0 

Using this interpretation, the requirements translate to:

  [[foldr(_F0, _x1, nil)]] = 3 + x1 + F0(0,0) > x1 = [[_x1]] 
  [[length(_x0)]] = 3 + 3x0 > x0 = [[foldr(/\x./\y.s(y), 0, _x0)]] 

We can thus remove the following rules:

  foldr(F, X, nil) => X 
  length(X) => foldr(/\x./\y.s(y), 0, X) 

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.


+++ Citations +++

[Kop12]  C. Kop.  Higher Order Termination.  PhD Thesis, 2012.