YES(?,O(n^1))
TRS:
 {
      g mark X -> g X,
    g active X -> g X,
      h mark X -> h X,
    h active X -> h X,
      mark g X -> active g X,
      mark h X -> active h X,
      mark d() -> active d(),
      mark c() -> active c(),
    active g X -> mark h X,
  active h d() -> mark g c(),
    active c() -> mark d()
 }
 DUP: We consider a non-duplicating system.
  Trs:
   {
        g mark X -> g X,
      g active X -> g X,
        h mark X -> h X,
      h active X -> h X,
        mark g X -> active g X,
        mark h X -> active h X,
        mark d() -> active d(),
        mark c() -> active c(),
      active g X -> mark h X,
    active h d() -> mark g c(),
      active c() -> mark d()
   }
  RLAB:
   Strict:
    {
       g(mark) mark(g) X -> g(g) X,
       g(mark) mark(g) g(g) X -> g(active) active(g) g(g) X,
       g(mark) mark(g) g(mark) X -> g(active) active(g) g(mark) X,
       g(mark) mark(g) g(h) X -> g(active) active(g) g(h) X,
       g(mark) mark(g) g(active) X -> g(active) active(g) g(active) X,
       g(mark) mark(g) g(d) X -> g(active) active(g) g(d) X,
       g(mark) mark(g) g(c) X -> g(active) active(g) g(c) X,
       g(mark) mark(mark) X -> g(mark) X,
       g(mark) mark(h) X -> g(h) X,
       g(mark) mark(h) h(g) X -> g(active) active(h) h(g) X,
       g(mark) mark(h) h(mark) X -> g(active) active(h) h(mark) X,
       g(mark) mark(h) h(h) X -> g(active) active(h) h(h) X,
       g(mark) mark(h) h(active) X -> g(active) active(h) h(active) X,
       g(mark) mark(h) h(d) X -> g(active) active(h) h(d) X,
       g(mark) mark(h) h(c) X -> g(active) active(h) h(c) X,
       g(mark) mark(active) X -> g(active) X,
       g(mark) mark(d) X -> g(d) X,
     g(mark) mark(d) d() -> g(active) active(d) d(),
       g(mark) mark(c) X -> g(c) X,
     g(mark) mark(c) c() -> g(active) active(c) c(),
       g(active) active(g) X -> g(g) X,
       g(active) active(g) g(g) X -> g(mark) mark(h) h(g) X,
       g(active) active(g) g(mark) X -> g(mark) mark(h) h(mark) X,
       g(active) active(g) g(h) X -> g(mark) mark(h) h(h) X,
       g(active) active(g) g(active) X -> g(mark) mark(h) h(active) X,
       g(active) active(g) g(d) X -> g(mark) mark(h) h(d) X,
       g(active) active(g) g(c) X -> g(mark) mark(h) h(c) X,
       g(active) active(mark) X -> g(mark) X,
       g(active) active(h) X -> g(h) X,
     g(active) active(h) h(d) d() -> g(mark) mark(g) g(c) c(),
       g(active) active(active) X -> g(active) X,
       g(active) active(d) X -> g(d) X,
       g(active) active(c) X -> g(c) X,
     g(active) active(c) c() -> g(mark) mark(d) d(),
       h(mark) mark(g) X -> h(g) X,
       h(mark) mark(g) g(g) X -> h(active) active(g) g(g) X,
       h(mark) mark(g) g(mark) X -> h(active) active(g) g(mark) X,
       h(mark) mark(g) g(h) X -> h(active) active(g) g(h) X,
       h(mark) mark(g) g(active) X -> h(active) active(g) g(active) X,
       h(mark) mark(g) g(d) X -> h(active) active(g) g(d) X,
       h(mark) mark(g) g(c) X -> h(active) active(g) g(c) X,
       h(mark) mark(mark) X -> h(mark) X,
       h(mark) mark(h) X -> h(h) X,
       h(mark) mark(h) h(g) X -> h(active) active(h) h(g) X,
       h(mark) mark(h) h(mark) X -> h(active) active(h) h(mark) X,
       h(mark) mark(h) h(h) X -> h(active) active(h) h(h) X,
       h(mark) mark(h) h(active) X -> h(active) active(h) h(active) X,
       h(mark) mark(h) h(d) X -> h(active) active(h) h(d) X,
       h(mark) mark(h) h(c) X -> h(active) active(h) h(c) X,
       h(mark) mark(active) X -> h(active) X,
       h(mark) mark(d) X -> h(d) X,
     h(mark) mark(d) d() -> h(active) active(d) d(),
       h(mark) mark(c) X -> h(c) X,
     h(mark) mark(c) c() -> h(active) active(c) c(),
       h(active) active(g) X -> h(g) X,
       h(active) active(g) g(g) X -> h(mark) mark(h) h(g) X,
       h(active) active(g) g(mark) X -> h(mark) mark(h) h(mark) X,
       h(active) active(g) g(h) X -> h(mark) mark(h) h(h) X,
       h(active) active(g) g(active) X -> h(mark) mark(h) h(active) X,
       h(active) active(g) g(d) X -> h(mark) mark(h) h(d) X,
       h(active) active(g) g(c) X -> h(mark) mark(h) h(c) X,
       h(active) active(mark) X -> h(mark) X,
       h(active) active(h) X -> h(h) X,
     h(active) active(h) h(d) d() -> h(mark) mark(g) g(c) c(),
       h(active) active(active) X -> h(active) X,
       h(active) active(d) X -> h(d) X,
       h(active) active(c) X -> h(c) X,
     h(active) active(c) c() -> h(mark) mark(d) d(),
       mark(mark) mark(g) g(g) X -> mark(active) active(g) g(g) X,
       mark(mark) mark(g) g(mark) X -> mark(active) active(g) g(mark) X,
       mark(mark) mark(g) g(h) X -> mark(active) active(g) g(h) X,
       mark(mark) mark(g) g(active) X -> mark(active) active(g) g(active) X,
       mark(mark) mark(g) g(d) X -> mark(active) active(g) g(d) X,
       mark(mark) mark(g) g(c) X -> mark(active) active(g) g(c) X,
       mark(mark) mark(h) h(g) X -> mark(active) active(h) h(g) X,
       mark(mark) mark(h) h(mark) X -> mark(active) active(h) h(mark) X,
       mark(mark) mark(h) h(h) X -> mark(active) active(h) h(h) X,
       mark(mark) mark(h) h(active) X -> mark(active) active(h) h(active) X,
       mark(mark) mark(h) h(d) X -> mark(active) active(h) h(d) X,
       mark(mark) mark(h) h(c) X -> mark(active) active(h) h(c) X,
     mark(mark) mark(d) d() -> mark(active) active(d) d(),
     mark(mark) mark(c) c() -> mark(active) active(c) c(),
       mark(active) active(g) g(g) X -> mark(mark) mark(h) h(g) X,
       mark(active) active(g) g(mark) X -> mark(mark) mark(h) h(mark) X,
       mark(active) active(g) g(h) X -> mark(mark) mark(h) h(h) X,
       mark(active) active(g) g(active) X -> mark(mark) mark(h) h(active) X,
       mark(active) active(g) g(d) X -> mark(mark) mark(h) h(d) X,
       mark(active) active(g) g(c) X -> mark(mark) mark(h) h(c) X,
     mark(active) active(h) h(d) d() -> mark(mark) mark(g) g(c) c(),
     mark(active) active(c) c() -> mark(mark) mark(d) d(),
       active(mark) mark(g) g(g) X -> active(active) active(g) g(g) X,
       active(mark) mark(g) g(mark) X -> active(active) active(g) g(mark) X,
       active(mark) mark(g) g(h) X -> active(active) active(g) g(h) X,
       active(mark) mark(g) g(active) X ->
     active(active) active(g) g(active) X,
       active(mark) mark(g) g(d) X -> active(active) active(g) g(d) X,
       active(mark) mark(g) g(c) X -> active(active) active(g) g(c) X,
       active(mark) mark(h) h(g) X -> active(active) active(h) h(g) X,
       active(mark) mark(h) h(mark) X -> active(active) active(h) h(mark) X,
       active(mark) mark(h) h(h) X -> active(active) active(h) h(h) X,
       active(mark) mark(h) h(active) X ->
     active(active) active(h) h(active) X,
       active(mark) mark(h) h(d) X -> active(active) active(h) h(d) X,
       active(mark) mark(h) h(c) X -> active(active) active(h) h(c) X,
     active(mark) mark(d) d() -> active(active) active(d) d(),
     active(mark) mark(c) c() -> active(active) active(c) c(),
       active(active) active(g) g(g) X -> active(mark) mark(h) h(g) X,
       active(active) active(g) g(mark) X -> active(mark) mark(h) h(mark) X,
       active(active) active(g) g(h) X -> active(mark) mark(h) h(h) X,
       active(active) active(g) g(active) X ->
     active(mark) mark(h) h(active) X,
       active(active) active(g) g(d) X -> active(mark) mark(h) h(d) X,
       active(active) active(g) g(c) X -> active(mark) mark(h) h(c) X,
     active(active) active(h) h(d) d() -> active(mark) mark(g) g(c) c(),
     active(active) active(c) c() -> active(mark) mark(d) d()
    }
   Weak:
    {}
   Natural interpretation:
    Strict:
     {
        g(mark) mark(g) X -> g(g) X,
        g(mark) mark(g) g(g) X -> g(active) active(g) g(g) X,
        g(mark) mark(g) g(mark) X -> g(active) active(g) g(mark) X,
        g(mark) mark(g) g(h) X -> g(active) active(g) g(h) X,
        g(mark) mark(g) g(active) X -> g(active) active(g) g(active) X,
        g(mark) mark(g) g(d) X -> g(active) active(g) g(d) X,
        g(mark) mark(g) g(c) X -> g(active) active(g) g(c) X,
        g(mark) mark(mark) X -> g(mark) X,
        g(mark) mark(h) X -> g(h) X,
        g(mark) mark(h) h(g) X -> g(active) active(h) h(g) X,
        g(mark) mark(h) h(mark) X -> g(active) active(h) h(mark) X,
        g(mark) mark(h) h(h) X -> g(active) active(h) h(h) X,
        g(mark) mark(h) h(active) X -> g(active) active(h) h(active) X,
        g(mark) mark(h) h(d) X -> g(active) active(h) h(d) X,
        g(mark) mark(h) h(c) X -> g(active) active(h) h(c) X,
        g(mark) mark(active) X -> g(active) X,
        g(mark) mark(d) X -> g(d) X,
      g(mark) mark(d) d() -> g(active) active(d) d(),
        g(mark) mark(c) X -> g(c) X,
      g(mark) mark(c) c() -> g(active) active(c) c(),
        g(active) active(g) X -> g(g) X,
        g(active) active(g) g(g) X -> g(mark) mark(h) h(g) X,
        g(active) active(g) g(mark) X -> g(mark) mark(h) h(mark) X,
        g(active) active(g) g(h) X -> g(mark) mark(h) h(h) X,
        g(active) active(g) g(active) X -> g(mark) mark(h) h(active) X,
        g(active) active(g) g(d) X -> g(mark) mark(h) h(d) X,
        g(active) active(g) g(c) X -> g(mark) mark(h) h(c) X,
        g(active) active(mark) X -> g(mark) X,
        g(active) active(h) X -> g(h) X,
      g(active) active(h) h(d) d() -> g(mark) mark(g) g(c) c(),
        g(active) active(active) X -> g(active) X,
        g(active) active(d) X -> g(d) X,
        g(active) active(c) X -> g(c) X,
      g(active) active(c) c() -> g(mark) mark(d) d(),
        h(mark) mark(g) X -> h(g) X,
        h(mark) mark(g) g(g) X -> h(active) active(g) g(g) X,
        h(mark) mark(g) g(mark) X -> h(active) active(g) g(mark) X,
        h(mark) mark(g) g(h) X -> h(active) active(g) g(h) X,
        h(mark) mark(g) g(active) X -> h(active) active(g) g(active) X,
        h(mark) mark(g) g(d) X -> h(active) active(g) g(d) X,
        h(mark) mark(g) g(c) X -> h(active) active(g) g(c) X,
        h(mark) mark(mark) X -> h(mark) X,
        h(mark) mark(h) X -> h(h) X,
        h(mark) mark(h) h(g) X -> h(active) active(h) h(g) X,
        h(mark) mark(h) h(mark) X -> h(active) active(h) h(mark) X,
        h(mark) mark(h) h(h) X -> h(active) active(h) h(h) X,
        h(mark) mark(h) h(active) X -> h(active) active(h) h(active) X,
        h(mark) mark(h) h(d) X -> h(active) active(h) h(d) X,
        h(mark) mark(h) h(c) X -> h(active) active(h) h(c) X,
        h(mark) mark(active) X -> h(active) X,
        h(mark) mark(d) X -> h(d) X,
      h(mark) mark(d) d() -> h(active) active(d) d(),
        h(mark) mark(c) X -> h(c) X,
      h(mark) mark(c) c() -> h(active) active(c) c(),
        h(active) active(g) X -> h(g) X,
        h(active) active(g) g(g) X -> h(mark) mark(h) h(g) X,
        h(active) active(g) g(mark) X -> h(mark) mark(h) h(mark) X,
        h(active) active(g) g(h) X -> h(mark) mark(h) h(h) X,
        h(active) active(g) g(active) X -> h(mark) mark(h) h(active) X,
        h(active) active(g) g(d) X -> h(mark) mark(h) h(d) X,
        h(active) active(g) g(c) X -> h(mark) mark(h) h(c) X,
        h(active) active(mark) X -> h(mark) X,
        h(active) active(h) X -> h(h) X,
      h(active) active(h) h(d) d() -> h(mark) mark(g) g(c) c(),
        h(active) active(active) X -> h(active) X,
        h(active) active(d) X -> h(d) X,
        h(active) active(c) X -> h(c) X,
      h(active) active(c) c() -> h(mark) mark(d) d(),
        mark(mark) mark(g) g(g) X -> mark(active) active(g) g(g) X,
        mark(mark) mark(g) g(mark) X -> mark(active) active(g) g(mark) X,
        mark(mark) mark(g) g(h) X -> mark(active) active(g) g(h) X,
        mark(mark) mark(g) g(active) X -> mark(active) active(g) g(active) X,
        mark(mark) mark(g) g(d) X -> mark(active) active(g) g(d) X,
        mark(mark) mark(g) g(c) X -> mark(active) active(g) g(c) X,
        mark(mark) mark(h) h(g) X -> mark(active) active(h) h(g) X,
        mark(mark) mark(h) h(mark) X -> mark(active) active(h) h(mark) X,
        mark(mark) mark(h) h(h) X -> mark(active) active(h) h(h) X,
        mark(mark) mark(h) h(active) X -> mark(active) active(h) h(active) X,
        mark(mark) mark(h) h(d) X -> mark(active) active(h) h(d) X,
        mark(mark) mark(h) h(c) X -> mark(active) active(h) h(c) X,
      mark(mark) mark(d) d() -> mark(active) active(d) d(),
      mark(mark) mark(c) c() -> mark(active) active(c) c(),
        mark(active) active(g) g(g) X -> mark(mark) mark(h) h(g) X,
        mark(active) active(g) g(mark) X -> mark(mark) mark(h) h(mark) X,
        mark(active) active(g) g(h) X -> mark(mark) mark(h) h(h) X,
        mark(active) active(g) g(active) X -> mark(mark) mark(h) h(active) X,
        mark(active) active(g) g(d) X -> mark(mark) mark(h) h(d) X,
        mark(active) active(g) g(c) X -> mark(mark) mark(h) h(c) X,
      mark(active) active(h) h(d) d() -> mark(mark) mark(g) g(c) c(),
      mark(active) active(c) c() -> mark(mark) mark(d) d(),
        active(mark) mark(g) g(g) X -> active(active) active(g) g(g) X,
        active(mark) mark(g) g(mark) X -> active(active) active(g) g(mark) X,
        active(mark) mark(g) g(h) X -> active(active) active(g) g(h) X,
        active(mark) mark(g) g(active) X ->
      active(active) active(g) g(active) X,
        active(mark) mark(g) g(d) X -> active(active) active(g) g(d) X,
        active(mark) mark(g) g(c) X -> active(active) active(g) g(c) X,
        active(mark) mark(h) h(g) X -> active(active) active(h) h(g) X,
        active(mark) mark(h) h(mark) X -> active(active) active(h) h(mark) X,
        active(mark) mark(h) h(h) X -> active(active) active(h) h(h) X,
        active(mark) mark(h) h(active) X ->
      active(active) active(h) h(active) X,
        active(mark) mark(h) h(d) X -> active(active) active(h) h(d) X,
        active(mark) mark(h) h(c) X -> active(active) active(h) h(c) X,
      active(mark) mark(d) d() -> active(active) active(d) d(),
      active(mark) mark(c) c() -> active(active) active(c) c(),
        active(active) active(g) g(g) X -> active(mark) mark(h) h(g) X,
        active(active) active(g) g(mark) X -> active(mark) mark(h) h(mark) X,
        active(active) active(g) g(h) X -> active(mark) mark(h) h(h) X,
        active(active) active(g) g(active) X ->
      active(mark) mark(h) h(active) X,
        active(active) active(g) g(d) X -> active(mark) mark(h) h(d) X,
        active(active) active(g) g(c) X -> active(mark) mark(h) h(c) X,
      active(active) active(h) h(d) d() -> active(mark) mark(g) g(c) c(),
      active(active) active(c) c() -> active(mark) mark(d) d()
     }
    Weak:
     {}
    Interpretation class: stronglylinear
    [c] = + 2
    [d] = + 4
    [active(5)](X0) = + 1*X0 + 7
    [active(4)](X0) = + 1*X0 + 0
    [active(3)](X0) = + 1*X0 + 1
    [active(2)](X0) = + 1*X0 + 3
    [active(1)](X0) = + 1*X0 + 4
    [active(0)](X0) = + 1*X0 + 5
    [mark(5)](X0) = + 1*X0 + 7
    [mark(4)](X0) = + 1*X0 + 1
    [mark(3)](X0) = + 1*X0 + 1
    [mark(2)](X0) = + 1*X0 + 1
    [mark(1)](X0) = + 1*X0 + 4
    [mark(0)](X0) = + 1*X0 + 3
    [h(5)](X0) = + 1*X0 + 0
    [h(4)](X0) = + 1*X0 + 2
    [h(3)](X0) = + 1*X0 + 4
    [h(2)](X0) = + 1*X0 + 0
    [h(1)](X0) = + 1*X0 + 7
    [h(0)](X0) = + 1*X0 + 1
    [g(5)](X0) = + 1*X0 + 0
    [g(4)](X0) = + 1*X0 + 2
    [g(3)](X0) = + 1*X0 + 4
    [g(2)](X0) = + 1*X0 + 4
    [g(1)](X0) = + 1*X0 + 7
    [g(0)](X0) = + 1*X0 + 4
    
    Qed