TRS:
 {    rev(nil()) -> nil(),
    rev(.(x, y)) -> ++(rev(y), .(x, nil())),
    car(.(x, y)) -> x,
    cdr(.(x, y)) -> y,
     null(nil()) -> true(),
   null(.(x, y)) -> false(),
    ++(nil(), y) -> y,
  ++(.(x, y), z) -> .(x, ++(y, z))}
 RPO Product:
  Quasi-Precedence:
  rev > ++
  empty
  
  Qed


TRS:
 {    rev(nil()) -> nil(),
    rev(.(x, y)) -> ++(rev(y), .(x, nil())),
    car(.(x, y)) -> x,
    cdr(.(x, y)) -> y,
     null(nil()) -> true(),
   null(.(x, y)) -> false(),
    ++(nil(), y) -> y,
  ++(.(x, y), z) -> .(x, ++(y, z))}
 Cdiprover:
  Interpretation class: quasisimplemixed
  Complexity bound: POLYTIME COMPUTABLE IF RPO-TERMINATING
  false = + 0
  null(X7) = + 0*X7^2 + 0 + 2*X7
  true = + 0
  cdr(X6) = + 0*X6^2 + 0 + 2*X6
  car(X5) = + 0*X5^2 + 0 + 2*X5
  .(X4, X3) = + 1*X3 + 1*X4 + 1
  ++(X2, X1) = + 0*X2^2 + 0*X1^2 + 1*X2 + 0 + 2*X1 + 0*X1*X2
  rev(X0) = + 0*X0^2 + 0 + 2*X0
  nil = + 0
  
  Qed