About the family of closure systems preserving non-unit implications in the Guigues-Duquenne base. (English) Zbl 1177.68207

Missaoui, Rokia (ed.) et al., Formal concept analysis. 4th international conference, ICFCA 2006, Dresden, Germany, February 13–17, 2006. Proceedings. Berlin: Springer (ISBN 3-540-32203-5/pbk). Lecture Notes in Computer Science 3874. Lecture Notes in Artificial Intelligence, 191-204 (2006).
Summary: Consider a Guigues-Duquenne base \(\Sigma^{\mathcal F} = \Sigma_J^{\mathcal F} \Sigma_\downarrow^{\mathcal F}\) of a closure system \(\mathcal F\), where \(\Sigma_J\) be the set of implications \(P \to P^{\Sigma^{\mathcal F}}\) with \(| P| =1\), and \(\Sigma_{\downarrow}^{\mathcal F}\) be the set of implications \(P \to P^{\Sigma^{\mathcal F}}\) with \(| P| >1\). Implications in \(\Sigma_J^{\mathcal F}\) can be computed efficiently from the set of meet-irreducible \(\mathcal M(\mathcal F)\); but the problem is open for \(\Sigma_\downarrow^{\mathcal F}\). Many existing algorithms build \(\mathcal F\) as an intermediate step.
In this paper, we characterize the cover relation in the family \({\mathcal C}_\downarrow(\mathcal F)\) with the same \(\Sigma_\downarrow\), when ordered under set-inclusion. We also show that \(\mathcal M({\mathcal F}_{\bot})\), the set of meet-irreducible elements of a minimal closure system in \({\mathcal C}_\downarrow(\mathcal F)\), can be computed from \(\mathcal M(\mathcal F)\) in polynomial time for any \(\mathcal F\) in \({\mathcal C}_\downarrow(\mathcal F)\). Moreover, the size of \(\mathcal M({\mathcal F}_{\bot})\) is less or equal to the size of \(\mathcal M(\mathcal F)\).
For the entire collection see [Zbl 1096.68005].


68T30 Knowledge representation
06A15 Galois correspondences, closure operators (in relation to ordered sets)
68P20 Information storage and retrieval of data
Full Text: DOI