Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements
From MaRDI portal
Abstract: We are interested in the problem of translating between two representations of closure systems, namely implicational bases and meet-irreducible elements. Albeit its importance, the problem is open. Motivated by this problem, we introduce splits of an implicational base. It is a partitioning operation of the implications which we apply recursively to obtain a binary tree representing a decomposition of the implicational base. We show that this decomposition can be conducted in polynomial time and space in the size of the input implicational base. In order to use our decomposition for the translation task, we focus on the case of acyclic splits. In this case, we obtain a recursive characterization of the meet-irreducible elements of the associated closure system. We use this characterization and hypergraph dualization to derive new results for the translation problem in acyclic convex geometries.
Recommendations
- On implication bases in \(n\)-lattices
- Implicational classes of De Morgan lattices
- Hierarchies in independence and inclusion logic with strict semantics
- scientific article; zbMATH DE number 2154085
- Representation of finite semilattices by meet-irreducibles
- Analyse logique, combinatoire et statistique de la construction d’une hiérarchie binaire implicative ; niveaux et nœuds significatifs,
- Implication and equivalential reducts of basic algebras
- Direct decomposability of implication operators on product lattices.
- Reducibilities among equivalence relations induced by recursively enumerable structures
- Decidability, Recursive Enumerability and Kleene Hierarchy ForL-Subsets
Cites work
- A cost function for similarity-based hierarchical clustering
- A theory of finite closure spaces based on implications
- Algorithms for k-meet-semidistributive lattices
- Algorithms for inferring functional dependencies from relations
- Attribute-incremental construction of the canonical implication basis
- Candidate keys for relations
- Characterizations of the convex geometries arising from the double shellings of posets
- Computing premises of a minimal cover of functional dependencies is intractable
- Computing the minimum cover of functional dependencies
- Convexity in Graphs and Hypergraphs
- Direct product decompositions of lattices, closures and relation schemes
- Discovery of the D-basis in binary tables based on hypergraph dualization
- Dualization in lattices given by ordered sets of irreducibles
- Functional dependencies in relational databases: A lattice point of view
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- Generating all maximal models of a Boolean expression
- scientific article; zbMATH DE number 108405 (Why is no real title available?)
- scientific article; zbMATH DE number 1534358 (Why is no real title available?)
- scientific article; zbMATH DE number 1748069 (Why is no real title available?)
- scientific article; zbMATH DE number 758787 (Why is no real title available?)
- scientific article; zbMATH DE number 861622 (Why is no real title available?)
- scientific article; zbMATH DE number 7635224 (Why is no real title available?)
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- Lattice Theory: Foundation
- Lattices, closures systems and implication bases: a survey of structural aspects and algorithms
- Minimal Representation of Directed Hypergraphs
- Notes on join semidistributive lattices
- On generating all maximal independent sets
- On implicational bases of closure systems with unique critical sets.
- On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- On the complexity of enumerating pseudo-intents
- On the dualization in distributive lattices and related problems
- On the intractability of computing the Duquenne-Guigues base
- Optimal implicational bases for finite modular lattices
- Ordered direct implicational basis of a finite closure system
- Representation of lattices via set-colored posets
- The Factorization and Representation of Lattices
- The joy of implications, aka pure Horn formulas: mainly a survey
- The multiple facets of the canonical direct unit implicational basis
- The theory of convex geometries
- Translating between the representations of a ranked convex geometry
- Worst-case Analysis of Set Union Algorithms
Cited in
(2)
This page was built for publication: Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6165553)
