YES

We show the termination of the relative TRS R/S:

  R:
  f(x,|0|()) -> s(x)
  g(x) -> h(x,gen())
  h(|0|(),x) -> f(x,x)
  a() -> b()

  S:
  gen() -> s(gen())

-- SCC decomposition.

Consider the non-minimal dependency pair problem (P, R), where P consists of

p1: g#(x) -> h#(x,gen())
p2: h#(|0|(),x) -> f#(x,x)

and R consists of:

r1: f(x,|0|()) -> s(x)
r2: g(x) -> h(x,gen())
r3: h(|0|(),x) -> f(x,x)
r4: a() -> b()
r5: gen() -> s(gen())

The estimated dependency graph contains the following SCCs:

  (no SCCs)