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

  a : [] --> o 
  div : [o * o] --> o 
  dx : [o] --> o 
  exp : [o * o] --> o 
  ln : [o] --> o 
  minus : [o * o] --> o 
  neg : [o] --> o 
  one : [] --> o 
  plus : [o * o] --> o 
  times : [o * o] --> o 
  two : [] --> o 
  zero : [] --> o 

  dx(X) => one 
  dx(a) => zero 
  dx(plus(X, Y)) => plus(dx(X), dx(Y)) 
  dx(times(X, Y)) => plus(times(Y, dx(X)), times(X, dx(Y))) 
  dx(minus(X, Y)) => minus(dx(X), dx(Y)) 
  dx(neg(X)) => neg(dx(X)) 
  dx(div(X, Y)) => minus(div(dx(X), Y), times(X, div(dx(Y), exp(Y, two)))) 
  dx(ln(X)) => div(dx(X), X) 
  dx(exp(X, Y)) => plus(times(Y, times(exp(X, minus(Y, one)), dx(X))), times(exp(X, Y), times(ln(X), dx(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]):

  dx(X) >? one 
  dx(a) >? zero 
  dx(plus(X, Y)) >? plus(dx(X), dx(Y)) 
  dx(times(X, Y)) >? plus(times(Y, dx(X)), times(X, dx(Y))) 
  dx(minus(X, Y)) >? minus(dx(X), dx(Y)) 
  dx(neg(X)) >? neg(dx(X)) 
  dx(div(X, Y)) >? minus(div(dx(X), Y), times(X, div(dx(Y), exp(Y, two)))) 
  dx(ln(X)) >? div(dx(X), X) 
  dx(exp(X, Y)) >? plus(times(Y, times(exp(X, minus(Y, one)), dx(X))), times(exp(X, Y), times(ln(X), dx(Y)))) 

about to try horpo

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

Argument functions:

  [[neg(x_1)]] = x_1 
  [[one]] = _|_ 
  [[two]] = _|_ 
  [[zero]] = _|_ 

We choose Lex = {} and Mul = {a, div, dx, exp, ln, minus, plus, times}, and the following precedence: a > dx = exp > plus > minus > ln > times > div

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

  dx(X) > _|_ 
  dx(a) >= _|_ 
  dx(plus(X, Y)) > plus(dx(X), dx(Y)) 
  dx(times(X, Y)) > plus(times(Y, dx(X)), times(X, dx(Y))) 
  dx(minus(X, Y)) >= minus(dx(X), dx(Y)) 
  dx(X) >= dx(X) 
  dx(div(X, Y)) >= minus(div(dx(X), Y), times(X, div(dx(Y), exp(Y, _|_)))) 
  dx(ln(X)) >= div(dx(X), X) 
  dx(exp(X, Y)) > plus(times(Y, times(exp(X, minus(Y, _|_)), dx(X))), times(exp(X, Y), times(ln(X), dx(Y)))) 

With these choices, we have:

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

  3] dx(a) >= _|_  by (Bot) 

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

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

  29] dx(minus(X, Y)) >= minus(dx(X), dx(Y))  because [30], by (Star) 
  30] dx*(minus(X, Y)) >= minus(dx(X), dx(Y))  because dx > minus, [31] and [34], by (Copy) 
  31] dx*(minus(X, Y)) >= dx(X)  because dx in Mul and [32], by (Stat) 
  32] minus(X, Y) > X  because [33], by definition 
  33] minus*(X, Y) >= X  because [9], by (Select) 
  34] dx*(minus(X, Y)) >= dx(Y)  because dx in Mul and [35], by (Stat) 
  35] minus(X, Y) > Y  because [36], by definition 
  36] minus*(X, Y) >= Y  because [13], by (Select) 

  37] dx(X) >= dx(X)  because dx in Mul and [38], by (Fun) 
  38] X >= X  by (Meta) 

  39] dx(div(X, Y)) >= minus(div(dx(X), Y), times(X, div(dx(Y), exp(Y, _|_))))  because [40], by (Star) 
  40] dx*(div(X, Y)) >= minus(div(dx(X), Y), times(X, div(dx(Y), exp(Y, _|_))))  because dx > minus, [41] and [48], by (Copy) 
  41] dx*(div(X, Y)) >= div(dx(X), Y)  because dx > div, [42] and [45], by (Copy) 
  42] dx*(div(X, Y)) >= dx(X)  because dx in Mul and [43], by (Stat) 
  43] div(X, Y) > X  because [44], by definition 
  44] div*(X, Y) >= X  because [38], by (Select) 
  45] dx*(div(X, Y)) >= Y  because [46], by (Select) 
  46] div(X, Y) >= Y  because [47], by (Star) 
  47] div*(X, Y) >= Y  because [13], by (Select) 
  48] dx*(div(X, Y)) >= times(X, div(dx(Y), exp(Y, _|_)))  because dx > times, [49] and [51], by (Copy) 
  49] dx*(div(X, Y)) >= X  because [50], by (Select) 
  50] div(X, Y) >= X  because [44], by (Star) 
  51] dx*(div(X, Y)) >= div(dx(Y), exp(Y, _|_))  because dx > div, [52] and [55], by (Copy) 
  52] dx*(div(X, Y)) >= dx(Y)  because dx in Mul and [53], by (Stat) 
  53] div(X, Y) > Y  because [54], by definition 
  54] div*(X, Y) >= Y  because [13], by (Select) 
  55] dx*(div(X, Y)) >= exp(Y, _|_)  because dx = exp, dx in Mul, [53] and [56], by (Stat) 
  56] div(X, Y) > _|_  because [57], by definition 
  57] div*(X, Y) >= _|_  by (Bot) 

  58] dx(ln(X)) >= div(dx(X), X)  because [59], by (Star) 
  59] dx*(ln(X)) >= div(dx(X), X)  because dx > div, [60] and [63], by (Copy) 
  60] dx*(ln(X)) >= dx(X)  because dx in Mul and [61], by (Stat) 
  61] ln(X) > X  because [62], by definition 
  62] ln*(X) >= X  because [38], by (Select) 
  63] dx*(ln(X)) >= X  because [64], by (Select) 
  64] ln(X) >= X  because [62], by (Star) 

  65] dx(exp(X, Y)) > plus(times(Y, times(exp(X, minus(Y, _|_)), dx(X))), times(exp(X, Y), times(ln(X), dx(Y))))  because [66], by definition 
  66] dx*(exp(X, Y)) >= plus(times(Y, times(exp(X, minus(Y, _|_)), dx(X))), times(exp(X, Y), times(ln(X), dx(Y))))  because dx > plus, [67] and [80], by (Copy) 
  67] dx*(exp(X, Y)) >= times(Y, times(exp(X, minus(Y, _|_)), dx(X)))  because dx > times, [68] and [71], by (Copy) 
  68] dx*(exp(X, Y)) >= Y  because [69], by (Select) 
  69] exp(X, Y) >= Y  because [70], by (Star) 
  70] exp*(X, Y) >= Y  because [13], by (Select) 
  71] dx*(exp(X, Y)) >= times(exp(X, minus(Y, _|_)), dx(X))  because dx > times, [72] and [79], by (Copy) 
  72] dx*(exp(X, Y)) >= exp(X, minus(Y, _|_))  because dx = exp, dx in Mul, [73] and [75], by (Stat) 
  73] exp(X, Y) > X  because [74], by definition 
  74] exp*(X, Y) >= X  because [38], by (Select) 
  75] exp(X, Y) > minus(Y, _|_)  because [76], by definition 
  76] exp*(X, Y) >= minus(Y, _|_)  because exp > minus, [77] and [78], by (Copy) 
  77] exp*(X, Y) >= Y  because [13], by (Select) 
  78] exp*(X, Y) >= _|_  by (Bot) 
  79] dx*(exp(X, Y)) >= dx(X)  because dx in Mul and [73], by (Stat) 
  80] dx*(exp(X, Y)) >= times(exp(X, Y), times(ln(X), dx(Y)))  because dx > times, [81] and [83], by (Copy) 
  81] dx*(exp(X, Y)) >= exp(X, Y)  because dx = exp, dx in Mul, [73] and [82], by (Stat) 
  82] exp(X, Y) > Y  because [77], by definition 
  83] dx*(exp(X, Y)) >= times(ln(X), dx(Y))  because dx > times, [84] and [87], by (Copy) 
  84] dx*(exp(X, Y)) >= ln(X)  because dx > ln and [85], by (Copy) 
  85] dx*(exp(X, Y)) >= X  because [86], by (Select) 
  86] exp(X, Y) >= X  because [74], by (Star) 
  87] dx*(exp(X, Y)) >= dx(Y)  because dx in Mul and [82], by (Stat) 

We can thus remove the following rules:

  dx(X) => one 
  dx(plus(X, Y)) => plus(dx(X), dx(Y)) 
  dx(times(X, Y)) => plus(times(Y, dx(X)), times(X, dx(Y))) 
  dx(exp(X, Y)) => plus(times(Y, times(exp(X, minus(Y, one)), dx(X))), times(exp(X, Y), times(ln(X), dx(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]):

  dx(a) >? zero 
  dx(minus(X, Y)) >? minus(dx(X), dx(Y)) 
  dx(neg(X)) >? neg(dx(X)) 
  dx(div(X, Y)) >? minus(div(dx(X), Y), times(X, div(dx(Y), exp(Y, two)))) 
  dx(ln(X)) >? div(dx(X), X) 

about to try horpo

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

Argument functions:

  [[two]] = _|_ 
  [[zero]] = _|_ 

We choose Lex = {} and Mul = {a, div, dx, exp, ln, minus, neg, times}, and the following precedence: dx = neg > div > exp > a > minus > times > ln

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

  dx(a) >= _|_ 
  dx(minus(X, Y)) >= minus(dx(X), dx(Y)) 
  dx(neg(X)) >= neg(dx(X)) 
  dx(div(X, Y)) >= minus(div(dx(X), Y), times(X, div(dx(Y), exp(Y, _|_)))) 
  dx(ln(X)) > div(dx(X), X) 

With these choices, we have:

  1] dx(a) >= _|_  by (Bot) 

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

  12] dx(neg(X)) >= neg(dx(X))  because dx = neg, dx in Mul and [13], by (Fun) 
  13] neg(X) >= dx(X)  because neg = dx, neg in Mul and [14], by (Fun) 
  14] X >= X  by (Meta) 

  15] dx(div(X, Y)) >= minus(div(dx(X), Y), times(X, div(dx(Y), exp(Y, _|_))))  because [16], by (Star) 
  16] dx*(div(X, Y)) >= minus(div(dx(X), Y), times(X, div(dx(Y), exp(Y, _|_))))  because dx > minus, [17] and [24], by (Copy) 
  17] dx*(div(X, Y)) >= div(dx(X), Y)  because dx > div, [18] and [21], by (Copy) 
  18] dx*(div(X, Y)) >= dx(X)  because dx in Mul and [19], by (Stat) 
  19] div(X, Y) > X  because [20], by definition 
  20] div*(X, Y) >= X  because [14], by (Select) 
  21] dx*(div(X, Y)) >= Y  because [22], by (Select) 
  22] div(X, Y) >= Y  because [23], by (Star) 
  23] div*(X, Y) >= Y  because [11], by (Select) 
  24] dx*(div(X, Y)) >= times(X, div(dx(Y), exp(Y, _|_)))  because dx > times, [25] and [27], by (Copy) 
  25] dx*(div(X, Y)) >= X  because [26], by (Select) 
  26] div(X, Y) >= X  because [20], by (Star) 
  27] dx*(div(X, Y)) >= div(dx(Y), exp(Y, _|_))  because dx > div, [28] and [31], by (Copy) 
  28] dx*(div(X, Y)) >= dx(Y)  because dx in Mul and [29], by (Stat) 
  29] div(X, Y) > Y  because [30], by definition 
  30] div*(X, Y) >= Y  because [11], by (Select) 
  31] dx*(div(X, Y)) >= exp(Y, _|_)  because dx > exp, [21] and [32], by (Copy) 
  32] dx*(div(X, Y)) >= _|_  by (Bot) 

  33] dx(ln(X)) > div(dx(X), X)  because [34], by definition 
  34] dx*(ln(X)) >= div(dx(X), X)  because dx > div, [35] and [38], by (Copy) 
  35] dx*(ln(X)) >= dx(X)  because dx in Mul and [36], by (Stat) 
  36] ln(X) > X  because [37], by definition 
  37] ln*(X) >= X  because [14], by (Select) 
  38] dx*(ln(X)) >= X  because [39], by (Select) 
  39] ln(X) >= X  because [37], by (Star) 

We can thus remove the following rules:

  dx(ln(X)) => div(dx(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]):

  dx(a) >? zero 
  dx(minus(X, Y)) >? minus(dx(X), dx(Y)) 
  dx(neg(X)) >? neg(dx(X)) 
  dx(div(X, Y)) >? minus(div(dx(X), Y), times(X, div(dx(Y), exp(Y, two)))) 

about to try horpo

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

Argument functions:

  [[two]] = _|_ 
  [[zero]] = _|_ 

We choose Lex = {} and Mul = {a, div, dx, exp, minus, neg, times}, and the following precedence: a > dx = exp > neg > div > minus > times

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

  dx(a) >= _|_ 
  dx(minus(X, Y)) >= minus(dx(X), dx(Y)) 
  dx(neg(X)) >= neg(dx(X)) 
  dx(div(X, Y)) > minus(div(dx(X), Y), times(X, div(dx(Y), exp(Y, _|_)))) 

With these choices, we have:

  1] dx(a) >= _|_  by (Bot) 

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

  12] dx(neg(X)) >= neg(dx(X))  because [13], by (Star) 
  13] dx*(neg(X)) >= neg(dx(X))  because dx > neg and [14], by (Copy) 
  14] dx*(neg(X)) >= dx(X)  because dx in Mul and [15], by (Stat) 
  15] neg(X) > X  because [16], by definition 
  16] neg*(X) >= X  because [7], by (Select) 

  17] dx(div(X, Y)) > minus(div(dx(X), Y), times(X, div(dx(Y), exp(Y, _|_))))  because [18], by definition 
  18] dx*(div(X, Y)) >= minus(div(dx(X), Y), times(X, div(dx(Y), exp(Y, _|_))))  because dx > minus, [19] and [26], by (Copy) 
  19] dx*(div(X, Y)) >= div(dx(X), Y)  because dx > div, [20] and [23], by (Copy) 
  20] dx*(div(X, Y)) >= dx(X)  because dx in Mul and [21], by (Stat) 
  21] div(X, Y) > X  because [22], by definition 
  22] div*(X, Y) >= X  because [7], by (Select) 
  23] dx*(div(X, Y)) >= Y  because [24], by (Select) 
  24] div(X, Y) >= Y  because [25], by (Star) 
  25] div*(X, Y) >= Y  because [11], by (Select) 
  26] dx*(div(X, Y)) >= times(X, div(dx(Y), exp(Y, _|_)))  because dx > times, [27] and [29], by (Copy) 
  27] dx*(div(X, Y)) >= X  because [28], by (Select) 
  28] div(X, Y) >= X  because [22], by (Star) 
  29] dx*(div(X, Y)) >= div(dx(Y), exp(Y, _|_))  because dx > div, [30] and [33], by (Copy) 
  30] dx*(div(X, Y)) >= dx(Y)  because dx in Mul and [31], by (Stat) 
  31] div(X, Y) > Y  because [32], by definition 
  32] div*(X, Y) >= Y  because [11], by (Select) 
  33] dx*(div(X, Y)) >= exp(Y, _|_)  because dx = exp, dx in Mul, [31] and [34], by (Stat) 
  34] div(X, Y) > _|_  because [35], by definition 
  35] div*(X, Y) >= _|_  by (Bot) 

We can thus remove the following rules:

  dx(div(X, Y)) => minus(div(dx(X), Y), times(X, div(dx(Y), exp(Y, two)))) 

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

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

  dx(a) >? zero 
  dx(minus(X, Y)) >? minus(dx(X), dx(Y)) 
  dx(neg(X)) >? neg(dx(X)) 

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

The following interpretation satisfies the requirements:

  a = 3 
  dx = \y0.3y0 
  minus = \y0y1.y0 + y1 
  neg = \y0.y0 
  zero = 0 

Using this interpretation, the requirements translate to:

  [[dx(a)]] = 9 > 0 = [[zero]] 
  [[dx(minus(_x0, _x1))]] = 3x0 + 3x1 >= 3x0 + 3x1 = [[minus(dx(_x0), dx(_x1))]] 
  [[dx(neg(_x0))]] = 3x0 >= 3x0 = [[neg(dx(_x0))]] 

We can thus remove the following rules:

  dx(a) => zero 

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

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

  dx(minus(X, Y)) >? minus(dx(X), dx(Y)) 
  dx(neg(X)) >? neg(dx(X)) 

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

The following interpretation satisfies the requirements:

  dx = \y0.3y0 
  minus = \y0y1.2 + y0 + y1 
  neg = \y0.y0 

Using this interpretation, the requirements translate to:

  [[dx(minus(_x0, _x1))]] = 6 + 3x0 + 3x1 > 2 + 3x0 + 3x1 = [[minus(dx(_x0), dx(_x1))]] 
  [[dx(neg(_x0))]] = 3x0 >= 3x0 = [[neg(dx(_x0))]] 

We can thus remove the following rules:

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

  dx(neg(X)) >? neg(dx(X)) 

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

The following interpretation satisfies the requirements:

  dx = \y0.3y0 
  neg = \y0.1 + y0 

Using this interpretation, the requirements translate to:

  [[dx(neg(_x0))]] = 3 + 3x0 > 1 + 3x0 = [[neg(dx(_x0))]] 

We can thus remove the following rules:

  dx(neg(X)) => neg(dx(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.