Some Notes on Managing Closure Operators

摘要

It is widely known that closure operators on finite sets can be represented by sets of implications (also known as inclusion dependencies) as well as by formal contexts. In this paper we survey known results and present new findings concerning time and space requirements of diverse tasks for managing closure operators, given in contextual, implicational, or black-box representation. These tasks include closure computation, size minimization, finer-coarser-comparison, modification by "adding" closed sets or implications, and conversion from one representation into another.