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

 

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

Projects funding this work

Citation

Please, cite this work as:

[LOP25] 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

@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.},
}