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

  !plus : [o * o] --> o 
  0 : [] --> o 
  s : [o] --> o 
  sum : [o] --> o 

  sum(0) => 0 
  sum(s(X)) => !plus(sum(X), s(X)) 
  !plus(X, 0) => X 
  !plus(X, s(Y)) => s(!plus(X, 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]):

  sum(0) >? 0 
  sum(s(X)) >? !plus(sum(X), s(X)) 
  !plus(X, 0) >? X 
  !plus(X, s(Y)) >? s(!plus(X, Y)) 

about to try horpo

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

Argument functions:

  [[0]] = _|_ 

We choose Lex = {} and Mul = {!plus, s, sum}, and the following precedence: sum > !plus > s

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

  sum(_|_) > _|_ 
  sum(s(X)) >= !plus(sum(X), s(X)) 
  !plus(X, _|_) >= X 
  !plus(X, s(Y)) >= s(!plus(X, Y)) 

With these choices, we have:

  1] sum(_|_) > _|_  because [2], by definition 
  2] sum*(_|_) >= _|_  by (Bot) 

  3] sum(s(X)) >= !plus(sum(X), s(X))  because [4], by (Star) 
  4] sum*(s(X)) >= !plus(sum(X), s(X))  because sum > !plus, [5] and [9], by (Copy) 
  5] sum*(s(X)) >= sum(X)  because sum in Mul and [6], by (Stat) 
  6] s(X) > X  because [7], by definition 
  7] s*(X) >= X  because [8], by (Select) 
  8] X >= X  by (Meta) 
  9] sum*(s(X)) >= s(X)  because sum > s and [10], by (Copy) 
  10] sum*(s(X)) >= X  because [11], by (Select) 
  11] s(X) >= X  because [7], by (Star) 

  12] !plus(X, _|_) >= X  because [13], by (Star) 
  13] !plus*(X, _|_) >= X  because [8], by (Select) 

  14] !plus(X, s(Y)) >= s(!plus(X, Y))  because [15], by (Star) 
  15] !plus*(X, s(Y)) >= s(!plus(X, Y))  because !plus > s and [16], by (Copy) 
  16] !plus*(X, s(Y)) >= !plus(X, Y)  because !plus in Mul, [17] and [18], by (Stat) 
  17] X >= X  by (Meta) 
  18] s(Y) > Y  because [19], by definition 
  19] s*(Y) >= Y  because [20], by (Select) 
  20] Y >= Y  by (Meta) 

We can thus remove the following rules:

  sum(0) => 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]):

  sum(s(X)) >? !plus(sum(X), s(X)) 
  !plus(X, 0) >? X 
  !plus(X, s(Y)) >? s(!plus(X, Y)) 

about to try horpo

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

We choose Lex = {} and Mul = {!plus, 0, s, sum}, and the following precedence: 0 > sum > !plus > s

With these choices, we have:

  1] sum(s(X)) >= !plus(sum(X), s(X))  because [2], by (Star) 
  2] sum*(s(X)) >= !plus(sum(X), s(X))  because sum > !plus, [3] and [7], by (Copy) 
  3] sum*(s(X)) >= sum(X)  because sum in Mul and [4], by (Stat) 
  4] s(X) > X  because [5], by definition 
  5] s*(X) >= X  because [6], by (Select) 
  6] X >= X  by (Meta) 
  7] sum*(s(X)) >= s(X)  because [8], by (Select) 
  8] s(X) >= s(X)  because s in Mul and [9], by (Fun) 
  9] X >= X  by (Meta) 

  10] !plus(X, 0) > X  because [11], by definition 
  11] !plus*(X, 0) >= X  because [9], by (Select) 

  12] !plus(X, s(Y)) >= s(!plus(X, Y))  because [13], by (Star) 
  13] !plus*(X, s(Y)) >= s(!plus(X, Y))  because !plus > s and [14], by (Copy) 
  14] !plus*(X, s(Y)) >= !plus(X, Y)  because !plus in Mul, [9] and [15], by (Stat) 
  15] s(Y) > Y  because [16], by definition 
  16] s*(Y) >= Y  because [17], by (Select) 
  17] Y >= Y  by (Meta) 

We can thus remove the following rules:

  !plus(X, 0) => 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]):

  sum(s(X)) >? !plus(sum(X), s(X)) 
  !plus(X, s(Y)) >? s(!plus(X, Y)) 

about to try horpo

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

We choose Lex = {} and Mul = {!plus, s, sum}, and the following precedence: sum > !plus > s

With these choices, we have:

  1] sum(s(X)) > !plus(sum(X), s(X))  because [2], by definition 
  2] sum*(s(X)) >= !plus(sum(X), s(X))  because sum > !plus, [3] and [7], by (Copy) 
  3] sum*(s(X)) >= sum(X)  because sum in Mul and [4], by (Stat) 
  4] s(X) > X  because [5], by definition 
  5] s*(X) >= X  because [6], by (Select) 
  6] X >= X  by (Meta) 
  7] sum*(s(X)) >= s(X)  because sum > s and [8], by (Copy) 
  8] sum*(s(X)) >= X  because [9], by (Select) 
  9] s(X) >= X  because [5], by (Star) 

  10] !plus(X, s(Y)) >= s(!plus(X, Y))  because [11], by (Star) 
  11] !plus*(X, s(Y)) >= s(!plus(X, Y))  because !plus > s and [12], by (Copy) 
  12] !plus*(X, s(Y)) >= !plus(X, Y)  because !plus in Mul, [13] and [14], by (Stat) 
  13] X >= X  by (Meta) 
  14] s(Y) > Y  because [15], by definition 
  15] s*(Y) >= Y  because [16], by (Select) 
  16] Y >= Y  by (Meta) 

We can thus remove the following rules:

  sum(s(X)) => !plus(sum(X), s(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]):

  !plus(X, s(Y)) >? s(!plus(X, Y)) 

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

The following interpretation satisfies the requirements:

  !plus = \y0y1.y0 + 3y1 
  s = \y0.1 + y0 

Using this interpretation, the requirements translate to:

  [[!plus(_x0, s(_x1))]] = 3 + x0 + 3x1 > 1 + x0 + 3x1 = [[s(!plus(_x0, _x1))]] 

We can thus remove the following rules:

  !plus(X, s(Y)) => s(!plus(X, Y)) 

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.