Systems of implications obtained using the Carve decomposition of a formal context

Authors

Domingo López-Rodríguez , Manuel Ojeda Hernández , Tim Pattison

Published

19 April 2025

Publication details

Knowledge-Based Systems , pages 113475.

Links

DOI PDF

 

Abstract

The Carve algorithm uses a divide-and-conquer strategy to compute the concept lattice of a formal context. The decomposition phase of the Carve algorithm discovers hierarchical structure in an amenable formal context, which the synthesis phase then exploits to construct the concept lattice from those of the component sub-contexts. In this paper, the problem of computing a sound and complete set of attribute implications via a refinement of the Carve decomposition is studied. Indeed, a set of rules is devised to obtain a set of valid implications which is proved to be complete. The refined decomposition and these rules are implemented in the novel Carve+ algorithm, whose runtime compares favourably with direct computation of the Duquenne–Guigues base of implications via the NextClosure algorithm.

Funding

NoteProjects funding this work

Citation

How to cite

D. López-Rodríguez, M. Ojeda-Hernández, and T. Pattison. “Systems of implications obtained using the Carve decomposition of a formal context”. In: Knowledge-Based Systems (2025), p. 113475. ISSN: 0950-7051. DOI: https://doi.org/10.1016/j.knosys.2025.113475. URL: https://www.sciencedirect.com/science/article/pii/S0950705125005210.

BibTeX

<pre><code>

@Article{LOPEZRODRIGUEZ2025113475, title = {Systems of implications obtained using the Carve decomposition of a formal context}, journal = {Knowledge-Based Systems}, pages = {113475}, year = {2025}, issn = {0950-7051}, doi = {https://doi.org/10.1016/j.knosys.2025.113475}, url = {https://www.sciencedirect.com/science/article/pii/S0950705125005210}, author = {Domingo L{‘o}pez-Rodr{’}guez and Manuel Ojeda-Hern{’a}ndez and Tim Pattison}, keywords = {Formal concept analysis, Implicational systems, Attribute implications, Divide-and-conquer algorithms, Knowledge representation}, abstract = {The Carve algorithm uses a divide-and-conquer strategy to compute the concept lattice of a formal context. The decomposition phase of the Carve algorithm discovers hierarchical structure in an amenable formal context, which the synthesis phase then exploits to construct the concept lattice from those of the component sub-contexts. In this paper, the problem of computing a sound and complete set of attribute implications via a refinement of the Carve decomposition is studied. Indeed, a set of rules is devised to obtain a set of valid implications which is proved to be complete. The refined decomposition and these rules are implemented in the novel Carve+ algorithm, whose runtime compares favourably with direct computation of the Duquenne–Guigues base of implications via the NextClosure algorithm.}, }

<button class='copy-bib-btn' id='copy-bib-btn'><i class='bi bi-clipboard'></i> Copy BibTeX</button>

Bibliometric data

The following data has been extracted from resources such as OpenAlex, Dimensions, PlumX or Altmetric.

Systems of implications obtained using the Carve decomposition of a formal context

Cites

The following graph plots the number of cites received by this work from its publication, on a yearly basis.

Papers citing this work

The following is a non-exhaustive list of papers that cite this work:

1. Tim Pattison, Dominik Dürrschnabel, Mohammed Abdullah (2026). Enumerating jointly reverse lectic orders for bi-adjacency matrices. International Journal of Approximate Reasoning DOI