In FCA, conceptual scaling is considered as a human-driven analysis tool: a know-
ledgeable person could provide attributes to be scaled for describing better the data to
be analysed. In RCA, scaling is used as an extraction tool, with the drawback to poten-
tially generate many attributes. By only extracting the least fixed point, RCA avoids
generating too many of them. This is useful when generating a description logic TBox
because all concepts are well-defined and necessary, but other contexts may benefit from
exploiting other solutions.

Beyond the minimal common acceptable lattices returned by RCA and the most
detailed ones that RCA returns, algorithms may be developed for returning all acceptable
solutions [Atencia et al., 2021]. The characterisation of the structure of the space of
acceptable solutions aims at contributing to this goal. However, our work does not
provide an 'efficient' way to obtain all elements of this set. The characterisation of the
structure of the space of acceptable solutions aims at contributing to this goal.

This work also opens perspectives for helping users to identify the acceptable solution
that they prefer. Beyond generating all solutions, another option is to offer users the
opportunity to guide the navigation among them. The structure of admissible solutions
and the associated functions may be fruitfully exploited in order to help users finding
an acceptable solution featuring the concepts and attributes that they want and not
unnecessary ones.

An anonymous reviewer remarked that variations of RCA, such as those based on
AOC-posets [Dolques et al., 2013], may receive the same treatment. This is a perspective
worth pursuing, that may lead to generalise the results presented here.

Finally, the position of relational concept analysis with respect to formal concept
analysis and Galois connections would be worth investigating. On the one hand, this
work shows that, contrary to other extensions that use scaling to encode a problem
within FCA, RCA cannot be encoded in FCA. Indeed, RCA admits various fixed points
contrary to FCA. RCA is not just the application of a product or sequence of FCA, but
relations between contexts introduce constraints between them leading to the possibility
of alternative fixed points. Hence, an encoding would not be direct, so that it provides
RCA solutions directly. On the other hand, other generalisations of FCA get closer to
general Galois connections by extending the structure of attributes. The open question
is whether RCA is another instance of a Galois connection extending FCA or if these
two need a common generalisation.

Acknowledgements

This work has been partially funded by the ANR Elker project (ANR-17-CE23-0007-01). The author thanks Petko Valtchev for comments and suggestions on an earlier version of this work, Marianne Huchard for taking the pain to describe the trick used for forcing discrimination, Amedeo Napoli for explaining me RCA (and so many other things), Jérôme David for reviewing the text, and Philippe Besnard for pointing to the Knaster-Tarski theorem. Anonymous JAIR reviewers helped clarifying the report.
10 References

Atencia, M., David, J., Euzenat, J., Napoli, A., & Vizzini, J. (2020). Link key candidate extraction with relational concept analysis. *Discrete applied mathematics*, 273, 2–20. DOI: 10.1016/J.DAM.2019.02.012 (cit. on pp. 6, 14).

Atencia, M., David, J., Euzenat, J., Napoli, A., & Vizzini, J. (2021). *Relational concept analysis for circular link key extraction* (Deliverable No. 1.2). Elker. https://moex.inria.fr/files/reports/elker-1.2.pdf. (Cit. on p. 78).

Baader, F., Calvanese, D., McGuinness, D., Nardi, D., & Patel-Schneider, P. (Eds.). (2007). *The description logic handbook: theory, implementations and applications* (2nd ed.). Cambridge University Press. DOI: 10.1017/cbo9780511711787. (Cit. on pp. 14, 18).

Baader, F., & Distel, F. (2008). A finite basis for the set of *E*L-implications holding in a finite model. *Proc. 6th International Conference on Formal Concept Analysis (ICFCA), Montréal (CA), 4933*, 46–61. DOI: 10.1007/978-3-540-78137-0_4 (cit. on p. 18).

Belohlávek, R. (2008). *Introduction to formal concept analysis* (tech. rep.). Univerzita Palackého, Olomouc (CZ). http://belohlavek.inf.upol.cz/vyuka/IntroFCA.pdf. (Cit. on p. 29).

Braud, A., Dolques, X., Huchard, M., & Le Ber, F. (2018). Generalization effect of quantifiers in a classification based on relational concept analysis. *Knowledge-based systems*, 160, 119–135. DOI: 10.1016/J.KNOSYS.2018.06.011 (cit. on pp. 6, 14).

Chaudron, L., & Maille, N. (2000). Generalized formal concept analysis. *Proc. 8th International Conference on Conceptual Structures (ICCS), Darmstadt (DE), 1867*, 357–370. DOI: 10.1007/1072280_25 (cit. on p. 16).

Dolques, X., Huchard, M., Nebut, C., & Reitz, P. (2012). Fixing generalization defects in UML use case diagrams. *Fundamenta informaticae*, 115(4), 327–356. DOI: 10.3233/FI-2012-658 (cit. on p. 6).

Dolques, X., Le Ber, F., & Huchard, M. (2013). AOC-posets: a scalable alternative to concept lattices for relational concept analysis. *Proc. of the 10th international conference on concept lattices and their applications (CLA), La Rochelle (FR)*, 129–140. https://ceur-ws.org/Vol-1062/paper11.pdf (cit. on p. 78).

Euzenat, J. (2021). Fixed-point semantics for barebone relational concept analysis. *Proc. 16th international conference on formal concept analysis (ICFCA), Strasbourg (FR)*, 12773, 20–37. DOI: 10.1007/978-3-030-77867-5_2 (cit. on pp. 7, 23, 31–35, 37, 39, 41–46, 59, 60, 82).

Euzenat, J. (2025). The fixed-point semantics of relational concept analysis. *Journal of artificial intelligence research*, 83, 1–38. DOI: 10.1613/jair.1.17882 (cit. on pp. 7, 82).

Ferré, S., & Cellier, P. (2020). Graph-FCA: an extension of formal concept analysis to knowledge graphs. *Discrete applied mathematics*, 273, 81–102. DOI: 10.1016/J.DAM.2019.03.003 (cit. on p. 17).
Ferré, S., & Ridoux, O. (2000). A logical generalization of formal concept analysis. *Proc. 8th International Conference on Conceptual Structures (ICCS), Darmstadt (DE), 1867*, 371–384. DOI: 10.1007/10722280_26 (cit. on p. 16).

Ganter, B., & Kuznetsov, S. (2001). Pattern structures and their projections. *Proc. 9th International conference on conceptual structures (ICCS), Stanford (CA US), 2120*, 129–142. DOI: 10.1007/3-540-44583-8_10 (cit. on p. 17).

Ganter, B., Stumme, G., & Wille, R. (Eds.). (2005). *Formal concept analysis: foundations and applications*. Springer. DOI: 10.1007/978-3-540-31881-1. (Cit. on p. 5).

Ganter, B., & Wille, R. (1999). *Formal concept analysis: mathematical foundations*. Springer. DOI: 10.1007/978-3-642-59830-2. (Cit. on pp. 5, 8, 10–12, 22, 34).

Guigues, J.-L., & Duquenne, V. (1986). Familles minimales d'implications informatives résultant d'un tableau de données binaires. *Mathématiques et sciences humaines*, 95, 5–18. https://www.numdam.org/item/MSH_1986__95__5_0/ (cit. on p. 18).

Guimarães, R., Ozaki, A., Persia, C., & Sertkaya, B. (2023). Mining $\mathcal{EL}^\perp$ bases with adaptable role depth. *Journal of artificial intelligence research*, 76, 119–135. DOI: 10.1613/jair.1.13777 (cit. on p. 18).

Huchard, M., Rouane Hacène, M., Roume, C., & Valtchev, P. (2007). Relational concept discovery in structured datasets. *Annals of Mathematics and Artificial Intelligence*, 49(1), 39–76. DOI: 10.1007/s10472-007-9056-3 (cit. on p. 6).

Kaytoue, M., Kuznetsov, S., Napoli, A., & Duplessis, S. (2011). Mining gene expression data with pattern structures in formal concept analysis. *Information science*, 181(10), 1989–2001. DOI: 10.1016/j.INS.2010.07.007 (cit. on p. 17).

Keip, P., Ferré, S., Gutierrez, A., Huchard, M., Silvie, P., & Martin, P. (2020). Practical comparison of FCA extensions to model indeterminate value of ternary data. *Proc. 15th International Conference on Concept Lattices and Their Applications (CLA), Tallinn (EE), 2668*, 197–208. https://ceur-ws.org/Vol-2668/paper15.pdf (cit. on p. 17).

Kötters, J. (2013). Concept lattices of a relational structure. *Proc. 20th International Conference on Conceptual Structures (ICCS), Mumbay (IN), 7735*, 301–310. DOI: 10.1007/978-3-642-35786-2_23 (cit. on p. 17).

Kuznetsov, S. (2009). Pattern structures for analyzing complex data. *Proc. 12th International Workshop on Rough Sets, Fuzzy Sets, Data Mining, and Granular-Soft Computing (RSFDGrC), Delhi (IN), 5908*, 33–44. DOI: 10.1007/978-3-642-10646-0_4 (cit. on p. 17).

Missaoui, R., Kwuida, L., & Abdessalem, T. (Eds.). (2022). *Complex data analytics with formal concept analysis*. Springer. DOI: 10.1007/978-3-030-93278-7. (Cit. on p. 5).

Nebel, B. (1990). *Reasoning and revision in hybrid representation systems* (Vol. 422). Springer. DOI: 10.1007/BFB0016445. (Cit. on p. 29).

Ouzerdine, A., Braud, A., Dolques, X., Huchard, M., & Le Ber, F. (2019). Adjusting the exploration flow in relational concept analysis – an experience on a watercourse quality dataset. In R. Jaziri, A. Martin, M.-C. Rousset, L. Boudjeloud-Assala & F. Guillet (Eds.), *Advances in knowledge discovery and management* (pp. 175–198, Vol. 1004). Springer. DOI: 10.1007/978-3-030-90287-2_9. (Cit. on p. 6).
Prediger, S. (1997). Logical scaling in formal concept analysis. *Proc. 5th International Conference on Conceptual Structures (ICCS), Seattle (WA US), 1257*, 332–341. DOI: 10.1007/BFB0027881 (cit. on p. 14).

Rouane Hacène, M., Huchard, M., Napoli, A., & Valtchev, P. (2013a). Relational concept analysis: mining concept lattices from multi-relational data. *Annals of Mathematics and Artificial Intelligence, 67*(1), 81–108. DOI: 10.1007/S10472-012-9329-3 (cit. on pp. 5, 6, 12, 14, 18, 22, 39, 43, 60).

Rouane Hacène, M., Huchard, M., Napoli, A., & Valtchev, P. (2013b). Soundness and completeness of relational concept analysis. *Proc. 11th International Conference on Formal Concept Analysis (ICFCA), Dresden (DE), 7880*, 228–243. DOI: 10.1007/978-3-642-38317-5_15 (cit. on pp. 6, 22, 33, 38).

Tarski, A. (1955). A lattice-theoretical fixpoint theorem and its applications. *Pacific journal of mathematics*, 5(2), 285-309. DOI: 10.2140/pjm.1955.5.285 (cit. on p. 34).

Wajnberg, M. (2020). *Analyse relationnelle de concepts: une méthode polyvalente pour l'extraction de connaissance* [Doctoral dissertation, Université du Québec à Montréal & Université de Lorraine]. https://hal.science/tel-03042085. (Cit. on pp. 10, 14).
A Correspondences between propositions

<table><thead><tr><th>[Euzenat, 2021]</th><th></th><th>[Euzenat, 2025]</th></tr></thead><tbody><tr><td></td><td>RR-9518 (v1)</td><td></td></tr><tr><td></td><td>Property 2</td><td>= Property 1</td></tr><tr><td></td><td>Property 3</td><td>= Property 2</td></tr><tr><td>Property 2</td><td>= Property 5 (3)</td><td></td></tr><tr><td>Property 1</td><td>= Property 6 (2)</td><td></td></tr><tr><td>Property 3</td><td>= Property 7 (4)</td><td></td></tr><tr><td>Property 4</td><td>= Property 8 (5)</td><td></td></tr><tr><td>Theorem 1</td><td>= Theorem 1 (6) (Knaster-Tarski)</td><td>= Theorem 1</td></tr><tr><td></td><td>Property 9 (7)</td><td>= Property 3</td></tr><tr><td></td><td>Property 10 (8)</td><td>= Property 4</td></tr><tr><td></td><td>Property 11</td><td>= Property 5</td></tr><tr><td>Proposition 3</td><td>= Property 14 (11)</td><td></td></tr><tr><td>Proposition 1</td><td>= Proposition 16 (13)</td><td></td></tr><tr><td>Proposition 2</td><td>= Proposition 17 (14)</td><td></td></tr><tr><td>Proposition 4</td><td>= Property 20 (16)</td><td></td></tr><tr><td>Proposition 5</td><td>&gt; Property 19 (19)</td><td></td></tr><tr><td>Proposition 5</td><td>&gt; Property 23 (19)</td><td></td></tr><tr><td>Proposition 6</td><td>= Proposition 29 (25)</td><td></td></tr><tr><td></td><td>Property 30 (26)</td><td>= Property 6</td></tr><tr><td></td><td>Property 31</td><td>= Property 7</td></tr><tr><td></td><td>Property 33 (27)</td><td>= Property 8</td></tr><tr><td></td><td>Property 42</td><td>= Property 9</td></tr><tr><td></td><td>Property 44 (36)</td><td>= Property 10</td></tr><tr><td>Proposition 46</td><td>(38)</td><td>= Proposition 11</td></tr><tr><td>Property 48</td><td>(40)</td><td>= Property 12</td></tr><tr><td>Property 49</td><td>(41)</td><td>= Property 13</td></tr><tr><td>Property 50</td><td></td><td>= Property 14</td></tr><tr><td>Property 52</td><td>(43)</td><td>= Property 15</td></tr><tr><td>Property 53</td><td>(44)</td><td>= Property 16</td></tr><tr><td>Property 54</td><td>(45)</td><td>= Property 17</td></tr><tr><td>Property 55</td><td>(46)</td><td>= Property 18</td></tr><tr><td>Property 56</td><td>(47)</td><td>= Property 19</td></tr><tr><td>Property 57</td><td>(48)</td><td>= Property 20</td></tr><tr><td>Property 58</td><td>(49)</td><td>= Property 21</td></tr><tr><td>Property 59</td><td>(49)</td><td>= Property 22</td></tr><tr><td>Property 60</td><td>(50)</td><td>= Property 23</td></tr><tr><td>Property 61</td><td>(51)</td><td>= Property 24</td></tr><tr><td>Property 62</td><td>(52)</td><td>= Property 25</td></tr><tr><td></td><td>Property 63</td><td>= Property 26</td></tr><tr><td></td><td>Property 64</td><td>= Property 27</td></tr><tr><td>Proposition 65</td><td>(53)</td><td>= Proposition 28</td></tr><tr><td>Proposition 66</td><td>(54)</td><td>= Proposition 29</td></tr><tr><td>Proposition 67</td><td>(55)</td><td>= Proposition 30</td></tr><tr><td>Proposition 68</td><td>(56)</td><td>= Proposition 31</td></tr><tr><td></td><td>Property 69 (58)</td><td>= Property 32</td></tr><tr><td></td><td>Property 70 (57)</td><td>= Property 33</td></tr><tr><td></td><td>Property 71 (59)</td><td>= Property 34</td></tr><tr><td>Proposition 72</td><td>(60)</td><td>= Proposition 35</td></tr><tr><td></td><td>Property 73 (61)</td><td>= Property 36</td></tr><tr><td></td><td>Property 74 (62)</td><td>= Property 37</td></tr><tr><td>Proposition 75</td><td>(63)</td><td>= Proposition 38</td></tr><tr><td></td><td>Property 76 (64)</td><td>= Property 39</td></tr><tr><td></td><td>Property 77 (65)</td><td>= Property 40</td></tr><tr><td></td><td>Property 78 (66)</td><td>= Property 41</td></tr><tr><td>Proposition 79</td><td>(67)</td><td>= Proposition 42</td></tr></tbody></table>

Inria
Inria

RESEARCH CENTRE
GRENOBLE - RHÔNE-ALPES

Inovallée

655 avenue de l'Europe Montbonnot

38334 Saint Ismier Cedex

Publisher

Inria

Domaine de Voluceau - Rocquencourt

BP 105 - 78153 Le Chesnay Cedex

inria.fr

ISSN 0249-0803