Аннотация:
We show that every optimum basis of a nite closure system,
in D. Maier's sense, is also right-side optimum, which is a parameter of a
minimum CNF representation of a Horn Boolean function. New parameters
for the size of the binary part are also established. We introduce the K-basis
of a general closure system, which is a re nement of the canonical basis of
V. Duquenne and J.L. Guigues, and discuss a polynomial algorithm to obtain
it. We study closure systems with unique critical sets, and some subclasses
of these where the K-basis is unique. A further re nement in the form of the
E-basis is possible for closure systems without D-cycles. There is a polynomial
algorithm to recognize the D-relation from a K-basis. Thus, closure systems
without D-cycles can be e ectively recognized. While the E-basis achieves an
optimum in one of its parts, the optimization of the others is an NP-complete
problem