MAYBE
TRS:
 {app(app(rec(), h), app(g, app(s(), x))) -> app(app(h, x), app(app(rec(), h), app(g, x))),
          app(app(rec(), h), app(g, 0())) -> g}
 DP:
  Strict:
   {app#(app(rec(), h), app(g, app(s(), x))) -> app#(g, x),
    app#(app(rec(), h), app(g, app(s(), x))) -> app#(h, x),
    app#(app(rec(), h), app(g, app(s(), x))) -> app#(app(h, x), app(app(rec(), h), app(g, x))),
    app#(app(rec(), h), app(g, app(s(), x))) -> app#(app(rec(), h), app(g, x))}
  Weak:
  {app(app(rec(), h), app(g, app(s(), x))) -> app(app(h, x), app(app(rec(), h), app(g, x))),
           app(app(rec(), h), app(g, 0())) -> g}
  EDG:
   {(app#(app(rec(), h), app(g, app(s(), x))) -> app#(app(rec(), h), app(g, x)), app#(app(rec(), h), app(g, app(s(), x))) -> app#(app(rec(), h), app(g, x)))
    (app#(app(rec(), h), app(g, app(s(), x))) -> app#(app(rec(), h), app(g, x)), app#(app(rec(), h), app(g, app(s(), x))) -> app#(app(h, x), app(app(rec(), h), app(g, x))))
    (app#(app(rec(), h), app(g, app(s(), x))) -> app#(app(rec(), h), app(g, x)), app#(app(rec(), h), app(g, app(s(), x))) -> app#(h, x))
    (app#(app(rec(), h), app(g, app(s(), x))) -> app#(app(rec(), h), app(g, x)), app#(app(rec(), h), app(g, app(s(), x))) -> app#(g, x))
    (app#(app(rec(), h), app(g, app(s(), x))) -> app#(h, x), app#(app(rec(), h), app(g, app(s(), x))) -> app#(app(rec(), h), app(g, x)))
    (app#(app(rec(), h), app(g, app(s(), x))) -> app#(h, x), app#(app(rec(), h), app(g, app(s(), x))) -> app#(app(h, x), app(app(rec(), h), app(g, x))))
    (app#(app(rec(), h), app(g, app(s(), x))) -> app#(h, x), app#(app(rec(), h), app(g, app(s(), x))) -> app#(h, x))
    (app#(app(rec(), h), app(g, app(s(), x))) -> app#(h, x), app#(app(rec(), h), app(g, app(s(), x))) -> app#(g, x))
    (app#(app(rec(), h), app(g, app(s(), x))) -> app#(g, x), app#(app(rec(), h), app(g, app(s(), x))) -> app#(g, x))
    (app#(app(rec(), h), app(g, app(s(), x))) -> app#(g, x), app#(app(rec(), h), app(g, app(s(), x))) -> app#(h, x))
    (app#(app(rec(), h), app(g, app(s(), x))) -> app#(g, x), app#(app(rec(), h), app(g, app(s(), x))) -> app#(app(h, x), app(app(rec(), h), app(g, x))))
    (app#(app(rec(), h), app(g, app(s(), x))) -> app#(g, x), app#(app(rec(), h), app(g, app(s(), x))) -> app#(app(rec(), h), app(g, x)))
    (app#(app(rec(), h), app(g, app(s(), x))) -> app#(app(h, x), app(app(rec(), h), app(g, x))), app#(app(rec(), h), app(g, app(s(), x))) -> app#(g, x))
    (app#(app(rec(), h), app(g, app(s(), x))) -> app#(app(h, x), app(app(rec(), h), app(g, x))), app#(app(rec(), h), app(g, app(s(), x))) -> app#(h, x))
    (app#(app(rec(), h), app(g, app(s(), x))) -> app#(app(h, x), app(app(rec(), h), app(g, x))), app#(app(rec(), h), app(g, app(s(), x))) -> app#(app(h, x), app(app(rec(), h), app(g, x))))
    (app#(app(rec(), h), app(g, app(s(), x))) -> app#(app(h, x), app(app(rec(), h), app(g, x))), app#(app(rec(), h), app(g, app(s(), x))) -> app#(app(rec(), h), app(g, x)))}
   SCCS:
    Scc:
     {app#(app(rec(), h), app(g, app(s(), x))) -> app#(g, x),
      app#(app(rec(), h), app(g, app(s(), x))) -> app#(h, x),
      app#(app(rec(), h), app(g, app(s(), x))) -> app#(app(h, x), app(app(rec(), h), app(g, x))),
      app#(app(rec(), h), app(g, app(s(), x))) -> app#(app(rec(), h), app(g, x))}
    SCC:
     Strict:
      {app#(app(rec(), h), app(g, app(s(), x))) -> app#(g, x),
       app#(app(rec(), h), app(g, app(s(), x))) -> app#(h, x),
       app#(app(rec(), h), app(g, app(s(), x))) -> app#(app(h, x), app(app(rec(), h), app(g, x))),
       app#(app(rec(), h), app(g, app(s(), x))) -> app#(app(rec(), h), app(g, x))}
     Weak:
     {app(app(rec(), h), app(g, app(s(), x))) -> app(app(h, x), app(app(rec(), h), app(g, x))),
              app(app(rec(), h), app(g, 0())) -> g}
     Fail