/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 
  a!6220!6220adx : [o] --> o 
  a!6220!6220hd : [o] --> o 
  a!6220!6220incr : [o] --> o 
  a!6220!6220nats : [] --> o 
  a!6220!6220tl : [o] --> o 
  a!6220!6220zeros : [] --> o 
  adx : [o] --> o 
  cons : [o * o] --> o 
  hd : [o] --> o 
  incr : [o] --> o 
  mark : [o] --> o 
  nats : [] --> o 
  s : [o] --> o 
  tl : [o] --> o 
  zeros : [] --> o 

  a!6220!6220nats => a!6220!6220adx(a!6220!6220zeros) 
  a!6220!6220zeros => cons(0, zeros) 
  a!6220!6220incr(cons(X, Y)) => cons(s(X), incr(Y)) 
  a!6220!6220adx(cons(X, Y)) => a!6220!6220incr(cons(X, adx(Y))) 
  a!6220!6220hd(cons(X, Y)) => mark(X) 
  a!6220!6220tl(cons(X, Y)) => mark(Y) 
  mark(nats) => a!6220!6220nats 
  mark(adx(X)) => a!6220!6220adx(mark(X)) 
  mark(zeros) => a!6220!6220zeros 
  mark(incr(X)) => a!6220!6220incr(mark(X)) 
  mark(hd(X)) => a!6220!6220hd(mark(X)) 
  mark(tl(X)) => a!6220!6220tl(mark(X)) 
  mark(cons(X, Y)) => cons(X, Y) 
  mark(0) => 0 
  mark(s(X)) => s(X) 
  a!6220!6220nats => nats 
  a!6220!6220adx(X) => adx(X) 
  a!6220!6220zeros => zeros 
  a!6220!6220incr(X) => incr(X) 
  a!6220!6220hd(X) => hd(X) 
  a!6220!6220tl(X) => tl(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]):

  a!6220!6220nats >? a!6220!6220adx(a!6220!6220zeros) 
  a!6220!6220zeros >? cons(0, zeros) 
  a!6220!6220incr(cons(X, Y)) >? cons(s(X), incr(Y)) 
  a!6220!6220adx(cons(X, Y)) >? a!6220!6220incr(cons(X, adx(Y))) 
  a!6220!6220hd(cons(X, Y)) >? mark(X) 
  a!6220!6220tl(cons(X, Y)) >? mark(Y) 
  mark(nats) >? a!6220!6220nats 
  mark(adx(X)) >? a!6220!6220adx(mark(X)) 
  mark(zeros) >? a!6220!6220zeros 
  mark(incr(X)) >? a!6220!6220incr(mark(X)) 
  mark(hd(X)) >? a!6220!6220hd(mark(X)) 
  mark(tl(X)) >? a!6220!6220tl(mark(X)) 
  mark(cons(X, Y)) >? cons(X, Y) 
  mark(0) >? 0 
  mark(s(X)) >? s(X) 
  a!6220!6220nats >? nats 
  a!6220!6220adx(X) >? adx(X) 
  a!6220!6220zeros >? zeros 
  a!6220!6220incr(X) >? incr(X) 
  a!6220!6220hd(X) >? hd(X) 
  a!6220!6220tl(X) >? tl(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  a!6220!6220adx = \y0.y0 
  a!6220!6220hd = \y0.y0 
  a!6220!6220incr = \y0.y0 
  a!6220!6220nats = 2 
  a!6220!6220tl = \y0.y0 
  a!6220!6220zeros = 0 
  adx = \y0.y0 
  cons = \y0y1.y1 + 2y0 
  hd = \y0.y0 
  incr = \y0.y0 
  mark = \y0.y0 
  nats = 2 
  s = \y0.y0 
  tl = \y0.y0 
  zeros = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220nats]] = 2 > 0 = [[a!6220!6220adx(a!6220!6220zeros)]] 
  [[a!6220!6220zeros]] = 0 >= 0 = [[cons(0, zeros)]] 
  [[a!6220!6220incr(cons(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[cons(s(_x0), incr(_x1))]] 
  [[a!6220!6220adx(cons(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[a!6220!6220incr(cons(_x0, adx(_x1)))]] 
  [[a!6220!6220hd(cons(_x0, _x1))]] = x1 + 2x0 >= x0 = [[mark(_x0)]] 
  [[a!6220!6220tl(cons(_x0, _x1))]] = x1 + 2x0 >= x1 = [[mark(_x1)]] 
  [[mark(nats)]] = 2 >= 2 = [[a!6220!6220nats]] 
  [[mark(adx(_x0))]] = x0 >= x0 = [[a!6220!6220adx(mark(_x0))]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(incr(_x0))]] = x0 >= x0 = [[a!6220!6220incr(mark(_x0))]] 
  [[mark(hd(_x0))]] = x0 >= x0 = [[a!6220!6220hd(mark(_x0))]] 
  [[mark(tl(_x0))]] = x0 >= x0 = [[a!6220!6220tl(mark(_x0))]] 
  [[mark(cons(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[cons(_x0, _x1)]] 
  [[mark(0)]] = 0 >= 0 = [[0]] 
  [[mark(s(_x0))]] = x0 >= x0 = [[s(_x0)]] 
  [[a!6220!6220nats]] = 2 >= 2 = [[nats]] 
  [[a!6220!6220adx(_x0)]] = x0 >= x0 = [[adx(_x0)]] 
  [[a!6220!6220zeros]] = 0 >= 0 = [[zeros]] 
  [[a!6220!6220incr(_x0)]] = x0 >= x0 = [[incr(_x0)]] 
  [[a!6220!6220hd(_x0)]] = x0 >= x0 = [[hd(_x0)]] 
  [[a!6220!6220tl(_x0)]] = x0 >= x0 = [[tl(_x0)]] 

We can thus remove the following rules:

  a!6220!6220nats => a!6220!6220adx(a!6220!6220zeros) 

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

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

  a!6220!6220zeros >? cons(0, zeros) 
  a!6220!6220incr(cons(X, Y)) >? cons(s(X), incr(Y)) 
  a!6220!6220adx(cons(X, Y)) >? a!6220!6220incr(cons(X, adx(Y))) 
  a!6220!6220hd(cons(X, Y)) >? mark(X) 
  a!6220!6220tl(cons(X, Y)) >? mark(Y) 
  mark(nats) >? a!6220!6220nats 
  mark(adx(X)) >? a!6220!6220adx(mark(X)) 
  mark(zeros) >? a!6220!6220zeros 
  mark(incr(X)) >? a!6220!6220incr(mark(X)) 
  mark(hd(X)) >? a!6220!6220hd(mark(X)) 
  mark(tl(X)) >? a!6220!6220tl(mark(X)) 
  mark(cons(X, Y)) >? cons(X, Y) 
  mark(0) >? 0 
  mark(s(X)) >? s(X) 
  a!6220!6220nats >? nats 
  a!6220!6220adx(X) >? adx(X) 
  a!6220!6220zeros >? zeros 
  a!6220!6220incr(X) >? incr(X) 
  a!6220!6220hd(X) >? hd(X) 
  a!6220!6220tl(X) >? tl(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  a!6220!6220adx = \y0.y0 
  a!6220!6220hd = \y0.2 + y0 
  a!6220!6220incr = \y0.y0 
  a!6220!6220nats = 0 
  a!6220!6220tl = \y0.2 + y0 
  a!6220!6220zeros = 0 
  adx = \y0.y0 
  cons = \y0y1.2y0 + 2y1 
  hd = \y0.1 + y0 
  incr = \y0.y0 
  mark = \y0.2y0 
  nats = 0 
  s = \y0.y0 
  tl = \y0.1 + y0 
  zeros = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220zeros]] = 0 >= 0 = [[cons(0, zeros)]] 
  [[a!6220!6220incr(cons(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[cons(s(_x0), incr(_x1))]] 
  [[a!6220!6220adx(cons(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[a!6220!6220incr(cons(_x0, adx(_x1)))]] 
  [[a!6220!6220hd(cons(_x0, _x1))]] = 2 + 2x0 + 2x1 > 2x0 = [[mark(_x0)]] 
  [[a!6220!6220tl(cons(_x0, _x1))]] = 2 + 2x0 + 2x1 > 2x1 = [[mark(_x1)]] 
  [[mark(nats)]] = 0 >= 0 = [[a!6220!6220nats]] 
  [[mark(adx(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220adx(mark(_x0))]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(incr(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220incr(mark(_x0))]] 
  [[mark(hd(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[a!6220!6220hd(mark(_x0))]] 
  [[mark(tl(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[a!6220!6220tl(mark(_x0))]] 
  [[mark(cons(_x0, _x1))]] = 4x0 + 4x1 >= 2x0 + 2x1 = [[cons(_x0, _x1)]] 
  [[mark(0)]] = 0 >= 0 = [[0]] 
  [[mark(s(_x0))]] = 2x0 >= x0 = [[s(_x0)]] 
  [[a!6220!6220nats]] = 0 >= 0 = [[nats]] 
  [[a!6220!6220adx(_x0)]] = x0 >= x0 = [[adx(_x0)]] 
  [[a!6220!6220zeros]] = 0 >= 0 = [[zeros]] 
  [[a!6220!6220incr(_x0)]] = x0 >= x0 = [[incr(_x0)]] 
  [[a!6220!6220hd(_x0)]] = 2 + x0 > 1 + x0 = [[hd(_x0)]] 
  [[a!6220!6220tl(_x0)]] = 2 + x0 > 1 + x0 = [[tl(_x0)]] 

We can thus remove the following rules:

  a!6220!6220hd(cons(X, Y)) => mark(X) 
  a!6220!6220tl(cons(X, Y)) => mark(Y) 
  a!6220!6220hd(X) => hd(X) 
  a!6220!6220tl(X) => tl(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]):

  a!6220!6220zeros >? cons(0, zeros) 
  a!6220!6220incr(cons(X, Y)) >? cons(s(X), incr(Y)) 
  a!6220!6220adx(cons(X, Y)) >? a!6220!6220incr(cons(X, adx(Y))) 
  mark(nats) >? a!6220!6220nats 
  mark(adx(X)) >? a!6220!6220adx(mark(X)) 
  mark(zeros) >? a!6220!6220zeros 
  mark(incr(X)) >? a!6220!6220incr(mark(X)) 
  mark(hd(X)) >? a!6220!6220hd(mark(X)) 
  mark(tl(X)) >? a!6220!6220tl(mark(X)) 
  mark(cons(X, Y)) >? cons(X, Y) 
  mark(0) >? 0 
  mark(s(X)) >? s(X) 
  a!6220!6220nats >? nats 
  a!6220!6220adx(X) >? adx(X) 
  a!6220!6220zeros >? zeros 
  a!6220!6220incr(X) >? incr(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  a!6220!6220adx = \y0.y0 
  a!6220!6220hd = \y0.y0 
  a!6220!6220incr = \y0.y0 
  a!6220!6220nats = 0 
  a!6220!6220tl = \y0.y0 
  a!6220!6220zeros = 0 
  adx = \y0.y0 
  cons = \y0y1.y0 + y1 
  hd = \y0.3 + 3y0 
  incr = \y0.y0 
  mark = \y0.2y0 
  nats = 0 
  s = \y0.y0 
  tl = \y0.3 + 3y0 
  zeros = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220zeros]] = 0 >= 0 = [[cons(0, zeros)]] 
  [[a!6220!6220incr(cons(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[cons(s(_x0), incr(_x1))]] 
  [[a!6220!6220adx(cons(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[a!6220!6220incr(cons(_x0, adx(_x1)))]] 
  [[mark(nats)]] = 0 >= 0 = [[a!6220!6220nats]] 
  [[mark(adx(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220adx(mark(_x0))]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(incr(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220incr(mark(_x0))]] 
  [[mark(hd(_x0))]] = 6 + 6x0 > 2x0 = [[a!6220!6220hd(mark(_x0))]] 
  [[mark(tl(_x0))]] = 6 + 6x0 > 2x0 = [[a!6220!6220tl(mark(_x0))]] 
  [[mark(cons(_x0, _x1))]] = 2x0 + 2x1 >= x0 + x1 = [[cons(_x0, _x1)]] 
  [[mark(0)]] = 0 >= 0 = [[0]] 
  [[mark(s(_x0))]] = 2x0 >= x0 = [[s(_x0)]] 
  [[a!6220!6220nats]] = 0 >= 0 = [[nats]] 
  [[a!6220!6220adx(_x0)]] = x0 >= x0 = [[adx(_x0)]] 
  [[a!6220!6220zeros]] = 0 >= 0 = [[zeros]] 
  [[a!6220!6220incr(_x0)]] = x0 >= x0 = [[incr(_x0)]] 

We can thus remove the following rules:

  mark(hd(X)) => a!6220!6220hd(mark(X)) 
  mark(tl(X)) => a!6220!6220tl(mark(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]):

  a!6220!6220zeros >? cons(0, zeros) 
  a!6220!6220incr(cons(X, Y)) >? cons(s(X), incr(Y)) 
  a!6220!6220adx(cons(X, Y)) >? a!6220!6220incr(cons(X, adx(Y))) 
  mark(nats) >? a!6220!6220nats 
  mark(adx(X)) >? a!6220!6220adx(mark(X)) 
  mark(zeros) >? a!6220!6220zeros 
  mark(incr(X)) >? a!6220!6220incr(mark(X)) 
  mark(cons(X, Y)) >? cons(X, Y) 
  mark(0) >? 0 
  mark(s(X)) >? s(X) 
  a!6220!6220nats >? nats 
  a!6220!6220adx(X) >? adx(X) 
  a!6220!6220zeros >? zeros 
  a!6220!6220incr(X) >? incr(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  a!6220!6220adx = \y0.2 + y0 
  a!6220!6220incr = \y0.y0 
  a!6220!6220nats = 0 
  a!6220!6220zeros = 0 
  adx = \y0.1 + y0 
  cons = \y0y1.y0 + 2y1 
  incr = \y0.y0 
  mark = \y0.2y0 
  nats = 0 
  s = \y0.y0 
  zeros = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220zeros]] = 0 >= 0 = [[cons(0, zeros)]] 
  [[a!6220!6220incr(cons(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[cons(s(_x0), incr(_x1))]] 
  [[a!6220!6220adx(cons(_x0, _x1))]] = 2 + x0 + 2x1 >= 2 + x0 + 2x1 = [[a!6220!6220incr(cons(_x0, adx(_x1)))]] 
  [[mark(nats)]] = 0 >= 0 = [[a!6220!6220nats]] 
  [[mark(adx(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[a!6220!6220adx(mark(_x0))]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(incr(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220incr(mark(_x0))]] 
  [[mark(cons(_x0, _x1))]] = 2x0 + 4x1 >= x0 + 2x1 = [[cons(_x0, _x1)]] 
  [[mark(0)]] = 0 >= 0 = [[0]] 
  [[mark(s(_x0))]] = 2x0 >= x0 = [[s(_x0)]] 
  [[a!6220!6220nats]] = 0 >= 0 = [[nats]] 
  [[a!6220!6220adx(_x0)]] = 2 + x0 > 1 + x0 = [[adx(_x0)]] 
  [[a!6220!6220zeros]] = 0 >= 0 = [[zeros]] 
  [[a!6220!6220incr(_x0)]] = x0 >= x0 = [[incr(_x0)]] 

We can thus remove the following rules:

  a!6220!6220adx(X) => adx(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]):

  a!6220!6220zeros >? cons(0, zeros) 
  a!6220!6220incr(cons(X, Y)) >? cons(s(X), incr(Y)) 
  a!6220!6220adx(cons(X, Y)) >? a!6220!6220incr(cons(X, adx(Y))) 
  mark(nats) >? a!6220!6220nats 
  mark(adx(X)) >? a!6220!6220adx(mark(X)) 
  mark(zeros) >? a!6220!6220zeros 
  mark(incr(X)) >? a!6220!6220incr(mark(X)) 
  mark(cons(X, Y)) >? cons(X, Y) 
  mark(0) >? 0 
  mark(s(X)) >? s(X) 
  a!6220!6220nats >? nats 
  a!6220!6220zeros >? zeros 
  a!6220!6220incr(X) >? incr(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  a!6220!6220adx = \y0.2y0 
  a!6220!6220incr = \y0.y0 
  a!6220!6220nats = 0 
  a!6220!6220zeros = 2 
  adx = \y0.2y0 
  cons = \y0y1.y0 + 2y1 
  incr = \y0.y0 
  mark = \y0.2y0 
  nats = 0 
  s = \y0.y0 
  zeros = 1 

Using this interpretation, the requirements translate to:

  [[a!6220!6220zeros]] = 2 >= 2 = [[cons(0, zeros)]] 
  [[a!6220!6220incr(cons(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[cons(s(_x0), incr(_x1))]] 
  [[a!6220!6220adx(cons(_x0, _x1))]] = 2x0 + 4x1 >= x0 + 4x1 = [[a!6220!6220incr(cons(_x0, adx(_x1)))]] 
  [[mark(nats)]] = 0 >= 0 = [[a!6220!6220nats]] 
  [[mark(adx(_x0))]] = 4x0 >= 4x0 = [[a!6220!6220adx(mark(_x0))]] 
  [[mark(zeros)]] = 2 >= 2 = [[a!6220!6220zeros]] 
  [[mark(incr(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220incr(mark(_x0))]] 
  [[mark(cons(_x0, _x1))]] = 2x0 + 4x1 >= x0 + 2x1 = [[cons(_x0, _x1)]] 
  [[mark(0)]] = 0 >= 0 = [[0]] 
  [[mark(s(_x0))]] = 2x0 >= x0 = [[s(_x0)]] 
  [[a!6220!6220nats]] = 0 >= 0 = [[nats]] 
  [[a!6220!6220zeros]] = 2 > 1 = [[zeros]] 
  [[a!6220!6220incr(_x0)]] = x0 >= x0 = [[incr(_x0)]] 

We can thus remove the following rules:

  a!6220!6220zeros => zeros 

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

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

  a!6220!6220zeros >? cons(0, zeros) 
  a!6220!6220incr(cons(X, Y)) >? cons(s(X), incr(Y)) 
  a!6220!6220adx(cons(X, Y)) >? a!6220!6220incr(cons(X, adx(Y))) 
  mark(nats) >? a!6220!6220nats 
  mark(adx(X)) >? a!6220!6220adx(mark(X)) 
  mark(zeros) >? a!6220!6220zeros 
  mark(incr(X)) >? a!6220!6220incr(mark(X)) 
  mark(cons(X, Y)) >? cons(X, Y) 
  mark(0) >? 0 
  mark(s(X)) >? s(X) 
  a!6220!6220nats >? nats 
  a!6220!6220incr(X) >? incr(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  a!6220!6220adx = \y0.y0 
  a!6220!6220incr = \y0.y0 
  a!6220!6220nats = 2 
  a!6220!6220zeros = 0 
  adx = \y0.y0 
  cons = \y0y1.y0 + y1 
  incr = \y0.y0 
  mark = \y0.2y0 
  nats = 1 
  s = \y0.y0 
  zeros = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220zeros]] = 0 >= 0 = [[cons(0, zeros)]] 
  [[a!6220!6220incr(cons(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[cons(s(_x0), incr(_x1))]] 
  [[a!6220!6220adx(cons(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[a!6220!6220incr(cons(_x0, adx(_x1)))]] 
  [[mark(nats)]] = 2 >= 2 = [[a!6220!6220nats]] 
  [[mark(adx(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220adx(mark(_x0))]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(incr(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220incr(mark(_x0))]] 
  [[mark(cons(_x0, _x1))]] = 2x0 + 2x1 >= x0 + x1 = [[cons(_x0, _x1)]] 
  [[mark(0)]] = 0 >= 0 = [[0]] 
  [[mark(s(_x0))]] = 2x0 >= x0 = [[s(_x0)]] 
  [[a!6220!6220nats]] = 2 > 1 = [[nats]] 
  [[a!6220!6220incr(_x0)]] = x0 >= x0 = [[incr(_x0)]] 

We can thus remove the following rules:

  a!6220!6220nats => nats 

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

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

  a!6220!6220zeros >? cons(0, zeros) 
  a!6220!6220incr(cons(X, Y)) >? cons(s(X), incr(Y)) 
  a!6220!6220adx(cons(X, Y)) >? a!6220!6220incr(cons(X, adx(Y))) 
  mark(nats) >? a!6220!6220nats 
  mark(adx(X)) >? a!6220!6220adx(mark(X)) 
  mark(zeros) >? a!6220!6220zeros 
  mark(incr(X)) >? a!6220!6220incr(mark(X)) 
  mark(cons(X, Y)) >? cons(X, Y) 
  mark(0) >? 0 
  mark(s(X)) >? s(X) 
  a!6220!6220incr(X) >? incr(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  a!6220!6220adx = \y0.y0 
  a!6220!6220incr = \y0.y0 
  a!6220!6220nats = 0 
  a!6220!6220zeros = 0 
  adx = \y0.y0 
  cons = \y0y1.y0 + y1 
  incr = \y0.y0 
  mark = \y0.2y0 
  nats = 3 
  s = \y0.y0 
  zeros = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220zeros]] = 0 >= 0 = [[cons(0, zeros)]] 
  [[a!6220!6220incr(cons(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[cons(s(_x0), incr(_x1))]] 
  [[a!6220!6220adx(cons(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[a!6220!6220incr(cons(_x0, adx(_x1)))]] 
  [[mark(nats)]] = 6 > 0 = [[a!6220!6220nats]] 
  [[mark(adx(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220adx(mark(_x0))]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(incr(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220incr(mark(_x0))]] 
  [[mark(cons(_x0, _x1))]] = 2x0 + 2x1 >= x0 + x1 = [[cons(_x0, _x1)]] 
  [[mark(0)]] = 0 >= 0 = [[0]] 
  [[mark(s(_x0))]] = 2x0 >= x0 = [[s(_x0)]] 
  [[a!6220!6220incr(_x0)]] = x0 >= x0 = [[incr(_x0)]] 

We can thus remove the following rules:

  mark(nats) => a!6220!6220nats 

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

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

  a!6220!6220zeros >? cons(0, zeros) 
  a!6220!6220incr(cons(X, Y)) >? cons(s(X), incr(Y)) 
  a!6220!6220adx(cons(X, Y)) >? a!6220!6220incr(cons(X, adx(Y))) 
  mark(adx(X)) >? a!6220!6220adx(mark(X)) 
  mark(zeros) >? a!6220!6220zeros 
  mark(incr(X)) >? a!6220!6220incr(mark(X)) 
  mark(cons(X, Y)) >? cons(X, Y) 
  mark(0) >? 0 
  mark(s(X)) >? s(X) 
  a!6220!6220incr(X) >? incr(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  a!6220!6220adx = \y0.y0 
  a!6220!6220incr = \y0.y0 
  a!6220!6220zeros = 2 
  adx = \y0.y0 
  cons = \y0y1.y0 + 2y1 
  incr = \y0.y0 
  mark = \y0.3y0 
  s = \y0.y0 
  zeros = 1 

Using this interpretation, the requirements translate to:

  [[a!6220!6220zeros]] = 2 >= 2 = [[cons(0, zeros)]] 
  [[a!6220!6220incr(cons(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[cons(s(_x0), incr(_x1))]] 
  [[a!6220!6220adx(cons(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[a!6220!6220incr(cons(_x0, adx(_x1)))]] 
  [[mark(adx(_x0))]] = 3x0 >= 3x0 = [[a!6220!6220adx(mark(_x0))]] 
  [[mark(zeros)]] = 3 > 2 = [[a!6220!6220zeros]] 
  [[mark(incr(_x0))]] = 3x0 >= 3x0 = [[a!6220!6220incr(mark(_x0))]] 
  [[mark(cons(_x0, _x1))]] = 3x0 + 6x1 >= x0 + 2x1 = [[cons(_x0, _x1)]] 
  [[mark(0)]] = 0 >= 0 = [[0]] 
  [[mark(s(_x0))]] = 3x0 >= x0 = [[s(_x0)]] 
  [[a!6220!6220incr(_x0)]] = x0 >= x0 = [[incr(_x0)]] 

We can thus remove the following rules:

  mark(zeros) => a!6220!6220zeros 

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

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

  a!6220!6220zeros >? cons(0, zeros) 
  a!6220!6220incr(cons(X, Y)) >? cons(s(X), incr(Y)) 
  a!6220!6220adx(cons(X, Y)) >? a!6220!6220incr(cons(X, adx(Y))) 
  mark(adx(X)) >? a!6220!6220adx(mark(X)) 
  mark(incr(X)) >? a!6220!6220incr(mark(X)) 
  mark(cons(X, Y)) >? cons(X, Y) 
  mark(0) >? 0 
  mark(s(X)) >? s(X) 
  a!6220!6220incr(X) >? incr(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  a!6220!6220adx = \y0.y0 
  a!6220!6220incr = \y0.y0 
  a!6220!6220zeros = 3 
  adx = \y0.y0 
  cons = \y0y1.2y0 + 2y1 
  incr = \y0.y0 
  mark = \y0.2y0 
  s = \y0.y0 
  zeros = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220zeros]] = 3 > 0 = [[cons(0, zeros)]] 
  [[a!6220!6220incr(cons(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[cons(s(_x0), incr(_x1))]] 
  [[a!6220!6220adx(cons(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[a!6220!6220incr(cons(_x0, adx(_x1)))]] 
  [[mark(adx(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220adx(mark(_x0))]] 
  [[mark(incr(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220incr(mark(_x0))]] 
  [[mark(cons(_x0, _x1))]] = 4x0 + 4x1 >= 2x0 + 2x1 = [[cons(_x0, _x1)]] 
  [[mark(0)]] = 0 >= 0 = [[0]] 
  [[mark(s(_x0))]] = 2x0 >= x0 = [[s(_x0)]] 
  [[a!6220!6220incr(_x0)]] = x0 >= x0 = [[incr(_x0)]] 

We can thus remove the following rules:

  a!6220!6220zeros => cons(0, zeros) 

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

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

  a!6220!6220incr(cons(X, Y)) >? cons(s(X), incr(Y)) 
  a!6220!6220adx(cons(X, Y)) >? a!6220!6220incr(cons(X, adx(Y))) 
  mark(adx(X)) >? a!6220!6220adx(mark(X)) 
  mark(incr(X)) >? a!6220!6220incr(mark(X)) 
  mark(cons(X, Y)) >? cons(X, Y) 
  mark(0) >? 0 
  mark(s(X)) >? s(X) 
  a!6220!6220incr(X) >? incr(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  a!6220!6220adx = \y0.y0 
  a!6220!6220incr = \y0.y0 
  adx = \y0.y0 
  cons = \y0y1.y0 + y1 
  incr = \y0.y0 
  mark = \y0.2 + y0 
  s = \y0.y0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220incr(cons(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[cons(s(_x0), incr(_x1))]] 
  [[a!6220!6220adx(cons(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[a!6220!6220incr(cons(_x0, adx(_x1)))]] 
  [[mark(adx(_x0))]] = 2 + x0 >= 2 + x0 = [[a!6220!6220adx(mark(_x0))]] 
  [[mark(incr(_x0))]] = 2 + x0 >= 2 + x0 = [[a!6220!6220incr(mark(_x0))]] 
  [[mark(cons(_x0, _x1))]] = 2 + x0 + x1 > x0 + x1 = [[cons(_x0, _x1)]] 
  [[mark(0)]] = 2 > 0 = [[0]] 
  [[mark(s(_x0))]] = 2 + x0 > x0 = [[s(_x0)]] 
  [[a!6220!6220incr(_x0)]] = x0 >= x0 = [[incr(_x0)]] 

We can thus remove the following rules:

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

  a!6220!6220incr(cons(X, Y)) >? cons(s(X), incr(Y)) 
  a!6220!6220adx(cons(X, Y)) >? a!6220!6220incr(cons(X, adx(Y))) 
  mark(adx(X)) >? a!6220!6220adx(mark(X)) 
  mark(incr(X)) >? a!6220!6220incr(mark(X)) 
  a!6220!6220incr(X) >? incr(X) 

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

The following interpretation satisfies the requirements:

  a!6220!6220adx = \y0.2y0 
  a!6220!6220incr = \y0.y0 
  adx = \y0.2y0 
  cons = \y0y1.1 + y0 + 2y1 
  incr = \y0.y0 
  mark = \y0.y0 
  s = \y0.y0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220incr(cons(_x0, _x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[cons(s(_x0), incr(_x1))]] 
  [[a!6220!6220adx(cons(_x0, _x1))]] = 2 + 2x0 + 4x1 > 1 + x0 + 4x1 = [[a!6220!6220incr(cons(_x0, adx(_x1)))]] 
  [[mark(adx(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220adx(mark(_x0))]] 
  [[mark(incr(_x0))]] = x0 >= x0 = [[a!6220!6220incr(mark(_x0))]] 
  [[a!6220!6220incr(_x0)]] = x0 >= x0 = [[incr(_x0)]] 

We can thus remove the following rules:

  a!6220!6220adx(cons(X, Y)) => a!6220!6220incr(cons(X, adx(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]):

  a!6220!6220incr(cons(X, Y)) >? cons(s(X), incr(Y)) 
  mark(adx(X)) >? a!6220!6220adx(mark(X)) 
  mark(incr(X)) >? a!6220!6220incr(mark(X)) 
  a!6220!6220incr(X) >? incr(X) 

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

The following interpretation satisfies the requirements:

  a!6220!6220adx = \y0.y0 
  a!6220!6220incr = \y0.y0 
  adx = \y0.3 + 3y0 
  cons = \y0y1.y0 + y1 
  incr = \y0.y0 
  mark = \y0.y0 
  s = \y0.y0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220incr(cons(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[cons(s(_x0), incr(_x1))]] 
  [[mark(adx(_x0))]] = 3 + 3x0 > x0 = [[a!6220!6220adx(mark(_x0))]] 
  [[mark(incr(_x0))]] = x0 >= x0 = [[a!6220!6220incr(mark(_x0))]] 
  [[a!6220!6220incr(_x0)]] = x0 >= x0 = [[incr(_x0)]] 

We can thus remove the following rules:

  mark(adx(X)) => a!6220!6220adx(mark(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]):

  a!6220!6220incr(cons(X, Y)) >? cons(s(X), incr(Y)) 
  mark(incr(X)) >? a!6220!6220incr(mark(X)) 
  a!6220!6220incr(X) >? incr(X) 

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

The following interpretation satisfies the requirements:

  a!6220!6220incr = \y0.2y0 
  cons = \y0y1.2 + y1 + 2y0 
  incr = \y0.2y0 
  mark = \y0.y0 
  s = \y0.y0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220incr(cons(_x0, _x1))]] = 4 + 2x1 + 4x0 > 2 + 2x0 + 2x1 = [[cons(s(_x0), incr(_x1))]] 
  [[mark(incr(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220incr(mark(_x0))]] 
  [[a!6220!6220incr(_x0)]] = 2x0 >= 2x0 = [[incr(_x0)]] 

We can thus remove the following rules:

  a!6220!6220incr(cons(X, Y)) => cons(s(X), incr(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]):

  mark(incr(X)) >? a!6220!6220incr(mark(X)) 
  a!6220!6220incr(X) >? incr(X) 

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

The following interpretation satisfies the requirements:

  a!6220!6220incr = \y0.1 + y0 
  incr = \y0.1 + y0 
  mark = \y0.2y0 

Using this interpretation, the requirements translate to:

  [[mark(incr(_x0))]] = 2 + 2x0 > 1 + 2x0 = [[a!6220!6220incr(mark(_x0))]] 
  [[a!6220!6220incr(_x0)]] = 1 + x0 >= 1 + x0 = [[incr(_x0)]] 

We can thus remove the following rules:

  mark(incr(X)) => a!6220!6220incr(mark(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]):

  a!6220!6220incr(X) >? incr(X) 

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

The following interpretation satisfies the requirements:

  a!6220!6220incr = \y0.3 + 3y0 
  incr = \y0.y0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220incr(_x0)]] = 3 + 3x0 > x0 = [[incr(_x0)]] 

We can thus remove the following rules:

  a!6220!6220incr(X) => incr(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.