Optimum basis of finite convex geometry

DOI10.1016/J.DAM.2017.06.009zbMATH Open1423.06012arXiv1205.3236OpenAlexW2963533754MaRDI QIDQ2399285FDOQ2399285

Authors: Kira Adaricheva 

Publication date: 22 August 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: 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

Full work available at URL: https://arxiv.org/abs/1205.3236

Recommendations

• On implicational bases of closure systems with unique critical sets.
• The theory of convex geometries
• Resolutions of convex geometries
• Representing finite convex geometries by relatively convex sets
• Base Points, Non-unit Implications, and Convex Geometries

zbMATH Keywords

convex geometrycanonical basissupersolvable latticeaffine convex geometryminimum basissystem of implicationsacyclic Horn Boolean functionsanti-exchange closure operatorHorn rules of antimatroidminimum CNF-representationminimum representations of acyclic hypergraphsoptimum basis

Mathematics Subject Classification ID

Galois correspondences, closure operators (in relation to ordered sets) (06A15) Boolean functions (06E30) Axiomatic and generalized convexity (52A01)

Cites Work

• The theory of convex geometries
• The core of finite lattices
• Join-semidistributive lattices and convex geometries.
• Representing finite convex geometries by relatively convex sets
• Supersolvable lattices
• Finite Sublattices of a Free Lattice
• Semidistributive and coalgebraic lattices of subsemilattices
• A use for frequently rediscovering a concept
• The sorting order on a Coxeter group.
• Minimum Covers in Relational Database Model
• The lattices of closure systems, closure operators, and implicational systems on a finite set: A survey
• Title not available (Why is that?)
• A subclass of Horn CNFs optimally compressible in polynomial time
• Title not available (Why is that?)
• A theory of finite closure spaces based on implications
• The multiple facets of the canonical direct unit implicational basis
• EL-labelings, supersolvability and 0-Hecke algebra actions on posets
• Realization of abstract convex geometries by point configurations
• A circuit set characterization of antimatroids
• Ordered direct implicational basis of a finite closure system
• The prime stems of rooted circuits of closure spaces and minimum implicational bases
• Lattices of regular closed subsets of closure spaces
• Optimal implicational bases for finite modular lattices
• On implicational bases of closure systems with unique critical sets.
• Two embedding theorems for lower bounded lattices
• Title not available (Why is that?)
• A representation of antimatroids by Horn rules and its application to educational systems

Cited In (11)

• A modular characterization of supersolvable lattices
• The prime stems of rooted circuits of closure spaces and minimum implicational bases
• Translating between the representations of a ranked convex geometry
• Enumerating maximal consistent closed sets in closure systems
• Description lattices of generalised convex hulls
• What convex geometries tell about shattering-extremal systems
• Quasi-closed elements in fuzzy posets
• The joy of implications, aka pure Horn formulas: mainly a survey
• A representation of antimatroids by Horn rules and its application to educational systems
• Notes on join semidistributive lattices
• On implicational bases of closure systems with unique critical sets.

This page was built for publication: Optimum basis of finite convex geometry

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2399285)