Computing the D-base and D-relation in finite closure systems

DOI10.1016/J.TCS.2025.115459MaRDI QIDQ6930243zbMATH OpenFDO

Authors Kira Adaricheva, Lhouari Nourine, Simon Vilmin

Publication date 16 September 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115459

zbMATH Keywords

\(D\)-base\(D\)-relationalgorithmic enumerationclosure systemsdistributive lattice dualizationminimal join coverssolution-graph traversal

Mathematics Subject Classification ID

Galois correspondences, closure operators (in relation to ordered sets) (06A15)

Cites work

• A polynomial delay algorithm for generating connected induced subgraphs of a given cardinality
• A subclass of Horn CNFs optimally compressible in polynomial time
• A theory of finite closure spaces based on implications
• Algorithms – ESA 2004
• Candidate keys for relations
• Computational aspects of monotone dualization: a brief survey
• Construction of finite lattices of subsemilattices
• Discovery of the D-basis in binary tables based on hypergraph dualization
• Doubling Constructions in Lattice Theory
• Enumeration complexity
• Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements
• Horn minimization by iterative decomposition
• scientific article; zbMATH DE number 108405 (Why is no real title available?)
• scientific article; zbMATH DE number 3580595 (Why is no real title available?)
• 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?)
• Hypergraph Horn functions
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Knowledge Spaces
• Lattice Theory: Foundation
• Lattices, closures systems and implication bases: a survey of structural aspects and algorithms
• Matroid Horn functions
• Measuring the implications of the D-basis in analysis of data in biomedical studies
• On a dependence relation in finite lattices
• On Dualization over Distributive Lattices
• On generating all maximal independent sets
• On implicational bases of closure systems with unique critical sets.
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• Optimum basis of finite convex geometry
• Ordered direct implicational basis of a finite closure system
• Polynomial delay hybrid algorithms to enumerate candidate keys for a relation
• Polynomial-time inference of all valid implications for Horn and related formulae
• Projective Geometry on Partially Ordered Sets
• The joy of implications, aka pure Horn formulas: mainly a survey
• THE LATTICE THEORY OF FUNCTIONAL DEPENDENCIES AND NORMAL DECOMPOSITIONS
• The multiple facets of the canonical direct unit implicational basis
• The theory of convex geometries

This page was built for publication: Computing the \(D\)-base and \(D\)-relation in finite closure systems

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