A compact representation for modular semilattices and its applications

DOI10.1007/S11083-019-09516-0zbMATH Open1484.06015arXiv1705.05781OpenAlexW3085082021MaRDI QIDQ2006979FDOQ2006979

Authors: Hiroshi Hirai, So Nakashima 

Publication date: 12 October 2020

Published in: Order (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

submodular functionimplicational basemodular semilatticeBirkhoff representation theorem

Mathematics Subject Classification ID

Semilattices (06A12)

Cites Work

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

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)