A linear delay algorithm for building concept lattices

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Abstract

Concept lattices (also called Galois lattices) have been applied in numerous areas, and several algorithms have been proposed to construct them. Generally, the input for lattice construction algorithms is a binary matrix with size |G||M| representing binary relation I ⊆ G × M . In this paper, we consider polynomial delay algorithms for building concept lattices. Although the concept lattice may be of exponential size, there exist polynomial delay algorithms for building them. The current best delay-time complexity is O(|G||M|2). In this paper, we introduce the notion of irregular concepts, the combinatorial structure of which allows us to develop a linear delay lattice construction algorithm, that is, we give an algorithm with delay time of O(|G||M|). Our algorithm avoids the union operation for the attribute set and does not require checking if new concepts are already generated. In addition, we propose a compact representation for concept lattices and a corresponding construction algorithm. Although we are not guaranteed to achieve optimal compression, the compact representation can save significant storage space compared to the full representation normally used for concept lattices.

Original languageEnglish (US)
Title of host publicationCombinatorial Pattern Matching - 19th Annual Symposium, CPM 2008, Proceedings
Pages204-216
Number of pages13
DOIs
StatePublished - 2008
Event19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008 - Pisa, Italy
Duration: Jun 18 2008Jun 20 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5029 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008
Country/TerritoryItaly
CityPisa
Period6/18/086/20/08

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'A linear delay algorithm for building concept lattices'. Together they form a unique fingerprint.

Cite this