Minimum Implicational Basis for -Semidistributive Lattices - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Information Processing Letters Year : 2006

Minimum Implicational Basis for -Semidistributive Lattices

Abstract

For a ∧-semidistributive lattice L, we study some particular implicational systems and show that the cardinality of a minimum implicational basis is polynomial in the size of join-irreducible elements of the lattice L. We also provide a polynomial time algorithm to compute a minimum implicational basis for L.

Domains

Other Discrete Mathematics [cs.DM] Data Structures and Algorithms [cs.DS]
Fichier principal
Vignette du fichier
pja_document_article.pdf (144.21 Ko) Télécharger le fichier

Martine Peridier  : Connect in order to contact the contributor

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00101743

Submitted on : Thursday, September 28, 2006-9:54:58 AM

Last modification on : Tuesday, April 18, 2023-10:00:05 AM

Long-term archiving on : Monday, April 5, 2010-11:56:00 PM

Download

Dates and versions

lirmm-00101743 , version 1 (28-09-2006)

Identifiers

Cite

Philippe Janssen, Lhouari Nourine. Minimum Implicational Basis for -Semidistributive Lattices. Information Processing Letters, 2006, 99 (5), pp.199-202. ⟨10.1016/j.ipl.2006.04.004⟩. ⟨lirmm-00101743⟩

Export

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

PRES_CLERMONT CNRS LIMOS ALGCO LIRMM TDS-MACS MIPS UNIV-MONTPELLIER CLERMONT-AUVERGNE-INP
561 View
300 Download

Altmetric

Share

More