/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.

  ackin : [o * o] --> o 
  ackout : [o] --> o 
  s : [o] --> o 
  u21 : [o * o] --> o 
  u22 : [o] --> o 

  ackin(s(X), s(Y)) => u21(ackin(s(X), Y), X) 
  u21(ackout(X), Y) => u22(ackin(Y, X)) 

As the system is orthogonal, it is terminating if it is innermost terminating by [Gra95].  Then, by [FuhGieParSchSwi11], it suffices to prove (innermost) termination of the typed system, with sort annotations chosen to respect the rules, as follows:

  ackin : [i * i] --> ca 
  ackout : [i] --> ca 
  s : [i] --> i 
  u21 : [ca * i] --> ca 
  u22 : [ca] --> ca 

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

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

  ackin(s(X), s(Y)) >? u21(ackin(s(X), Y), X) 
  u21(ackout(X), Y) >? u22(ackin(Y, X)) 

about to try horpo

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

Argument functions:

  [[u21(x_1, x_2)]] = u21(x_2, x_1) 
  [[u22(x_1)]] = x_1 

We choose Lex = {ackin, u21} and Mul = {ackout, s}, and the following precedence: ackout > s > ackin = u21

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

  ackin(s(X), s(Y)) > u21(ackin(s(X), Y), X) 
  u21(ackout(X), Y) >= ackin(Y, X) 

With these choices, we have:

  1] ackin(s(X), s(Y)) > u21(ackin(s(X), Y), X)  because [2], by definition 
  2] ackin*(s(X), s(Y)) >= u21(ackin(s(X), Y), X)  because ackin = u21, [3], [6] and [15], by (Stat) 
  3] s(X) > X  because [4], by definition 
  4] s*(X) >= X  because [5], by (Select) 
  5] X >= X  by (Meta) 
  6] ackin*(s(X), s(Y)) >= ackin(s(X), Y)  because [7], [9], [12] and [13], by (Stat) 
  7] s(X) >= s(X)  because s in Mul and [8], by (Fun) 
  8] X >= X  by (Meta) 
  9] s(Y) > Y  because [10], by definition 
  10] s*(Y) >= Y  because [11], by (Select) 
  11] Y >= Y  by (Meta) 
  12] ackin*(s(X), s(Y)) >= s(X)  because [7], by (Select) 
  13] ackin*(s(X), s(Y)) >= Y  because [14], by (Select) 
  14] s(Y) >= Y  because [10], by (Star) 
  15] ackin*(s(X), s(Y)) >= X  because [16], by (Select) 
  16] s(X) >= X  because [4], by (Star) 

  17] u21(ackout(X), Y) >= ackin(Y, X)  because u21 = ackin, [18] and [20], by (Fun) 
  18] ackout(X) >= X  because [19], by (Star) 
  19] ackout*(X) >= X  because [8], by (Select) 
  20] Y >= Y  by (Meta) 

We can thus remove the following rules:

  ackin(s(X), s(Y)) => u21(ackin(s(X), Y), X) 

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

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

  u21(ackout(X), Y) >? u22(ackin(Y, X)) 

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

The following interpretation satisfies the requirements:

  ackin = \y0y1.y0 + y1 
  ackout = \y0.3 + 3y0 
  u21 = \y0y1.3 + 3y0 + 3y1 
  u22 = \y0.y0 

Using this interpretation, the requirements translate to:

  [[u21(ackout(_x0), _x1)]] = 12 + 3x1 + 9x0 > x0 + x1 = [[u22(ackin(_x1, _x0))]] 

We can thus remove the following rules:

  u21(ackout(X), Y) => u22(ackin(Y, 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 +++

[FuhGieParSchSwi11]  C. Fuhs, J. Giesl, M. Parting, P. Schneider-Kamp, and S. Swiderski.  Proving Termination by Dependency Pairs and Inductive Theorem Proving.  In volume 47(2) of Journal of Automated Reasoning.  133--160, 2011.
[Gra95]  B. Gramlich.  Abstract Relations Between Restricted Termination and Confluence Properties of Rewrite Systems.  In volume 24(1-2) of Fundamentae Informaticae.  3--23, 1995.
[Kop12]  C. Kop.  Higher Order Termination.  PhD Thesis, 2012.