Optimum basis of finite convex geometry

DOI10.1016/J.DAM.2017.06.009MaRDI QIDQ2399285zbMATH OpenOpenAlexFDO

Authors Kira Adaricheva

Publication date 22 August 2017

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

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

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)

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

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

Cites work

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

Cited in

(11)

• The prime stems of rooted circuits of closure spaces and minimum implicational bases
• A modular characterization of supersolvable lattices
• 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
• On implicational bases of closure systems with unique critical sets.
• Notes on join semidistributive lattices

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)