/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 
  sum1 : [o] --> o 

  sum(0) => 0 
  sum(s(X)) => !plus(sum(X), s(X)) 
  sum1(0) => 0 
  sum1(s(X)) => s(!plus(sum1(X), !plus(X, 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(0) >? 0 
  sum(s(X)) >? !plus(sum(X), s(X)) 
  sum1(0) >? 0 
  sum1(s(X)) >? s(!plus(sum1(X), !plus(X, X))) 

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, sum1}, and the following precedence: sum > 0 > sum1 > !plus > s

With these choices, we have:

  1] sum(0) >= 0  because [2], by (Star) 
  2] sum*(0) >= 0  because sum > 0, by (Copy) 

  3] sum(s(X)) > !plus(sum(X), s(X))  because [4], by definition 
  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] sum1(0) > 0  because [13], by definition 
  13] sum1*(0) >= 0  because [14], by (Select) 
  14] 0 >= 0  by (Fun) 

  15] sum1(s(X)) >= s(!plus(sum1(X), !plus(X, X)))  because [16], by (Star) 
  16] sum1*(s(X)) >= s(!plus(sum1(X), !plus(X, X)))  because sum1 > s and [17], by (Copy) 
  17] sum1*(s(X)) >= !plus(sum1(X), !plus(X, X))  because sum1 > !plus, [18] and [19], by (Copy) 
  18] sum1*(s(X)) >= sum1(X)  because sum1 in Mul and [6], by (Stat) 
  19] sum1*(s(X)) >= !plus(X, X)  because sum1 > !plus, [20] and [20], by (Copy) 
  20] sum1*(s(X)) >= X  because [11], by (Select) 

We can thus remove the following rules:

  sum(s(X)) => !plus(sum(X), s(X)) 
  sum1(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(0) >? 0 
  sum1(s(X)) >? s(!plus(sum1(X), !plus(X, X))) 

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, sum1}, and the following precedence: sum > sum1 > s > !plus

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

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

With these choices, we have:

  1] sum(_|_) >= _|_  by (Bot) 

  2] sum1(s(X)) > s(!plus(sum1(X), !plus(X, X)))  because [3], by definition 
  3] sum1*(s(X)) >= s(!plus(sum1(X), !plus(X, X)))  because sum1 > s and [4], by (Copy) 
  4] sum1*(s(X)) >= !plus(sum1(X), !plus(X, X))  because sum1 > !plus, [5] and [9], by (Copy) 
  5] sum1*(s(X)) >= sum1(X)  because sum1 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] sum1*(s(X)) >= !plus(X, X)  because sum1 > !plus, [10] and [10], by (Copy) 
  10] sum1*(s(X)) >= X  because [11], by (Select) 
  11] s(X) >= X  because [7], by (Star) 

We can thus remove the following rules:

  sum1(s(X)) => s(!plus(sum1(X), !plus(X, 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(0) >? 0 

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

The following interpretation satisfies the requirements:

  0 = 0 
  sum = \y0.3 + 3y0 

Using this interpretation, the requirements translate to:

  [[sum(0)]] = 3 > 0 = [[0]] 

We can thus remove the following rules:

  sum(0) => 0 

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.