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

  !minus : [o * o] --> o 
  !plus : [o * o] --> o 
  !times : [o * o] --> o 
  0 : [] --> o 
  1 : [] --> o 
  D : [o] --> o 
  constant : [] --> o 
  t : [] --> o 

  D(t) => 1 
  D(constant) => 0 
  D(!plus(X, Y)) => !plus(D(X), D(Y)) 
  D(!times(X, Y)) => !plus(!times(Y, D(X)), !times(X, D(Y))) 
  D(!minus(X, Y)) => !minus(D(X), D(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]):

  D(t) >? 1 
  D(constant) >? 0 
  D(!plus(X, Y)) >? !plus(D(X), D(Y)) 
  D(!times(X, Y)) >? !plus(!times(Y, D(X)), !times(X, D(Y))) 
  D(!minus(X, Y)) >? !minus(D(X), D(Y)) 

about to try horpo

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

Argument functions:

  [[0]] = _|_ 
  [[1]] = _|_ 

We choose Lex = {} and Mul = {!minus, !plus, !times, D, constant, t}, and the following precedence: !times = D > !plus > t > constant > !minus

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

  D(t) >= _|_ 
  D(constant) >= _|_ 
  D(!plus(X, Y)) >= !plus(D(X), D(Y)) 
  D(!times(X, Y)) >= !plus(!times(Y, D(X)), !times(X, D(Y))) 
  D(!minus(X, Y)) > !minus(D(X), D(Y)) 

With these choices, we have:

  1] D(t) >= _|_  by (Bot) 

  2] D(constant) >= _|_  by (Bot) 

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

  13] D(!times(X, Y)) >= !plus(!times(Y, D(X)), !times(X, D(Y)))  because [14], by (Star) 
  14] D*(!times(X, Y)) >= !plus(!times(Y, D(X)), !times(X, D(Y)))  because D > !plus, [15] and [21], by (Copy) 
  15] D*(!times(X, Y)) >= !times(Y, D(X))  because D = !times, D in Mul, [16] and [18], by (Stat) 
  16] !times(X, Y) > Y  because [17], by definition 
  17] !times*(X, Y) >= Y  because [12], by (Select) 
  18] !times(X, Y) > D(X)  because [19], by definition 
  19] !times*(X, Y) >= D(X)  because !times = D, !times in Mul and [20], by (Stat) 
  20] X >= X  by (Meta) 
  21] D*(!times(X, Y)) >= !times(X, D(Y))  because D = !times, D in Mul, [22] and [24], by (Stat) 
  22] !times(X, Y) > X  because [23], by definition 
  23] !times*(X, Y) >= X  because [20], by (Select) 
  24] !times(X, Y) > D(Y)  because [25], by definition 
  25] !times*(X, Y) >= D(Y)  because !times = D, !times in Mul and [26], by (Stat) 
  26] Y >= Y  by (Meta) 

  27] D(!minus(X, Y)) > !minus(D(X), D(Y))  because [28], by definition 
  28] D*(!minus(X, Y)) >= !minus(D(X), D(Y))  because D > !minus, [29] and [32], by (Copy) 
  29] D*(!minus(X, Y)) >= D(X)  because D in Mul and [30], by (Stat) 
  30] !minus(X, Y) > X  because [31], by definition 
  31] !minus*(X, Y) >= X  because [20], by (Select) 
  32] D*(!minus(X, Y)) >= D(Y)  because D in Mul and [33], by (Stat) 
  33] !minus(X, Y) > Y  because [34], by definition 
  34] !minus*(X, Y) >= Y  because [26], by (Select) 

We can thus remove the following rules:

  D(!minus(X, Y)) => !minus(D(X), D(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]):

  D(t) >? 1 
  D(constant) >? 0 
  D(!plus(X, Y)) >? !plus(D(X), D(Y)) 
  D(!times(X, Y)) >? !plus(!times(Y, D(X)), !times(X, D(Y))) 

about to try horpo

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

Argument functions:

  [[0]] = _|_ 
  [[1]] = _|_ 

We choose Lex = {} and Mul = {!plus, !times, D, constant, t}, and the following precedence: constant > t > D > !plus > !times

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

  D(t) >= _|_ 
  D(constant) >= _|_ 
  D(!plus(X, Y)) >= !plus(D(X), D(Y)) 
  D(!times(X, Y)) > !plus(!times(Y, D(X)), !times(X, D(Y))) 

With these choices, we have:

  1] D(t) >= _|_  by (Bot) 

  2] D(constant) >= _|_  by (Bot) 

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

  13] D(!times(X, Y)) > !plus(!times(Y, D(X)), !times(X, D(Y)))  because [14], by definition 
  14] D*(!times(X, Y)) >= !plus(!times(Y, D(X)), !times(X, D(Y)))  because D > !plus, [15] and [22], by (Copy) 
  15] D*(!times(X, Y)) >= !times(Y, D(X))  because D > !times, [16] and [19], by (Copy) 
  16] D*(!times(X, Y)) >= Y  because [17], by (Select) 
  17] !times(X, Y) >= Y  because [18], by (Star) 
  18] !times*(X, Y) >= Y  because [12], by (Select) 
  19] D*(!times(X, Y)) >= D(X)  because D in Mul and [20], by (Stat) 
  20] !times(X, Y) > X  because [21], by definition 
  21] !times*(X, Y) >= X  because [8], by (Select) 
  22] D*(!times(X, Y)) >= !times(X, D(Y))  because D > !times, [23] and [25], by (Copy) 
  23] D*(!times(X, Y)) >= X  because [24], by (Select) 
  24] !times(X, Y) >= X  because [21], by (Star) 
  25] D*(!times(X, Y)) >= D(Y)  because D in Mul and [26], by (Stat) 
  26] !times(X, Y) > Y  because [27], by definition 
  27] !times*(X, Y) >= Y  because [12], by (Select) 

We can thus remove the following rules:

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

  D(t) >? 1 
  D(constant) >? 0 
  D(!plus(X, Y)) >? !plus(D(X), D(Y)) 

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

The following interpretation satisfies the requirements:

  !plus = \y0y1.y0 + y1 
  0 = 0 
  1 = 0 
  D = \y0.3y0 
  constant = 3 
  t = 3 

Using this interpretation, the requirements translate to:

  [[D(t)]] = 9 > 0 = [[1]] 
  [[D(constant)]] = 9 > 0 = [[0]] 
  [[D(!plus(_x0, _x1))]] = 3x0 + 3x1 >= 3x0 + 3x1 = [[!plus(D(_x0), D(_x1))]] 

We can thus remove the following rules:

  D(t) => 1 
  D(constant) => 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]):

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

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

The following interpretation satisfies the requirements:

  !plus = \y0y1.3 + y0 + y1 
  D = \y0.3y0 

Using this interpretation, the requirements translate to:

  [[D(!plus(_x0, _x1))]] = 9 + 3x0 + 3x1 > 3 + 3x0 + 3x1 = [[!plus(D(_x0), D(_x1))]] 

We can thus remove the following rules:

  D(!plus(X, Y)) => !plus(D(X), D(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.