/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 
  U11 : [o * o] --> o 
  a!6220!6220U11 : [o * o] --> o 
  a!6220!6220and : [o * o] --> o 
  a!6220!6220isNat : [o] --> o 
  a!6220!6220isNatIList : [o] --> o 
  a!6220!6220isNatList : [o] --> o 
  a!6220!6220length : [o] --> o 
  a!6220!6220zeros : [] --> o 
  and : [o * o] --> o 
  cons : [o * o] --> o 
  isNat : [o] --> o 
  isNatIList : [o] --> o 
  isNatList : [o] --> o 
  length : [o] --> o 
  mark : [o] --> o 
  nil : [] --> o 
  s : [o] --> o 
  tt : [] --> o 
  zeros : [] --> o 

  a!6220!6220zeros => cons(0, zeros) 
  a!6220!6220U11(tt, X) => s(a!6220!6220length(mark(X))) 
  a!6220!6220and(tt, X) => mark(X) 
  a!6220!6220isNat(0) => tt 
  a!6220!6220isNat(length(X)) => a!6220!6220isNatList(X) 
  a!6220!6220isNat(s(X)) => a!6220!6220isNat(X) 
  a!6220!6220isNatIList(X) => a!6220!6220isNatList(X) 
  a!6220!6220isNatIList(zeros) => tt 
  a!6220!6220isNatIList(cons(X, Y)) => a!6220!6220and(a!6220!6220isNat(X), isNatIList(Y)) 
  a!6220!6220isNatList(nil) => tt 
  a!6220!6220isNatList(cons(X, Y)) => a!6220!6220and(a!6220!6220isNat(X), isNatList(Y)) 
  a!6220!6220length(nil) => 0 
  a!6220!6220length(cons(X, Y)) => a!6220!6220U11(a!6220!6220and(a!6220!6220isNatList(Y), isNat(X)), Y) 
  mark(zeros) => a!6220!6220zeros 
  mark(U11(X, Y)) => a!6220!6220U11(mark(X), Y) 
  mark(length(X)) => a!6220!6220length(mark(X)) 
  mark(and(X, Y)) => a!6220!6220and(mark(X), Y) 
  mark(isNat(X)) => a!6220!6220isNat(X) 
  mark(isNatList(X)) => a!6220!6220isNatList(X) 
  mark(isNatIList(X)) => a!6220!6220isNatIList(X) 
  mark(cons(X, Y)) => cons(mark(X), Y) 
  mark(0) => 0 
  mark(tt) => tt 
  mark(s(X)) => s(mark(X)) 
  mark(nil) => nil 
  a!6220!6220zeros => zeros 
  a!6220!6220U11(X, Y) => U11(X, Y) 
  a!6220!6220length(X) => length(X) 
  a!6220!6220and(X, Y) => and(X, Y) 
  a!6220!6220isNat(X) => isNat(X) 
  a!6220!6220isNatList(X) => isNatList(X) 
  a!6220!6220isNatIList(X) => isNatIList(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!6220U11(tt, X) >? s(a!6220!6220length(mark(X))) 
  a!6220!6220and(tt, X) >? mark(X) 
  a!6220!6220isNat(0) >? tt 
  a!6220!6220isNat(length(X)) >? a!6220!6220isNatList(X) 
  a!6220!6220isNat(s(X)) >? a!6220!6220isNat(X) 
  a!6220!6220isNatIList(X) >? a!6220!6220isNatList(X) 
  a!6220!6220isNatIList(zeros) >? tt 
  a!6220!6220isNatIList(cons(X, Y)) >? a!6220!6220and(a!6220!6220isNat(X), isNatIList(Y)) 
  a!6220!6220isNatList(nil) >? tt 
  a!6220!6220isNatList(cons(X, Y)) >? a!6220!6220and(a!6220!6220isNat(X), isNatList(Y)) 
  a!6220!6220length(nil) >? 0 
  a!6220!6220length(cons(X, Y)) >? a!6220!6220U11(a!6220!6220and(a!6220!6220isNatList(Y), isNat(X)), Y) 
  mark(zeros) >? a!6220!6220zeros 
  mark(U11(X, Y)) >? a!6220!6220U11(mark(X), Y) 
  mark(length(X)) >? a!6220!6220length(mark(X)) 
  mark(and(X, Y)) >? a!6220!6220and(mark(X), Y) 
  mark(isNat(X)) >? a!6220!6220isNat(X) 
  mark(isNatList(X)) >? a!6220!6220isNatList(X) 
  mark(isNatIList(X)) >? a!6220!6220isNatIList(X) 
  mark(cons(X, Y)) >? cons(mark(X), Y) 
  mark(0) >? 0 
  mark(tt) >? tt 
  mark(s(X)) >? s(mark(X)) 
  mark(nil) >? nil 
  a!6220!6220zeros >? zeros 
  a!6220!6220U11(X, Y) >? U11(X, Y) 
  a!6220!6220length(X) >? length(X) 
  a!6220!6220and(X, Y) >? and(X, Y) 
  a!6220!6220isNat(X) >? isNat(X) 
  a!6220!6220isNatList(X) >? isNatList(X) 
  a!6220!6220isNatIList(X) >? isNatIList(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  U11 = \y0y1.y0 + 2y1 
  a!6220!6220U11 = \y0y1.y0 + 2y1 
  a!6220!6220and = \y0y1.y0 + 2y1 
  a!6220!6220isNat = \y0.y0 
  a!6220!6220isNatIList = \y0.y0 
  a!6220!6220isNatList = \y0.y0 
  a!6220!6220length = \y0.y0 
  a!6220!6220zeros = 0 
  and = \y0y1.y0 + 2y1 
  cons = \y0y1.2y0 + 3y1 
  isNat = \y0.y0 
  isNatIList = \y0.y0 
  isNatList = \y0.y0 
  length = \y0.y0 
  mark = \y0.y0 
  nil = 1 
  s = \y0.2y0 
  tt = 0 
  zeros = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220zeros]] = 0 >= 0 = [[cons(0, zeros)]] 
  [[a!6220!6220U11(tt, _x0)]] = 2x0 >= 2x0 = [[s(a!6220!6220length(mark(_x0)))]] 
  [[a!6220!6220and(tt, _x0)]] = 2x0 >= x0 = [[mark(_x0)]] 
  [[a!6220!6220isNat(0)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220isNat(length(_x0))]] = x0 >= x0 = [[a!6220!6220isNatList(_x0)]] 
  [[a!6220!6220isNat(s(_x0))]] = 2x0 >= x0 = [[a!6220!6220isNat(_x0)]] 
  [[a!6220!6220isNatIList(_x0)]] = x0 >= x0 = [[a!6220!6220isNatList(_x0)]] 
  [[a!6220!6220isNatIList(zeros)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220isNatIList(cons(_x0, _x1))]] = 2x0 + 3x1 >= x0 + 2x1 = [[a!6220!6220and(a!6220!6220isNat(_x0), isNatIList(_x1))]] 
  [[a!6220!6220isNatList(nil)]] = 1 > 0 = [[tt]] 
  [[a!6220!6220isNatList(cons(_x0, _x1))]] = 2x0 + 3x1 >= x0 + 2x1 = [[a!6220!6220and(a!6220!6220isNat(_x0), isNatList(_x1))]] 
  [[a!6220!6220length(nil)]] = 1 > 0 = [[0]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = 2x0 + 3x1 >= 2x0 + 3x1 = [[a!6220!6220U11(a!6220!6220and(a!6220!6220isNatList(_x1), isNat(_x0)), _x1)]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(U11(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[a!6220!6220U11(mark(_x0), _x1)]] 
  [[mark(length(_x0))]] = x0 >= x0 = [[a!6220!6220length(mark(_x0))]] 
  [[mark(and(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[a!6220!6220and(mark(_x0), _x1)]] 
  [[mark(isNat(_x0))]] = x0 >= x0 = [[a!6220!6220isNat(_x0)]] 
  [[mark(isNatList(_x0))]] = x0 >= x0 = [[a!6220!6220isNatList(_x0)]] 
  [[mark(isNatIList(_x0))]] = x0 >= x0 = [[a!6220!6220isNatIList(_x0)]] 
  [[mark(cons(_x0, _x1))]] = 2x0 + 3x1 >= 2x0 + 3x1 = [[cons(mark(_x0), _x1)]] 
  [[mark(0)]] = 0 >= 0 = [[0]] 
  [[mark(tt)]] = 0 >= 0 = [[tt]] 
  [[mark(s(_x0))]] = 2x0 >= 2x0 = [[s(mark(_x0))]] 
  [[mark(nil)]] = 1 >= 1 = [[nil]] 
  [[a!6220!6220zeros]] = 0 >= 0 = [[zeros]] 
  [[a!6220!6220U11(_x0, _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U11(_x0, _x1)]] 
  [[a!6220!6220length(_x0)]] = x0 >= x0 = [[length(_x0)]] 
  [[a!6220!6220and(_x0, _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[and(_x0, _x1)]] 
  [[a!6220!6220isNat(_x0)]] = x0 >= x0 = [[isNat(_x0)]] 
  [[a!6220!6220isNatList(_x0)]] = x0 >= x0 = [[isNatList(_x0)]] 
  [[a!6220!6220isNatIList(_x0)]] = x0 >= x0 = [[isNatIList(_x0)]] 

We can thus remove the following rules:

  a!6220!6220isNatList(nil) => tt 
  a!6220!6220length(nil) => 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]):

  a!6220!6220zeros >? cons(0, zeros) 
  a!6220!6220U11(tt, X) >? s(a!6220!6220length(mark(X))) 
  a!6220!6220and(tt, X) >? mark(X) 
  a!6220!6220isNat(0) >? tt 
  a!6220!6220isNat(length(X)) >? a!6220!6220isNatList(X) 
  a!6220!6220isNat(s(X)) >? a!6220!6220isNat(X) 
  a!6220!6220isNatIList(X) >? a!6220!6220isNatList(X) 
  a!6220!6220isNatIList(zeros) >? tt 
  a!6220!6220isNatIList(cons(X, Y)) >? a!6220!6220and(a!6220!6220isNat(X), isNatIList(Y)) 
  a!6220!6220isNatList(cons(X, Y)) >? a!6220!6220and(a!6220!6220isNat(X), isNatList(Y)) 
  a!6220!6220length(cons(X, Y)) >? a!6220!6220U11(a!6220!6220and(a!6220!6220isNatList(Y), isNat(X)), Y) 
  mark(zeros) >? a!6220!6220zeros 
  mark(U11(X, Y)) >? a!6220!6220U11(mark(X), Y) 
  mark(length(X)) >? a!6220!6220length(mark(X)) 
  mark(and(X, Y)) >? a!6220!6220and(mark(X), Y) 
  mark(isNat(X)) >? a!6220!6220isNat(X) 
  mark(isNatList(X)) >? a!6220!6220isNatList(X) 
  mark(isNatIList(X)) >? a!6220!6220isNatIList(X) 
  mark(cons(X, Y)) >? cons(mark(X), Y) 
  mark(0) >? 0 
  mark(tt) >? tt 
  mark(s(X)) >? s(mark(X)) 
  mark(nil) >? nil 
  a!6220!6220zeros >? zeros 
  a!6220!6220U11(X, Y) >? U11(X, Y) 
  a!6220!6220length(X) >? length(X) 
  a!6220!6220and(X, Y) >? and(X, Y) 
  a!6220!6220isNat(X) >? isNat(X) 
  a!6220!6220isNatList(X) >? isNatList(X) 
  a!6220!6220isNatIList(X) >? isNatIList(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  U11 = \y0y1.y0 + 2y1 
  a!6220!6220U11 = \y0y1.y0 + 2y1 
  a!6220!6220and = \y0y1.y1 + 2y0 
  a!6220!6220isNat = \y0.y0 
  a!6220!6220isNatIList = \y0.2 + 2y0 
  a!6220!6220isNatList = \y0.y0 
  a!6220!6220length = \y0.2y0 
  a!6220!6220zeros = 0 
  and = \y0y1.y1 + 2y0 
  cons = \y0y1.2y0 + 2y1 
  isNat = \y0.y0 
  isNatIList = \y0.2 + 2y0 
  isNatList = \y0.y0 
  length = \y0.2y0 
  mark = \y0.y0 
  nil = 0 
  s = \y0.y0 
  tt = 0 
  zeros = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220zeros]] = 0 >= 0 = [[cons(0, zeros)]] 
  [[a!6220!6220U11(tt, _x0)]] = 2x0 >= 2x0 = [[s(a!6220!6220length(mark(_x0)))]] 
  [[a!6220!6220and(tt, _x0)]] = x0 >= x0 = [[mark(_x0)]] 
  [[a!6220!6220isNat(0)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220isNat(length(_x0))]] = 2x0 >= x0 = [[a!6220!6220isNatList(_x0)]] 
  [[a!6220!6220isNat(s(_x0))]] = x0 >= x0 = [[a!6220!6220isNat(_x0)]] 
  [[a!6220!6220isNatIList(_x0)]] = 2 + 2x0 > x0 = [[a!6220!6220isNatList(_x0)]] 
  [[a!6220!6220isNatIList(zeros)]] = 2 > 0 = [[tt]] 
  [[a!6220!6220isNatIList(cons(_x0, _x1))]] = 2 + 4x0 + 4x1 >= 2 + 2x0 + 2x1 = [[a!6220!6220and(a!6220!6220isNat(_x0), isNatIList(_x1))]] 
  [[a!6220!6220isNatList(cons(_x0, _x1))]] = 2x0 + 2x1 >= x1 + 2x0 = [[a!6220!6220and(a!6220!6220isNat(_x0), isNatList(_x1))]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = 4x0 + 4x1 >= x0 + 4x1 = [[a!6220!6220U11(a!6220!6220and(a!6220!6220isNatList(_x1), isNat(_x0)), _x1)]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(U11(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[a!6220!6220U11(mark(_x0), _x1)]] 
  [[mark(length(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220length(mark(_x0))]] 
  [[mark(and(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[a!6220!6220and(mark(_x0), _x1)]] 
  [[mark(isNat(_x0))]] = x0 >= x0 = [[a!6220!6220isNat(_x0)]] 
  [[mark(isNatList(_x0))]] = x0 >= x0 = [[a!6220!6220isNatList(_x0)]] 
  [[mark(isNatIList(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[a!6220!6220isNatIList(_x0)]] 
  [[mark(cons(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[cons(mark(_x0), _x1)]] 
  [[mark(0)]] = 0 >= 0 = [[0]] 
  [[mark(tt)]] = 0 >= 0 = [[tt]] 
  [[mark(s(_x0))]] = x0 >= x0 = [[s(mark(_x0))]] 
  [[mark(nil)]] = 0 >= 0 = [[nil]] 
  [[a!6220!6220zeros]] = 0 >= 0 = [[zeros]] 
  [[a!6220!6220U11(_x0, _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U11(_x0, _x1)]] 
  [[a!6220!6220length(_x0)]] = 2x0 >= 2x0 = [[length(_x0)]] 
  [[a!6220!6220and(_x0, _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[and(_x0, _x1)]] 
  [[a!6220!6220isNat(_x0)]] = x0 >= x0 = [[isNat(_x0)]] 
  [[a!6220!6220isNatList(_x0)]] = x0 >= x0 = [[isNatList(_x0)]] 
  [[a!6220!6220isNatIList(_x0)]] = 2 + 2x0 >= 2 + 2x0 = [[isNatIList(_x0)]] 

We can thus remove the following rules:

  a!6220!6220isNatIList(X) => a!6220!6220isNatList(X) 
  a!6220!6220isNatIList(zeros) => tt 

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!6220U11(tt, X) >? s(a!6220!6220length(mark(X))) 
  a!6220!6220and(tt, X) >? mark(X) 
  a!6220!6220isNat(0) >? tt 
  a!6220!6220isNat(length(X)) >? a!6220!6220isNatList(X) 
  a!6220!6220isNat(s(X)) >? a!6220!6220isNat(X) 
  a!6220!6220isNatIList(cons(X, Y)) >? a!6220!6220and(a!6220!6220isNat(X), isNatIList(Y)) 
  a!6220!6220isNatList(cons(X, Y)) >? a!6220!6220and(a!6220!6220isNat(X), isNatList(Y)) 
  a!6220!6220length(cons(X, Y)) >? a!6220!6220U11(a!6220!6220and(a!6220!6220isNatList(Y), isNat(X)), Y) 
  mark(zeros) >? a!6220!6220zeros 
  mark(U11(X, Y)) >? a!6220!6220U11(mark(X), Y) 
  mark(length(X)) >? a!6220!6220length(mark(X)) 
  mark(and(X, Y)) >? a!6220!6220and(mark(X), Y) 
  mark(isNat(X)) >? a!6220!6220isNat(X) 
  mark(isNatList(X)) >? a!6220!6220isNatList(X) 
  mark(isNatIList(X)) >? a!6220!6220isNatIList(X) 
  mark(cons(X, Y)) >? cons(mark(X), Y) 
  mark(0) >? 0 
  mark(tt) >? tt 
  mark(s(X)) >? s(mark(X)) 
  mark(nil) >? nil 
  a!6220!6220zeros >? zeros 
  a!6220!6220U11(X, Y) >? U11(X, Y) 
  a!6220!6220length(X) >? length(X) 
  a!6220!6220and(X, Y) >? and(X, Y) 
  a!6220!6220isNat(X) >? isNat(X) 
  a!6220!6220isNatList(X) >? isNatList(X) 
  a!6220!6220isNatIList(X) >? isNatIList(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  U11 = \y0y1.y0 + 2y1 
  a!6220!6220U11 = \y0y1.y0 + 2y1 
  a!6220!6220and = \y0y1.y0 + 2y1 
  a!6220!6220isNat = \y0.2y0 
  a!6220!6220isNatIList = \y0.2y0 
  a!6220!6220isNatList = \y0.y0 
  a!6220!6220length = \y0.y0 
  a!6220!6220zeros = 0 
  and = \y0y1.y0 + 2y1 
  cons = \y0y1.2y0 + 3y1 
  isNat = \y0.y0 
  isNatIList = \y0.y0 
  isNatList = \y0.y0 
  length = \y0.y0 
  mark = \y0.2y0 
  nil = 3 
  s = \y0.y0 
  tt = 0 
  zeros = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220zeros]] = 0 >= 0 = [[cons(0, zeros)]] 
  [[a!6220!6220U11(tt, _x0)]] = 2x0 >= 2x0 = [[s(a!6220!6220length(mark(_x0)))]] 
  [[a!6220!6220and(tt, _x0)]] = 2x0 >= 2x0 = [[mark(_x0)]] 
  [[a!6220!6220isNat(0)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220isNat(length(_x0))]] = 2x0 >= x0 = [[a!6220!6220isNatList(_x0)]] 
  [[a!6220!6220isNat(s(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220isNat(_x0)]] 
  [[a!6220!6220isNatIList(cons(_x0, _x1))]] = 4x0 + 6x1 >= 2x0 + 2x1 = [[a!6220!6220and(a!6220!6220isNat(_x0), isNatIList(_x1))]] 
  [[a!6220!6220isNatList(cons(_x0, _x1))]] = 2x0 + 3x1 >= 2x0 + 2x1 = [[a!6220!6220and(a!6220!6220isNat(_x0), isNatList(_x1))]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = 2x0 + 3x1 >= 2x0 + 3x1 = [[a!6220!6220U11(a!6220!6220and(a!6220!6220isNatList(_x1), isNat(_x0)), _x1)]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(U11(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[a!6220!6220U11(mark(_x0), _x1)]] 
  [[mark(length(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220length(mark(_x0))]] 
  [[mark(and(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[a!6220!6220and(mark(_x0), _x1)]] 
  [[mark(isNat(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220isNat(_x0)]] 
  [[mark(isNatList(_x0))]] = 2x0 >= x0 = [[a!6220!6220isNatList(_x0)]] 
  [[mark(isNatIList(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220isNatIList(_x0)]] 
  [[mark(cons(_x0, _x1))]] = 4x0 + 6x1 >= 3x1 + 4x0 = [[cons(mark(_x0), _x1)]] 
  [[mark(0)]] = 0 >= 0 = [[0]] 
  [[mark(tt)]] = 0 >= 0 = [[tt]] 
  [[mark(s(_x0))]] = 2x0 >= 2x0 = [[s(mark(_x0))]] 
  [[mark(nil)]] = 6 > 3 = [[nil]] 
  [[a!6220!6220zeros]] = 0 >= 0 = [[zeros]] 
  [[a!6220!6220U11(_x0, _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U11(_x0, _x1)]] 
  [[a!6220!6220length(_x0)]] = x0 >= x0 = [[length(_x0)]] 
  [[a!6220!6220and(_x0, _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[and(_x0, _x1)]] 
  [[a!6220!6220isNat(_x0)]] = 2x0 >= x0 = [[isNat(_x0)]] 
  [[a!6220!6220isNatList(_x0)]] = x0 >= x0 = [[isNatList(_x0)]] 
  [[a!6220!6220isNatIList(_x0)]] = 2x0 >= x0 = [[isNatIList(_x0)]] 

We can thus remove the following rules:

  mark(nil) => nil 

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!6220U11(tt, X) >? s(a!6220!6220length(mark(X))) 
  a!6220!6220and(tt, X) >? mark(X) 
  a!6220!6220isNat(0) >? tt 
  a!6220!6220isNat(length(X)) >? a!6220!6220isNatList(X) 
  a!6220!6220isNat(s(X)) >? a!6220!6220isNat(X) 
  a!6220!6220isNatIList(cons(X, Y)) >? a!6220!6220and(a!6220!6220isNat(X), isNatIList(Y)) 
  a!6220!6220isNatList(cons(X, Y)) >? a!6220!6220and(a!6220!6220isNat(X), isNatList(Y)) 
  a!6220!6220length(cons(X, Y)) >? a!6220!6220U11(a!6220!6220and(a!6220!6220isNatList(Y), isNat(X)), Y) 
  mark(zeros) >? a!6220!6220zeros 
  mark(U11(X, Y)) >? a!6220!6220U11(mark(X), Y) 
  mark(length(X)) >? a!6220!6220length(mark(X)) 
  mark(and(X, Y)) >? a!6220!6220and(mark(X), Y) 
  mark(isNat(X)) >? a!6220!6220isNat(X) 
  mark(isNatList(X)) >? a!6220!6220isNatList(X) 
  mark(isNatIList(X)) >? a!6220!6220isNatIList(X) 
  mark(cons(X, Y)) >? cons(mark(X), Y) 
  mark(0) >? 0 
  mark(tt) >? tt 
  mark(s(X)) >? s(mark(X)) 
  a!6220!6220zeros >? zeros 
  a!6220!6220U11(X, Y) >? U11(X, Y) 
  a!6220!6220length(X) >? length(X) 
  a!6220!6220and(X, Y) >? and(X, Y) 
  a!6220!6220isNat(X) >? isNat(X) 
  a!6220!6220isNatList(X) >? isNatList(X) 
  a!6220!6220isNatIList(X) >? isNatIList(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  U11 = \y0y1.1 + y1 + 2y0 
  a!6220!6220U11 = \y0y1.1 + y1 + 2y0 
  a!6220!6220and = \y0y1.y0 + y1 
  a!6220!6220isNat = \y0.y0 
  a!6220!6220isNatIList = \y0.2y0 
  a!6220!6220isNatList = \y0.y0 
  a!6220!6220length = \y0.1 + y0 
  a!6220!6220zeros = 0 
  and = \y0y1.y0 + y1 
  cons = \y0y1.2y0 + 3y1 
  isNat = \y0.y0 
  isNatIList = \y0.2y0 
  isNatList = \y0.y0 
  length = \y0.1 + y0 
  mark = \y0.y0 
  s = \y0.y0 
  tt = 0 
  zeros = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220zeros]] = 0 >= 0 = [[cons(0, zeros)]] 
  [[a!6220!6220U11(tt, _x0)]] = 1 + x0 >= 1 + x0 = [[s(a!6220!6220length(mark(_x0)))]] 
  [[a!6220!6220and(tt, _x0)]] = x0 >= x0 = [[mark(_x0)]] 
  [[a!6220!6220isNat(0)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220isNat(length(_x0))]] = 1 + x0 > x0 = [[a!6220!6220isNatList(_x0)]] 
  [[a!6220!6220isNat(s(_x0))]] = x0 >= x0 = [[a!6220!6220isNat(_x0)]] 
  [[a!6220!6220isNatIList(cons(_x0, _x1))]] = 4x0 + 6x1 >= x0 + 2x1 = [[a!6220!6220and(a!6220!6220isNat(_x0), isNatIList(_x1))]] 
  [[a!6220!6220isNatList(cons(_x0, _x1))]] = 2x0 + 3x1 >= x0 + x1 = [[a!6220!6220and(a!6220!6220isNat(_x0), isNatList(_x1))]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = 1 + 2x0 + 3x1 >= 1 + 2x0 + 3x1 = [[a!6220!6220U11(a!6220!6220and(a!6220!6220isNatList(_x1), isNat(_x0)), _x1)]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(U11(_x0, _x1))]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[a!6220!6220U11(mark(_x0), _x1)]] 
  [[mark(length(_x0))]] = 1 + x0 >= 1 + x0 = [[a!6220!6220length(mark(_x0))]] 
  [[mark(and(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[a!6220!6220and(mark(_x0), _x1)]] 
  [[mark(isNat(_x0))]] = x0 >= x0 = [[a!6220!6220isNat(_x0)]] 
  [[mark(isNatList(_x0))]] = x0 >= x0 = [[a!6220!6220isNatList(_x0)]] 
  [[mark(isNatIList(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220isNatIList(_x0)]] 
  [[mark(cons(_x0, _x1))]] = 2x0 + 3x1 >= 2x0 + 3x1 = [[cons(mark(_x0), _x1)]] 
  [[mark(0)]] = 0 >= 0 = [[0]] 
  [[mark(tt)]] = 0 >= 0 = [[tt]] 
  [[mark(s(_x0))]] = x0 >= x0 = [[s(mark(_x0))]] 
  [[a!6220!6220zeros]] = 0 >= 0 = [[zeros]] 
  [[a!6220!6220U11(_x0, _x1)]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[U11(_x0, _x1)]] 
  [[a!6220!6220length(_x0)]] = 1 + x0 >= 1 + x0 = [[length(_x0)]] 
  [[a!6220!6220and(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] 
  [[a!6220!6220isNat(_x0)]] = x0 >= x0 = [[isNat(_x0)]] 
  [[a!6220!6220isNatList(_x0)]] = x0 >= x0 = [[isNatList(_x0)]] 
  [[a!6220!6220isNatIList(_x0)]] = 2x0 >= 2x0 = [[isNatIList(_x0)]] 

We can thus remove the following rules:

  a!6220!6220isNat(length(X)) => a!6220!6220isNatList(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!6220U11(tt, X) >? s(a!6220!6220length(mark(X))) 
  a!6220!6220and(tt, X) >? mark(X) 
  a!6220!6220isNat(0) >? tt 
  a!6220!6220isNat(s(X)) >? a!6220!6220isNat(X) 
  a!6220!6220isNatIList(cons(X, Y)) >? a!6220!6220and(a!6220!6220isNat(X), isNatIList(Y)) 
  a!6220!6220isNatList(cons(X, Y)) >? a!6220!6220and(a!6220!6220isNat(X), isNatList(Y)) 
  a!6220!6220length(cons(X, Y)) >? a!6220!6220U11(a!6220!6220and(a!6220!6220isNatList(Y), isNat(X)), Y) 
  mark(zeros) >? a!6220!6220zeros 
  mark(U11(X, Y)) >? a!6220!6220U11(mark(X), Y) 
  mark(length(X)) >? a!6220!6220length(mark(X)) 
  mark(and(X, Y)) >? a!6220!6220and(mark(X), Y) 
  mark(isNat(X)) >? a!6220!6220isNat(X) 
  mark(isNatList(X)) >? a!6220!6220isNatList(X) 
  mark(isNatIList(X)) >? a!6220!6220isNatIList(X) 
  mark(cons(X, Y)) >? cons(mark(X), Y) 
  mark(0) >? 0 
  mark(tt) >? tt 
  mark(s(X)) >? s(mark(X)) 
  a!6220!6220zeros >? zeros 
  a!6220!6220U11(X, Y) >? U11(X, Y) 
  a!6220!6220length(X) >? length(X) 
  a!6220!6220and(X, Y) >? and(X, Y) 
  a!6220!6220isNat(X) >? isNat(X) 
  a!6220!6220isNatList(X) >? isNatList(X) 
  a!6220!6220isNatIList(X) >? isNatIList(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  U11 = \y0y1.1 + y0 + y1 
  a!6220!6220U11 = \y0y1.1 + y0 + 2y1 
  a!6220!6220and = \y0y1.y0 + 2y1 
  a!6220!6220isNat = \y0.y0 
  a!6220!6220isNatIList = \y0.3y0 
  a!6220!6220isNatList = \y0.y0 
  a!6220!6220length = \y0.1 + y0 
  a!6220!6220zeros = 0 
  and = \y0y1.y0 + y1 
  cons = \y0y1.2y0 + 3y1 
  isNat = \y0.y0 
  isNatIList = \y0.2y0 
  isNatList = \y0.y0 
  length = \y0.1 + y0 
  mark = \y0.2y0 
  s = \y0.y0 
  tt = 0 
  zeros = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220zeros]] = 0 >= 0 = [[cons(0, zeros)]] 
  [[a!6220!6220U11(tt, _x0)]] = 1 + 2x0 >= 1 + 2x0 = [[s(a!6220!6220length(mark(_x0)))]] 
  [[a!6220!6220and(tt, _x0)]] = 2x0 >= 2x0 = [[mark(_x0)]] 
  [[a!6220!6220isNat(0)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220isNat(s(_x0))]] = x0 >= x0 = [[a!6220!6220isNat(_x0)]] 
  [[a!6220!6220isNatIList(cons(_x0, _x1))]] = 6x0 + 9x1 >= x0 + 4x1 = [[a!6220!6220and(a!6220!6220isNat(_x0), isNatIList(_x1))]] 
  [[a!6220!6220isNatList(cons(_x0, _x1))]] = 2x0 + 3x1 >= x0 + 2x1 = [[a!6220!6220and(a!6220!6220isNat(_x0), isNatList(_x1))]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = 1 + 2x0 + 3x1 >= 1 + 2x0 + 3x1 = [[a!6220!6220U11(a!6220!6220and(a!6220!6220isNatList(_x1), isNat(_x0)), _x1)]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(U11(_x0, _x1))]] = 2 + 2x0 + 2x1 > 1 + 2x0 + 2x1 = [[a!6220!6220U11(mark(_x0), _x1)]] 
  [[mark(length(_x0))]] = 2 + 2x0 > 1 + 2x0 = [[a!6220!6220length(mark(_x0))]] 
  [[mark(and(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[a!6220!6220and(mark(_x0), _x1)]] 
  [[mark(isNat(_x0))]] = 2x0 >= x0 = [[a!6220!6220isNat(_x0)]] 
  [[mark(isNatList(_x0))]] = 2x0 >= x0 = [[a!6220!6220isNatList(_x0)]] 
  [[mark(isNatIList(_x0))]] = 4x0 >= 3x0 = [[a!6220!6220isNatIList(_x0)]] 
  [[mark(cons(_x0, _x1))]] = 4x0 + 6x1 >= 3x1 + 4x0 = [[cons(mark(_x0), _x1)]] 
  [[mark(0)]] = 0 >= 0 = [[0]] 
  [[mark(tt)]] = 0 >= 0 = [[tt]] 
  [[mark(s(_x0))]] = 2x0 >= 2x0 = [[s(mark(_x0))]] 
  [[a!6220!6220zeros]] = 0 >= 0 = [[zeros]] 
  [[a!6220!6220U11(_x0, _x1)]] = 1 + x0 + 2x1 >= 1 + x0 + x1 = [[U11(_x0, _x1)]] 
  [[a!6220!6220length(_x0)]] = 1 + x0 >= 1 + x0 = [[length(_x0)]] 
  [[a!6220!6220and(_x0, _x1)]] = x0 + 2x1 >= x0 + x1 = [[and(_x0, _x1)]] 
  [[a!6220!6220isNat(_x0)]] = x0 >= x0 = [[isNat(_x0)]] 
  [[a!6220!6220isNatList(_x0)]] = x0 >= x0 = [[isNatList(_x0)]] 
  [[a!6220!6220isNatIList(_x0)]] = 3x0 >= 2x0 = [[isNatIList(_x0)]] 

We can thus remove the following rules:

  mark(U11(X, Y)) => a!6220!6220U11(mark(X), Y) 
  mark(length(X)) => a!6220!6220length(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!6220U11(tt, X) >? s(a!6220!6220length(mark(X))) 
  a!6220!6220and(tt, X) >? mark(X) 
  a!6220!6220isNat(0) >? tt 
  a!6220!6220isNat(s(X)) >? a!6220!6220isNat(X) 
  a!6220!6220isNatIList(cons(X, Y)) >? a!6220!6220and(a!6220!6220isNat(X), isNatIList(Y)) 
  a!6220!6220isNatList(cons(X, Y)) >? a!6220!6220and(a!6220!6220isNat(X), isNatList(Y)) 
  a!6220!6220length(cons(X, Y)) >? a!6220!6220U11(a!6220!6220and(a!6220!6220isNatList(Y), isNat(X)), Y) 
  mark(zeros) >? a!6220!6220zeros 
  mark(and(X, Y)) >? a!6220!6220and(mark(X), Y) 
  mark(isNat(X)) >? a!6220!6220isNat(X) 
  mark(isNatList(X)) >? a!6220!6220isNatList(X) 
  mark(isNatIList(X)) >? a!6220!6220isNatIList(X) 
  mark(cons(X, Y)) >? cons(mark(X), Y) 
  mark(0) >? 0 
  mark(tt) >? tt 
  mark(s(X)) >? s(mark(X)) 
  a!6220!6220zeros >? zeros 
  a!6220!6220U11(X, Y) >? U11(X, Y) 
  a!6220!6220length(X) >? length(X) 
  a!6220!6220and(X, Y) >? and(X, Y) 
  a!6220!6220isNat(X) >? isNat(X) 
  a!6220!6220isNatList(X) >? isNatList(X) 
  a!6220!6220isNatIList(X) >? isNatIList(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  U11 = \y0y1.y0 + y1 
  a!6220!6220U11 = \y0y1.1 + y0 + 2y1 
  a!6220!6220and = \y0y1.y0 + 2y1 
  a!6220!6220isNat = \y0.2y0 
  a!6220!6220isNatIList = \y0.2y0 
  a!6220!6220isNatList = \y0.y0 
  a!6220!6220length = \y0.1 + y0 
  a!6220!6220zeros = 0 
  and = \y0y1.y0 + y1 
  cons = \y0y1.2y0 + 3y1 
  isNat = \y0.y0 
  isNatIList = \y0.2y0 
  isNatList = \y0.y0 
  length = \y0.y0 
  mark = \y0.2y0 
  s = \y0.y0 
  tt = 0 
  zeros = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220zeros]] = 0 >= 0 = [[cons(0, zeros)]] 
  [[a!6220!6220U11(tt, _x0)]] = 1 + 2x0 >= 1 + 2x0 = [[s(a!6220!6220length(mark(_x0)))]] 
  [[a!6220!6220and(tt, _x0)]] = 2x0 >= 2x0 = [[mark(_x0)]] 
  [[a!6220!6220isNat(0)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220isNat(s(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220isNat(_x0)]] 
  [[a!6220!6220isNatIList(cons(_x0, _x1))]] = 4x0 + 6x1 >= 2x0 + 4x1 = [[a!6220!6220and(a!6220!6220isNat(_x0), isNatIList(_x1))]] 
  [[a!6220!6220isNatList(cons(_x0, _x1))]] = 2x0 + 3x1 >= 2x0 + 2x1 = [[a!6220!6220and(a!6220!6220isNat(_x0), isNatList(_x1))]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = 1 + 2x0 + 3x1 >= 1 + 2x0 + 3x1 = [[a!6220!6220U11(a!6220!6220and(a!6220!6220isNatList(_x1), isNat(_x0)), _x1)]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(and(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[a!6220!6220and(mark(_x0), _x1)]] 
  [[mark(isNat(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220isNat(_x0)]] 
  [[mark(isNatList(_x0))]] = 2x0 >= x0 = [[a!6220!6220isNatList(_x0)]] 
  [[mark(isNatIList(_x0))]] = 4x0 >= 2x0 = [[a!6220!6220isNatIList(_x0)]] 
  [[mark(cons(_x0, _x1))]] = 4x0 + 6x1 >= 3x1 + 4x0 = [[cons(mark(_x0), _x1)]] 
  [[mark(0)]] = 0 >= 0 = [[0]] 
  [[mark(tt)]] = 0 >= 0 = [[tt]] 
  [[mark(s(_x0))]] = 2x0 >= 2x0 = [[s(mark(_x0))]] 
  [[a!6220!6220zeros]] = 0 >= 0 = [[zeros]] 
  [[a!6220!6220U11(_x0, _x1)]] = 1 + x0 + 2x1 > x0 + x1 = [[U11(_x0, _x1)]] 
  [[a!6220!6220length(_x0)]] = 1 + x0 > x0 = [[length(_x0)]] 
  [[a!6220!6220and(_x0, _x1)]] = x0 + 2x1 >= x0 + x1 = [[and(_x0, _x1)]] 
  [[a!6220!6220isNat(_x0)]] = 2x0 >= x0 = [[isNat(_x0)]] 
  [[a!6220!6220isNatList(_x0)]] = x0 >= x0 = [[isNatList(_x0)]] 
  [[a!6220!6220isNatIList(_x0)]] = 2x0 >= 2x0 = [[isNatIList(_x0)]] 

We can thus remove the following rules:

  a!6220!6220U11(X, Y) => U11(X, Y) 
  a!6220!6220length(X) => length(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!6220U11(tt, X) >? s(a!6220!6220length(mark(X))) 
  a!6220!6220and(tt, X) >? mark(X) 
  a!6220!6220isNat(0) >? tt 
  a!6220!6220isNat(s(X)) >? a!6220!6220isNat(X) 
  a!6220!6220isNatIList(cons(X, Y)) >? a!6220!6220and(a!6220!6220isNat(X), isNatIList(Y)) 
  a!6220!6220isNatList(cons(X, Y)) >? a!6220!6220and(a!6220!6220isNat(X), isNatList(Y)) 
  a!6220!6220length(cons(X, Y)) >? a!6220!6220U11(a!6220!6220and(a!6220!6220isNatList(Y), isNat(X)), Y) 
  mark(zeros) >? a!6220!6220zeros 
  mark(and(X, Y)) >? a!6220!6220and(mark(X), Y) 
  mark(isNat(X)) >? a!6220!6220isNat(X) 
  mark(isNatList(X)) >? a!6220!6220isNatList(X) 
  mark(isNatIList(X)) >? a!6220!6220isNatIList(X) 
  mark(cons(X, Y)) >? cons(mark(X), Y) 
  mark(0) >? 0 
  mark(tt) >? tt 
  mark(s(X)) >? s(mark(X)) 
  a!6220!6220zeros >? zeros 
  a!6220!6220and(X, Y) >? and(X, Y) 
  a!6220!6220isNat(X) >? isNat(X) 
  a!6220!6220isNatList(X) >? isNatList(X) 
  a!6220!6220isNatIList(X) >? isNatIList(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  a!6220!6220U11 = \y0y1.y0 + 2y1 
  a!6220!6220and = \y0y1.y0 + 2y1 
  a!6220!6220isNat = \y0.y0 
  a!6220!6220isNatIList = \y0.2 + y0 
  a!6220!6220isNatList = \y0.y0 
  a!6220!6220length = \y0.y0 
  a!6220!6220zeros = 0 
  and = \y0y1.y0 + 2y1 
  cons = \y0y1.2y0 + 3y1 
  isNat = \y0.y0 
  isNatIList = \y0.1 + y0 
  isNatList = \y0.y0 
  mark = \y0.2y0 
  s = \y0.y0 
  tt = 0 
  zeros = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220zeros]] = 0 >= 0 = [[cons(0, zeros)]] 
  [[a!6220!6220U11(tt, _x0)]] = 2x0 >= 2x0 = [[s(a!6220!6220length(mark(_x0)))]] 
  [[a!6220!6220and(tt, _x0)]] = 2x0 >= 2x0 = [[mark(_x0)]] 
  [[a!6220!6220isNat(0)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220isNat(s(_x0))]] = x0 >= x0 = [[a!6220!6220isNat(_x0)]] 
  [[a!6220!6220isNatIList(cons(_x0, _x1))]] = 2 + 2x0 + 3x1 >= 2 + x0 + 2x1 = [[a!6220!6220and(a!6220!6220isNat(_x0), isNatIList(_x1))]] 
  [[a!6220!6220isNatList(cons(_x0, _x1))]] = 2x0 + 3x1 >= x0 + 2x1 = [[a!6220!6220and(a!6220!6220isNat(_x0), isNatList(_x1))]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = 2x0 + 3x1 >= 2x0 + 3x1 = [[a!6220!6220U11(a!6220!6220and(a!6220!6220isNatList(_x1), isNat(_x0)), _x1)]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(and(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[a!6220!6220and(mark(_x0), _x1)]] 
  [[mark(isNat(_x0))]] = 2x0 >= x0 = [[a!6220!6220isNat(_x0)]] 
  [[mark(isNatList(_x0))]] = 2x0 >= x0 = [[a!6220!6220isNatList(_x0)]] 
  [[mark(isNatIList(_x0))]] = 2 + 2x0 >= 2 + x0 = [[a!6220!6220isNatIList(_x0)]] 
  [[mark(cons(_x0, _x1))]] = 4x0 + 6x1 >= 3x1 + 4x0 = [[cons(mark(_x0), _x1)]] 
  [[mark(0)]] = 0 >= 0 = [[0]] 
  [[mark(tt)]] = 0 >= 0 = [[tt]] 
  [[mark(s(_x0))]] = 2x0 >= 2x0 = [[s(mark(_x0))]] 
  [[a!6220!6220zeros]] = 0 >= 0 = [[zeros]] 
  [[a!6220!6220and(_x0, _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[and(_x0, _x1)]] 
  [[a!6220!6220isNat(_x0)]] = x0 >= x0 = [[isNat(_x0)]] 
  [[a!6220!6220isNatList(_x0)]] = x0 >= x0 = [[isNatList(_x0)]] 
  [[a!6220!6220isNatIList(_x0)]] = 2 + x0 > 1 + x0 = [[isNatIList(_x0)]] 

We can thus remove the following rules:

  a!6220!6220isNatIList(X) => isNatIList(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!6220U11(tt, X) >? s(a!6220!6220length(mark(X))) 
  a!6220!6220and(tt, X) >? mark(X) 
  a!6220!6220isNat(0) >? tt 
  a!6220!6220isNat(s(X)) >? a!6220!6220isNat(X) 
  a!6220!6220isNatIList(cons(X, Y)) >? a!6220!6220and(a!6220!6220isNat(X), isNatIList(Y)) 
  a!6220!6220isNatList(cons(X, Y)) >? a!6220!6220and(a!6220!6220isNat(X), isNatList(Y)) 
  a!6220!6220length(cons(X, Y)) >? a!6220!6220U11(a!6220!6220and(a!6220!6220isNatList(Y), isNat(X)), Y) 
  mark(zeros) >? a!6220!6220zeros 
  mark(and(X, Y)) >? a!6220!6220and(mark(X), Y) 
  mark(isNat(X)) >? a!6220!6220isNat(X) 
  mark(isNatList(X)) >? a!6220!6220isNatList(X) 
  mark(isNatIList(X)) >? a!6220!6220isNatIList(X) 
  mark(cons(X, Y)) >? cons(mark(X), Y) 
  mark(0) >? 0 
  mark(tt) >? tt 
  mark(s(X)) >? s(mark(X)) 
  a!6220!6220zeros >? zeros 
  a!6220!6220and(X, Y) >? and(X, Y) 
  a!6220!6220isNat(X) >? isNat(X) 
  a!6220!6220isNatList(X) >? isNatList(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  a!6220!6220U11 = \y0y1.2 + y0 + 2y1 
  a!6220!6220and = \y0y1.1 + y0 + 2y1 
  a!6220!6220isNat = \y0.1 + y0 
  a!6220!6220isNatIList = \y0.2y0 
  a!6220!6220isNatList = \y0.y0 
  a!6220!6220length = \y0.1 + y0 
  a!6220!6220zeros = 2 
  and = \y0y1.1 + y0 + y1 
  cons = \y0y1.2 + 2y0 + 3y1 
  isNat = \y0.y0 
  isNatIList = \y0.2y0 
  isNatList = \y0.y0 
  mark = \y0.2 + 2y0 
  s = \y0.y0 
  tt = 1 
  zeros = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220zeros]] = 2 >= 2 = [[cons(0, zeros)]] 
  [[a!6220!6220U11(tt, _x0)]] = 3 + 2x0 >= 3 + 2x0 = [[s(a!6220!6220length(mark(_x0)))]] 
  [[a!6220!6220and(tt, _x0)]] = 2 + 2x0 >= 2 + 2x0 = [[mark(_x0)]] 
  [[a!6220!6220isNat(0)]] = 1 >= 1 = [[tt]] 
  [[a!6220!6220isNat(s(_x0))]] = 1 + x0 >= 1 + x0 = [[a!6220!6220isNat(_x0)]] 
  [[a!6220!6220isNatIList(cons(_x0, _x1))]] = 4 + 4x0 + 6x1 > 2 + x0 + 4x1 = [[a!6220!6220and(a!6220!6220isNat(_x0), isNatIList(_x1))]] 
  [[a!6220!6220isNatList(cons(_x0, _x1))]] = 2 + 2x0 + 3x1 >= 2 + x0 + 2x1 = [[a!6220!6220and(a!6220!6220isNat(_x0), isNatList(_x1))]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = 3 + 2x0 + 3x1 >= 3 + 2x0 + 3x1 = [[a!6220!6220U11(a!6220!6220and(a!6220!6220isNatList(_x1), isNat(_x0)), _x1)]] 
  [[mark(zeros)]] = 2 >= 2 = [[a!6220!6220zeros]] 
  [[mark(and(_x0, _x1))]] = 4 + 2x0 + 2x1 > 3 + 2x0 + 2x1 = [[a!6220!6220and(mark(_x0), _x1)]] 
  [[mark(isNat(_x0))]] = 2 + 2x0 > 1 + x0 = [[a!6220!6220isNat(_x0)]] 
  [[mark(isNatList(_x0))]] = 2 + 2x0 > x0 = [[a!6220!6220isNatList(_x0)]] 
  [[mark(isNatIList(_x0))]] = 2 + 4x0 > 2x0 = [[a!6220!6220isNatIList(_x0)]] 
  [[mark(cons(_x0, _x1))]] = 6 + 4x0 + 6x1 >= 6 + 3x1 + 4x0 = [[cons(mark(_x0), _x1)]] 
  [[mark(0)]] = 2 > 0 = [[0]] 
  [[mark(tt)]] = 4 > 1 = [[tt]] 
  [[mark(s(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[s(mark(_x0))]] 
  [[a!6220!6220zeros]] = 2 > 0 = [[zeros]] 
  [[a!6220!6220and(_x0, _x1)]] = 1 + x0 + 2x1 >= 1 + x0 + x1 = [[and(_x0, _x1)]] 
  [[a!6220!6220isNat(_x0)]] = 1 + x0 > x0 = [[isNat(_x0)]] 
  [[a!6220!6220isNatList(_x0)]] = x0 >= x0 = [[isNatList(_x0)]] 

We can thus remove the following rules:

  a!6220!6220isNatIList(cons(X, Y)) => a!6220!6220and(a!6220!6220isNat(X), isNatIList(Y)) 
  mark(and(X, Y)) => a!6220!6220and(mark(X), Y) 
  mark(isNat(X)) => a!6220!6220isNat(X) 
  mark(isNatList(X)) => a!6220!6220isNatList(X) 
  mark(isNatIList(X)) => a!6220!6220isNatIList(X) 
  mark(0) => 0 
  mark(tt) => tt 
  a!6220!6220zeros => zeros 
  a!6220!6220isNat(X) => isNat(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!6220U11(tt, X) >? s(a!6220!6220length(mark(X))) 
  a!6220!6220and(tt, X) >? mark(X) 
  a!6220!6220isNat(0) >? tt 
  a!6220!6220isNat(s(X)) >? a!6220!6220isNat(X) 
  a!6220!6220isNatList(cons(X, Y)) >? a!6220!6220and(a!6220!6220isNat(X), isNatList(Y)) 
  a!6220!6220length(cons(X, Y)) >? a!6220!6220U11(a!6220!6220and(a!6220!6220isNatList(Y), isNat(X)), Y) 
  mark(zeros) >? a!6220!6220zeros 
  mark(cons(X, Y)) >? cons(mark(X), Y) 
  mark(s(X)) >? s(mark(X)) 
  a!6220!6220and(X, Y) >? and(X, Y) 
  a!6220!6220isNatList(X) >? isNatList(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  a!6220!6220U11 = \y0y1.y0 + 2y1 
  a!6220!6220and = \y0y1.y0 + 2y1 
  a!6220!6220isNat = \y0.1 + 2y0 
  a!6220!6220isNatList = \y0.1 + y0 
  a!6220!6220length = \y0.1 + y0 
  a!6220!6220zeros = 0 
  and = \y0y1.y0 + y1 
  cons = \y0y1.2y0 + 3y1 
  isNat = \y0.y0 
  isNatList = \y0.y0 
  mark = \y0.2y0 
  s = \y0.y0 
  tt = 1 
  zeros = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220zeros]] = 0 >= 0 = [[cons(0, zeros)]] 
  [[a!6220!6220U11(tt, _x0)]] = 1 + 2x0 >= 1 + 2x0 = [[s(a!6220!6220length(mark(_x0)))]] 
  [[a!6220!6220and(tt, _x0)]] = 1 + 2x0 > 2x0 = [[mark(_x0)]] 
  [[a!6220!6220isNat(0)]] = 1 >= 1 = [[tt]] 
  [[a!6220!6220isNat(s(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[a!6220!6220isNat(_x0)]] 
  [[a!6220!6220isNatList(cons(_x0, _x1))]] = 1 + 2x0 + 3x1 >= 1 + 2x0 + 2x1 = [[a!6220!6220and(a!6220!6220isNat(_x0), isNatList(_x1))]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = 1 + 2x0 + 3x1 >= 1 + 2x0 + 3x1 = [[a!6220!6220U11(a!6220!6220and(a!6220!6220isNatList(_x1), isNat(_x0)), _x1)]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(cons(_x0, _x1))]] = 4x0 + 6x1 >= 3x1 + 4x0 = [[cons(mark(_x0), _x1)]] 
  [[mark(s(_x0))]] = 2x0 >= 2x0 = [[s(mark(_x0))]] 
  [[a!6220!6220and(_x0, _x1)]] = x0 + 2x1 >= x0 + x1 = [[and(_x0, _x1)]] 
  [[a!6220!6220isNatList(_x0)]] = 1 + x0 > x0 = [[isNatList(_x0)]] 

We can thus remove the following rules:

  a!6220!6220and(tt, X) => mark(X) 
  a!6220!6220isNatList(X) => isNatList(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!6220U11(tt, X) >? s(a!6220!6220length(mark(X))) 
  a!6220!6220isNat(0) >? tt 
  a!6220!6220isNat(s(X)) >? a!6220!6220isNat(X) 
  a!6220!6220isNatList(cons(X, Y)) >? a!6220!6220and(a!6220!6220isNat(X), isNatList(Y)) 
  a!6220!6220length(cons(X, Y)) >? a!6220!6220U11(a!6220!6220and(a!6220!6220isNatList(Y), isNat(X)), Y) 
  mark(zeros) >? a!6220!6220zeros 
  mark(cons(X, Y)) >? cons(mark(X), Y) 
  mark(s(X)) >? s(mark(X)) 
  a!6220!6220and(X, Y) >? and(X, Y) 

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

The following interpretation satisfies the requirements:

  0 = 2 
  a!6220!6220U11 = \y0y1.y0 + y1 
  a!6220!6220and = \y0y1.y0 + y1 
  a!6220!6220isNat = \y0.2y0 
  a!6220!6220isNatList = \y0.2y0 
  a!6220!6220length = \y0.y0 
  a!6220!6220zeros = 2 
  and = \y0y1.y0 + y1 
  cons = \y0y1.y0 + 3y1 
  isNat = \y0.y0 
  isNatList = \y0.y0 
  mark = \y0.2 + y0 
  s = \y0.y0 
  tt = 2 
  zeros = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220zeros]] = 2 >= 2 = [[cons(0, zeros)]] 
  [[a!6220!6220U11(tt, _x0)]] = 2 + x0 >= 2 + x0 = [[s(a!6220!6220length(mark(_x0)))]] 
  [[a!6220!6220isNat(0)]] = 4 > 2 = [[tt]] 
  [[a!6220!6220isNat(s(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220isNat(_x0)]] 
  [[a!6220!6220isNatList(cons(_x0, _x1))]] = 2x0 + 6x1 >= x1 + 2x0 = [[a!6220!6220and(a!6220!6220isNat(_x0), isNatList(_x1))]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = x0 + 3x1 >= x0 + 3x1 = [[a!6220!6220U11(a!6220!6220and(a!6220!6220isNatList(_x1), isNat(_x0)), _x1)]] 
  [[mark(zeros)]] = 2 >= 2 = [[a!6220!6220zeros]] 
  [[mark(cons(_x0, _x1))]] = 2 + x0 + 3x1 >= 2 + x0 + 3x1 = [[cons(mark(_x0), _x1)]] 
  [[mark(s(_x0))]] = 2 + x0 >= 2 + x0 = [[s(mark(_x0))]] 
  [[a!6220!6220and(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] 

We can thus remove the following rules:

  a!6220!6220isNat(0) => tt 

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!6220U11(tt, X) >? s(a!6220!6220length(mark(X))) 
  a!6220!6220isNat(s(X)) >? a!6220!6220isNat(X) 
  a!6220!6220isNatList(cons(X, Y)) >? a!6220!6220and(a!6220!6220isNat(X), isNatList(Y)) 
  a!6220!6220length(cons(X, Y)) >? a!6220!6220U11(a!6220!6220and(a!6220!6220isNatList(Y), isNat(X)), Y) 
  mark(zeros) >? a!6220!6220zeros 
  mark(cons(X, Y)) >? cons(mark(X), Y) 
  mark(s(X)) >? s(mark(X)) 
  a!6220!6220and(X, Y) >? and(X, Y) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  a!6220!6220U11 = \y0y1.y0 + 2y1 
  a!6220!6220and = \y0y1.y0 + y1 
  a!6220!6220isNat = \y0.2y0 
  a!6220!6220isNatList = \y0.y0 
  a!6220!6220length = \y0.1 + y0 
  a!6220!6220zeros = 0 
  and = \y0y1.y0 + y1 
  cons = \y0y1.2y0 + 3y1 
  isNat = \y0.y0 
  isNatList = \y0.y0 
  mark = \y0.y0 
  s = \y0.2y0 
  tt = 3 
  zeros = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220zeros]] = 0 >= 0 = [[cons(0, zeros)]] 
  [[a!6220!6220U11(tt, _x0)]] = 3 + 2x0 > 2 + 2x0 = [[s(a!6220!6220length(mark(_x0)))]] 
  [[a!6220!6220isNat(s(_x0))]] = 4x0 >= 2x0 = [[a!6220!6220isNat(_x0)]] 
  [[a!6220!6220isNatList(cons(_x0, _x1))]] = 2x0 + 3x1 >= x1 + 2x0 = [[a!6220!6220and(a!6220!6220isNat(_x0), isNatList(_x1))]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = 1 + 2x0 + 3x1 > x0 + 3x1 = [[a!6220!6220U11(a!6220!6220and(a!6220!6220isNatList(_x1), isNat(_x0)), _x1)]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(cons(_x0, _x1))]] = 2x0 + 3x1 >= 2x0 + 3x1 = [[cons(mark(_x0), _x1)]] 
  [[mark(s(_x0))]] = 2x0 >= 2x0 = [[s(mark(_x0))]] 
  [[a!6220!6220and(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] 

We can thus remove the following rules:

  a!6220!6220U11(tt, X) => s(a!6220!6220length(mark(X))) 
  a!6220!6220length(cons(X, Y)) => a!6220!6220U11(a!6220!6220and(a!6220!6220isNatList(Y), isNat(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]):

  a!6220!6220zeros >? cons(0, zeros) 
  a!6220!6220isNat(s(X)) >? a!6220!6220isNat(X) 
  a!6220!6220isNatList(cons(X, Y)) >? a!6220!6220and(a!6220!6220isNat(X), isNatList(Y)) 
  mark(zeros) >? a!6220!6220zeros 
  mark(cons(X, Y)) >? cons(mark(X), Y) 
  mark(s(X)) >? s(mark(X)) 
  a!6220!6220and(X, Y) >? and(X, Y) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  a!6220!6220and = \y0y1.y0 + y1 
  a!6220!6220isNat = \y0.y0 
  a!6220!6220isNatList = \y0.3 + 3y0 
  a!6220!6220zeros = 3 
  and = \y0y1.y0 + y1 
  cons = \y0y1.3 + y0 + y1 
  isNatList = \y0.y0 
  mark = \y0.3 + 3y0 
  s = \y0.3 + y0 
  zeros = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220zeros]] = 3 >= 3 = [[cons(0, zeros)]] 
  [[a!6220!6220isNat(s(_x0))]] = 3 + x0 > x0 = [[a!6220!6220isNat(_x0)]] 
  [[a!6220!6220isNatList(cons(_x0, _x1))]] = 12 + 3x0 + 3x1 > x0 + x1 = [[a!6220!6220and(a!6220!6220isNat(_x0), isNatList(_x1))]] 
  [[mark(zeros)]] = 3 >= 3 = [[a!6220!6220zeros]] 
  [[mark(cons(_x0, _x1))]] = 12 + 3x0 + 3x1 > 6 + x1 + 3x0 = [[cons(mark(_x0), _x1)]] 
  [[mark(s(_x0))]] = 12 + 3x0 > 6 + 3x0 = [[s(mark(_x0))]] 
  [[a!6220!6220and(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] 

We can thus remove the following rules:

  a!6220!6220isNat(s(X)) => a!6220!6220isNat(X) 
  a!6220!6220isNatList(cons(X, Y)) => a!6220!6220and(a!6220!6220isNat(X), isNatList(Y)) 
  mark(cons(X, Y)) => cons(mark(X), Y) 
  mark(s(X)) => s(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) 
  mark(zeros) >? a!6220!6220zeros 
  a!6220!6220and(X, Y) >? and(X, Y) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  a!6220!6220and = \y0y1.3 + y0 + y1 
  a!6220!6220zeros = 3 
  and = \y0y1.y0 + y1 
  cons = \y0y1.y0 + y1 
  mark = \y0.3 + 3y0 
  zeros = 1 

Using this interpretation, the requirements translate to:

  [[a!6220!6220zeros]] = 3 > 1 = [[cons(0, zeros)]] 
  [[mark(zeros)]] = 6 > 3 = [[a!6220!6220zeros]] 
  [[a!6220!6220and(_x0, _x1)]] = 3 + x0 + x1 > x0 + x1 = [[and(_x0, _x1)]] 

We can thus remove the following rules:

  a!6220!6220zeros => cons(0, zeros) 
  mark(zeros) => a!6220!6220zeros 
  a!6220!6220and(X, Y) => and(X, 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.