## 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].

### MSC:

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

### Keywords:

Closure system; Guigues-Duquenne base; Equivalence relation
Full Text: