An algorithm for the difference between set covers

A set cover for a set SS is a collection CC of special subsets whose union is SS. Given covers AA and BB for two sets, the set-cover difference problem   is to construct a new cover for the elements covered by AA but not BB. Applications include testing equivalence of set covers and maintaining a set cover dynamically. In this paper, we solve the set-cover difference problem by defining a difference operation A-BA-B, which turns out to be a pseudocomplement on a distributive lattice. We give an algorithm for constructing this difference, and show how to implement the algorithm for two examples with applications in computer science: face covers on a hypercube, and rectangle covers on a grid. We derive an upper bound on the time complexity of the algorithm, and give upper and lower bounds on complexity for face covers and rectangle covers.