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


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


YES
We consider the system theBenchmark.

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

  !colon : [o * o] --> o 
  C : [] --> o 

  !colon(!colon(!colon(!colon(C, X), Y), Z), U) => !colon(!colon(X, Z), !colon(!colon(!colon(X, Y), Z), U)) 

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

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

  !colon(!colon(!colon(!colon(C, X), Y), Z), U) >? !colon(!colon(X, Z), !colon(!colon(!colon(X, Y), Z), U)) 

about to try horpo

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

We choose Lex = {!colon} and Mul = {C}, and the following precedence: !colon > C

With these choices, we have:

  1] !colon(!colon(!colon(!colon(C, X), Y), Z), U) > !colon(!colon(X, Z), !colon(!colon(!colon(X, Y), Z), U))  because [2], by definition 
  2] !colon*(!colon(!colon(!colon(C, X), Y), Z), U) >= !colon(!colon(X, Z), !colon(!colon(!colon(X, Y), Z), U))  because [3], [14] and [18], by (Stat) 
  3] !colon(!colon(!colon(C, X), Y), Z) > !colon(X, Z)  because [4], by definition 
  4] !colon*(!colon(!colon(C, X), Y), Z) >= !colon(X, Z)  because [5], [10] and [12], by (Stat) 
  5] !colon(!colon(C, X), Y) > X  because [6], by definition 
  6] !colon*(!colon(C, X), Y) >= X  because [7], by (Select) 
  7] !colon(C, X) >= X  because [8], by (Star) 
  8] !colon*(C, X) >= X  because [9], by (Select) 
  9] X >= X  by (Meta) 
  10] !colon*(!colon(!colon(C, X), Y), Z) >= X  because [11], by (Select) 
  11] !colon(!colon(C, X), Y) >= X  because [6], by (Star) 
  12] !colon*(!colon(!colon(C, X), Y), Z) >= Z  because [13], by (Select) 
  13] Z >= Z  by (Meta) 
  14] !colon*(!colon(!colon(!colon(C, X), Y), Z), U) >= !colon(X, Z)  because [15], by (Select) 
  15] !colon(!colon(!colon(C, X), Y), Z) >= !colon(X, Z)  because [16] and [17], by (Fun) 
  16] !colon(!colon(C, X), Y) >= X  because [6], by (Star) 
  17] Z >= Z  by (Meta) 
  18] !colon*(!colon(!colon(!colon(C, X), Y), Z), U) >= !colon(!colon(!colon(X, Y), Z), U)  because [19], [31] and [34], by (Stat) 
  19] !colon(!colon(!colon(C, X), Y), Z) > !colon(!colon(X, Y), Z)  because [20], by definition 
  20] !colon*(!colon(!colon(C, X), Y), Z) >= !colon(!colon(X, Y), Z)  because [21], [27] and [12], by (Stat) 
  21] !colon(!colon(C, X), Y) > !colon(X, Y)  because [22], by definition 
  22] !colon*(!colon(C, X), Y) >= !colon(X, Y)  because [23], [6] and [25], by (Stat) 
  23] !colon(C, X) > X  because [24], by definition 
  24] !colon*(C, X) >= X  because [9], by (Select) 
  25] !colon*(!colon(C, X), Y) >= Y  because [26], by (Select) 
  26] Y >= Y  by (Meta) 
  27] !colon*(!colon(!colon(C, X), Y), Z) >= !colon(X, Y)  because [28], by (Select) 
  28] !colon(!colon(C, X), Y) >= !colon(X, Y)  because [29] and [30], by (Fun) 
  29] !colon(C, X) >= X  because [24], by (Star) 
  30] Y >= Y  by (Meta) 
  31] !colon*(!colon(!colon(!colon(C, X), Y), Z), U) >= !colon(!colon(X, Y), Z)  because [32], by (Select) 
  32] !colon(!colon(!colon(C, X), Y), Z) >= !colon(!colon(X, Y), Z)  because [33] and [17], by (Fun) 
  33] !colon(!colon(C, X), Y) >= !colon(X, Y)  because [29] and [30], by (Fun) 
  34] !colon*(!colon(!colon(!colon(C, X), Y), Z), U) >= U  because [35], by (Select) 
  35] U >= U  by (Meta) 

We can thus remove the following rules:

  !colon(!colon(!colon(!colon(C, X), Y), Z), U) => !colon(!colon(X, Z), !colon(!colon(!colon(X, Y), Z), U)) 

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.