A compact representation for modular semilattices and its applications

DOI10.1007/S11083-019-09516-0MaRDI QIDQ2006979zbMATH OpenOpenAlexFDO

Authors Hiroshi Hirai, So Nakashima

Publication date 12 October 2020

Published in Order (Search for Journal in Brave)

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

zbMATH Keywords

submodular functionimplicational basemodular semilatticeBirkhoff representation theorem

Mathematics Subject Classification ID

Semilattices (06A12)

Abstract: A modular semilattice is a semilattice generalization of a modular lattice. We establish a Birkhoff-type representation theorem for modular semilattices, which says that every modular semilattice is isomorphic to the family of ideals in a certain poset with additional relations.This new poset structure, which we axiomatize in this paper, is called a PPIP (projective poset with inconsistent pairs). A PPIP is a common generalization of a PIP (poset with inconsistent pairs) and a projective ordered space. The former was introduced by Barth'elemy and Constantin for establishing Birkhoff-type theorem for median semilattices, and the latter by Herrmann, Pickering, and Roddy for modular lattices. We show the $Theta(n)$ representation complexityand a construction algorithm for PPIP-representations of $(wedge,vee)$-closed sets in the product $L^n$ of modular semilattice $L$. This generalizes the results of Hirai and Oki for a special median semilattice $S_k$. We also investigate implicational bases for modular semilattices. Extending earlier results of Wild and Herrmann for modular lattices, we determine optimal implicational bases and develop a polynomial time recognition algorithm for modular semilattices. These results can be applied to retain the minimizer set of a submodular function on a modular semilattice.

Recommendations

• On modular pairs in semilattices
• scientific article; zbMATH DE number 1313604
• scientific article; zbMATH DE number 5610899
• A Representation Theorem for Semilattices
• Compactable semilattices
• Modular and Admissible Semilattices
• Quasi-modular pseudocomplemented semilattices
• scientific article; zbMATH DE number 1220854
• Representations of matroids in semimodular lattices
• The modularity of the lattice of varieties of completely regular semigroups and related representations

Cites work

• scientific article; zbMATH DE number 3865299 (Why is no real title available?)
• scientific article; zbMATH DE number 3823168 (Why is no real title available?)
• scientific article; zbMATH DE number 3751028 (Why is no real title available?)
• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• scientific article; zbMATH DE number 7635224 (Why is no real title available?)
• A POLYNOMIAL ALGORITHM FOR TESTING CONGRUENCE MODULARITY
• A compact representation for minimizers of \(k\)-submodular functions
• A geometric description of modular lattices
• A theory of finite closure spaces based on implications
• Block-Triangularizations of Partitioned Matrices Under Similarity/Equivalence Transformations
• Canonical Horn representations and query learning
• Combinatorial Canonical Form of Layered Mixed Matrices and Its Application to Block-Triangularization of Systems of Linear/Nonlinear Equations
• Combinatorial theory.
• Computing DM-decomposition of a partitioned matrix with rank-1 blocks
• Constructive non-commutative rank computation is in deterministic polynomial time
• Discrete convex functions on graphs and their algorithmic applications
• Discrete convexity and polynomial solvability in minimum 0-extension problems
• Foundations of incidence geometry. Projective and polar spaces
• Geodesics in CAT(0) cubical complexes
• Matrices and matroids for systems analysis
• Median graphs, parallelism and posets
• Medians and Betweenness
• Minimum Covers in Relational Database Model
• Modular Interval Spaces
• Operator scaling: theory and applications
• Optimal implicational bases for finite modular lattices
• Petri nets, event structures and domains. I
• Submodular functions and optimization.
• The joy of implications, aka pure Horn formulas: mainly a survey
• The power of linear programming for general-valued CSPs
• Theory of principal partitions revisited
• Towards minimizing \(k\)-submodular functions
• Varieties with few subalgebras of powers
• \(L\)-convexity on graph structures

Cited in

(2)

• A nonpositive curvature property of modular semilattices
• Enumerating maximal consistent closed sets in closure systems

This page was built for publication: A compact representation for modular semilattices and its applications

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