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 Usable Rule 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))))) Arctic Interpretation Processor: dimension: 1 usable rules: interpretation: [cond#](x0, x1) = x0 + 1, [admit#](x0, x1) = 4x0 + 4x1 + 0, [cond](x0, x1) = x1 + 0, [carry](x0, x1, x2) = x1, [=](x0, x1) = x0 + x1 + 1, [sum](x0, x1, x2) = x0 + x2 + 1, [.](x0, x1) = 1x0 + 1x1 + 0, [w] = 0, [admit](x0, x1) = 4x0 + x1 + 1, [nil] = 4 orientation: admit#(x,.(u,.(v,.(w(),z)))) = 5u + 6v + 4x + 7z + 7 >= 4u + 4z + 0 = admit#(carry(x,u,v),z) admit#(x,.(u,.(v,.(w(),z)))) = 5u + 6v + 4x + 7z + 7 >= v + x + 1 = cond#(=(sum(x,u,v),w()),.(u,.(v,.(w(),admit(carry(x,u,v),z))))) admit(x,nil()) = 4x + 4 >= 4 = nil() admit(x,.(u,.(v,.(w(),z)))) = 1u + 2v + 4x + 3z + 3 >= 7u + 2v + 3z + 4 = cond(=(sum(x,u,v),w()),.(u,.(v,.(w(),admit(carry(x,u,v),z))))) 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))))) Qed