Optimum basis of finite convex geometry

Convex geometries form a subclass of closure systems with unique criticals, or \(UC\)-systems. We show that the \(F\)-basis introduced in [1] for \(UC\)-systems, becomes optimum in convex geometries, in two essential parts of the basis: right sides (conclusions) of binary implications and left sides...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2016-01
Main Author: Adaricheva, Kira
Format: Article
Language:English
Subjects:
Boolean algebra
Boolean functions
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Convex geometries form a subclass of closure systems with unique criticals, or \(UC\)-systems. We show that the \(F\)-basis introduced in [1] 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 satisfies 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. [1] K. Adaricheva and J.B.Nation, On implicational bases of closure systems with unique critical sets, arxiv:1205.2881
ISSN:2331-8422