Optimum basis of finite convex geometry
Loading...
Date
2016
Authors
Adaricheva, Kira
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Convex geometries form a subclass of closure systems with unique
criticals, or UC-systems. We show that the F-basis introduced in [6] for UC-
systems, becomes optimum in convex geometries, in two essential parts of the
basis: right sides (conclusions) of binary implications and left sides (premises)
of non-binary ones. The right sides of non-binary implications can also be
optimized, when the convex geometry either satis es the Carousel property,
or does not have D-cycles. The latter generalizes a result of P.L. Hammer
and A. Kogan for acyclic Horn Boolean functions. Convex geometries of order
convex subsets in a poset also have tractable optimum basis. The problem of
tractability of optimum basis in convex geometries in general remains to be
open
Description
Keywords
Research Subject Categories::MATHEMATICS, finite convex geometry
Citation
Adaricheva Kira; 2016; Optimum basis of finite convex geometry; arXiv.org