Lattices, closures systems and implication bases: A survey of structural aspects and algorithms
| Autor: | Clément Guérin, Christophe Demko, Jean-François Viaud, Karell Bertet |
|---|---|
| Přispěvatelé: | Laboratoire Informatique, Image et Interaction - EA 2118 (L3I), Université de La Rochelle (ULR), Institut de Recherche en Communications et en Cybernétique de Nantes (IRCCyN), Mines Nantes (Mines Nantes)-École Centrale de Nantes (ECN)-Ecole Polytechnique de l'Université de Nantes (EPUN), Université de Nantes (UN)-Université de Nantes (UN)-PRES Université Nantes Angers Le Mans (UNAM)-Centre National de la Recherche Scientifique (CNRS) |
| Rok vydání: | 2018 |
| Předmět: |
General Computer Science
High Energy Physics::Lattice Lattice problem Distributive lattice 0102 computer and information sciences 02 engineering and technology 01 natural sciences Congruence lattice problem Map of lattices [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] Theoretical Computer Science Complemented lattice Algebra 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Lattice Miner Free lattice Algorithm ComputingMilieux_MISCELLANEOUS Lattice model (physics) MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Theoretical Computer Science Theoretical Computer Science, Elsevier, 2018, 743, pp.93-109. ⟨10.1016/j.tcs.2016.11.021⟩ |
| ISSN: | 0304-3975 1879-2294 |
| Popis: | Concept lattices and closed set lattices are graphs with the lattice property. They have been increasingly used this last decade in various domains of computer science, such as data mining, knowledge representation, databases or information retrieval. A fundamental result of lattice theory establishes that any lattice is the concept lattice of its binary table. A consequence is the existence of a bijective link between lattices, contexts (via the table) and a set of implicational rules (via the canonical (direct) basis). The possible transformations between these objects give rise to relevant tools for data analysis. In this paper, we present a survey of lattice theory, from the algebraic definition of a lattice, to that of a concept lattice, through closure systems and implicational rules; including the exploration of fundamental bijective links between lattices, reduced contexts and bases of implicational rules; and concluding with the presentation of the main generation algorithms of these objects. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect