MAYBE

We are left with following problem, upon which TcT provides the
certificate MAYBE.

Strict Trs:
  { f(s(x)) -> f(id_inc(c(x, x)))
  , f(c(s(x), y)) -> g(c(x, y))
  , id_inc(s(x)) -> s(id_inc(x))
  , id_inc(c(x, y)) -> c(id_inc(x), id_inc(y))
  , id_inc(0()) -> s(0())
  , id_inc(0()) -> 0()
  , g(c(x, x)) -> f(x)
  , g(c(x, s(y))) -> g(c(y, x))
  , g(c(s(x), y)) -> g(c(y, x)) }
Obligation:
  innermost runtime complexity
Answer:
  MAYBE

The input cannot be shown compatible

Arrrr..