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

  0 : [] --> o 
  plus : [o * o] --> o 
  s : [o] --> o 
  times : [o * o] --> o 

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

  times(X, 0) >? 0 
  times(X, s(Y)) >? plus(times(X, Y), X) 
  plus(X, 0) >? X 
  plus(0, X) >? X 
  plus(X, s(Y)) >? s(plus(X, Y)) 
  plus(s(X), 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, times}, and the following precedence: times > plus > s

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

  times(X, _|_) >= _|_ 
  times(X, s(Y)) >= plus(times(X, Y), X) 
  plus(X, _|_) >= X 
  plus(_|_, X) >= X 
  plus(X, s(Y)) > s(plus(X, Y)) 
  plus(s(X), Y) >= s(plus(X, Y)) 

With these choices, we have:

  1] times(X, _|_) >= _|_  by (Bot) 

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

  10] plus(X, _|_) >= X  because [11], by (Star) 
  11] plus*(X, _|_) >= X  because [5], by (Select) 

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

  14] plus(X, s(Y)) > s(plus(X, Y))  because [15], by definition 
  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, [5] and [6], by (Stat) 

  17] plus(s(X), Y) >= s(plus(X, Y))  because [18], by (Star) 
  18] plus*(s(X), Y) >= s(plus(X, Y))  because plus > s and [19], by (Copy) 
  19] plus*(s(X), Y) >= plus(X, Y)  because plus in Mul, [20] and [22], by (Stat) 
  20] s(X) > X  because [21], by definition 
  21] s*(X) >= X  because [5], by (Select) 
  22] Y >= Y  by (Meta) 

We can thus remove the following rules:

  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]):

  times(X, 0) >? 0 
  times(X, s(Y)) >? plus(times(X, Y), X) 
  plus(X, 0) >? X 
  plus(0, X) >? X 
  plus(s(X), 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, times}, and the following precedence: times > plus > s

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

  times(X, _|_) >= _|_ 
  times(X, s(Y)) >= plus(times(X, Y), X) 
  plus(X, _|_) > X 
  plus(_|_, X) >= X 
  plus(s(X), Y) >= s(plus(X, Y)) 

With these choices, we have:

  1] times(X, _|_) >= _|_  by (Bot) 

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

  10] plus(X, _|_) > X  because [11], by definition 
  11] plus*(X, _|_) >= X  because [5], by (Select) 

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

  14] plus(s(X), Y) >= s(plus(X, Y))  because [15], by (Star) 
  15] plus*(s(X), Y) >= s(plus(X, Y))  because plus > s and [16], by (Copy) 
  16] plus*(s(X), Y) >= plus(X, Y)  because plus in Mul, [17] and [19], by (Stat) 
  17] s(X) > X  because [18], by definition 
  18] s*(X) >= X  because [5], by (Select) 
  19] 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]):

  times(X, 0) >? 0 
  times(X, s(Y)) >? plus(times(X, Y), X) 
  plus(0, X) >? X 
  plus(s(X), 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, times}, and the following precedence: times > plus > s

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

  times(X, _|_) > _|_ 
  times(X, s(Y)) >= plus(times(X, Y), X) 
  plus(_|_, X) >= X 
  plus(s(X), Y) >= s(plus(X, Y)) 

With these choices, we have:

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

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

  11] plus(_|_, X) >= X  because [12], by (Star) 
  12] plus*(_|_, X) >= X  because [6], by (Select) 

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

We can thus remove the following rules:

  times(X, 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]):

  times(X, s(Y)) >? plus(times(X, Y), X) 
  plus(0, X) >? X 
  plus(s(X), 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 = {0, plus, s, times}, and the following precedence: 0 > times > plus > s

With these choices, we have:

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

  9] plus(0, X) >= X  because [10], by (Star) 
  10] plus*(0, X) >= X  because [4], by (Select) 

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

We can thus remove the following rules:

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

  times(X, s(Y)) >? plus(times(X, Y), X) 
  plus(0, X) >? X 

about to try horpo

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

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

With these choices, we have:

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

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

We can thus remove the following rules:

  times(X, s(Y)) => plus(times(X, Y), X) 
  plus(0, X) => 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 +++

[Kop12]  C. Kop.  Higher Order Termination.  PhD Thesis, 2012.