/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 
  U21 : [o] --> o 
  U31 : [o] --> o 
  U41 : [o * o] --> o 
  U42 : [o] --> o 
  U51 : [o * o] --> o 
  U52 : [o] --> o 
  U61 : [o * o * o] --> o 
  U62 : [o * o] --> o 
  a!6220!6220U11 : [o] --> o 
  a!6220!6220U21 : [o] --> o 
  a!6220!6220U31 : [o] --> o 
  a!6220!6220U41 : [o * o] --> o 
  a!6220!6220U42 : [o] --> o 
  a!6220!6220U51 : [o * o] --> o 
  a!6220!6220U52 : [o] --> o 
  a!6220!6220U61 : [o * o * o] --> o 
  a!6220!6220U62 : [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 
  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) => tt 
  a!6220!6220U21(tt) => tt 
  a!6220!6220U31(tt) => tt 
  a!6220!6220U41(tt, X) => a!6220!6220U42(a!6220!6220isNatIList(X)) 
  a!6220!6220U42(tt) => tt 
  a!6220!6220U51(tt, X) => a!6220!6220U52(a!6220!6220isNatList(X)) 
  a!6220!6220U52(tt) => tt 
  a!6220!6220U61(tt, X, Y) => a!6220!6220U62(a!6220!6220isNat(Y), X) 
  a!6220!6220U62(tt, X) => s(a!6220!6220length(mark(X))) 
  a!6220!6220isNat(0) => tt 
  a!6220!6220isNat(length(X)) => a!6220!6220U11(a!6220!6220isNatList(X)) 
  a!6220!6220isNat(s(X)) => a!6220!6220U21(a!6220!6220isNat(X)) 
  a!6220!6220isNatIList(X) => a!6220!6220U31(a!6220!6220isNatList(X)) 
  a!6220!6220isNatIList(zeros) => tt 
  a!6220!6220isNatIList(cons(X, Y)) => a!6220!6220U41(a!6220!6220isNat(X), Y) 
  a!6220!6220isNatList(nil) => tt 
  a!6220!6220isNatList(cons(X, Y)) => a!6220!6220U51(a!6220!6220isNat(X), Y) 
  a!6220!6220length(nil) => 0 
  a!6220!6220length(cons(X, Y)) => a!6220!6220U61(a!6220!6220isNatList(Y), Y, X) 
  mark(zeros) => a!6220!6220zeros 
  mark(U11(X)) => a!6220!6220U11(mark(X)) 
  mark(U21(X)) => a!6220!6220U21(mark(X)) 
  mark(U31(X)) => a!6220!6220U31(mark(X)) 
  mark(U41(X, Y)) => a!6220!6220U41(mark(X), Y) 
  mark(U42(X)) => a!6220!6220U42(mark(X)) 
  mark(isNatIList(X)) => a!6220!6220isNatIList(X) 
  mark(U51(X, Y)) => a!6220!6220U51(mark(X), Y) 
  mark(U52(X)) => a!6220!6220U52(mark(X)) 
  mark(isNatList(X)) => a!6220!6220isNatList(X) 
  mark(U61(X, Y, Z)) => a!6220!6220U61(mark(X), Y, Z) 
  mark(U62(X, Y)) => a!6220!6220U62(mark(X), Y) 
  mark(isNat(X)) => a!6220!6220isNat(X) 
  mark(length(X)) => a!6220!6220length(mark(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) => U11(X) 
  a!6220!6220U21(X) => U21(X) 
  a!6220!6220U31(X) => U31(X) 
  a!6220!6220U41(X, Y) => U41(X, Y) 
  a!6220!6220U42(X) => U42(X) 
  a!6220!6220isNatIList(X) => isNatIList(X) 
  a!6220!6220U51(X, Y) => U51(X, Y) 
  a!6220!6220U52(X) => U52(X) 
  a!6220!6220isNatList(X) => isNatList(X) 
  a!6220!6220U61(X, Y, Z) => U61(X, Y, Z) 
  a!6220!6220U62(X, Y) => U62(X, Y) 
  a!6220!6220isNat(X) => isNat(X) 
  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) >? tt 
  a!6220!6220U21(tt) >? tt 
  a!6220!6220U31(tt) >? tt 
  a!6220!6220U41(tt, X) >? a!6220!6220U42(a!6220!6220isNatIList(X)) 
  a!6220!6220U42(tt) >? tt 
  a!6220!6220U51(tt, X) >? a!6220!6220U52(a!6220!6220isNatList(X)) 
  a!6220!6220U52(tt) >? tt 
  a!6220!6220U61(tt, X, Y) >? a!6220!6220U62(a!6220!6220isNat(Y), X) 
  a!6220!6220U62(tt, X) >? s(a!6220!6220length(mark(X))) 
  a!6220!6220isNat(0) >? tt 
  a!6220!6220isNat(length(X)) >? a!6220!6220U11(a!6220!6220isNatList(X)) 
  a!6220!6220isNat(s(X)) >? a!6220!6220U21(a!6220!6220isNat(X)) 
  a!6220!6220isNatIList(X) >? a!6220!6220U31(a!6220!6220isNatList(X)) 
  a!6220!6220isNatIList(zeros) >? tt 
  a!6220!6220isNatIList(cons(X, Y)) >? a!6220!6220U41(a!6220!6220isNat(X), Y) 
  a!6220!6220isNatList(nil) >? tt 
  a!6220!6220isNatList(cons(X, Y)) >? a!6220!6220U51(a!6220!6220isNat(X), Y) 
  a!6220!6220length(nil) >? 0 
  a!6220!6220length(cons(X, Y)) >? a!6220!6220U61(a!6220!6220isNatList(Y), Y, X) 
  mark(zeros) >? a!6220!6220zeros 
  mark(U11(X)) >? a!6220!6220U11(mark(X)) 
  mark(U21(X)) >? a!6220!6220U21(mark(X)) 
  mark(U31(X)) >? a!6220!6220U31(mark(X)) 
  mark(U41(X, Y)) >? a!6220!6220U41(mark(X), Y) 
  mark(U42(X)) >? a!6220!6220U42(mark(X)) 
  mark(isNatIList(X)) >? a!6220!6220isNatIList(X) 
  mark(U51(X, Y)) >? a!6220!6220U51(mark(X), Y) 
  mark(U52(X)) >? a!6220!6220U52(mark(X)) 
  mark(isNatList(X)) >? a!6220!6220isNatList(X) 
  mark(U61(X, Y, Z)) >? a!6220!6220U61(mark(X), Y, Z) 
  mark(U62(X, Y)) >? a!6220!6220U62(mark(X), Y) 
  mark(isNat(X)) >? a!6220!6220isNat(X) 
  mark(length(X)) >? a!6220!6220length(mark(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) >? U11(X) 
  a!6220!6220U21(X) >? U21(X) 
  a!6220!6220U31(X) >? U31(X) 
  a!6220!6220U41(X, Y) >? U41(X, Y) 
  a!6220!6220U42(X) >? U42(X) 
  a!6220!6220isNatIList(X) >? isNatIList(X) 
  a!6220!6220U51(X, Y) >? U51(X, Y) 
  a!6220!6220U52(X) >? U52(X) 
  a!6220!6220isNatList(X) >? isNatList(X) 
  a!6220!6220U61(X, Y, Z) >? U61(X, Y, Z) 
  a!6220!6220U62(X, Y) >? U62(X, Y) 
  a!6220!6220isNat(X) >? isNat(X) 
  a!6220!6220length(X) >? length(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  U11 = \y0.y0 
  U21 = \y0.y0 
  U31 = \y0.y0 
  U41 = \y0y1.y0 + y1 
  U42 = \y0.y0 
  U51 = \y0y1.y0 + 2y1 
  U52 = \y0.2y0 
  U61 = \y0y1y2.y0 + y2 + 2y1 
  U62 = \y0y1.y0 + 2y1 
  a!6220!6220U11 = \y0.y0 
  a!6220!6220U21 = \y0.y0 
  a!6220!6220U31 = \y0.y0 
  a!6220!6220U41 = \y0y1.y0 + y1 
  a!6220!6220U42 = \y0.y0 
  a!6220!6220U51 = \y0y1.y0 + 2y1 
  a!6220!6220U52 = \y0.2y0 
  a!6220!6220U61 = \y0y1y2.y0 + 2y1 + 2y2 
  a!6220!6220U62 = \y0y1.y0 + 2y1 
  a!6220!6220isNat = \y0.2y0 
  a!6220!6220isNatIList = \y0.y0 
  a!6220!6220isNatList = \y0.y0 
  a!6220!6220length = \y0.y0 
  a!6220!6220zeros = 0 
  cons = \y0y1.2y0 + 3y1 
  isNat = \y0.2y0 
  isNatIList = \y0.y0 
  isNatList = \y0.y0 
  length = \y0.y0 
  mark = \y0.2y0 
  nil = 2 
  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)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U21(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U31(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U41(tt, _x0)]] = x0 >= x0 = [[a!6220!6220U42(a!6220!6220isNatIList(_x0))]] 
  [[a!6220!6220U42(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U51(tt, _x0)]] = 2x0 >= 2x0 = [[a!6220!6220U52(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220U52(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U61(tt, _x0, _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[a!6220!6220U62(a!6220!6220isNat(_x1), _x0)]] 
  [[a!6220!6220U62(tt, _x0)]] = 2x0 >= 2x0 = [[s(a!6220!6220length(mark(_x0)))]] 
  [[a!6220!6220isNat(0)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220isNat(length(_x0))]] = 2x0 >= x0 = [[a!6220!6220U11(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220isNat(s(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U21(a!6220!6220isNat(_x0))]] 
  [[a!6220!6220isNatIList(_x0)]] = x0 >= x0 = [[a!6220!6220U31(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220isNatIList(zeros)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220isNatIList(cons(_x0, _x1))]] = 2x0 + 3x1 >= x1 + 2x0 = [[a!6220!6220U41(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220isNatList(nil)]] = 2 > 0 = [[tt]] 
  [[a!6220!6220isNatList(cons(_x0, _x1))]] = 2x0 + 3x1 >= 2x0 + 2x1 = [[a!6220!6220U51(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220length(nil)]] = 2 > 0 = [[0]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = 2x0 + 3x1 >= 2x0 + 3x1 = [[a!6220!6220U61(a!6220!6220isNatList(_x1), _x1, _x0)]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(U11(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U11(mark(_x0))]] 
  [[mark(U21(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U21(mark(_x0))]] 
  [[mark(U31(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U31(mark(_x0))]] 
  [[mark(U41(_x0, _x1))]] = 2x0 + 2x1 >= x1 + 2x0 = [[a!6220!6220U41(mark(_x0), _x1)]] 
  [[mark(U42(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U42(mark(_x0))]] 
  [[mark(isNatIList(_x0))]] = 2x0 >= x0 = [[a!6220!6220isNatIList(_x0)]] 
  [[mark(U51(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[a!6220!6220U51(mark(_x0), _x1)]] 
  [[mark(U52(_x0))]] = 4x0 >= 4x0 = [[a!6220!6220U52(mark(_x0))]] 
  [[mark(isNatList(_x0))]] = 2x0 >= x0 = [[a!6220!6220isNatList(_x0)]] 
  [[mark(U61(_x0, _x1, _x2))]] = 2x0 + 2x2 + 4x1 >= 2x0 + 2x1 + 2x2 = [[a!6220!6220U61(mark(_x0), _x1, _x2)]] 
  [[mark(U62(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[a!6220!6220U62(mark(_x0), _x1)]] 
  [[mark(isNat(_x0))]] = 4x0 >= 2x0 = [[a!6220!6220isNat(_x0)]] 
  [[mark(length(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220length(mark(_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)]] = 4 > 2 = [[nil]] 
  [[a!6220!6220zeros]] = 0 >= 0 = [[zeros]] 
  [[a!6220!6220U11(_x0)]] = x0 >= x0 = [[U11(_x0)]] 
  [[a!6220!6220U21(_x0)]] = x0 >= x0 = [[U21(_x0)]] 
  [[a!6220!6220U31(_x0)]] = x0 >= x0 = [[U31(_x0)]] 
  [[a!6220!6220U41(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[U41(_x0, _x1)]] 
  [[a!6220!6220U42(_x0)]] = x0 >= x0 = [[U42(_x0)]] 
  [[a!6220!6220isNatIList(_x0)]] = x0 >= x0 = [[isNatIList(_x0)]] 
  [[a!6220!6220U51(_x0, _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U51(_x0, _x1)]] 
  [[a!6220!6220U52(_x0)]] = 2x0 >= 2x0 = [[U52(_x0)]] 
  [[a!6220!6220isNatList(_x0)]] = x0 >= x0 = [[isNatList(_x0)]] 
  [[a!6220!6220U61(_x0, _x1, _x2)]] = x0 + 2x1 + 2x2 >= x0 + x2 + 2x1 = [[U61(_x0, _x1, _x2)]] 
  [[a!6220!6220U62(_x0, _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U62(_x0, _x1)]] 
  [[a!6220!6220isNat(_x0)]] = 2x0 >= 2x0 = [[isNat(_x0)]] 
  [[a!6220!6220length(_x0)]] = x0 >= x0 = [[length(_x0)]] 

We can thus remove the following rules:

  a!6220!6220isNatList(nil) => tt 
  a!6220!6220length(nil) => 0 
  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) >? tt 
  a!6220!6220U21(tt) >? tt 
  a!6220!6220U31(tt) >? tt 
  a!6220!6220U41(tt, X) >? a!6220!6220U42(a!6220!6220isNatIList(X)) 
  a!6220!6220U42(tt) >? tt 
  a!6220!6220U51(tt, X) >? a!6220!6220U52(a!6220!6220isNatList(X)) 
  a!6220!6220U52(tt) >? tt 
  a!6220!6220U61(tt, X, Y) >? a!6220!6220U62(a!6220!6220isNat(Y), X) 
  a!6220!6220U62(tt, X) >? s(a!6220!6220length(mark(X))) 
  a!6220!6220isNat(0) >? tt 
  a!6220!6220isNat(length(X)) >? a!6220!6220U11(a!6220!6220isNatList(X)) 
  a!6220!6220isNat(s(X)) >? a!6220!6220U21(a!6220!6220isNat(X)) 
  a!6220!6220isNatIList(X) >? a!6220!6220U31(a!6220!6220isNatList(X)) 
  a!6220!6220isNatIList(zeros) >? tt 
  a!6220!6220isNatIList(cons(X, Y)) >? a!6220!6220U41(a!6220!6220isNat(X), Y) 
  a!6220!6220isNatList(cons(X, Y)) >? a!6220!6220U51(a!6220!6220isNat(X), Y) 
  a!6220!6220length(cons(X, Y)) >? a!6220!6220U61(a!6220!6220isNatList(Y), Y, X) 
  mark(zeros) >? a!6220!6220zeros 
  mark(U11(X)) >? a!6220!6220U11(mark(X)) 
  mark(U21(X)) >? a!6220!6220U21(mark(X)) 
  mark(U31(X)) >? a!6220!6220U31(mark(X)) 
  mark(U41(X, Y)) >? a!6220!6220U41(mark(X), Y) 
  mark(U42(X)) >? a!6220!6220U42(mark(X)) 
  mark(isNatIList(X)) >? a!6220!6220isNatIList(X) 
  mark(U51(X, Y)) >? a!6220!6220U51(mark(X), Y) 
  mark(U52(X)) >? a!6220!6220U52(mark(X)) 
  mark(isNatList(X)) >? a!6220!6220isNatList(X) 
  mark(U61(X, Y, Z)) >? a!6220!6220U61(mark(X), Y, Z) 
  mark(U62(X, Y)) >? a!6220!6220U62(mark(X), Y) 
  mark(isNat(X)) >? a!6220!6220isNat(X) 
  mark(length(X)) >? a!6220!6220length(mark(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) >? U11(X) 
  a!6220!6220U21(X) >? U21(X) 
  a!6220!6220U31(X) >? U31(X) 
  a!6220!6220U41(X, Y) >? U41(X, Y) 
  a!6220!6220U42(X) >? U42(X) 
  a!6220!6220isNatIList(X) >? isNatIList(X) 
  a!6220!6220U51(X, Y) >? U51(X, Y) 
  a!6220!6220U52(X) >? U52(X) 
  a!6220!6220isNatList(X) >? isNatList(X) 
  a!6220!6220U61(X, Y, Z) >? U61(X, Y, Z) 
  a!6220!6220U62(X, Y) >? U62(X, Y) 
  a!6220!6220isNat(X) >? isNat(X) 
  a!6220!6220length(X) >? length(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  U11 = \y0.1 + 2y0 
  U21 = \y0.y0 
  U31 = \y0.y0 
  U41 = \y0y1.y0 + 2y1 
  U42 = \y0.2y0 
  U51 = \y0y1.y0 + y1 
  U52 = \y0.y0 
  U61 = \y0y1y2.3 + y0 + y1 + 2y2 
  U62 = \y0y1.3 + y0 + y1 
  a!6220!6220U11 = \y0.1 + 2y0 
  a!6220!6220U21 = \y0.y0 
  a!6220!6220U31 = \y0.y0 
  a!6220!6220U41 = \y0y1.y0 + 2y1 
  a!6220!6220U42 = \y0.2y0 
  a!6220!6220U51 = \y0y1.y0 + y1 
  a!6220!6220U52 = \y0.y0 
  a!6220!6220U61 = \y0y1y2.3 + y0 + y1 + 2y2 
  a!6220!6220U62 = \y0y1.3 + y0 + y1 
  a!6220!6220isNat = \y0.2y0 
  a!6220!6220isNatIList = \y0.y0 
  a!6220!6220isNatList = \y0.y0 
  a!6220!6220length = \y0.3 + y0 
  a!6220!6220zeros = 0 
  cons = \y0y1.2y0 + 2y1 
  isNat = \y0.2y0 
  isNatIList = \y0.y0 
  isNatList = \y0.y0 
  length = \y0.3 + 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)]] = 1 > 0 = [[tt]] 
  [[a!6220!6220U21(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U31(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U41(tt, _x0)]] = 2x0 >= 2x0 = [[a!6220!6220U42(a!6220!6220isNatIList(_x0))]] 
  [[a!6220!6220U42(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U51(tt, _x0)]] = x0 >= x0 = [[a!6220!6220U52(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220U52(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U61(tt, _x0, _x1)]] = 3 + x0 + 2x1 >= 3 + x0 + 2x1 = [[a!6220!6220U62(a!6220!6220isNat(_x1), _x0)]] 
  [[a!6220!6220U62(tt, _x0)]] = 3 + x0 >= 3 + x0 = [[s(a!6220!6220length(mark(_x0)))]] 
  [[a!6220!6220isNat(0)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220isNat(length(_x0))]] = 6 + 2x0 > 1 + 2x0 = [[a!6220!6220U11(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220isNat(s(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U21(a!6220!6220isNat(_x0))]] 
  [[a!6220!6220isNatIList(_x0)]] = x0 >= x0 = [[a!6220!6220U31(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220isNatIList(zeros)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220isNatIList(cons(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[a!6220!6220U41(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220isNatList(cons(_x0, _x1))]] = 2x0 + 2x1 >= x1 + 2x0 = [[a!6220!6220U51(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = 3 + 2x0 + 2x1 >= 3 + 2x0 + 2x1 = [[a!6220!6220U61(a!6220!6220isNatList(_x1), _x1, _x0)]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(U11(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[a!6220!6220U11(mark(_x0))]] 
  [[mark(U21(_x0))]] = x0 >= x0 = [[a!6220!6220U21(mark(_x0))]] 
  [[mark(U31(_x0))]] = x0 >= x0 = [[a!6220!6220U31(mark(_x0))]] 
  [[mark(U41(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[a!6220!6220U41(mark(_x0), _x1)]] 
  [[mark(U42(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U42(mark(_x0))]] 
  [[mark(isNatIList(_x0))]] = x0 >= x0 = [[a!6220!6220isNatIList(_x0)]] 
  [[mark(U51(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[a!6220!6220U51(mark(_x0), _x1)]] 
  [[mark(U52(_x0))]] = x0 >= x0 = [[a!6220!6220U52(mark(_x0))]] 
  [[mark(isNatList(_x0))]] = x0 >= x0 = [[a!6220!6220isNatList(_x0)]] 
  [[mark(U61(_x0, _x1, _x2))]] = 3 + x0 + x1 + 2x2 >= 3 + x0 + x1 + 2x2 = [[a!6220!6220U61(mark(_x0), _x1, _x2)]] 
  [[mark(U62(_x0, _x1))]] = 3 + x0 + x1 >= 3 + x0 + x1 = [[a!6220!6220U62(mark(_x0), _x1)]] 
  [[mark(isNat(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220isNat(_x0)]] 
  [[mark(length(_x0))]] = 3 + x0 >= 3 + x0 = [[a!6220!6220length(mark(_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))]] 
  [[a!6220!6220zeros]] = 0 >= 0 = [[zeros]] 
  [[a!6220!6220U11(_x0)]] = 1 + 2x0 >= 1 + 2x0 = [[U11(_x0)]] 
  [[a!6220!6220U21(_x0)]] = x0 >= x0 = [[U21(_x0)]] 
  [[a!6220!6220U31(_x0)]] = x0 >= x0 = [[U31(_x0)]] 
  [[a!6220!6220U41(_x0, _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U41(_x0, _x1)]] 
  [[a!6220!6220U42(_x0)]] = 2x0 >= 2x0 = [[U42(_x0)]] 
  [[a!6220!6220isNatIList(_x0)]] = x0 >= x0 = [[isNatIList(_x0)]] 
  [[a!6220!6220U51(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[U51(_x0, _x1)]] 
  [[a!6220!6220U52(_x0)]] = x0 >= x0 = [[U52(_x0)]] 
  [[a!6220!6220isNatList(_x0)]] = x0 >= x0 = [[isNatList(_x0)]] 
  [[a!6220!6220U61(_x0, _x1, _x2)]] = 3 + x0 + x1 + 2x2 >= 3 + x0 + x1 + 2x2 = [[U61(_x0, _x1, _x2)]] 
  [[a!6220!6220U62(_x0, _x1)]] = 3 + x0 + x1 >= 3 + x0 + x1 = [[U62(_x0, _x1)]] 
  [[a!6220!6220isNat(_x0)]] = 2x0 >= 2x0 = [[isNat(_x0)]] 
  [[a!6220!6220length(_x0)]] = 3 + x0 >= 3 + x0 = [[length(_x0)]] 

We can thus remove the following rules:

  a!6220!6220U11(tt) => tt 
  a!6220!6220isNat(length(X)) => a!6220!6220U11(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!6220U21(tt) >? tt 
  a!6220!6220U31(tt) >? tt 
  a!6220!6220U41(tt, X) >? a!6220!6220U42(a!6220!6220isNatIList(X)) 
  a!6220!6220U42(tt) >? tt 
  a!6220!6220U51(tt, X) >? a!6220!6220U52(a!6220!6220isNatList(X)) 
  a!6220!6220U52(tt) >? tt 
  a!6220!6220U61(tt, X, Y) >? a!6220!6220U62(a!6220!6220isNat(Y), X) 
  a!6220!6220U62(tt, X) >? s(a!6220!6220length(mark(X))) 
  a!6220!6220isNat(0) >? tt 
  a!6220!6220isNat(s(X)) >? a!6220!6220U21(a!6220!6220isNat(X)) 
  a!6220!6220isNatIList(X) >? a!6220!6220U31(a!6220!6220isNatList(X)) 
  a!6220!6220isNatIList(zeros) >? tt 
  a!6220!6220isNatIList(cons(X, Y)) >? a!6220!6220U41(a!6220!6220isNat(X), Y) 
  a!6220!6220isNatList(cons(X, Y)) >? a!6220!6220U51(a!6220!6220isNat(X), Y) 
  a!6220!6220length(cons(X, Y)) >? a!6220!6220U61(a!6220!6220isNatList(Y), Y, X) 
  mark(zeros) >? a!6220!6220zeros 
  mark(U11(X)) >? a!6220!6220U11(mark(X)) 
  mark(U21(X)) >? a!6220!6220U21(mark(X)) 
  mark(U31(X)) >? a!6220!6220U31(mark(X)) 
  mark(U41(X, Y)) >? a!6220!6220U41(mark(X), Y) 
  mark(U42(X)) >? a!6220!6220U42(mark(X)) 
  mark(isNatIList(X)) >? a!6220!6220isNatIList(X) 
  mark(U51(X, Y)) >? a!6220!6220U51(mark(X), Y) 
  mark(U52(X)) >? a!6220!6220U52(mark(X)) 
  mark(isNatList(X)) >? a!6220!6220isNatList(X) 
  mark(U61(X, Y, Z)) >? a!6220!6220U61(mark(X), Y, Z) 
  mark(U62(X, Y)) >? a!6220!6220U62(mark(X), Y) 
  mark(isNat(X)) >? a!6220!6220isNat(X) 
  mark(length(X)) >? a!6220!6220length(mark(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) >? U11(X) 
  a!6220!6220U21(X) >? U21(X) 
  a!6220!6220U31(X) >? U31(X) 
  a!6220!6220U41(X, Y) >? U41(X, Y) 
  a!6220!6220U42(X) >? U42(X) 
  a!6220!6220isNatIList(X) >? isNatIList(X) 
  a!6220!6220U51(X, Y) >? U51(X, Y) 
  a!6220!6220U52(X) >? U52(X) 
  a!6220!6220isNatList(X) >? isNatList(X) 
  a!6220!6220U61(X, Y, Z) >? U61(X, Y, Z) 
  a!6220!6220U62(X, Y) >? U62(X, Y) 
  a!6220!6220isNat(X) >? isNat(X) 
  a!6220!6220length(X) >? length(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  U11 = \y0.2 + y0 
  U21 = \y0.y0 
  U31 = \y0.2y0 
  U41 = \y0y1.2y0 + 2y1 
  U42 = \y0.y0 
  U51 = \y0y1.y0 + y1 
  U52 = \y0.y0 
  U61 = \y0y1y2.y0 + y2 + 2y1 
  U62 = \y0y1.y0 + y1 
  a!6220!6220U11 = \y0.3 + y0 
  a!6220!6220U21 = \y0.y0 
  a!6220!6220U31 = \y0.2y0 
  a!6220!6220U41 = \y0y1.2y0 + 2y1 
  a!6220!6220U42 = \y0.y0 
  a!6220!6220U51 = \y0y1.y0 + y1 
  a!6220!6220U52 = \y0.y0 
  a!6220!6220U61 = \y0y1y2.y0 + y2 + 2y1 
  a!6220!6220U62 = \y0y1.y0 + 2y1 
  a!6220!6220isNat = \y0.y0 
  a!6220!6220isNatIList = \y0.2y0 
  a!6220!6220isNatList = \y0.y0 
  a!6220!6220length = \y0.y0 
  a!6220!6220zeros = 0 
  cons = \y0y1.y0 + 3y1 
  isNat = \y0.y0 
  isNatIList = \y0.y0 
  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!6220U21(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U31(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U41(tt, _x0)]] = 2x0 >= 2x0 = [[a!6220!6220U42(a!6220!6220isNatIList(_x0))]] 
  [[a!6220!6220U42(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U51(tt, _x0)]] = x0 >= x0 = [[a!6220!6220U52(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220U52(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U61(tt, _x0, _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[a!6220!6220U62(a!6220!6220isNat(_x1), _x0)]] 
  [[a!6220!6220U62(tt, _x0)]] = 2x0 >= 2x0 = [[s(a!6220!6220length(mark(_x0)))]] 
  [[a!6220!6220isNat(0)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220isNat(s(_x0))]] = x0 >= x0 = [[a!6220!6220U21(a!6220!6220isNat(_x0))]] 
  [[a!6220!6220isNatIList(_x0)]] = 2x0 >= 2x0 = [[a!6220!6220U31(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220isNatIList(zeros)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220isNatIList(cons(_x0, _x1))]] = 2x0 + 6x1 >= 2x0 + 2x1 = [[a!6220!6220U41(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220isNatList(cons(_x0, _x1))]] = x0 + 3x1 >= x0 + x1 = [[a!6220!6220U51(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = x0 + 3x1 >= x0 + 3x1 = [[a!6220!6220U61(a!6220!6220isNatList(_x1), _x1, _x0)]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(U11(_x0))]] = 4 + 2x0 > 3 + 2x0 = [[a!6220!6220U11(mark(_x0))]] 
  [[mark(U21(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U21(mark(_x0))]] 
  [[mark(U31(_x0))]] = 4x0 >= 4x0 = [[a!6220!6220U31(mark(_x0))]] 
  [[mark(U41(_x0, _x1))]] = 4x0 + 4x1 >= 2x1 + 4x0 = [[a!6220!6220U41(mark(_x0), _x1)]] 
  [[mark(U42(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U42(mark(_x0))]] 
  [[mark(isNatIList(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220isNatIList(_x0)]] 
  [[mark(U51(_x0, _x1))]] = 2x0 + 2x1 >= x1 + 2x0 = [[a!6220!6220U51(mark(_x0), _x1)]] 
  [[mark(U52(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U52(mark(_x0))]] 
  [[mark(isNatList(_x0))]] = 2x0 >= x0 = [[a!6220!6220isNatList(_x0)]] 
  [[mark(U61(_x0, _x1, _x2))]] = 2x0 + 2x2 + 4x1 >= x2 + 2x0 + 2x1 = [[a!6220!6220U61(mark(_x0), _x1, _x2)]] 
  [[mark(U62(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[a!6220!6220U62(mark(_x0), _x1)]] 
  [[mark(isNat(_x0))]] = 2x0 >= x0 = [[a!6220!6220isNat(_x0)]] 
  [[mark(length(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220length(mark(_x0))]] 
  [[mark(cons(_x0, _x1))]] = 2x0 + 6x1 >= 2x0 + 3x1 = [[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)]] = 3 + x0 > 2 + x0 = [[U11(_x0)]] 
  [[a!6220!6220U21(_x0)]] = x0 >= x0 = [[U21(_x0)]] 
  [[a!6220!6220U31(_x0)]] = 2x0 >= 2x0 = [[U31(_x0)]] 
  [[a!6220!6220U41(_x0, _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[U41(_x0, _x1)]] 
  [[a!6220!6220U42(_x0)]] = x0 >= x0 = [[U42(_x0)]] 
  [[a!6220!6220isNatIList(_x0)]] = 2x0 >= x0 = [[isNatIList(_x0)]] 
  [[a!6220!6220U51(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[U51(_x0, _x1)]] 
  [[a!6220!6220U52(_x0)]] = x0 >= x0 = [[U52(_x0)]] 
  [[a!6220!6220isNatList(_x0)]] = x0 >= x0 = [[isNatList(_x0)]] 
  [[a!6220!6220U61(_x0, _x1, _x2)]] = x0 + x2 + 2x1 >= x0 + x2 + 2x1 = [[U61(_x0, _x1, _x2)]] 
  [[a!6220!6220U62(_x0, _x1)]] = x0 + 2x1 >= x0 + x1 = [[U62(_x0, _x1)]] 
  [[a!6220!6220isNat(_x0)]] = x0 >= x0 = [[isNat(_x0)]] 
  [[a!6220!6220length(_x0)]] = x0 >= x0 = [[length(_x0)]] 

We can thus remove the following rules:

  mark(U11(X)) => a!6220!6220U11(mark(X)) 
  a!6220!6220U11(X) => U11(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!6220U21(tt) >? tt 
  a!6220!6220U31(tt) >? tt 
  a!6220!6220U41(tt, X) >? a!6220!6220U42(a!6220!6220isNatIList(X)) 
  a!6220!6220U42(tt) >? tt 
  a!6220!6220U51(tt, X) >? a!6220!6220U52(a!6220!6220isNatList(X)) 
  a!6220!6220U52(tt) >? tt 
  a!6220!6220U61(tt, X, Y) >? a!6220!6220U62(a!6220!6220isNat(Y), X) 
  a!6220!6220U62(tt, X) >? s(a!6220!6220length(mark(X))) 
  a!6220!6220isNat(0) >? tt 
  a!6220!6220isNat(s(X)) >? a!6220!6220U21(a!6220!6220isNat(X)) 
  a!6220!6220isNatIList(X) >? a!6220!6220U31(a!6220!6220isNatList(X)) 
  a!6220!6220isNatIList(zeros) >? tt 
  a!6220!6220isNatIList(cons(X, Y)) >? a!6220!6220U41(a!6220!6220isNat(X), Y) 
  a!6220!6220isNatList(cons(X, Y)) >? a!6220!6220U51(a!6220!6220isNat(X), Y) 
  a!6220!6220length(cons(X, Y)) >? a!6220!6220U61(a!6220!6220isNatList(Y), Y, X) 
  mark(zeros) >? a!6220!6220zeros 
  mark(U21(X)) >? a!6220!6220U21(mark(X)) 
  mark(U31(X)) >? a!6220!6220U31(mark(X)) 
  mark(U41(X, Y)) >? a!6220!6220U41(mark(X), Y) 
  mark(U42(X)) >? a!6220!6220U42(mark(X)) 
  mark(isNatIList(X)) >? a!6220!6220isNatIList(X) 
  mark(U51(X, Y)) >? a!6220!6220U51(mark(X), Y) 
  mark(U52(X)) >? a!6220!6220U52(mark(X)) 
  mark(isNatList(X)) >? a!6220!6220isNatList(X) 
  mark(U61(X, Y, Z)) >? a!6220!6220U61(mark(X), Y, Z) 
  mark(U62(X, Y)) >? a!6220!6220U62(mark(X), Y) 
  mark(isNat(X)) >? a!6220!6220isNat(X) 
  mark(length(X)) >? a!6220!6220length(mark(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!6220U21(X) >? U21(X) 
  a!6220!6220U31(X) >? U31(X) 
  a!6220!6220U41(X, Y) >? U41(X, Y) 
  a!6220!6220U42(X) >? U42(X) 
  a!6220!6220isNatIList(X) >? isNatIList(X) 
  a!6220!6220U51(X, Y) >? U51(X, Y) 
  a!6220!6220U52(X) >? U52(X) 
  a!6220!6220isNatList(X) >? isNatList(X) 
  a!6220!6220U61(X, Y, Z) >? U61(X, Y, Z) 
  a!6220!6220U62(X, Y) >? U62(X, Y) 
  a!6220!6220isNat(X) >? isNat(X) 
  a!6220!6220length(X) >? length(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  U21 = \y0.y0 
  U31 = \y0.2 + y0 
  U41 = \y0y1.2 + y0 + 2y1 
  U42 = \y0.y0 
  U51 = \y0y1.y0 + y1 
  U52 = \y0.y0 
  U61 = \y0y1y2.y0 + y1 + 2y2 
  U62 = \y0y1.y1 + 2y0 
  a!6220!6220U21 = \y0.y0 
  a!6220!6220U31 = \y0.2 + y0 
  a!6220!6220U41 = \y0y1.2 + y0 + 2y1 
  a!6220!6220U42 = \y0.y0 
  a!6220!6220U51 = \y0y1.y0 + y1 
  a!6220!6220U52 = \y0.y0 
  a!6220!6220U61 = \y0y1y2.y0 + y1 + 2y2 
  a!6220!6220U62 = \y0y1.y1 + 2y0 
  a!6220!6220isNat = \y0.y0 
  a!6220!6220isNatIList = \y0.2 + 2y0 
  a!6220!6220isNatList = \y0.y0 
  a!6220!6220length = \y0.y0 
  a!6220!6220zeros = 0 
  cons = \y0y1.2y0 + 2y1 
  isNat = \y0.y0 
  isNatIList = \y0.2 + 2y0 
  isNatList = \y0.y0 
  length = \y0.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!6220U21(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U31(tt)]] = 2 > 0 = [[tt]] 
  [[a!6220!6220U41(tt, _x0)]] = 2 + 2x0 >= 2 + 2x0 = [[a!6220!6220U42(a!6220!6220isNatIList(_x0))]] 
  [[a!6220!6220U42(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U51(tt, _x0)]] = x0 >= x0 = [[a!6220!6220U52(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220U52(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U61(tt, _x0, _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[a!6220!6220U62(a!6220!6220isNat(_x1), _x0)]] 
  [[a!6220!6220U62(tt, _x0)]] = x0 >= x0 = [[s(a!6220!6220length(mark(_x0)))]] 
  [[a!6220!6220isNat(0)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220isNat(s(_x0))]] = x0 >= x0 = [[a!6220!6220U21(a!6220!6220isNat(_x0))]] 
  [[a!6220!6220isNatIList(_x0)]] = 2 + 2x0 >= 2 + x0 = [[a!6220!6220U31(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220isNatIList(zeros)]] = 2 > 0 = [[tt]] 
  [[a!6220!6220isNatIList(cons(_x0, _x1))]] = 2 + 4x0 + 4x1 >= 2 + x0 + 2x1 = [[a!6220!6220U41(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220isNatList(cons(_x0, _x1))]] = 2x0 + 2x1 >= x0 + x1 = [[a!6220!6220U51(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[a!6220!6220U61(a!6220!6220isNatList(_x1), _x1, _x0)]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(U21(_x0))]] = x0 >= x0 = [[a!6220!6220U21(mark(_x0))]] 
  [[mark(U31(_x0))]] = 2 + x0 >= 2 + x0 = [[a!6220!6220U31(mark(_x0))]] 
  [[mark(U41(_x0, _x1))]] = 2 + x0 + 2x1 >= 2 + x0 + 2x1 = [[a!6220!6220U41(mark(_x0), _x1)]] 
  [[mark(U42(_x0))]] = x0 >= x0 = [[a!6220!6220U42(mark(_x0))]] 
  [[mark(isNatIList(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[a!6220!6220isNatIList(_x0)]] 
  [[mark(U51(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[a!6220!6220U51(mark(_x0), _x1)]] 
  [[mark(U52(_x0))]] = x0 >= x0 = [[a!6220!6220U52(mark(_x0))]] 
  [[mark(isNatList(_x0))]] = x0 >= x0 = [[a!6220!6220isNatList(_x0)]] 
  [[mark(U61(_x0, _x1, _x2))]] = x0 + x1 + 2x2 >= x0 + x1 + 2x2 = [[a!6220!6220U61(mark(_x0), _x1, _x2)]] 
  [[mark(U62(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[a!6220!6220U62(mark(_x0), _x1)]] 
  [[mark(isNat(_x0))]] = x0 >= x0 = [[a!6220!6220isNat(_x0)]] 
  [[mark(length(_x0))]] = x0 >= x0 = [[a!6220!6220length(mark(_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))]] 
  [[a!6220!6220zeros]] = 0 >= 0 = [[zeros]] 
  [[a!6220!6220U21(_x0)]] = x0 >= x0 = [[U21(_x0)]] 
  [[a!6220!6220U31(_x0)]] = 2 + x0 >= 2 + x0 = [[U31(_x0)]] 
  [[a!6220!6220U41(_x0, _x1)]] = 2 + x0 + 2x1 >= 2 + x0 + 2x1 = [[U41(_x0, _x1)]] 
  [[a!6220!6220U42(_x0)]] = x0 >= x0 = [[U42(_x0)]] 
  [[a!6220!6220isNatIList(_x0)]] = 2 + 2x0 >= 2 + 2x0 = [[isNatIList(_x0)]] 
  [[a!6220!6220U51(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[U51(_x0, _x1)]] 
  [[a!6220!6220U52(_x0)]] = x0 >= x0 = [[U52(_x0)]] 
  [[a!6220!6220isNatList(_x0)]] = x0 >= x0 = [[isNatList(_x0)]] 
  [[a!6220!6220U61(_x0, _x1, _x2)]] = x0 + x1 + 2x2 >= x0 + x1 + 2x2 = [[U61(_x0, _x1, _x2)]] 
  [[a!6220!6220U62(_x0, _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[U62(_x0, _x1)]] 
  [[a!6220!6220isNat(_x0)]] = x0 >= x0 = [[isNat(_x0)]] 
  [[a!6220!6220length(_x0)]] = x0 >= x0 = [[length(_x0)]] 

We can thus remove the following rules:

  a!6220!6220U31(tt) => tt 
  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!6220U21(tt) >? tt 
  a!6220!6220U41(tt, X) >? a!6220!6220U42(a!6220!6220isNatIList(X)) 
  a!6220!6220U42(tt) >? tt 
  a!6220!6220U51(tt, X) >? a!6220!6220U52(a!6220!6220isNatList(X)) 
  a!6220!6220U52(tt) >? tt 
  a!6220!6220U61(tt, X, Y) >? a!6220!6220U62(a!6220!6220isNat(Y), X) 
  a!6220!6220U62(tt, X) >? s(a!6220!6220length(mark(X))) 
  a!6220!6220isNat(0) >? tt 
  a!6220!6220isNat(s(X)) >? a!6220!6220U21(a!6220!6220isNat(X)) 
  a!6220!6220isNatIList(X) >? a!6220!6220U31(a!6220!6220isNatList(X)) 
  a!6220!6220isNatIList(cons(X, Y)) >? a!6220!6220U41(a!6220!6220isNat(X), Y) 
  a!6220!6220isNatList(cons(X, Y)) >? a!6220!6220U51(a!6220!6220isNat(X), Y) 
  a!6220!6220length(cons(X, Y)) >? a!6220!6220U61(a!6220!6220isNatList(Y), Y, X) 
  mark(zeros) >? a!6220!6220zeros 
  mark(U21(X)) >? a!6220!6220U21(mark(X)) 
  mark(U31(X)) >? a!6220!6220U31(mark(X)) 
  mark(U41(X, Y)) >? a!6220!6220U41(mark(X), Y) 
  mark(U42(X)) >? a!6220!6220U42(mark(X)) 
  mark(isNatIList(X)) >? a!6220!6220isNatIList(X) 
  mark(U51(X, Y)) >? a!6220!6220U51(mark(X), Y) 
  mark(U52(X)) >? a!6220!6220U52(mark(X)) 
  mark(isNatList(X)) >? a!6220!6220isNatList(X) 
  mark(U61(X, Y, Z)) >? a!6220!6220U61(mark(X), Y, Z) 
  mark(U62(X, Y)) >? a!6220!6220U62(mark(X), Y) 
  mark(isNat(X)) >? a!6220!6220isNat(X) 
  mark(length(X)) >? a!6220!6220length(mark(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!6220U21(X) >? U21(X) 
  a!6220!6220U31(X) >? U31(X) 
  a!6220!6220U41(X, Y) >? U41(X, Y) 
  a!6220!6220U42(X) >? U42(X) 
  a!6220!6220isNatIList(X) >? isNatIList(X) 
  a!6220!6220U51(X, Y) >? U51(X, Y) 
  a!6220!6220U52(X) >? U52(X) 
  a!6220!6220isNatList(X) >? isNatList(X) 
  a!6220!6220U61(X, Y, Z) >? U61(X, Y, Z) 
  a!6220!6220U62(X, Y) >? U62(X, Y) 
  a!6220!6220isNat(X) >? isNat(X) 
  a!6220!6220length(X) >? length(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  U21 = \y0.y0 
  U31 = \y0.2y0 
  U41 = \y0y1.y1 + 2y0 
  U42 = \y0.y0 
  U51 = \y0y1.2y0 + 2y1 
  U52 = \y0.y0 
  U61 = \y0y1y2.1 + y0 + y1 + y2 
  U62 = \y0y1.1 + y0 + y1 
  a!6220!6220U21 = \y0.y0 
  a!6220!6220U31 = \y0.2y0 
  a!6220!6220U41 = \y0y1.2y0 + 2y1 
  a!6220!6220U42 = \y0.y0 
  a!6220!6220U51 = \y0y1.2y0 + 2y1 
  a!6220!6220U52 = \y0.y0 
  a!6220!6220U61 = \y0y1y2.1 + y0 + 2y1 + 2y2 
  a!6220!6220U62 = \y0y1.1 + y0 + 2y1 
  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 
  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!6220U21(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U41(tt, _x0)]] = 2x0 >= 2x0 = [[a!6220!6220U42(a!6220!6220isNatIList(_x0))]] 
  [[a!6220!6220U42(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U51(tt, _x0)]] = 2x0 >= x0 = [[a!6220!6220U52(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220U52(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U61(tt, _x0, _x1)]] = 1 + 2x0 + 2x1 >= 1 + x1 + 2x0 = [[a!6220!6220U62(a!6220!6220isNat(_x1), _x0)]] 
  [[a!6220!6220U62(tt, _x0)]] = 1 + 2x0 >= 1 + 2x0 = [[s(a!6220!6220length(mark(_x0)))]] 
  [[a!6220!6220isNat(0)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220isNat(s(_x0))]] = x0 >= x0 = [[a!6220!6220U21(a!6220!6220isNat(_x0))]] 
  [[a!6220!6220isNatIList(_x0)]] = 2x0 >= 2x0 = [[a!6220!6220U31(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220isNatIList(cons(_x0, _x1))]] = 4x0 + 6x1 >= 2x0 + 2x1 = [[a!6220!6220U41(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220isNatList(cons(_x0, _x1))]] = 2x0 + 3x1 >= 2x0 + 2x1 = [[a!6220!6220U51(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = 1 + 2x0 + 3x1 >= 1 + 2x0 + 3x1 = [[a!6220!6220U61(a!6220!6220isNatList(_x1), _x1, _x0)]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(U21(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U21(mark(_x0))]] 
  [[mark(U31(_x0))]] = 4x0 >= 4x0 = [[a!6220!6220U31(mark(_x0))]] 
  [[mark(U41(_x0, _x1))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[a!6220!6220U41(mark(_x0), _x1)]] 
  [[mark(U42(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U42(mark(_x0))]] 
  [[mark(isNatIList(_x0))]] = 4x0 >= 2x0 = [[a!6220!6220isNatIList(_x0)]] 
  [[mark(U51(_x0, _x1))]] = 4x0 + 4x1 >= 2x1 + 4x0 = [[a!6220!6220U51(mark(_x0), _x1)]] 
  [[mark(U52(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U52(mark(_x0))]] 
  [[mark(isNatList(_x0))]] = 2x0 >= x0 = [[a!6220!6220isNatList(_x0)]] 
  [[mark(U61(_x0, _x1, _x2))]] = 2 + 2x0 + 2x1 + 2x2 > 1 + 2x0 + 2x1 + 2x2 = [[a!6220!6220U61(mark(_x0), _x1, _x2)]] 
  [[mark(U62(_x0, _x1))]] = 2 + 2x0 + 2x1 > 1 + 2x0 + 2x1 = [[a!6220!6220U62(mark(_x0), _x1)]] 
  [[mark(isNat(_x0))]] = 2x0 >= x0 = [[a!6220!6220isNat(_x0)]] 
  [[mark(length(_x0))]] = 2 + 2x0 > 1 + 2x0 = [[a!6220!6220length(mark(_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!6220U21(_x0)]] = x0 >= x0 = [[U21(_x0)]] 
  [[a!6220!6220U31(_x0)]] = 2x0 >= 2x0 = [[U31(_x0)]] 
  [[a!6220!6220U41(_x0, _x1)]] = 2x0 + 2x1 >= x1 + 2x0 = [[U41(_x0, _x1)]] 
  [[a!6220!6220U42(_x0)]] = x0 >= x0 = [[U42(_x0)]] 
  [[a!6220!6220isNatIList(_x0)]] = 2x0 >= 2x0 = [[isNatIList(_x0)]] 
  [[a!6220!6220U51(_x0, _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[U51(_x0, _x1)]] 
  [[a!6220!6220U52(_x0)]] = x0 >= x0 = [[U52(_x0)]] 
  [[a!6220!6220isNatList(_x0)]] = x0 >= x0 = [[isNatList(_x0)]] 
  [[a!6220!6220U61(_x0, _x1, _x2)]] = 1 + x0 + 2x1 + 2x2 >= 1 + x0 + x1 + x2 = [[U61(_x0, _x1, _x2)]] 
  [[a!6220!6220U62(_x0, _x1)]] = 1 + x0 + 2x1 >= 1 + x0 + x1 = [[U62(_x0, _x1)]] 
  [[a!6220!6220isNat(_x0)]] = x0 >= x0 = [[isNat(_x0)]] 
  [[a!6220!6220length(_x0)]] = 1 + x0 >= 1 + x0 = [[length(_x0)]] 

We can thus remove the following rules:

  mark(U61(X, Y, Z)) => a!6220!6220U61(mark(X), Y, Z) 
  mark(U62(X, Y)) => a!6220!6220U62(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!6220U21(tt) >? tt 
  a!6220!6220U41(tt, X) >? a!6220!6220U42(a!6220!6220isNatIList(X)) 
  a!6220!6220U42(tt) >? tt 
  a!6220!6220U51(tt, X) >? a!6220!6220U52(a!6220!6220isNatList(X)) 
  a!6220!6220U52(tt) >? tt 
  a!6220!6220U61(tt, X, Y) >? a!6220!6220U62(a!6220!6220isNat(Y), X) 
  a!6220!6220U62(tt, X) >? s(a!6220!6220length(mark(X))) 
  a!6220!6220isNat(0) >? tt 
  a!6220!6220isNat(s(X)) >? a!6220!6220U21(a!6220!6220isNat(X)) 
  a!6220!6220isNatIList(X) >? a!6220!6220U31(a!6220!6220isNatList(X)) 
  a!6220!6220isNatIList(cons(X, Y)) >? a!6220!6220U41(a!6220!6220isNat(X), Y) 
  a!6220!6220isNatList(cons(X, Y)) >? a!6220!6220U51(a!6220!6220isNat(X), Y) 
  a!6220!6220length(cons(X, Y)) >? a!6220!6220U61(a!6220!6220isNatList(Y), Y, X) 
  mark(zeros) >? a!6220!6220zeros 
  mark(U21(X)) >? a!6220!6220U21(mark(X)) 
  mark(U31(X)) >? a!6220!6220U31(mark(X)) 
  mark(U41(X, Y)) >? a!6220!6220U41(mark(X), Y) 
  mark(U42(X)) >? a!6220!6220U42(mark(X)) 
  mark(isNatIList(X)) >? a!6220!6220isNatIList(X) 
  mark(U51(X, Y)) >? a!6220!6220U51(mark(X), Y) 
  mark(U52(X)) >? a!6220!6220U52(mark(X)) 
  mark(isNatList(X)) >? a!6220!6220isNatList(X) 
  mark(isNat(X)) >? a!6220!6220isNat(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!6220U21(X) >? U21(X) 
  a!6220!6220U31(X) >? U31(X) 
  a!6220!6220U41(X, Y) >? U41(X, Y) 
  a!6220!6220U42(X) >? U42(X) 
  a!6220!6220isNatIList(X) >? isNatIList(X) 
  a!6220!6220U51(X, Y) >? U51(X, Y) 
  a!6220!6220U52(X) >? U52(X) 
  a!6220!6220isNatList(X) >? isNatList(X) 
  a!6220!6220U61(X, Y, Z) >? U61(X, Y, Z) 
  a!6220!6220U62(X, Y) >? U62(X, Y) 
  a!6220!6220isNat(X) >? isNat(X) 
  a!6220!6220length(X) >? length(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  U21 = \y0.y0 
  U31 = \y0.y0 
  U41 = \y0y1.2y0 + 2y1 
  U42 = \y0.y0 
  U51 = \y0y1.y0 + y1 
  U52 = \y0.y0 
  U61 = \y0y1y2.y0 + y1 + y2 
  U62 = \y0y1.y0 + y1 
  a!6220!6220U21 = \y0.y0 
  a!6220!6220U31 = \y0.y0 
  a!6220!6220U41 = \y0y1.2y0 + 2y1 
  a!6220!6220U42 = \y0.y0 
  a!6220!6220U51 = \y0y1.y0 + y1 
  a!6220!6220U52 = \y0.y0 
  a!6220!6220U61 = \y0y1y2.1 + y0 + y1 + y2 
  a!6220!6220U62 = \y0y1.1 + 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 
  cons = \y0y1.y0 + 2y1 
  isNat = \y0.y0 
  isNatIList = \y0.2y0 
  isNatList = \y0.y0 
  length = \y0.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!6220U21(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U41(tt, _x0)]] = 2x0 >= 2x0 = [[a!6220!6220U42(a!6220!6220isNatIList(_x0))]] 
  [[a!6220!6220U42(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U51(tt, _x0)]] = x0 >= x0 = [[a!6220!6220U52(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220U52(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U61(tt, _x0, _x1)]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[a!6220!6220U62(a!6220!6220isNat(_x1), _x0)]] 
  [[a!6220!6220U62(tt, _x0)]] = 1 + x0 >= 1 + x0 = [[s(a!6220!6220length(mark(_x0)))]] 
  [[a!6220!6220isNat(0)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220isNat(s(_x0))]] = x0 >= x0 = [[a!6220!6220U21(a!6220!6220isNat(_x0))]] 
  [[a!6220!6220isNatIList(_x0)]] = 2x0 >= x0 = [[a!6220!6220U31(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220isNatIList(cons(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[a!6220!6220U41(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220isNatList(cons(_x0, _x1))]] = x0 + 2x1 >= x0 + x1 = [[a!6220!6220U51(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[a!6220!6220U61(a!6220!6220isNatList(_x1), _x1, _x0)]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(U21(_x0))]] = x0 >= x0 = [[a!6220!6220U21(mark(_x0))]] 
  [[mark(U31(_x0))]] = x0 >= x0 = [[a!6220!6220U31(mark(_x0))]] 
  [[mark(U41(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[a!6220!6220U41(mark(_x0), _x1)]] 
  [[mark(U42(_x0))]] = x0 >= x0 = [[a!6220!6220U42(mark(_x0))]] 
  [[mark(isNatIList(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220isNatIList(_x0)]] 
  [[mark(U51(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[a!6220!6220U51(mark(_x0), _x1)]] 
  [[mark(U52(_x0))]] = x0 >= x0 = [[a!6220!6220U52(mark(_x0))]] 
  [[mark(isNatList(_x0))]] = x0 >= x0 = [[a!6220!6220isNatList(_x0)]] 
  [[mark(isNat(_x0))]] = x0 >= x0 = [[a!6220!6220isNat(_x0)]] 
  [[mark(cons(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[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!6220U21(_x0)]] = x0 >= x0 = [[U21(_x0)]] 
  [[a!6220!6220U31(_x0)]] = x0 >= x0 = [[U31(_x0)]] 
  [[a!6220!6220U41(_x0, _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[U41(_x0, _x1)]] 
  [[a!6220!6220U42(_x0)]] = x0 >= x0 = [[U42(_x0)]] 
  [[a!6220!6220isNatIList(_x0)]] = 2x0 >= 2x0 = [[isNatIList(_x0)]] 
  [[a!6220!6220U51(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[U51(_x0, _x1)]] 
  [[a!6220!6220U52(_x0)]] = x0 >= x0 = [[U52(_x0)]] 
  [[a!6220!6220isNatList(_x0)]] = x0 >= x0 = [[isNatList(_x0)]] 
  [[a!6220!6220U61(_x0, _x1, _x2)]] = 1 + x0 + x1 + x2 > x0 + x1 + x2 = [[U61(_x0, _x1, _x2)]] 
  [[a!6220!6220U62(_x0, _x1)]] = 1 + x0 + x1 > x0 + x1 = [[U62(_x0, _x1)]] 
  [[a!6220!6220isNat(_x0)]] = x0 >= x0 = [[isNat(_x0)]] 
  [[a!6220!6220length(_x0)]] = 1 + x0 > x0 = [[length(_x0)]] 

We can thus remove the following rules:

  a!6220!6220U61(X, Y, Z) => U61(X, Y, Z) 
  a!6220!6220U62(X, Y) => U62(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!6220U21(tt) >? tt 
  a!6220!6220U41(tt, X) >? a!6220!6220U42(a!6220!6220isNatIList(X)) 
  a!6220!6220U42(tt) >? tt 
  a!6220!6220U51(tt, X) >? a!6220!6220U52(a!6220!6220isNatList(X)) 
  a!6220!6220U52(tt) >? tt 
  a!6220!6220U61(tt, X, Y) >? a!6220!6220U62(a!6220!6220isNat(Y), X) 
  a!6220!6220U62(tt, X) >? s(a!6220!6220length(mark(X))) 
  a!6220!6220isNat(0) >? tt 
  a!6220!6220isNat(s(X)) >? a!6220!6220U21(a!6220!6220isNat(X)) 
  a!6220!6220isNatIList(X) >? a!6220!6220U31(a!6220!6220isNatList(X)) 
  a!6220!6220isNatIList(cons(X, Y)) >? a!6220!6220U41(a!6220!6220isNat(X), Y) 
  a!6220!6220isNatList(cons(X, Y)) >? a!6220!6220U51(a!6220!6220isNat(X), Y) 
  a!6220!6220length(cons(X, Y)) >? a!6220!6220U61(a!6220!6220isNatList(Y), Y, X) 
  mark(zeros) >? a!6220!6220zeros 
  mark(U21(X)) >? a!6220!6220U21(mark(X)) 
  mark(U31(X)) >? a!6220!6220U31(mark(X)) 
  mark(U41(X, Y)) >? a!6220!6220U41(mark(X), Y) 
  mark(U42(X)) >? a!6220!6220U42(mark(X)) 
  mark(isNatIList(X)) >? a!6220!6220isNatIList(X) 
  mark(U51(X, Y)) >? a!6220!6220U51(mark(X), Y) 
  mark(U52(X)) >? a!6220!6220U52(mark(X)) 
  mark(isNatList(X)) >? a!6220!6220isNatList(X) 
  mark(isNat(X)) >? a!6220!6220isNat(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!6220U21(X) >? U21(X) 
  a!6220!6220U31(X) >? U31(X) 
  a!6220!6220U41(X, Y) >? U41(X, Y) 
  a!6220!6220U42(X) >? U42(X) 
  a!6220!6220isNatIList(X) >? isNatIList(X) 
  a!6220!6220U51(X, Y) >? U51(X, Y) 
  a!6220!6220U52(X) >? U52(X) 
  a!6220!6220isNatList(X) >? isNatList(X) 
  a!6220!6220isNat(X) >? isNat(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  U21 = \y0.2y0 
  U31 = \y0.2y0 
  U41 = \y0y1.1 + 2y0 + 2y1 
  U42 = \y0.y0 
  U51 = \y0y1.y0 + y1 
  U52 = \y0.y0 
  a!6220!6220U21 = \y0.2y0 
  a!6220!6220U31 = \y0.2y0 
  a!6220!6220U41 = \y0y1.1 + 2y0 + 2y1 
  a!6220!6220U42 = \y0.y0 
  a!6220!6220U51 = \y0y1.y0 + y1 
  a!6220!6220U52 = \y0.y0 
  a!6220!6220U61 = \y0y1y2.y0 + 2y1 + 2y2 
  a!6220!6220U62 = \y0y1.y0 + 2y1 
  a!6220!6220isNat = \y0.2y0 
  a!6220!6220isNatIList = \y0.1 + 2y0 
  a!6220!6220isNatList = \y0.y0 
  a!6220!6220length = \y0.y0 
  a!6220!6220zeros = 0 
  cons = \y0y1.2y0 + 3y1 
  isNat = \y0.2y0 
  isNatIList = \y0.1 + 2y0 
  isNatList = \y0.y0 
  mark = \y0.y0 
  s = \y0.2y0 
  tt = 0 
  zeros = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220zeros]] = 0 >= 0 = [[cons(0, zeros)]] 
  [[a!6220!6220U21(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U41(tt, _x0)]] = 1 + 2x0 >= 1 + 2x0 = [[a!6220!6220U42(a!6220!6220isNatIList(_x0))]] 
  [[a!6220!6220U42(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U51(tt, _x0)]] = x0 >= x0 = [[a!6220!6220U52(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220U52(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U61(tt, _x0, _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[a!6220!6220U62(a!6220!6220isNat(_x1), _x0)]] 
  [[a!6220!6220U62(tt, _x0)]] = 2x0 >= 2x0 = [[s(a!6220!6220length(mark(_x0)))]] 
  [[a!6220!6220isNat(0)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220isNat(s(_x0))]] = 4x0 >= 4x0 = [[a!6220!6220U21(a!6220!6220isNat(_x0))]] 
  [[a!6220!6220isNatIList(_x0)]] = 1 + 2x0 > 2x0 = [[a!6220!6220U31(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220isNatIList(cons(_x0, _x1))]] = 1 + 4x0 + 6x1 >= 1 + 2x1 + 4x0 = [[a!6220!6220U41(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220isNatList(cons(_x0, _x1))]] = 2x0 + 3x1 >= x1 + 2x0 = [[a!6220!6220U51(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = 2x0 + 3x1 >= 2x0 + 3x1 = [[a!6220!6220U61(a!6220!6220isNatList(_x1), _x1, _x0)]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(U21(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U21(mark(_x0))]] 
  [[mark(U31(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U31(mark(_x0))]] 
  [[mark(U41(_x0, _x1))]] = 1 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[a!6220!6220U41(mark(_x0), _x1)]] 
  [[mark(U42(_x0))]] = x0 >= x0 = [[a!6220!6220U42(mark(_x0))]] 
  [[mark(isNatIList(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[a!6220!6220isNatIList(_x0)]] 
  [[mark(U51(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[a!6220!6220U51(mark(_x0), _x1)]] 
  [[mark(U52(_x0))]] = x0 >= x0 = [[a!6220!6220U52(mark(_x0))]] 
  [[mark(isNatList(_x0))]] = x0 >= x0 = [[a!6220!6220isNatList(_x0)]] 
  [[mark(isNat(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220isNat(_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))]] 
  [[a!6220!6220zeros]] = 0 >= 0 = [[zeros]] 
  [[a!6220!6220U21(_x0)]] = 2x0 >= 2x0 = [[U21(_x0)]] 
  [[a!6220!6220U31(_x0)]] = 2x0 >= 2x0 = [[U31(_x0)]] 
  [[a!6220!6220U41(_x0, _x1)]] = 1 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[U41(_x0, _x1)]] 
  [[a!6220!6220U42(_x0)]] = x0 >= x0 = [[U42(_x0)]] 
  [[a!6220!6220isNatIList(_x0)]] = 1 + 2x0 >= 1 + 2x0 = [[isNatIList(_x0)]] 
  [[a!6220!6220U51(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[U51(_x0, _x1)]] 
  [[a!6220!6220U52(_x0)]] = x0 >= x0 = [[U52(_x0)]] 
  [[a!6220!6220isNatList(_x0)]] = x0 >= x0 = [[isNatList(_x0)]] 
  [[a!6220!6220isNat(_x0)]] = 2x0 >= 2x0 = [[isNat(_x0)]] 

We can thus remove the following rules:

  a!6220!6220isNatIList(X) => a!6220!6220U31(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!6220U21(tt) >? tt 
  a!6220!6220U41(tt, X) >? a!6220!6220U42(a!6220!6220isNatIList(X)) 
  a!6220!6220U42(tt) >? tt 
  a!6220!6220U51(tt, X) >? a!6220!6220U52(a!6220!6220isNatList(X)) 
  a!6220!6220U52(tt) >? tt 
  a!6220!6220U61(tt, X, Y) >? a!6220!6220U62(a!6220!6220isNat(Y), X) 
  a!6220!6220U62(tt, X) >? s(a!6220!6220length(mark(X))) 
  a!6220!6220isNat(0) >? tt 
  a!6220!6220isNat(s(X)) >? a!6220!6220U21(a!6220!6220isNat(X)) 
  a!6220!6220isNatIList(cons(X, Y)) >? a!6220!6220U41(a!6220!6220isNat(X), Y) 
  a!6220!6220isNatList(cons(X, Y)) >? a!6220!6220U51(a!6220!6220isNat(X), Y) 
  a!6220!6220length(cons(X, Y)) >? a!6220!6220U61(a!6220!6220isNatList(Y), Y, X) 
  mark(zeros) >? a!6220!6220zeros 
  mark(U21(X)) >? a!6220!6220U21(mark(X)) 
  mark(U31(X)) >? a!6220!6220U31(mark(X)) 
  mark(U41(X, Y)) >? a!6220!6220U41(mark(X), Y) 
  mark(U42(X)) >? a!6220!6220U42(mark(X)) 
  mark(isNatIList(X)) >? a!6220!6220isNatIList(X) 
  mark(U51(X, Y)) >? a!6220!6220U51(mark(X), Y) 
  mark(U52(X)) >? a!6220!6220U52(mark(X)) 
  mark(isNatList(X)) >? a!6220!6220isNatList(X) 
  mark(isNat(X)) >? a!6220!6220isNat(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!6220U21(X) >? U21(X) 
  a!6220!6220U31(X) >? U31(X) 
  a!6220!6220U41(X, Y) >? U41(X, Y) 
  a!6220!6220U42(X) >? U42(X) 
  a!6220!6220isNatIList(X) >? isNatIList(X) 
  a!6220!6220U51(X, Y) >? U51(X, Y) 
  a!6220!6220U52(X) >? U52(X) 
  a!6220!6220isNatList(X) >? isNatList(X) 
  a!6220!6220isNat(X) >? isNat(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  U21 = \y0.y0 
  U31 = \y0.1 + y0 
  U41 = \y0y1.y0 + y1 
  U42 = \y0.y0 
  U51 = \y0y1.y0 + 2y1 
  U52 = \y0.y0 
  a!6220!6220U21 = \y0.y0 
  a!6220!6220U31 = \y0.2 + y0 
  a!6220!6220U41 = \y0y1.y0 + y1 
  a!6220!6220U42 = \y0.y0 
  a!6220!6220U51 = \y0y1.y0 + 2y1 
  a!6220!6220U52 = \y0.y0 
  a!6220!6220U61 = \y0y1y2.y0 + y2 + 2y1 
  a!6220!6220U62 = \y0y1.y0 + 2y1 
  a!6220!6220isNat = \y0.1 + y0 
  a!6220!6220isNatIList = \y0.1 + y0 
  a!6220!6220isNatList = \y0.1 + y0 
  a!6220!6220length = \y0.1 + y0 
  a!6220!6220zeros = 0 
  cons = \y0y1.2y0 + 3y1 
  isNat = \y0.1 + y0 
  isNatIList = \y0.1 + y0 
  isNatList = \y0.1 + 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!6220U21(tt)]] = 1 >= 1 = [[tt]] 
  [[a!6220!6220U41(tt, _x0)]] = 1 + x0 >= 1 + x0 = [[a!6220!6220U42(a!6220!6220isNatIList(_x0))]] 
  [[a!6220!6220U42(tt)]] = 1 >= 1 = [[tt]] 
  [[a!6220!6220U51(tt, _x0)]] = 1 + 2x0 >= 1 + x0 = [[a!6220!6220U52(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220U52(tt)]] = 1 >= 1 = [[tt]] 
  [[a!6220!6220U61(tt, _x0, _x1)]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[a!6220!6220U62(a!6220!6220isNat(_x1), _x0)]] 
  [[a!6220!6220U62(tt, _x0)]] = 1 + 2x0 >= 1 + 2x0 = [[s(a!6220!6220length(mark(_x0)))]] 
  [[a!6220!6220isNat(0)]] = 1 >= 1 = [[tt]] 
  [[a!6220!6220isNat(s(_x0))]] = 1 + x0 >= 1 + x0 = [[a!6220!6220U21(a!6220!6220isNat(_x0))]] 
  [[a!6220!6220isNatIList(cons(_x0, _x1))]] = 1 + 2x0 + 3x1 >= 1 + x0 + x1 = [[a!6220!6220U41(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220isNatList(cons(_x0, _x1))]] = 1 + 2x0 + 3x1 >= 1 + x0 + 2x1 = [[a!6220!6220U51(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = 1 + 2x0 + 3x1 >= 1 + x0 + 3x1 = [[a!6220!6220U61(a!6220!6220isNatList(_x1), _x1, _x0)]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(U21(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U21(mark(_x0))]] 
  [[mark(U31(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[a!6220!6220U31(mark(_x0))]] 
  [[mark(U41(_x0, _x1))]] = 2x0 + 2x1 >= x1 + 2x0 = [[a!6220!6220U41(mark(_x0), _x1)]] 
  [[mark(U42(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U42(mark(_x0))]] 
  [[mark(isNatIList(_x0))]] = 2 + 2x0 > 1 + x0 = [[a!6220!6220isNatIList(_x0)]] 
  [[mark(U51(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[a!6220!6220U51(mark(_x0), _x1)]] 
  [[mark(U52(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U52(mark(_x0))]] 
  [[mark(isNatList(_x0))]] = 2 + 2x0 > 1 + x0 = [[a!6220!6220isNatList(_x0)]] 
  [[mark(isNat(_x0))]] = 2 + 2x0 > 1 + x0 = [[a!6220!6220isNat(_x0)]] 
  [[mark(cons(_x0, _x1))]] = 4x0 + 6x1 >= 3x1 + 4x0 = [[cons(mark(_x0), _x1)]] 
  [[mark(0)]] = 0 >= 0 = [[0]] 
  [[mark(tt)]] = 2 > 1 = [[tt]] 
  [[mark(s(_x0))]] = 2x0 >= 2x0 = [[s(mark(_x0))]] 
  [[a!6220!6220zeros]] = 0 >= 0 = [[zeros]] 
  [[a!6220!6220U21(_x0)]] = x0 >= x0 = [[U21(_x0)]] 
  [[a!6220!6220U31(_x0)]] = 2 + x0 > 1 + x0 = [[U31(_x0)]] 
  [[a!6220!6220U41(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[U41(_x0, _x1)]] 
  [[a!6220!6220U42(_x0)]] = x0 >= x0 = [[U42(_x0)]] 
  [[a!6220!6220isNatIList(_x0)]] = 1 + x0 >= 1 + x0 = [[isNatIList(_x0)]] 
  [[a!6220!6220U51(_x0, _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U51(_x0, _x1)]] 
  [[a!6220!6220U52(_x0)]] = x0 >= x0 = [[U52(_x0)]] 
  [[a!6220!6220isNatList(_x0)]] = 1 + x0 >= 1 + x0 = [[isNatList(_x0)]] 
  [[a!6220!6220isNat(_x0)]] = 1 + x0 >= 1 + x0 = [[isNat(_x0)]] 

We can thus remove the following rules:

  mark(isNatIList(X)) => a!6220!6220isNatIList(X) 
  mark(isNatList(X)) => a!6220!6220isNatList(X) 
  mark(isNat(X)) => a!6220!6220isNat(X) 
  mark(tt) => tt 
  a!6220!6220U31(X) => U31(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!6220U21(tt) >? tt 
  a!6220!6220U41(tt, X) >? a!6220!6220U42(a!6220!6220isNatIList(X)) 
  a!6220!6220U42(tt) >? tt 
  a!6220!6220U51(tt, X) >? a!6220!6220U52(a!6220!6220isNatList(X)) 
  a!6220!6220U52(tt) >? tt 
  a!6220!6220U61(tt, X, Y) >? a!6220!6220U62(a!6220!6220isNat(Y), X) 
  a!6220!6220U62(tt, X) >? s(a!6220!6220length(mark(X))) 
  a!6220!6220isNat(0) >? tt 
  a!6220!6220isNat(s(X)) >? a!6220!6220U21(a!6220!6220isNat(X)) 
  a!6220!6220isNatIList(cons(X, Y)) >? a!6220!6220U41(a!6220!6220isNat(X), Y) 
  a!6220!6220isNatList(cons(X, Y)) >? a!6220!6220U51(a!6220!6220isNat(X), Y) 
  a!6220!6220length(cons(X, Y)) >? a!6220!6220U61(a!6220!6220isNatList(Y), Y, X) 
  mark(zeros) >? a!6220!6220zeros 
  mark(U21(X)) >? a!6220!6220U21(mark(X)) 
  mark(U31(X)) >? a!6220!6220U31(mark(X)) 
  mark(U41(X, Y)) >? a!6220!6220U41(mark(X), Y) 
  mark(U42(X)) >? a!6220!6220U42(mark(X)) 
  mark(U51(X, Y)) >? a!6220!6220U51(mark(X), Y) 
  mark(U52(X)) >? a!6220!6220U52(mark(X)) 
  mark(cons(X, Y)) >? cons(mark(X), Y) 
  mark(0) >? 0 
  mark(s(X)) >? s(mark(X)) 
  a!6220!6220zeros >? zeros 
  a!6220!6220U21(X) >? U21(X) 
  a!6220!6220U41(X, Y) >? U41(X, Y) 
  a!6220!6220U42(X) >? U42(X) 
  a!6220!6220isNatIList(X) >? isNatIList(X) 
  a!6220!6220U51(X, Y) >? U51(X, Y) 
  a!6220!6220U52(X) >? U52(X) 
  a!6220!6220isNatList(X) >? isNatList(X) 
  a!6220!6220isNat(X) >? isNat(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  U21 = \y0.y0 
  U31 = \y0.3 + 3y0 
  U41 = \y0y1.y0 + 2y1 
  U42 = \y0.y0 
  U51 = \y0y1.y0 + y1 
  U52 = \y0.y0 
  a!6220!6220U21 = \y0.y0 
  a!6220!6220U31 = \y0.y0 
  a!6220!6220U41 = \y0y1.y0 + 2y1 
  a!6220!6220U42 = \y0.y0 
  a!6220!6220U51 = \y0y1.y0 + y1 
  a!6220!6220U52 = \y0.y0 
  a!6220!6220U61 = \y0y1y2.y0 + y1 + 2y2 
  a!6220!6220U62 = \y0y1.y1 + 2y0 
  a!6220!6220isNat = \y0.y0 
  a!6220!6220isNatIList = \y0.2y0 
  a!6220!6220isNatList = \y0.y0 
  a!6220!6220length = \y0.y0 
  a!6220!6220zeros = 0 
  cons = \y0y1.2y0 + 2y1 
  isNat = \y0.y0 
  isNatIList = \y0.y0 
  isNatList = \y0.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!6220U21(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U41(tt, _x0)]] = 2x0 >= 2x0 = [[a!6220!6220U42(a!6220!6220isNatIList(_x0))]] 
  [[a!6220!6220U42(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U51(tt, _x0)]] = x0 >= x0 = [[a!6220!6220U52(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220U52(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U61(tt, _x0, _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[a!6220!6220U62(a!6220!6220isNat(_x1), _x0)]] 
  [[a!6220!6220U62(tt, _x0)]] = x0 >= x0 = [[s(a!6220!6220length(mark(_x0)))]] 
  [[a!6220!6220isNat(0)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220isNat(s(_x0))]] = x0 >= x0 = [[a!6220!6220U21(a!6220!6220isNat(_x0))]] 
  [[a!6220!6220isNatIList(cons(_x0, _x1))]] = 4x0 + 4x1 >= x0 + 2x1 = [[a!6220!6220U41(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220isNatList(cons(_x0, _x1))]] = 2x0 + 2x1 >= x0 + x1 = [[a!6220!6220U51(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[a!6220!6220U61(a!6220!6220isNatList(_x1), _x1, _x0)]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(U21(_x0))]] = x0 >= x0 = [[a!6220!6220U21(mark(_x0))]] 
  [[mark(U31(_x0))]] = 3 + 3x0 > x0 = [[a!6220!6220U31(mark(_x0))]] 
  [[mark(U41(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[a!6220!6220U41(mark(_x0), _x1)]] 
  [[mark(U42(_x0))]] = x0 >= x0 = [[a!6220!6220U42(mark(_x0))]] 
  [[mark(U51(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[a!6220!6220U51(mark(_x0), _x1)]] 
  [[mark(U52(_x0))]] = x0 >= x0 = [[a!6220!6220U52(mark(_x0))]] 
  [[mark(cons(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[cons(mark(_x0), _x1)]] 
  [[mark(0)]] = 0 >= 0 = [[0]] 
  [[mark(s(_x0))]] = x0 >= x0 = [[s(mark(_x0))]] 
  [[a!6220!6220zeros]] = 0 >= 0 = [[zeros]] 
  [[a!6220!6220U21(_x0)]] = x0 >= x0 = [[U21(_x0)]] 
  [[a!6220!6220U41(_x0, _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U41(_x0, _x1)]] 
  [[a!6220!6220U42(_x0)]] = x0 >= x0 = [[U42(_x0)]] 
  [[a!6220!6220isNatIList(_x0)]] = 2x0 >= x0 = [[isNatIList(_x0)]] 
  [[a!6220!6220U51(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[U51(_x0, _x1)]] 
  [[a!6220!6220U52(_x0)]] = x0 >= x0 = [[U52(_x0)]] 
  [[a!6220!6220isNatList(_x0)]] = x0 >= x0 = [[isNatList(_x0)]] 
  [[a!6220!6220isNat(_x0)]] = x0 >= x0 = [[isNat(_x0)]] 

We can thus remove the following rules:

  mark(U31(X)) => a!6220!6220U31(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!6220U21(tt) >? tt 
  a!6220!6220U41(tt, X) >? a!6220!6220U42(a!6220!6220isNatIList(X)) 
  a!6220!6220U42(tt) >? tt 
  a!6220!6220U51(tt, X) >? a!6220!6220U52(a!6220!6220isNatList(X)) 
  a!6220!6220U52(tt) >? tt 
  a!6220!6220U61(tt, X, Y) >? a!6220!6220U62(a!6220!6220isNat(Y), X) 
  a!6220!6220U62(tt, X) >? s(a!6220!6220length(mark(X))) 
  a!6220!6220isNat(0) >? tt 
  a!6220!6220isNat(s(X)) >? a!6220!6220U21(a!6220!6220isNat(X)) 
  a!6220!6220isNatIList(cons(X, Y)) >? a!6220!6220U41(a!6220!6220isNat(X), Y) 
  a!6220!6220isNatList(cons(X, Y)) >? a!6220!6220U51(a!6220!6220isNat(X), Y) 
  a!6220!6220length(cons(X, Y)) >? a!6220!6220U61(a!6220!6220isNatList(Y), Y, X) 
  mark(zeros) >? a!6220!6220zeros 
  mark(U21(X)) >? a!6220!6220U21(mark(X)) 
  mark(U41(X, Y)) >? a!6220!6220U41(mark(X), Y) 
  mark(U42(X)) >? a!6220!6220U42(mark(X)) 
  mark(U51(X, Y)) >? a!6220!6220U51(mark(X), Y) 
  mark(U52(X)) >? a!6220!6220U52(mark(X)) 
  mark(cons(X, Y)) >? cons(mark(X), Y) 
  mark(0) >? 0 
  mark(s(X)) >? s(mark(X)) 
  a!6220!6220zeros >? zeros 
  a!6220!6220U21(X) >? U21(X) 
  a!6220!6220U41(X, Y) >? U41(X, Y) 
  a!6220!6220U42(X) >? U42(X) 
  a!6220!6220isNatIList(X) >? isNatIList(X) 
  a!6220!6220U51(X, Y) >? U51(X, Y) 
  a!6220!6220U52(X) >? U52(X) 
  a!6220!6220isNatList(X) >? isNatList(X) 
  a!6220!6220isNat(X) >? isNat(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  U21 = \y0.y0 
  U41 = \y0y1.1 + y0 + y1 
  U42 = \y0.y0 
  U51 = \y0y1.y0 + y1 
  U52 = \y0.y0 
  a!6220!6220U21 = \y0.y0 
  a!6220!6220U41 = \y0y1.1 + y0 + y1 
  a!6220!6220U42 = \y0.y0 
  a!6220!6220U51 = \y0y1.y0 + y1 
  a!6220!6220U52 = \y0.y0 
  a!6220!6220U61 = \y0y1y2.y0 + 2y1 + 2y2 
  a!6220!6220U62 = \y0y1.2y0 + 2y1 
  a!6220!6220isNat = \y0.y0 
  a!6220!6220isNatIList = \y0.1 + y0 
  a!6220!6220isNatList = \y0.y0 
  a!6220!6220length = \y0.y0 
  a!6220!6220zeros = 0 
  cons = \y0y1.2y0 + 3y1 
  isNat = \y0.y0 
  isNatIList = \y0.y0 
  isNatList = \y0.y0 
  mark = \y0.y0 
  s = \y0.2y0 
  tt = 0 
  zeros = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220zeros]] = 0 >= 0 = [[cons(0, zeros)]] 
  [[a!6220!6220U21(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U41(tt, _x0)]] = 1 + x0 >= 1 + x0 = [[a!6220!6220U42(a!6220!6220isNatIList(_x0))]] 
  [[a!6220!6220U42(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U51(tt, _x0)]] = x0 >= x0 = [[a!6220!6220U52(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220U52(tt)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220U61(tt, _x0, _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[a!6220!6220U62(a!6220!6220isNat(_x1), _x0)]] 
  [[a!6220!6220U62(tt, _x0)]] = 2x0 >= 2x0 = [[s(a!6220!6220length(mark(_x0)))]] 
  [[a!6220!6220isNat(0)]] = 0 >= 0 = [[tt]] 
  [[a!6220!6220isNat(s(_x0))]] = 2x0 >= x0 = [[a!6220!6220U21(a!6220!6220isNat(_x0))]] 
  [[a!6220!6220isNatIList(cons(_x0, _x1))]] = 1 + 2x0 + 3x1 >= 1 + x0 + x1 = [[a!6220!6220U41(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220isNatList(cons(_x0, _x1))]] = 2x0 + 3x1 >= x0 + x1 = [[a!6220!6220U51(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = 2x0 + 3x1 >= 2x0 + 3x1 = [[a!6220!6220U61(a!6220!6220isNatList(_x1), _x1, _x0)]] 
  [[mark(zeros)]] = 0 >= 0 = [[a!6220!6220zeros]] 
  [[mark(U21(_x0))]] = x0 >= x0 = [[a!6220!6220U21(mark(_x0))]] 
  [[mark(U41(_x0, _x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[a!6220!6220U41(mark(_x0), _x1)]] 
  [[mark(U42(_x0))]] = x0 >= x0 = [[a!6220!6220U42(mark(_x0))]] 
  [[mark(U51(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[a!6220!6220U51(mark(_x0), _x1)]] 
  [[mark(U52(_x0))]] = x0 >= x0 = [[a!6220!6220U52(mark(_x0))]] 
  [[mark(cons(_x0, _x1))]] = 2x0 + 3x1 >= 2x0 + 3x1 = [[cons(mark(_x0), _x1)]] 
  [[mark(0)]] = 0 >= 0 = [[0]] 
  [[mark(s(_x0))]] = 2x0 >= 2x0 = [[s(mark(_x0))]] 
  [[a!6220!6220zeros]] = 0 >= 0 = [[zeros]] 
  [[a!6220!6220U21(_x0)]] = x0 >= x0 = [[U21(_x0)]] 
  [[a!6220!6220U41(_x0, _x1)]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[U41(_x0, _x1)]] 
  [[a!6220!6220U42(_x0)]] = x0 >= x0 = [[U42(_x0)]] 
  [[a!6220!6220isNatIList(_x0)]] = 1 + x0 > x0 = [[isNatIList(_x0)]] 
  [[a!6220!6220U51(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[U51(_x0, _x1)]] 
  [[a!6220!6220U52(_x0)]] = x0 >= x0 = [[U52(_x0)]] 
  [[a!6220!6220isNatList(_x0)]] = x0 >= x0 = [[isNatList(_x0)]] 
  [[a!6220!6220isNat(_x0)]] = x0 >= x0 = [[isNat(_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!6220U21(tt) >? tt 
  a!6220!6220U41(tt, X) >? a!6220!6220U42(a!6220!6220isNatIList(X)) 
  a!6220!6220U42(tt) >? tt 
  a!6220!6220U51(tt, X) >? a!6220!6220U52(a!6220!6220isNatList(X)) 
  a!6220!6220U52(tt) >? tt 
  a!6220!6220U61(tt, X, Y) >? a!6220!6220U62(a!6220!6220isNat(Y), X) 
  a!6220!6220U62(tt, X) >? s(a!6220!6220length(mark(X))) 
  a!6220!6220isNat(0) >? tt 
  a!6220!6220isNat(s(X)) >? a!6220!6220U21(a!6220!6220isNat(X)) 
  a!6220!6220isNatIList(cons(X, Y)) >? a!6220!6220U41(a!6220!6220isNat(X), Y) 
  a!6220!6220isNatList(cons(X, Y)) >? a!6220!6220U51(a!6220!6220isNat(X), Y) 
  a!6220!6220length(cons(X, Y)) >? a!6220!6220U61(a!6220!6220isNatList(Y), Y, X) 
  mark(zeros) >? a!6220!6220zeros 
  mark(U21(X)) >? a!6220!6220U21(mark(X)) 
  mark(U41(X, Y)) >? a!6220!6220U41(mark(X), Y) 
  mark(U42(X)) >? a!6220!6220U42(mark(X)) 
  mark(U51(X, Y)) >? a!6220!6220U51(mark(X), Y) 
  mark(U52(X)) >? a!6220!6220U52(mark(X)) 
  mark(cons(X, Y)) >? cons(mark(X), Y) 
  mark(0) >? 0 
  mark(s(X)) >? s(mark(X)) 
  a!6220!6220zeros >? zeros 
  a!6220!6220U21(X) >? U21(X) 
  a!6220!6220U41(X, Y) >? U41(X, Y) 
  a!6220!6220U42(X) >? U42(X) 
  a!6220!6220U51(X, Y) >? U51(X, Y) 
  a!6220!6220U52(X) >? U52(X) 
  a!6220!6220isNatList(X) >? isNatList(X) 
  a!6220!6220isNat(X) >? isNat(X) 

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

The following interpretation satisfies the requirements:

  0 = 1 
  U21 = \y0.y0 
  U41 = \y0y1.1 + y0 + 2y1 
  U42 = \y0.y0 
  U51 = \y0y1.y0 + 2y1 
  U52 = \y0.y0 
  a!6220!6220U21 = \y0.y0 
  a!6220!6220U41 = \y0y1.1 + y0 + 2y1 
  a!6220!6220U42 = \y0.y0 
  a!6220!6220U51 = \y0y1.y0 + 2y1 
  a!6220!6220U52 = \y0.y0 
  a!6220!6220U61 = \y0y1y2.y0 + 2y1 + 2y2 
  a!6220!6220U62 = \y0y1.1 + y0 + 2y1 
  a!6220!6220isNat = \y0.2y0 
  a!6220!6220isNatIList = \y0.2 + 2y0 
  a!6220!6220isNatList = \y0.1 + 2y0 
  a!6220!6220length = \y0.1 + 2y0 
  a!6220!6220zeros = 1 
  cons = \y0y1.y0 + 2y1 
  isNat = \y0.y0 
  isNatList = \y0.y0 
  mark = \y0.1 + y0 
  s = \y0.y0 
  tt = 2 
  zeros = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220zeros]] = 1 >= 1 = [[cons(0, zeros)]] 
  [[a!6220!6220U21(tt)]] = 2 >= 2 = [[tt]] 
  [[a!6220!6220U41(tt, _x0)]] = 3 + 2x0 > 2 + 2x0 = [[a!6220!6220U42(a!6220!6220isNatIList(_x0))]] 
  [[a!6220!6220U42(tt)]] = 2 >= 2 = [[tt]] 
  [[a!6220!6220U51(tt, _x0)]] = 2 + 2x0 > 1 + 2x0 = [[a!6220!6220U52(a!6220!6220isNatList(_x0))]] 
  [[a!6220!6220U52(tt)]] = 2 >= 2 = [[tt]] 
  [[a!6220!6220U61(tt, _x0, _x1)]] = 2 + 2x0 + 2x1 > 1 + 2x0 + 2x1 = [[a!6220!6220U62(a!6220!6220isNat(_x1), _x0)]] 
  [[a!6220!6220U62(tt, _x0)]] = 3 + 2x0 >= 3 + 2x0 = [[s(a!6220!6220length(mark(_x0)))]] 
  [[a!6220!6220isNat(0)]] = 2 >= 2 = [[tt]] 
  [[a!6220!6220isNat(s(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220U21(a!6220!6220isNat(_x0))]] 
  [[a!6220!6220isNatIList(cons(_x0, _x1))]] = 2 + 2x0 + 4x1 > 1 + 2x0 + 2x1 = [[a!6220!6220U41(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220isNatList(cons(_x0, _x1))]] = 1 + 2x0 + 4x1 > 2x0 + 2x1 = [[a!6220!6220U51(a!6220!6220isNat(_x0), _x1)]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = 1 + 2x0 + 4x1 >= 1 + 2x0 + 4x1 = [[a!6220!6220U61(a!6220!6220isNatList(_x1), _x1, _x0)]] 
  [[mark(zeros)]] = 1 >= 1 = [[a!6220!6220zeros]] 
  [[mark(U21(_x0))]] = 1 + x0 >= 1 + x0 = [[a!6220!6220U21(mark(_x0))]] 
  [[mark(U41(_x0, _x1))]] = 2 + x0 + 2x1 >= 2 + x0 + 2x1 = [[a!6220!6220U41(mark(_x0), _x1)]] 
  [[mark(U42(_x0))]] = 1 + x0 >= 1 + x0 = [[a!6220!6220U42(mark(_x0))]] 
  [[mark(U51(_x0, _x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[a!6220!6220U51(mark(_x0), _x1)]] 
  [[mark(U52(_x0))]] = 1 + x0 >= 1 + x0 = [[a!6220!6220U52(mark(_x0))]] 
  [[mark(cons(_x0, _x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[cons(mark(_x0), _x1)]] 
  [[mark(0)]] = 2 > 1 = [[0]] 
  [[mark(s(_x0))]] = 1 + x0 >= 1 + x0 = [[s(mark(_x0))]] 
  [[a!6220!6220zeros]] = 1 > 0 = [[zeros]] 
  [[a!6220!6220U21(_x0)]] = x0 >= x0 = [[U21(_x0)]] 
  [[a!6220!6220U41(_x0, _x1)]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[U41(_x0, _x1)]] 
  [[a!6220!6220U42(_x0)]] = x0 >= x0 = [[U42(_x0)]] 
  [[a!6220!6220U51(_x0, _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U51(_x0, _x1)]] 
  [[a!6220!6220U52(_x0)]] = x0 >= x0 = [[U52(_x0)]] 
  [[a!6220!6220isNatList(_x0)]] = 1 + 2x0 > x0 = [[isNatList(_x0)]] 
  [[a!6220!6220isNat(_x0)]] = 2x0 >= x0 = [[isNat(_x0)]] 

We can thus remove the following rules:

  a!6220!6220U41(tt, X) => a!6220!6220U42(a!6220!6220isNatIList(X)) 
  a!6220!6220U51(tt, X) => a!6220!6220U52(a!6220!6220isNatList(X)) 
  a!6220!6220U61(tt, X, Y) => a!6220!6220U62(a!6220!6220isNat(Y), X) 
  a!6220!6220isNatIList(cons(X, Y)) => a!6220!6220U41(a!6220!6220isNat(X), Y) 
  a!6220!6220isNatList(cons(X, Y)) => a!6220!6220U51(a!6220!6220isNat(X), Y) 
  mark(0) => 0 
  a!6220!6220zeros => zeros 
  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!6220U21(tt) >? tt 
  a!6220!6220U42(tt) >? tt 
  a!6220!6220U52(tt) >? tt 
  a!6220!6220U62(tt, X) >? s(a!6220!6220length(mark(X))) 
  a!6220!6220isNat(0) >? tt 
  a!6220!6220isNat(s(X)) >? a!6220!6220U21(a!6220!6220isNat(X)) 
  a!6220!6220length(cons(X, Y)) >? a!6220!6220U61(a!6220!6220isNatList(Y), Y, X) 
  mark(zeros) >? a!6220!6220zeros 
  mark(U21(X)) >? a!6220!6220U21(mark(X)) 
  mark(U41(X, Y)) >? a!6220!6220U41(mark(X), Y) 
  mark(U42(X)) >? a!6220!6220U42(mark(X)) 
  mark(U51(X, Y)) >? a!6220!6220U51(mark(X), Y) 
  mark(U52(X)) >? a!6220!6220U52(mark(X)) 
  mark(cons(X, Y)) >? cons(mark(X), Y) 
  mark(s(X)) >? s(mark(X)) 
  a!6220!6220U21(X) >? U21(X) 
  a!6220!6220U41(X, Y) >? U41(X, Y) 
  a!6220!6220U42(X) >? U42(X) 
  a!6220!6220U51(X, Y) >? U51(X, Y) 
  a!6220!6220U52(X) >? U52(X) 
  a!6220!6220isNat(X) >? isNat(X) 

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

The following interpretation satisfies the requirements:

  0 = 1 
  U21 = \y0.1 + y0 
  U41 = \y0y1.y0 + y1 
  U42 = \y0.2 + y0 
  U51 = \y0y1.2 + y1 + 2y0 
  U52 = \y0.1 + y0 
  a!6220!6220U21 = \y0.1 + y0 
  a!6220!6220U41 = \y0y1.y0 + y1 
  a!6220!6220U42 = \y0.2 + y0 
  a!6220!6220U51 = \y0y1.2 + y1 + 2y0 
  a!6220!6220U52 = \y0.2 + y0 
  a!6220!6220U61 = \y0y1y2.y0 + y1 + y2 
  a!6220!6220U62 = \y0y1.3 + 3y0 + 3y1 
  a!6220!6220isNat = \y0.2y0 
  a!6220!6220isNatList = \y0.y0 
  a!6220!6220length = \y0.y0 
  a!6220!6220zeros = 1 
  cons = \y0y1.y0 + 2y1 
  isNat = \y0.y0 
  mark = \y0.1 + 2y0 
  s = \y0.1 + y0 
  tt = 1 
  zeros = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220zeros]] = 1 >= 1 = [[cons(0, zeros)]] 
  [[a!6220!6220U21(tt)]] = 2 > 1 = [[tt]] 
  [[a!6220!6220U42(tt)]] = 3 > 1 = [[tt]] 
  [[a!6220!6220U52(tt)]] = 3 > 1 = [[tt]] 
  [[a!6220!6220U62(tt, _x0)]] = 6 + 3x0 > 2 + 2x0 = [[s(a!6220!6220length(mark(_x0)))]] 
  [[a!6220!6220isNat(0)]] = 2 > 1 = [[tt]] 
  [[a!6220!6220isNat(s(_x0))]] = 2 + 2x0 > 1 + 2x0 = [[a!6220!6220U21(a!6220!6220isNat(_x0))]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[a!6220!6220U61(a!6220!6220isNatList(_x1), _x1, _x0)]] 
  [[mark(zeros)]] = 1 >= 1 = [[a!6220!6220zeros]] 
  [[mark(U21(_x0))]] = 3 + 2x0 > 2 + 2x0 = [[a!6220!6220U21(mark(_x0))]] 
  [[mark(U41(_x0, _x1))]] = 1 + 2x0 + 2x1 >= 1 + x1 + 2x0 = [[a!6220!6220U41(mark(_x0), _x1)]] 
  [[mark(U42(_x0))]] = 5 + 2x0 > 3 + 2x0 = [[a!6220!6220U42(mark(_x0))]] 
  [[mark(U51(_x0, _x1))]] = 5 + 2x1 + 4x0 > 4 + x1 + 4x0 = [[a!6220!6220U51(mark(_x0), _x1)]] 
  [[mark(U52(_x0))]] = 3 + 2x0 >= 3 + 2x0 = [[a!6220!6220U52(mark(_x0))]] 
  [[mark(cons(_x0, _x1))]] = 1 + 2x0 + 4x1 >= 1 + 2x0 + 2x1 = [[cons(mark(_x0), _x1)]] 
  [[mark(s(_x0))]] = 3 + 2x0 > 2 + 2x0 = [[s(mark(_x0))]] 
  [[a!6220!6220U21(_x0)]] = 1 + x0 >= 1 + x0 = [[U21(_x0)]] 
  [[a!6220!6220U41(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[U41(_x0, _x1)]] 
  [[a!6220!6220U42(_x0)]] = 2 + x0 >= 2 + x0 = [[U42(_x0)]] 
  [[a!6220!6220U51(_x0, _x1)]] = 2 + x1 + 2x0 >= 2 + x1 + 2x0 = [[U51(_x0, _x1)]] 
  [[a!6220!6220U52(_x0)]] = 2 + x0 > 1 + x0 = [[U52(_x0)]] 
  [[a!6220!6220isNat(_x0)]] = 2x0 >= x0 = [[isNat(_x0)]] 

We can thus remove the following rules:

  a!6220!6220U21(tt) => tt 
  a!6220!6220U42(tt) => tt 
  a!6220!6220U52(tt) => tt 
  a!6220!6220U62(tt, X) => s(a!6220!6220length(mark(X))) 
  a!6220!6220isNat(0) => tt 
  a!6220!6220isNat(s(X)) => a!6220!6220U21(a!6220!6220isNat(X)) 
  mark(U21(X)) => a!6220!6220U21(mark(X)) 
  mark(U42(X)) => a!6220!6220U42(mark(X)) 
  mark(U51(X, Y)) => a!6220!6220U51(mark(X), Y) 
  mark(s(X)) => s(mark(X)) 
  a!6220!6220U52(X) => U52(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!6220length(cons(X, Y)) >? a!6220!6220U61(a!6220!6220isNatList(Y), Y, X) 
  mark(zeros) >? a!6220!6220zeros 
  mark(U41(X, Y)) >? a!6220!6220U41(mark(X), Y) 
  mark(U52(X)) >? a!6220!6220U52(mark(X)) 
  mark(cons(X, Y)) >? cons(mark(X), Y) 
  a!6220!6220U21(X) >? U21(X) 
  a!6220!6220U41(X, Y) >? U41(X, Y) 
  a!6220!6220U42(X) >? U42(X) 
  a!6220!6220U51(X, Y) >? U51(X, Y) 
  a!6220!6220isNat(X) >? isNat(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  U21 = \y0.y0 
  U41 = \y0y1.2 + y0 + y1 
  U42 = \y0.y0 
  U51 = \y0y1.y0 + y1 
  U52 = \y0.3 + 3y0 
  a!6220!6220U21 = \y0.3 + 2y0 
  a!6220!6220U41 = \y0y1.3 + y0 + y1 
  a!6220!6220U42 = \y0.3 + y0 
  a!6220!6220U51 = \y0y1.3 + y1 + 2y0 
  a!6220!6220U52 = \y0.y0 
  a!6220!6220U61 = \y0y1y2.y0 + y1 + y2 
  a!6220!6220isNat = \y0.3 + 2y0 
  a!6220!6220isNatList = \y0.y0 
  a!6220!6220length = \y0.3 + 3y0 
  a!6220!6220zeros = 2 
  cons = \y0y1.y0 + y1 
  isNat = \y0.y0 
  mark = \y0.2y0 
  zeros = 1 

Using this interpretation, the requirements translate to:

  [[a!6220!6220zeros]] = 2 > 1 = [[cons(0, zeros)]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = 3 + 3x0 + 3x1 > x0 + 2x1 = [[a!6220!6220U61(a!6220!6220isNatList(_x1), _x1, _x0)]] 
  [[mark(zeros)]] = 2 >= 2 = [[a!6220!6220zeros]] 
  [[mark(U41(_x0, _x1))]] = 4 + 2x0 + 2x1 > 3 + x1 + 2x0 = [[a!6220!6220U41(mark(_x0), _x1)]] 
  [[mark(U52(_x0))]] = 6 + 6x0 > 2x0 = [[a!6220!6220U52(mark(_x0))]] 
  [[mark(cons(_x0, _x1))]] = 2x0 + 2x1 >= x1 + 2x0 = [[cons(mark(_x0), _x1)]] 
  [[a!6220!6220U21(_x0)]] = 3 + 2x0 > x0 = [[U21(_x0)]] 
  [[a!6220!6220U41(_x0, _x1)]] = 3 + x0 + x1 > 2 + x0 + x1 = [[U41(_x0, _x1)]] 
  [[a!6220!6220U42(_x0)]] = 3 + x0 > x0 = [[U42(_x0)]] 
  [[a!6220!6220U51(_x0, _x1)]] = 3 + x1 + 2x0 > x0 + x1 = [[U51(_x0, _x1)]] 
  [[a!6220!6220isNat(_x0)]] = 3 + 2x0 > x0 = [[isNat(_x0)]] 

We can thus remove the following rules:

  a!6220!6220zeros => cons(0, zeros) 
  a!6220!6220length(cons(X, Y)) => a!6220!6220U61(a!6220!6220isNatList(Y), Y, X) 
  mark(U41(X, Y)) => a!6220!6220U41(mark(X), Y) 
  mark(U52(X)) => a!6220!6220U52(mark(X)) 
  a!6220!6220U21(X) => U21(X) 
  a!6220!6220U41(X, Y) => U41(X, Y) 
  a!6220!6220U42(X) => U42(X) 
  a!6220!6220U51(X, Y) => U51(X, Y) 
  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]):

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

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

The following interpretation satisfies the requirements:

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

Using this interpretation, the requirements translate to:

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

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

  mark(cons(X, Y)) >? cons(mark(X), Y) 

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

The following interpretation satisfies the requirements:

  cons = \y0y1.1 + y0 + y1 
  mark = \y0.3y0 

Using this interpretation, the requirements translate to:

  [[mark(cons(_x0, _x1))]] = 3 + 3x0 + 3x1 > 1 + x1 + 3x0 = [[cons(mark(_x0), _x1)]] 

We can thus remove the following rules:

  mark(cons(X, Y)) => cons(mark(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.