On implicational bases of closure system with unique critical sets
Loading...
Date
2013
Authors
Adaricheva, Kira
Nation, J.B.
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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
Description
Keywords
Research Subject Categories::MATHEMATICS, finite closure system
Citation
Adaricheva Kira, Nation J.B.; 2013; On implicational bases of closure system with unique critical sets; arXiv.org