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


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


YES
We consider the system theBenchmark.

  Alphabet:

    c : [] --> C -> L -> L -> C 
    d : [] --> C 
    ex : [] --> C -> L 
    nil : [] --> L 

  Rules:

    ex d => nil 
    ex (c (/\f.g f)) => g ex 

Using the transformations described in [Kop11], this system can be brought in a form without leading free variables in the left-hand side, and where the left-hand side of a variable is always a functional term or application headed by a functional term.

We now transform the resulting AFS into an AFSM by replacing all free variables by meta-variables (with arity 0).  This leads to the following AFSM:

  Alphabet:

    c : [C -> L -> L] --> C 
    d : [] --> C 
    ex : [] --> C -> L 
    nil : [] --> L 
    ~AP1 : [C -> L -> L * C -> L] --> L 

  Rules:

    ex d => nil 
    ex c(/\f.~AP1(F, f)) => ~AP1(F, ex) 
    ~AP1(F, G) => F G 

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

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

  ex d >? nil 
  ex c(/\f.~AP1(F, f)) >? ~AP1(F, ex) 
  ~AP1(F, G) >? F G 

about to try horpo

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

Argument functions:

  [[ex]] = _|_ 
  [[nil]] = _|_ 

We choose Lex = {} and Mul = {@_{(o -> o) -> o}, @_{o -> o}, c, d, ~AP1}, and the following precedence: d > c > ~AP1 > @_{(o -> o) -> o} > @_{o -> o}

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

  @_{o -> o}(_|_, d) > _|_ 
  @_{o -> o}(_|_, c(/\f.~AP1(F, f))) >= ~AP1(F, _|_) 
  ~AP1(F, G) >= @_{(o -> o) -> o}(F, G) 

With these choices, we have:

  1] @_{o -> o}(_|_, d) > _|_  because [2], by definition 
  2] @_{o -> o}*(_|_, d) >= _|_  by (Bot) 

  3] @_{o -> o}(_|_, c(/\f.~AP1(F, f))) >= ~AP1(F, _|_)  because [4], by (Star) 
  4] @_{o -> o}*(_|_, c(/\f.~AP1(F, f))) >= ~AP1(F, _|_)  because [5], by (Select) 
  5] c(/\f.~AP1(F, f)) >= ~AP1(F, _|_)  because [6], by (Star) 
  6] c*(/\f.~AP1(F, f)) >= ~AP1(F, _|_)  because [7], by (Select) 
  7] ~AP1(F, c*(/\f.~AP1(F, f))) >= ~AP1(F, _|_)  because ~AP1 in Mul, [8] and [9], by (Fun) 
  8] F >= F  by (Meta) 
  9] c*(/\f.~AP1(F, f)) >= _|_  by (Bot) 

  10] ~AP1(F, G) >= @_{(o -> o) -> o}(F, G)  because [11], by (Star) 
  11] ~AP1*(F, G) >= @_{(o -> o) -> o}(F, G)  because ~AP1 > @_{(o -> o) -> o}, [12] and [14], by (Copy) 
  12] ~AP1*(F, G) >= F  because [13], by (Select) 
  13] F >= F  by (Meta) 
  14] ~AP1*(F, G) >= G  because [15], by (Select) 
  15] G >= G  by (Meta) 

We can thus remove the following rules:

  ex d => nil 

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

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

  ex c(/\f.~AP1(F, f)) >? ~AP1(F, ex) 
  ~AP1(F, G) >? F G 

about to try horpo

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

Argument functions:

  [[ex]] = _|_ 

We choose Lex = {} and Mul = {@_{(o -> o) -> o}, @_{o -> o}, c, ~AP1}, and the following precedence: ~AP1 > @_{(o -> o) -> o} > c > @_{o -> o}

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

  @_{o -> o}(_|_, c(/\f.~AP1(F, f))) >= ~AP1(F, _|_) 
  ~AP1(F, G) > @_{(o -> o) -> o}(F, G) 

With these choices, we have:

  1] @_{o -> o}(_|_, c(/\f.~AP1(F, f))) >= ~AP1(F, _|_)  because [2], by (Star) 
  2] @_{o -> o}*(_|_, c(/\f.~AP1(F, f))) >= ~AP1(F, _|_)  because [3], by (Select) 
  3] c(/\f.~AP1(F, f)) >= ~AP1(F, _|_)  because [4], by (Star) 
  4] c*(/\f.~AP1(F, f)) >= ~AP1(F, _|_)  because [5], by (Select) 
  5] ~AP1(F, c*(/\f.~AP1(F, f))) >= ~AP1(F, _|_)  because ~AP1 in Mul, [6] and [7], by (Fun) 
  6] F >= F  by (Meta) 
  7] c*(/\f.~AP1(F, f)) >= _|_  by (Bot) 

  8] ~AP1(F, G) > @_{(o -> o) -> o}(F, G)  because [9], by definition 
  9] ~AP1*(F, G) >= @_{(o -> o) -> o}(F, G)  because ~AP1 > @_{(o -> o) -> o}, [10] and [12], by (Copy) 
  10] ~AP1*(F, G) >= F  because [11], by (Select) 
  11] F >= F  by (Meta) 
  12] ~AP1*(F, G) >= G  because [13], by (Select) 
  13] G >= G  by (Meta) 

We can thus remove the following rules:

  ~AP1(F, G) => F G 

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

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

  ex c(/\f.~AP1(F, f)) >? ~AP1(F, ex) 

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

The following interpretation satisfies the requirements:

  c = \G0.3 + 3G0(\y1.0) 
  ex = \y0.3y0 
  ~AP1 = \G0G1.G0(\y2.0) + G1(0) 

Using this interpretation, the requirements translate to:

  [[ex c(/\f.~AP1(_F0, f))]] = 12 + 12F0(\y0.0) > F0(\y0.0) = [[~AP1(_F0, ex)]] 

We can thus remove the following rules:

  ex c(/\f.~AP1(F, f)) => ~AP1(F, ex) 

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 +++

[Kop11]  C. Kop.  Simplifying Algebraic Functional Systems.  In Proceedings of CAI 2011, volume 6742 of LNCS.  201--215, Springer, 2011.
[Kop12]  C. Kop.  Higher Order Termination.  PhD Thesis, 2012.