YES Problem: admit(x,nil()) -> nil() admit(x,.(u,.(v,.(w(),z)))) -> cond(=(sum(x,u,v),w()),.(u,.(v,.(w(),admit(carry(x,u,v),z))))) cond(true(),y) -> y Proof: DP Processor: DPs: admit#(x,.(u,.(v,.(w(),z)))) -> admit#(carry(x,u,v),z) admit#(x,.(u,.(v,.(w(),z)))) -> cond#(=(sum(x,u,v),w()),.(u,.(v,.(w(),admit(carry(x,u,v),z))))) TRS: admit(x,nil()) -> nil() admit(x,.(u,.(v,.(w(),z)))) -> cond(=(sum(x,u,v),w()),.(u,.(v,.(w(),admit(carry(x,u,v),z))))) cond(true(),y) -> y Matrix Interpretation Processor: dim=1 interpretation: [cond#](x0, x1) = 4x0 + x1, [admit#](x0, x1) = 7x0 + 2x1 + 6, [true] = 4, [cond](x0, x1) = 3x0 + x1 + 2, [carry](x0, x1, x2) = x0 + x1 + 2, [=](x0, x1) = x0 + x1, [sum](x0, x1, x2) = x1, [.](x0, x1) = 4x0 + x1, [w] = 2, [admit](x0, x1) = 2x1, [nil] = 4 orientation: admit#(x,.(u,.(v,.(w(),z)))) = 8u + 8v + 7x + 2z + 22 >= 7u + 7x + 2z + 20 = admit#(carry(x,u,v),z) admit#(x,.(u,.(v,.(w(),z)))) = 8u + 8v + 7x + 2z + 22 >= 8u + 4v + 2z + 16 = cond#(=(sum(x,u,v),w()),.(u,.(v,.(w(),admit(carry(x,u,v),z))))) admit(x,nil()) = 8 >= 4 = nil() admit(x,.(u,.(v,.(w(),z)))) = 8u + 8v + 2z + 16 >= 7u + 4v + 2z + 16 = cond(=(sum(x,u,v),w()),.(u,.(v,.(w(),admit(carry(x,u,v),z))))) cond(true(),y) = y + 14 >= y = y problem: DPs: TRS: admit(x,nil()) -> nil() admit(x,.(u,.(v,.(w(),z)))) -> cond(=(sum(x,u,v),w()),.(u,.(v,.(w(),admit(carry(x,u,v),z))))) cond(true(),y) -> y Qed