# Stepwise functional refoundation of relational concept analysis

Jérôme Euzenat

► To cite this version:

Jérôme Euzenat. Stepwise functional refoundation of relational concept analysis. [Research Report] RR-9518, INRIA. 2023, pp.73. hal-04230481v3

HAL Id: hal-04230481

https://hal.science/hal-04230481v3

Submitted on 25 Jun 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Ínria

Stepwise functional
refoundation of
relational concept
analysis

Jérôme Euzenat

RESEARCH
REPORT

Nº 9518

October 2023

Project-Team mOeX
<figure><img src="image_2.png" /></figure>
Inria

Stepwise functional refoundation of
relational concept analysis

Jérôme Euzenat*

Project-Team mOeX

Research Report n° 9518 — version 3 — initial version October
2023 — revised version May 2025 — 82 pages

RESEARCH CENTRE
GRENOBLE - RHÔNE-ALPES

Inovallée

655 avenue de l'Europe Montbonnot

38334 Saint Ismier Cedex

<footnote>* Affiliation: Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, F-38000 Grenoble, France</footnote>

<footnote>Contact: Jerome.Euzenat@inria.fr</footnote>
**Abstract:** Relational concept analysis (RCA) is an extension of formal concept analysis dealing with several related formal contexts simultaneously. It can learn description logic theories from data and has been used within various applications. However, RCA returns a single family of concept lattices, though, when the data feature circular dependencies, other solutions may be considered acceptable. The semantics of RCA, provided in an operational way, does not shed light on this issue. This reports aims at defining precisely the semantics of RCA and identifying alternative solutions. We characterise these acceptable solutions as those families of concept lattices which belong to the space determined by the initial contexts (*well-formed*), which cannot scale new attributes (*saturated*), and which refer only to concepts of the family (*self-supported*). We adopt a functional view on the RCA process by defining the space of well-formed solutions and two functions on that space: one expansive and the other contractive. We show that the acceptable solutions are the common fixed points of both functions. This is achieved step-by-step by starting from a minimal version of RCA that considers only one single context defined on a space of contexts and a space of lattices. These spaces are then joined into a single space of context-lattice pairs, which is further extended to a space of indexed families of context-lattice pairs representing the objects manipulated by RCA. We show that RCA returns the least element of the set of acceptable solutions. In addition, it is possible to build dually an operation that generates its greatest element. The set of acceptable solutions is a complete sublattice of the interval between these two elements. Its structure and how the defined functions traverse it are studied in detail.

**Key-words:** Formal concept analysis – relational concept analysis – fixed point – fixed-point semantics – circular dependency
Refondation fonctionnelle progressive de
l'analyse relationnelle de concepts

**Résumé** : L'analyse relationnelle de concepts (RCA) est une extension de l'analyse formelle de concepts qui permet de traiter simultanément plusieurs contextes formels liés. Elle permet d'induire des théories en logiques de description à partir de données et est utilisée dans diverses applications. La RCA retourne une unique famille de treillis de concepts bien que, lorsque les données entretiennent des dépendances circulaires, d'autres solutions semblent acceptables. La sémantique de l'analyse relationnelle de concepts, définie de manière opérationnelle, n'éclaire pas cette question. Le but de ce rapport est de définir précisément la sémantique de l'analyse relationnelle de concepts et d'identifier des solutions alternatives. Les solutions acceptables y sont définies comme les familles de treillis de concepts qui appartiennent à l'espace délimité par les contextes initiaux (bien formées), ne peuvent supporter de nouveaux attributs (saturées) et ne réfèrent qu'à des concepts de la famille (auto-supportées). Nous adoptons une approche fonctionnelle de la RCA en définissant l'espace des solutions bien formées et deux fonctions sur cet espace : l'une expansive et l'autre contractive. Nous montrons que les solutions acceptables sont les points fixes communs aux deux fonctions. Ce résultat est obtenu progressivement en partant d'une version minimale de RCA qui ne considère qu'un unique contexte et en définissant un espace de contextes et un espace de treillis correspondant. Ces espaces sont ensuite rassemblés en un espace de paires contexte-treillis qui est étendu en un espace de familles indexées de paires de contexte-treillis représentant les objets manipulés par la RCA. Ceci permet de montrer que l'algorithme de RCA retourne le plus petit élément de l'ensemble des solutions acceptables. De plus, il est possible de définir une opération duale qui retourne le plus grand élément. L'ensemble des solutions acceptables forme un sous-treillis complet de l'intervalle entre ces deux éléments. Nous étudions en détail la structure de celui-ci et, en particulier, comment les fonctions définies le parcourent.

**Mots-clés** : Analyse formelle de concepts – analyse relationnelle de concepts – point fixe – sémantique de point fixe – dépendance circulaire
# Contents

<table><tr><td>1 Introduction</td><td>5</td></tr><tr><td>2 Preliminaries and related work</td><td>8</td></tr><tr><td>2.1 Basics of formal concept analysis</td><td>8</td></tr><tr><td>2.2 Extending formal concept analysis with scaling</td><td>10</td></tr><tr><td>2.3 Other extensions</td><td>16</td></tr><tr><td>2.4 A very short introduction to RCA</td><td>18</td></tr><tr><td>2.5 Dependencies and cycles</td><td>22</td></tr><tr><td>3 Examples</td><td>23</td></tr><tr><td>3.1 RCA may accept different families of concept lattices</td><td>24</td></tr><tr><td>3.2 Minimal RCA<sup>0</sup> example</td><td>25</td></tr><tr><td>3.3 Minimal RCA example</td><td>27</td></tr><tr><td>4 A parallel context-lattice fixed-point semantics for RCA<sup>0</sup></td><td>29</td></tr><tr><td>4.1 Semantics and properties: the context approach</td><td>29</td></tr><tr><td>4.2 Semantics and properties: the lattice approach</td><td>34</td></tr><tr><td>4.3 Well-grounded and least fixed-point semantics</td><td>38</td></tr><tr><td>5 Self-supported fixed points in RCA<sup>0</sup></td><td>40</td></tr><tr><td>5.1 Self-supported lattices</td><td>40</td></tr><tr><td>5.2 Contraction functions Q and P</td><td>42</td></tr><tr><td>5.3 Fixed points of Q</td><td>44</td></tr><tr><td>5.4 Relations between E and Q</td><td>44</td></tr><tr><td>6 Unified view of the RCA<sup>0</sup> space</td><td>46</td></tr><tr><td>6.1 The lattice T of context-lattice pairs</td><td>46</td></tr><tr><td>6.2 The expansion function EF</td><td>49</td></tr><tr><td>6.3 The contraction function PQ</td><td>50</td></tr><tr><td>7 Generalisation to full RCA</td><td>51</td></tr><tr><td>7.1 The lattice O of families of context-lattice pairs</td><td>52</td></tr><tr><td>7.2 The expansion function EF*</td><td>55</td></tr><tr><td>7.3 Self-supporting families of context-lattice pairs</td><td>56</td></tr><tr><td>7.4 The contraction function PQ*</td><td>57</td></tr><tr><td>7.5 The fixed points of EF* and PQ*</td><td>59</td></tr><tr><td>7.6 Acceptable solutions</td><td>61</td></tr><tr><td>8 The fixed-point semantics of RCA</td><td>63</td></tr><tr><td>8.1 Classical RCA computes EF*'s least fixed point</td><td>63</td></tr><tr><td>8.2 Greatest fixed-point (of PQ*) semantics</td><td>63</td></tr><tr><td>8.3 The structure of fixed points</td><td>67</td></tr><tr><td>9 Conclusion</td><td>77</td></tr><tr><td>10 References</td><td>79</td></tr><tr><td>A Correspondences between propositions</td><td>82</td></tr></table>
# 1 Introduction

Formal concept analysis (FCA) is a well-defined and widely used operation for extracting concept lattices from binary data tables [Ganter and Wille, 1999]. This means that, from a set of objects described by Boolean attributes (called context), it will generate the set of all descriptions relevant to these objects (called concepts) organised in a lattice following a generalisation order relation between these concepts. For instance, from a description of people through their diploma, major and current job it is possible to generate concepts about those bachelors in literature who hold a teacher position. This concept is a subconcept of bachelors in literature, which is a subconcept of that of people having a bachelor degree. The subconcepts add more constraints (attributes) to the objects they cover and thus cover less objects. These concepts, in turn, may be used to study the diploma-job matching.

Many other techniques exist in AI and elsewhere for analysing data. Features that distinguish FCA is that it is symbolic, i.e. concept descriptions are algebraic combinations of attributes, and complete, i.e. FCA provides the lattice of *all* symbolically described concepts covering the input data. From this set, it is possible to select those which are more relevant to a particular purpose. Some numerical techniques would instead provide the concepts which optimise a criterion or may project the object descriptions in a space that make their separation and grouping easier. This leads to select the concepts to be considered, for which a description remains to be found. FCA and these types of techniques are complementary.

Formal concept analysis has been put to work in a variety of applications [Ganter et al., 2005; Missaoui et al., 2022], but its Boolean descriptions are limited with respect to real data. It has thus received many extensions for using concrete domains to overcome this limitation. For instance, people may be further characterised by their salary, age and hobby. ‘Conceptual scaling’ can group age and salary into intervals so as to be treated by FCA. However, such extensions do not cover relations between objects themselves: the fact that students have been taught by specific teachers or have been registered to specific schools.

Relational concept analysis (RCA) extends FCA by taking into account *relations between objects* [Rouane Hacène et al., 2013a]. Such relations induce possible ‘relational attributes’ that are added to the initial contexts, through ‘relational scaling’. From a family of related scaled contexts, RCA generates a family of dependent concept lattices which may include concepts that would not exist in FCA. For instance, people may be related to their household, their employer or their properties. Household, themselves may be described by their income, size and related to their members and the neighbourhood in which they are settled. This may lead to classify household depending on these features and creating new attributes for people based on whether they live in a low-income household and whether they have been employed by a school. These new attributes, in turn, will generate new people concepts such as low-income household teachers and may lead to unveil indirect relations between household and jobs.

Although RCA was initially targeting conceptual description languages such as UML
[Huchard et al., 2007], it has been generalised to more varied description logic constructors [Rouane Hacène et al., 2013a]. Relational concept analysis has been used for instance for analysing the ecological and sanitary quality of water courses [Ouzerdine et al., 2019]. For that purpose, it connects formal contexts corresponding to water courses to data collection points which themselves are connected to measures and to organisms collected in water that can be described by further attributes. These relations between objects help generating richer concept descriptions comprising relations between concepts. It is then possible to connect the abundance or scarcity of some species to the presence of some pollutants, e.g. glyphosate. RCA has also been used for other purposes such as generating link keys used to extract links from RDF data sets [Atencia et al., 2020].

In principle, RCA contributes to the completeness of FCA by providing more concepts to classify objects in. However, some concepts that can be considered acceptable may still not be generated by RCA. Indeed, in presence of circular relationships between objects, RCA may not identify reciprocally supporting concepts. For instance, consider that people are related to the schools they have attended, and schools are related to the students that they graduated. People attended multiple schools and schools had many student. There may be populations who have attended specific groups of schools and graduated from these. Although there may be no attribute distinguishing these populations and groups, they can be described by having attended at least one school of the group of schools having graduated only students of the population. These reciprocally supporting attributes lead to a refined version of the returned concept lattice which contains more concepts. Such concepts may reveal distinct populations based on various hidden factors not directly available from the data, such as wealth or information whose collection is not possible.

These mutually supported concepts may not be returned by RCA. However, they determine families of more complete concept lattices covering the data. Hence, it remains to determine which unique family is returned by RCA. In this respect, this report may be thought of as a way to restore the completeness of RCA by providing more possible concepts. This completeness may be useful in applications in which the most relevant solution is not the minimal one. It may also contribute to unveil more implications or dependencies between concepts.

This problem of alternative RCA results stemmed out of curiosity. It occurred to us through experimenting with relational concept analysis for extracting link keys. Although RCA was returning acceptable results, it was easy to identify other acceptable results that it did not return. When RCA is used for extracting description logic terminologies, it makes sense to return minimal terminologies that may be extended. But different sets of link keys would return totally different sets of links. The problem also manifests itself in applications in which developers add artificial identifiers in their data in order to constrain the returned solution to include more concepts [Braud et al., 2018; Dolques et al., 2012].

To understand why such concepts are not provided, and which concepts are returned by RCA, this report questions its semantics. The semantics of relational concept analysis has, so far, been provided in a rather operational way [Rouane Hacène et al., 2013b]. It
specifies that RCA returns a family of concept lattices referring to each other that describe the input data and it shows that this result is unique. However, when there exist cycles in the dependencies between data, several families may satisfy these constraints. Hence, relational concept analysis needs a more precise and process-independent semantics that defines what it returns. For that purpose, this report provides a structured description of the space on which relational concept analysis applies. It then defines acceptable solutions as those families of concept lattices which belong to the space determined by the initial family of formal contexts (*well-formed*), cannot scale new attributes (*saturated*), and refer only to concepts of the family (*self-supported*).

Relational concept analysis is then studied in a functional framework. It characterises the acceptable solutions as the fixed points of two functions, one expansive, which extends concept lattices as long as there are reasons to generate concepts distinguishing objects, and the other contractive, which reduces concept lattices as long as the attributes they are built on are not supported by remaining concepts. These functions can be iterated and the acceptable solutions are those families of concept lattices which are fixed points for both (Proposition 65): there is no reason to either extend or reduce them. The results provided by RCA are then proved to be the smallest acceptable solution, which is the least fixed point of the expansive function (Proposition 66). It also offers an alternative semantics based on the greatest element of this set, which is the greatest fixed point of the contractive function (Proposition 67). The structure of the set of fixed points is further characterised to support algorithmic developments.

This report extends the results obtained for the RCA⁰ restriction of RCA [Euzenat, 2021], which contains a single formal context, hence a single concept lattice, and no attribute, only relations. In spite of the simplicity of RCA⁰, the main arguments of this work were already valid for RCA⁰ which remains a good introduction to the problems faced. Here, we develop the full argument starting from RCA⁰ and extending it step-by-step to apply to RCA. A more direct and synthetic presentation of these results can be found in [Euzenat, 2025]. It sometimes uses slightly different concepts. A full table provides the correspondence between these results in Appendix A.

In addition to these more general results, the current report provides better and more examples, a revised more general notation, wider related work, and insights on the structure of the set of acceptable solutions. It features many elementary properties and propositions which help keeping their proof manageable so the proofs are given immediately.

We first present the work on which this one builds (relational concept analysis) and relevant related work (Section 2). We then provide simple examples illustrating that RCA and RCA⁰ may accept concept lattices which are not those provided by RCA (Section 3). RCA⁰ is then provided with a fixed-point semantics through an expansion function corresponding to the RCA algorithm (Section 4). We then discuss the notion of self-supported lattices (Section 5) which is characterised as the fixed points of another function that can be seen as dual to that used by RCA. So far, these characterisations have been provided in parallel on both formal contexts and concept lattices. Section 6 reconciles them by unifying both approaches in dependent pairs of contexts and lattices.
This allows us to precisely characterise the space of acceptable solutions, fixed points of these complementary functions, by considering the composition of the corresponding closures. This is finally generalised to RCA globally by considering families of related context-lattice pairs and showing that the acceptable solutions are those families which are fixed-points for both functions (Section 7). We characterise exactly the results of RCA as the smallest element of this set, we provide an alternative operation returning the greatest element and we study the structure of the set of acceptable solutions (Section 8).

# 2 Preliminaries and related work

We mix preliminaries with related work for reasons of space, but also because the report directly builds on this related work.

Hereafter, we use a simple and regular notation: K denotes contexts, L lattices, T context-lattice pairs and O families of context-lattice pairs. In addition, R is used for relations, N for names and D for attributes. Greek letters are devoted to some auxiliary functions (η, κ, σ, π). E, F, P and Q are used for functions names and * is used for distinguishing the parallel application of such functions. Table 1 provides a list of used symbols.

## 2.1 Basics of formal concept analysis

This report relies only on the most basic results of formal concept analysis expressed as order-preserving functions.

Formal Concept Analysis (FCA) [Ganter and Wille, 1999] starts with a formal context (hereafter context) $\langle G, M, I \rangle$ where G denotes a set of objects, M a set of attributes, and $I \subseteq G \times M$ a binary relation between G and M, called the incidence relation. The statement $gIm$ is interpreted as ‘object g has attribute m’, also noted $m(g)$. Two operators $\uparrow$ and $\downarrow$ define a Galois connection between the powersets $\langle 2^G, \subseteq \rangle$ and $\langle 2^M, \subseteq \rangle$, with $A \subseteq G$ and $B \subseteq M$:

$$A^{\uparrow} = \{m \in M \mid gIm \text{ for all } g \in A\},$$

$$B^{\downarrow} = \{g \in G \mid gIm \text{ for all } m \in B\}.$$

The operators $\uparrow$ and $\downarrow$ are decreasing, i.e. if $A_1 \subseteq A_2$ then $A_2^{\uparrow} \subseteq A_1^{\uparrow}$ and if $B_1 \subseteq B_2$ then $B_2^{\downarrow} \subseteq B_1^{\downarrow}$. Intuitively, the less objects there are, the more attributes they share, and dually, the less attributes there are, the more objects have these attributes. It can be checked that $A \subseteq A^{\uparrow\downarrow}$ and that $B \subseteq B^{\downarrow\uparrow}$, that $A^{\uparrow} = A^{\uparrow\downarrow}$ and that $B^{\downarrow} = B^{\downarrow\uparrow}$.

A pair $\langle A, B \rangle \in 2^G \times 2^M$, such that $A^{\uparrow} = B$ and $B^{\downarrow} = A$, is called a formal concept (hereafter concept), where $A = \text{extent}(\langle A, B \rangle)$ is the extent and $B = \text{intent}(\langle A, B \rangle)$ the intent of $\langle A, B \rangle$. Moreover, for a formal concept $\langle A, B \rangle$, A and B are closed for the closure operations $\uparrow\downarrow$ and $\downarrow\uparrow$, respectively, i.e. $A^{\uparrow\downarrow} = A$ and $B^{\downarrow\uparrow} = B$.

Concepts are partially ordered by $\langle A_1, B_1 \rangle \le \langle A_2, B_2 \rangle \Leftrightarrow A_1 \subseteq A_2$ or equivalently $B_2 \subseteq B_1$. With respect to this partial order, the set of all formal concepts is a complete
## Sets and structures

<table><tr><td>G</td><td>set of objects ($g \in G$)</td><td>10</td></tr><tr><td>M</td><td>set of attribute ($M \subseteq D, m \in M$)</td><td>10</td></tr><tr><td>I</td><td>incidence relation ($I \subseteq M \times G$)</td><td>10</td></tr><tr><td>J</td><td>'ternary' element used in conceptual scaling ($J \subseteq G \times M \times W$)</td><td>11</td></tr><tr><td>R</td><td>set of relations ($R \subseteq G \times G', r \in R$)</td><td>22</td></tr><tr><td>K</td><td>formal contexts ($K = \langle G, M, I \rangle, K \in \mathcal{K}$)</td><td>10</td></tr><tr><td>Ω</td><td>set of scaling operations ($\zeta \in \Omega$)</td><td>18</td></tr><tr><td>N</td><td>concept names (given after extent $c \in N \subseteq 2^G$)</td><td>12</td></tr><tr><td>D</td><td>domain language for expressing attributes (inspired from Pattern structures)</td><td>10</td></tr><tr><td>L</td><td>concept lattice ($L = \langle C, \leq, L \in \mathcal{L} \rangle$)</td><td>10</td></tr><tr><td>C</td><td>set of formal concepts ($C \subseteq 2^{G \times M}, c \in C$)</td><td>10</td></tr><tr><td>T</td><td>context-lattice pair ($T = \langle K, L \rangle, T \in \mathcal{T}$)</td><td>46</td></tr><tr><td>O</td><td>indexed context-lattice pairs ($O = \{T_x\}_{x \in X}, O \in \mathcal{O}$) for modelling RCA entirely</td><td>52</td></tr><tr><td>Σ</td><td>semantic structure grounding scaling ($\Sigma \in \mathcal{K}$, here $\Sigma \subseteq \{R\} \times \mathcal{L}$)</td><td>10</td></tr></table>

## Functions

<table><caption>Table 1: Some symbols used in this document (signatures are simplified omitting $R$ and $\Omega$).</caption><tr><td>FCA</td><td>$\mathcal{K} \to \mathcal{L}$ Formal concept analysis (extended to indexed families as FCA*)</td><td>10</td></tr><tr><td>η</td><td>$\mathcal{K} \cup \mathcal{L} \to 2^G$ concept name extractors ($\eta^*$)</td><td>8</td></tr><tr><td>κ</td><td>$\mathcal{L} \to \mathcal{K}$ Context extraction operation</td><td>34</td></tr><tr><td>σ</td><td>$\mathcal{K} \times \mathcal{L} \to \mathcal{K}$ Scaling operation ($\sigma^*$)</td><td>11</td></tr><tr><td>π</td><td>$\mathcal{L} \to \mathcal{K}$ Purge function ($\pi^*$)</td><td>41</td></tr><tr><td>F</td><td>$\mathcal{L} \to \mathcal{L}$ Concept lattice expansion</td><td>33</td></tr><tr><td>E</td><td>$\mathcal{K} \to \mathcal{K}$ Context expansion</td><td>37</td></tr><tr><td>P</td><td>$\mathcal{K} \to \mathcal{K}$ Context contraction</td><td>42</td></tr><tr><td>Q</td><td>$\mathcal{L} \to \mathcal{L}$ Concept lattice contraction</td><td>42</td></tr><tr><td>T</td><td>$\mathcal{K} \to \mathcal{T}$ Context-lattice pair constructor ($T^*$)</td><td>46</td></tr><tr><td>EF</td><td>$\mathcal{T} \to \mathcal{T}$ Context-lattice pair expansion ($EF^*: \mathcal{O} \to \mathcal{O}$)</td><td>49</td></tr><tr><td>PQ</td><td>$\mathcal{T} \to \mathcal{T}$ Context-lattice pair contraction ($PQ^*: \mathcal{O} \to \mathcal{O}$)</td><td>50</td></tr><tr><td>RCA</td><td>$\mathcal{K}^* \to \mathcal{L}^*$ Relational concept analysis</td><td>18</td></tr><tr><td>RCA</td><td>$\mathcal{K}^* \to \mathcal{L}^*$ Relational concept analysis with a greatest fixed-point semantics</td><td>63</td></tr></table>

lattice called the concept lattice of $\langle G, M, I \rangle$. It has for supremum the concept $\top = \langle G, G^\top \rangle$ and for infimum the concept $\bot = \langle M^\bot, M \rangle$.

**Example 1** (Formal concept analysis). Starting from a context $K_1^0 = \langle G_1, M_1^0, I_1^0 \rangle$ with $G_1 = \{a, b, c\}$, $M_1^0 = \{m_1, m_2, m_3\}$ and $I_1^0$ as the incidence relation whose table is given below, the application of FCA results in the lattice made of the concepts ABC, AB, C and $\bot$ as:
<figure><img src="image_3.png" /></figure>

By convention, concept lattices are represented by their reflexive-transitive reduction (Haase diagram) in which concepts are displayed in two parts: an upper part representing their intent and a lower part representing their extent. They only display the proper part of their intent and extent. Their actual intent is obtained by joining it to the union of the proper extents of their more general concepts. Conversely, their extent is obtained by joining it to the union of the proper extent of their more specific concepts. Hence, $ABC = \langle\{a, b, c\}, \emptyset\rangle$ and $\perp = \langle\emptyset, \{m_1, m_2, m_3\}\rangle$.

Formal concept analysis can be considered as a function that associates to a context $\langle G, M, I \rangle$ its concept lattice $\langle C, \leq \rangle = \text{FCA}(\langle G, M, I \rangle)$ (or $\mathfrak{B}(G, M, I)$ [Ganter and Wille, 1999]). This is illustrated by Example 1. By abuse of language, when a variable $L$ denotes a concept lattice $\langle C, \leq \rangle$, $L$ will also be used to denote $C$.

The concepts that can be created from a context can be identified by their extent. Hence, $\eta(\langle G, M, I \rangle) = 2^G$ is the set of all concept names that may be used in any such concept lattice<fnref n="1" />. We will identify the concepts by such sets; the extent of a so-named concept will be the set of objects in its name. In any specific concept lattice $L = \text{FCA}(K)$, the subset $\eta(L)$ of $\eta(K)$ is the set of names of concepts in this lattice according to this convention as illustrated in Example 2.

**Example 2 (Concept names).** Consider the context $K_1^0$ of Example 1. The set of objects of $K_1^0$ being $G_1 = \{a, b, c\}$, the set of concept names that can be created for them in any concept lattice is $\eta(K_1^0) = \{ABC, AB, AC, BC, A, B, C, \perp\}$. In the specific lattice obtained in Example 1, the set of concept names is $\eta(L_1^0) = \{ABC, AB, C, \perp\}$.

Throughout the report, concepts are named after their extent. They will be displayed as uppercase character strings.

In order to discuss algorithms performing formal concept analysis, we will restrict ourselves to finite structures, as it is often the case. In such a case, from finite contexts are generated finite lattices whose concepts have finite extents and intents.

## 2.2 Extending formal concept analysis with scaling

Formal concept analysis is defined on relatively simple structures hence many extensions of it have been designed. These may allow formal concept analysis to (a) deal with more complex input structures, and/or (b) generate more expressive and interpretable knowledge structures.

<footnote n="1">¹A similar remark is made in [Wajnberg, 2020, §4.1.2].</footnote>
### 2.2.1 Scaling: a generalisation

Scaling is one kind of extension of type (a). It is a way to encode a more complex structure $\Sigma$ into FCA. For that purpose, a scaling operation $\zeta$ determines a set $D_{\zeta,\Sigma}$ of Boolean attributes to be added to a context $K$ from a structure $\Sigma$. In scaled contexts, these attributes can be interpreted so that the incidence relation $I$ is immediately derived from the attribute $m \in D_{\zeta,\Sigma}$ following:

$$ \Sigma \models gIm \text{ or } \Sigma \models m(g). $$

In FCA, $D = M$ and $I$ is provided by its matrix:

$$ I \models m(g) \text{ iff } \langle m, g \rangle \in I. $$

Hence, adding attributes $M'$ to a context under such a structure $\Sigma$ consists of adding the attributes and extending the incidence relation according to this interpretation. It may be performed as:

$$ K_{+M'}^{\Sigma}(\langle G, M, I \rangle) = \langle G, M \cup M', I \cup \{\langle g, m \rangle \in G \times M' \mid \Sigma \models m(g)\} \rangle $$

and suppressing them as:

$$ K_{-M'}^{\Sigma}(\langle G, M, I \rangle) = \langle G, M \setminus M', I \setminus \{\langle g, m \rangle \in G \times M' \} \rangle. $$

Applying a scaling operation $\zeta$ to a context $K$ following a structure $\Sigma$ can thus be decomposed into (i) determining the set $D_{\zeta,\Sigma}$ of attributes to add, and (ii) extending the context with these attributes:

$$ \sigma_{\zeta}(K, \Sigma) = K_{+D_{\zeta,\Sigma}}^{\Sigma}(K). $$

This unified view of scaling may be applied to many available scaling operations. We discuss these below.

### 2.2.2 Conceptual scaling

Attributes found in data sets typically do not range on Booleans, but instead in numbers, intervals, strings, etc. Such data can be represented as a many-valued context $\Sigma = \langle G, M, W, J \rangle$, such that $G$ is a set of objects, $M$ a set of attributes, $W$ a set of values, and $J$ a ternary relation defined on $G \times M \times W$. $\langle g, m, w \rangle \in J$ or simply $m(g) = w$ means that object $g$ takes the value $w$ for the attribute $m$. In addition, when $\langle g, m, w \rangle \in J$ and $\langle g, m, v \rangle \in J$ then $w = v$ [Ganter and Wille, 1999, §1.3]: in FCA, ‘many-valued’ means that the range of an attribute may include more than two values, but for any object, the attribute can only have one of these values.

Conceptual scaling transforms such a many-valued context into a one-valued context. For instance, for nominal scaling, given a set $W$ of values and a set $N$ of properties taking
<table><caption>Table 2: Conceptual scaling operations (inspired from [Ganter and Wille, 1999]).</caption><thead><tr><th>name</th><th>language (D)</th><th>scale</th><th>Σ</th><th>condition (m(g))</th></tr></thead><tbody><tr><td>FCA</td><td>m</td><td>-</td><td>I</td><td>⟨m, g⟩ ∈ I</td></tr><tr><td>dichotomic</td><td>n = v</td><td>monocolumn</td><td>⟨G, N, W, J⟩</td><td>n(g) = v</td></tr><tr><td>nominal</td><td>n = w</td><td>diagonal</td><td>⟨G, N, W, J⟩</td><td>n(g) = w ∀w ∈ W</td></tr><tr><td>ordinal</td><td>n ≤ w</td><td>triangular</td><td>⟨G, N, W, J⟩</td><td>n(g) ≤ w ∀w ∈ W</td></tr><tr><td>inter-ordinal</td><td>n ≤ w, n ≥ w</td><td>-</td><td>⟨G, N, W, J⟩</td><td>n(g) ≤ w or<br>n(g) ≥ w ∀w ∈ W</td></tr><tr><td>contranominal</td><td>n ≠ w</td><td>antidiagonal</td><td>⟨G, N, W, J⟩</td><td>n(g) ≠ w ∀w ∈ W</td></tr></tbody></table>

these values, $D_{=,\Sigma} = \{n = w | n \in N \text{ and } w \in W\}$ splits the ranges of the multi-valued attributes in $N$ into binary attributes. Attributes of $D_{=,\Sigma}$ are interpreted as:

$$ \langle G, N, W, J \rangle \models gI(n = w) \text{ iff } \langle g, n, w \rangle \in J. $$

There are other types of scalings and some of them are detailed in Table 2. The same can be built for ordinal scaling, e.g.

$$ \langle G, N, W, J \rangle \models gI(n \le w) \text{ iff } \langle g, n, v \rangle \in J \wedge v \le w. $$

These scaling operations only use a simple structure, i.e. $\Sigma = \langle G, N, W, J \rangle$ in which everything is stored in $J$ and the attributes are expressed as predicates, e.g. $\cdot = v$ for nominal scaling or $\cdot \le n$ for ordinal scaling. $\models$ is the evaluation of the predicate for the value, hence they can have also been called structural scaling.

**Example 3 (Conceptual scaling).** Consider a many-valued context $\langle G, N, W, J \rangle$ with $G = \{\text{Alice}, \text{Bob}, \text{Carol}\}$, $N = \{\text{age}, \text{shoesize}\}$, $W = \mathbb{N}$ and $J$ as below:

<table><thead><tr><th>J</th><th>age</th><th>shoesize</th></tr></thead><tbody><tr><td>Alice</td><td>12</td><td>32</td></tr><tr><td>Bob</td><td>14</td><td>36</td></tr><tr><td>Carol</td><td>14</td><td>34</td></tr></tbody></table><table><thead><tr><th>I</th><th>age=12</th><th>age=14</th><th>shoesize&lt;35</th></tr></thead><tbody><tr><td>Alice</td><td>×</td><td>×</td><td>×</td></tr><tr><td>Bob</td><td>×</td><td>×</td><td>×</td></tr><tr><td>Carol</td><td>×</td><td>×</td><td>×</td></tr></tbody></table>

It is possible to scale *age* with nominal scaling and *shoesize* with (partial) ordinal scaling generating the context with $G$, $M = \{\text{age}=12, \text{age}=14, \text{shoesize}<35\}$ and $I$ as above.

### 2.2.3 Relational scaling

Relational scaling operations ($\zeta$) considered in [Rouane Hacène et al., 2013a] create relational attributes from a binary relation $r \subseteq G \times G'$ between two sets of objects $G = \text{dom}(r)$ and $G' = \text{cod}(r)$ and a concept lattice $L$ on $G'$. $\zeta(r, c)$ provides the syntactic form of the attribute. For example, qualified existential scaling ($\zeta = \exists$) is expressed
by $\exists(r, c) = \exists r.c.$ For instance, the employer relation may relate people to companies depending on whether one works for the other. If the company lattice contains the school concept, then the relational attribute $\exists \text{employer.School}$ may be scaled and holds for all people employed by a school.

Thus, the set of qualified existential attributes are:

$$D_{\exists, \langle r, L \rangle} = \{ \exists r.c \mid c \in \eta(L) \}.$$

Such attributes are interpreted, according to a closed-world description logic interpretation, by

$$\langle r, L \rangle \models gI\exists r.c \text{ iff } \exists g'; \langle g, g' \rangle \in r \wedge g' \in \text{extent}(c).$$

This is illustrated in Example 4.

**Example 4 (Relational scaling).** Consider that the relation $q$ is given by the table:

$$\begin{array}{c|ccc}
q & a & b & c \\
d & \times & & \\
e & & \times & \\
f & & & \times
\end{array}$$

between $G_1 = \{a, b, c\}$ and $G_2 = \{d, e, f\}$ and consider the concept lattice $L_1^0$ corresponding to the context $K_1^0$ of Example 1. The concepts in $L_1^0$ have names in $\eta(L_1^0) = \{ABC, AB, C, \perp\}$ (Example 2) hence scaling by $\sigma_{\exists}$ will provide the attribute set $\{\exists q.ABC, \exists q.AB, \exists q.C, \exists q.\perp\}$. The description of the relation $q$ allows to uncover the incidence relation for these (the incidence relation for $\perp$ is always empty for $\exists$ so never displayed in the examples):

$$\begin{array}{c|ccc}
 & \exists q.ABC & \exists q.AB & \exists q.C \\
d & \times & \times & \\
e & \times & \times & \\
f & \times & &
\end{array}$$

If, in addition, the context $K_2^0$ of $G_2$ had two other attributes $n_1$ and $n_2$ whose incidence relation is given as $I_2^0$ displayed below, then the scaling operation would correspond to:

$$\sigma_{\exists}( \begin{array}{c|cc} K_2^0 & n_1 & n_2 \\ \hline d & \times & \\ e & \times & \times \\ f & & \end{array} , \begin{array}{c|ccc} q & a & b & c \\ \hline d & \times & & \\ e & \times & \times & \\ f & & & \times \end{array} , \text{AB} \quad \text{ABC} \quad \text{AB} \quad \text{ABC} ) = \begin{array}{c|cccc} K_2^1 & n_1 & n_2 & \exists q.ABC & \exists q.AB \\ \hline d & \times & & \times & \times \\ e & \times & \times & \times & \times \\ f & & & \times & \times \end{array}$$

When generating relational attributes, scaling only relies on the *names* of the concepts in $L$. It is thus possible to define the sets of attributes from the set of names. The set of
<table><caption>Table 3: Relational scaling operations (inspired from [Braud et al., 2018; Rouane Hacène et al., 2013a]) and additional link key condition scaling operations [Atencia et al., 2020].</caption><thead><tr><th>name</th><th>language (D)</th><th>Σ</th><th>condition (m(g))</th></tr></thead><tbody><tr><td>existential</td><td>∃r</td><td>R</td><td>r(g) ≠ Ø</td></tr><tr><td>universal (wide)</td><td>∀r.c</td><td>R, L</td><td>r(g) ⊆ extent(c)</td></tr><tr><td>strict universal</td><td>∀∃r.c</td><td>R, L</td><td>r(g) ≠ Ø ∧ r(g) ⊆ extent(c)</td></tr><tr><td>contains (wide)</td><td>∀c.r</td><td>R, L</td><td>extent(c) ⊆ r(g)</td></tr><tr><td>strict contains</td><td>∀∃c.r</td><td>R, L</td><td>extent(c) ≠ Ø<br>∧extent(c) ⊆ r(g)</td></tr><tr><td>qualified existential</td><td>∃r.c</td><td>R, L</td><td>r(g) ∩ extent(c) ≠ Ø</td></tr><tr><td>qualified min cardinality</td><td>≤<sub>n</sub> r.c</td><td>R, L</td><td>|r(g) ∩ extent(c)| ≤ n</td></tr><tr><td>qualified max cardinality</td><td>≥<sub>n</sub> r.c</td><td>R, L</td><td>|r(g) ∩ extent(c)| ≥ n</td></tr><tr><td>∀-condition</td><td>∀⟨r, r'⟩<sub>k</sub></td><td>R × R', L<sub>C×C'</sub></td><td>r(g) =<sub>k</sub> r'(g')</td></tr><tr><td>∃-condition</td><td>∃⟨r, r'⟩<sub>k</sub></td><td>R × R', L<sub>C×C'</sub></td><td>r(g) ∩<sub>k</sub> r'(g') ≠ Ø</td></tr></tbody></table>

relational attributes that can be scaled from $\zeta$ and $r$ against a set $N$ of concept of names is $D_{\zeta,r,N} = \{\zeta(r, c) | c \in N\}$. This can be used with $\eta(L)$, i.e. the names of concepts actually in $L$, or with $\eta(K)$, i.e. the names of all possible concepts to be generated from a context $K$. Example 5 illustrates this.

**Example 5** (Set of relational attributes). For the context $K_2^0$ of Example 4, if there is only one relation $q$, whose codomain is $K_1^0$ of Example 1, and the existential scaling operation $∃$, then the set of possibly scalable relational attributes is:

$$D_{∃,q,\eta(K_1^0)} = \{∃q.ABC, ∃q.AB, ∃q.AC, ∃q.BC, ∃q.A, ∃q.B, ∃q.C, ∃q.⊥\}$$

But using only those concepts from the lattice $L_1^0$ obtained in Example 1, this set is reduced to:

$$D_{∃,q,\eta(L_1^0)} = \{∃q.ABC, ∃q.AB, ∃q.C, ∃q.⊥\}$$

Various relational scaling operations exist, such as existential, strict and wide universal, min and max cardinality, which all follow the classical role restriction semantics of description logics [Baader et al., 2007] under the closed-world assumption (see Table 3). The set of relational attributes obtained from a relation $r$ by relational scaling may be large but remains finite as long as $G' = \text{cod}(r)$ is finite. Cardinality constraints, relying on integers, may entail infinite sets of concepts in theory, but in practice, when $G'$ is finite, the set of meaningful cardinality attributes is bounded by $|G'|$.

In fact, RCA may be considered as a very general way to apply relational scaling across contexts. Various kinds of relational scaling operations have been provided [Atencia et al., 2020; Braud et al., 2018; Wajnberg, 2020].

### 2.2.4 Logical scaling

Logical scaling [Prediger, 1997] has been introduced for more versatile languages such as description logics and SQL. It introduces query results within contexts. In this case, $\Sigma$
is a logical theory or database tables, D the set of formulas of the logic or queries (Q) and $|\models$ is entailment or query evaluation. The scaling can be rewritten as:

$$ \Sigma \models gIQ \text{ iff } \Sigma \models Q(g). $$

Here, the nearly identical notation shows the relevance of this generalisation. We expressed it with respect to one individual g, so it applies to unary queries or formulas with one variable placeholder. However, it is possible to generalise this to contexts in which individuals in G are elements of the products of sets of individuals.

### 2.2.5 Relational scaling as logical scaling

The type of scaling used by RCA, relational scaling, can be thought of as an extension of logical scaling based on description logic.

Relational scaling is based on a set of contexts {$\langle G_x, M_x, I_x \rangle$}$_{x \in X}$, the corresponding lattices {$L_x$}$_{x \in X}$ = {FCA($\langle G_x, M_x, I_x \rangle$)}$_{x \in X}$ and a set R of relations. This input can be encoded as sets of description logic axioms by:

$$ \begin{aligned} |K_x| &= \{m(g) \mid m \in M_x \wedge g \in G_x \wedge gI_x m\}, \\ |r| &= \{r(g, g') \mid g \in G_x \wedge g' \in G_z \wedge \langle g, g' \rangle \in r\}, \\ \|L_x\| &= \{c \equiv \sqcap_{d \in \text{intent}(c)} d \mid c \in L_x\}. \end{aligned} $$

The elements in $|\cdot|$ are part of an ABox and those in $\|\cdot\|$ are part of a TBox. They may be combined into a description logic knowledge base $\Sigma = \langle T_\Sigma, A_\Sigma \rangle$ such that:

$$ \begin{aligned} T_\Sigma &= \bigcup_{x \in X} \|L_x\|, \\ A_\Sigma &= \bigcup_{x \in X} |K_x| \cup \bigcup_{r \in R} |r|. \end{aligned} $$

In principle, it should be possible to deduce the extent of each concept and the order between concepts from this:

$$ \begin{aligned} \Sigma &\models c(g) \text{ iff } g \in \text{extent}(c), \\ \Sigma &\models c \sqsubseteq c' \text{ iff } c \le c'. \end{aligned} $$

The attributes provided by relational scaling are description logic concept descriptions, i.e. unary predicates. They can be interpreted with respect to the knowledge base associated to $\Sigma$:

$$ \Sigma \models gI \forall \exists p.c \text{ iff } \Sigma \models (\forall p.c \sqcap \exists p)(g). $$

This way of interpreting relational scaling opens the door to introducing arbitrary description logic axioms within $\Sigma$ and thus to use background knowledge.
## 2.3 Other extensions

There are other extensions providing formal concept analysis with more expressiveness in the expression of intents without scaling (type b extension). Instead of scaling, they change the structure of the set of attributes, staying within the scope of Galois lattices. We mention them here briefly.

**Logical concept analysis** Logical concept analysis is an extension of formal concept analysis in which the set of attributes is replaced by logical formulas attached to objects [Ferré and Ridoux, 2000].

$\langle 2^M, \subseteq, \cap, \cup \rangle$ is replaced by $\langle L, \models, \vee, \wedge \rangle$ in which $L$ is a set of logic formulas. The extension is defined semantically, hence the formula may be thought of as the class of equivalent formulas. It could be redefined by using closed sets of formulas instead of single formulas and closed union instead of conjunction.

The context is $\langle G, L, i \rangle$ with $i: G \to L$ a mapping. In this case, the two operators $\uparrow$ and $\downarrow$ define a Galois connection between $\langle 2^G, \subseteq \rangle$ and $\langle L, \models \rangle$ with $O \subseteq G$ and $\phi \in L$:

$$O^{\uparrow} = \bigvee_{o \in O} i(o), \\ \phi^{\downarrow} = \{o \in G \mid i(o) \models \phi\}.$$

As for scaling, it is possible to rewrite:

$$\langle L, \models, \vee, \wedge \rangle \models oI\phi \text{ iff } i(o) \models \phi.$$

A benefit of plunging the logic in FCA is the definition of contextualised entailment<fnref n="2" /> as:

$$\phi \models^K \psi \text{ iff } \phi^{\downarrow} \subseteq \psi^{\downarrow}.$$

This extension is very ‘structural’: concepts are carrying theories which do not apply to the objects of the concepts.

**Generalised formal concept analysis** Generalised formal concept analysis [Chaudron and Maille, 2000] attaches to each object $g$ an element $T = \zeta(g)$ of a lattice $\langle \mathcal{L}, \sqsubseteq, \sqcap, \sqcup \rangle$ which replaces $\langle 2^M, \subseteq, \cap, \cup \rangle$ in formal concept analysis. Hence a general context is a triple $\langle G, \mathcal{L}, \zeta \rangle$, such that $\zeta: G \to \mathcal{L}$. The incidence relation is implicitly defined by:

$$\langle \mathcal{L}, \sqsubseteq, \sqcap, \sqcup \rangle \models gIT \text{ iff } \zeta(g) \supseteq T.$$

so that the two operators $\uparrow$ and $\downarrow$ define a Galois connection between $\langle 2^G, \subseteq \rangle$ and $\langle \mathcal{L}, \sqsubseteq \rangle$ with $O \subseteq G$ and $T \in \mathcal{L}$:

$$O^{\uparrow} = \sqcap_{g \in O} \zeta(g), \\ T^{\downarrow} = \{g \in G \mid T \sqsubseteq \zeta(g)\}.$$

<footnote n="2">²Contextualized deduction in [Ferré and Ridoux, 2000].</footnote>
This theory has been instantiated to the unification of existentially quantified con-junctions of first order atoms, represented as sets of atoms. ⊑ is syntactic subsumption, i.e. the fact that there exists a variable substitution on the subsumee such that it is included in the subsumer. In such a case, $\mathcal{L}$ is the set of such formulas reduced to a non-redundant form and ⊓ is antiunification. Because of the use of unification, this approach remains syntactic.

**Pattern Structures** It is also possible to avoid scaling and to directly work on complex data, using the formalism of 'pattern structures' [Ganter and Kuznetsov, 2001; Kaytoue et al., 2011]. Pattern structures generalise FCA in a similar way as logical concept analysis. In this case, $2^M$ is replaced by elements of a meet-semilattice $\langle D, \sqcap \rangle$ [Ganter and Kuznetsov, 2001; Kuznetsov, 2009]. The context is now $\langle G, D, \delta \rangle$ with $\delta: G \to D$ a mapping.

In this case, the two operators $\uparrow$ and $\downarrow$ define a Galois connection between $\langle 2^G, \subseteq \rangle$ and $\langle D, \subseteq \rangle$ with $A \subseteq G$ and $d \in D$:

$$A^{\uparrow} = \sqcap_{g \in A} \delta(g), \\ d^{\downarrow} = \{g \in G \mid d \subseteq \delta(g)\}.$$

such that $c \subseteq d \equiv c \sqcap d = c$.

This requires to define: (a) how to order its elements ($\subseteq$), and (b) how to test that an object satisfies an attribute expression ($gId$ for $d \in D$). This can be rewritten as for scaling:

$$\langle D, \subseteq \rangle \models gId \text{ iff } d \subseteq \delta(g).$$

Pattern structures [Ganter and Kuznetsov, 2001; Kuznetsov, 2009] provide a more structured attribute language without scaling.

However, these extensions are not directly affected by the problem of context dependencies considered here as the attributes do not refer to concepts.

**Relational extensions** On the contrary, other approaches [Ferré and Cellier, 2020; Kötters, 2013] aim at extracting conceptual structures from n-ary relations without re-sorting to scaling. Their concepts have intents that can be thought of as conjunctive queries and extents as tuples of objects, i.e. answers to these queries. Hence, instead of being classes, i.e. monadic predicates, concepts correspond to general polyadic predicates. For that purpose, they rely on more expressive input, e.g. in Graph-FCA [Ferré and Cellier, 2020] the incidence relation is a hypergraph between objects, and produce more expressive representations. A comparison of RCA and Graph-FCA is provided in [Keip et al., 2020]. Graph-FCA adopts a different approach from RCA but should, in principle, suffer from the same problem as the one considered here as soon as it contains circular dependencies: intents would need to refer to concepts so created, i.e. named subqueries. This remains to be studied.
**Terminological base extraction** Finally, description logic base mining [Baader and Distel, 2008; Guimarães et al., 2023] and relational concept analysis share the same purpose: inferring a TBox from an ABox (taken as an interpretation). However, RCA does this by introducing new named concepts based on FCA, though description logic base mining does not introduce new names but uses new concept descriptions inspired from Duquenne-Guigues implication bases [Guigues and Duquenne, 1986]. Where, in Example 4, relational scaling would use attribute $∃q.AB$, base mining would use the description $∃q.∃m_2.⊤$. As soon as cycles occur in context dependencies, this naturally leads to cyclic concept definitions. This has been interpreted with the greatest fixed-point semantics in $\mathcal{EL}_{gfp}$. However, led by complexity considerations, work has focused on extracting minimal bases in $\mathcal{EL}$ through unravelling [Baader and Distel, 2008; Guimarães et al., 2023]. The problem raised in this report is different but applies as well to description logic base mining as soon as it is taken as a knowledge induction task from data: circular dependencies may lead to different, equally well-behaving, bases that would be worth taking in consideration.

## 2.4 A very short introduction to RCA

Relational Concept Analysis (RCA) [Rouane Hacène et al., 2013a] extends FCA to the processing of relational datasets and allows inter-object relations to be materialised and incorporated into formal concept intents. RCA can be considered as a way to induce a description logic TBox from a simple ABox [Baader et al., 2007], using specific scaling operations. It may also be thought of as a general way to deal with circular references using different scaling operations.

RCA applies

- a set $\Omega$ of relational scaling operations on

- a family of contexts $K^0 = \{\langle G_x, M_x^0, I_x^0 \rangle\}_{x \in X}$ indexed by a finite set $X$, such that, if $x \neq z$, $G_x \cap G_z = \emptyset$, and

- a finite set $R$ of binary relations, i.e. relations $r \subseteq G_x \times G_z$ (with $x, z \in X$).

$\langle K^0, R \rangle$ is called a relational context<fnref n="3" />. Each context of the family $K^t$ may be abbreviated as $K_x^t = \langle G_x, M_x^t, I_x^t \rangle$. The use of the ordinal superscript $t$ will become clearer in a few lines and can be ignored at that stage. We note $R_x = \{r \in R \mid \text{dom}(r) = G_x\}$ and $R_{x,z} = \{r \in R_x \mid \text{cod}(r) = G_z\}$.

### 2.4.1 Concept names and relational attributes

The notation used for expressing sets of relational attributes can be generalised. For RCA, $\eta^*(K^0) = \{\eta(K_x^0)\}_{x \in X}$ is the indexed set of all concept names induced from all contexts in $K^0$. Similarly, for an indexed set of concept lattices $L = \{L_x\}_{x \in X}$, $\eta^*(L) = \{\eta(L_x)\}_{x \in X}$. Then, given a set $\Omega$ of relational scaling operations, a set $R$ of relations, the set of scalable relational attributes for a concept with respect to an indexed family

<footnote n="3">³We use the term ‘relational context’ instead of ‘relational context family’.</footnote>
of sets of concept names N is:

$$D_{\Omega,R_x,N} = \bigcup_{\zeta \in \Omega} \bigcup_{z \in X} \bigcup_{r \in R_x,z} D_{\zeta,r,N_z}.$$

This notation is used for identifying the relational attributes that can be scaled for a context $K_x$ from a set of concept lattices:

$$D_{\Omega,R_x,L} = D_{\Omega,R_x,\eta^*(L)}$$

or the set of all the possible relational attributes that can be scaled for a context $K_x$ given a family of formal contexts $K^0$ as

$$D_{\Omega,R_x,K^0} = D_{\Omega,R_x,\eta^*(K^0)}.$$

Since $\forall z \in X, \eta(L_z) \subseteq \eta(K_z^0)$, then $D_{\Omega,R_x,\{L_z\}_{z \in X}} \subseteq D_{\Omega,R_x,K^0}$. This is illustrated by Example 6.

**Example 6** (Set of relational attributes (cont'd)). Following Example 5, if $K_2^0$, whose objects are $\{d, e, f\}$, is also linked to itself ($K_2^0$) by the relation s and the current set of concept names is $\eta(L_2^0) = \{DEF, DE, E\}$, then it would additionally scale the relational attributes: $D_{\{\exists\},\{s\},\{L_2^0\}} = D_{\exists,s,\eta(L_2^0)} = \{\exists s.DEF, \exists s.DE, \exists s.E\}$. If, in addition, the strict contains scaling operation ($\forall \exists C.r$, see Table 3) is used, then new relational attributes would be:

$$D_{\{\exists,\forall\},\{q,s\},\{L_1^0,L_2^0\}} = \{\exists q.ABC, \exists q.AB, \exists q.C, \exists q.\perp, \exists s.DEF, \exists s.DE, \exists s.E, \\ \forall \exists ABC.q, \forall \exists AB.q, \forall \exists C.q, \forall \exists \perp.q, \forall \exists DEF.s, \forall \exists DE.s, \forall \exists E.s\}.$$

The semantics of these attributes is provided in the same way as above and noted $\langle R, L \rangle \models gI\zeta(r, c)$.

### 2.4.2 Operations and algorithm

Hereafter, we will consider relational scaling with the structure $\Sigma = \langle R, L \rangle$ made of a set $R$ of binary relations between two sets of objects from $K^0$, and a family $L^t = \{L_x^t\}_{x \in X}$ of concept lattices obtained from $K^t$.

RCA applies relational scaling operations from a set $\Omega$ to each $K_x^t \in K^t$ and all relations $r \in R_{x,z}$ from the set of concepts in the corresponding $L_z^t = \text{FCA}(K_z^t)$. Such scaling is defined as:

$$\sigma_{\Omega}(K_x, R, L) = K_{+D_{\Omega,R_x,L}}^{\langle R,L \rangle}(K_x).$$

The classical RCA algorithm, that is called here RCA, thus relies on FCA and $\sigma_{\Omega}$. More precisely, it applies these in parallel on all contexts. Hence, $\text{FCA}^*$ and $\sigma_{\Omega}^*$ are defined as:

$$\text{FCA}^*(\{K_x\}_{x \in X}) = \{\text{FCA}(K_x)\}_{x \in X}, \\ \sigma_{\Omega}^*(\{K_x\}_{x \in X}, R, L) = \{\sigma_{\Omega}(K_x, R, L)\}_{x \in X}.$$
such that $L$ is a family of concept lattices. The whole family of concepts lattices needs to be passed to $\sigma$.

RCA starts from the initial family of contexts $K^0$ and iterates the application of the two operations:

$$K^{t+1} = \sigma_{\Omega}^{*}(K^{t}, R, \text{FCA}^{*}(K^{t}))$$

until reaching a fixed point, i.e. reaching $n$ such that $K^{n+1} = K^n$. Then, RCA$_{\Omega}(K^0, R) = \text{FCA}^*(K^n)$.

Thus, the RCA algorithm proceeds in the following way:

1. Initial contexts: $t \leftarrow 0$; $\{\langle G_x, M_x^t, I_x^t \rangle\}_{x \in X} \leftarrow \{\langle G_x, M_x, I_x \rangle\}_{x \in X}$.

2. $\{L_x^t\}_{x \in X} \leftarrow \text{FCA}^*(\{\langle G_x, M_x^t, I_x^t \rangle\}_{x \in X})$ (or, for each context, $\langle G_x, M_x^t, I_x^t \rangle$ the corresponding concept lattice $L_x = \text{FCA}(\langle G_x, M_x^t, I_x^t \rangle)$ is created using FCA).

3. $\{\langle G_x, M_x^{t+1}, I_x^{t+1} \rangle\}_{x \in X} \leftarrow \sigma_{\Omega}^*(\{\langle G_x, M_x^t, I_x^t \rangle\}_{x \in X}, R, \{L_x^t\}_{x \in X})$ (i.e. relational scaling is applied, for each relation $r$ whose codomain lattice has new concepts, generating new contexts $\langle G_x, M_x^{t+1}, I_x^{t+1} \rangle$ including both plain and relational attributes in $M_x^{t+1}$).

4. If $\exists x \in X$ such that $M_x^{t+1} \neq M_x^t$ (scaling has occurred), then $t \leftarrow t+1$; go to Step 2.

5. Return $\{L_x^t\}_{x \in X}$.

This is illustrated by Example 7.

**Example 7 (Relational concept analysis).** Consider two relations $p$ and $q$ defined as:

$$\begin{array}{c|ccc}
p & d & e & f \\
\hline
a & \times & & \\
b & & \times & \\
c & & & \times
\end{array}$$

$$\begin{array}{c|ccc}
q & a & b & c \\
\hline
d & \times & & \\
e & & \times & \\
f & & & \times
\end{array}$$

and applying on the contexts $K_1^0$ of Example 1 and $K_2^0$ of Example 4 (Figure 1).

Applying FCA* to the two contexts $K_1^0$ and $K_2^0$, provides the very simple lattices $L_1^0$ and $L_2^0$ of Figure 1 with concepts ABC, AB, C and $\perp$, and DEF, DE and E, respectively. Applying scaling, as seen partially in Example 4, provides the context $K_1^1$ with new attributes $\exists p.DEF, \exists p.DE, \exists p.E$ and $K_2^1$ with $\exists q.ABC, \exists q.AB, \exists q.C$ (Example 5). Applying FCA* to these contexts provides the lattices $L_1^1$ and $L_2^1$ with additional concepts B and F. These can in turn go through scaling and unveil new attributes $\exists p.F$ and $\exists q.B$ added to $K_1^1$ and $K_2^1$ to give $K_1^2$ and $K_2^2$. FCA* introduces the new attributes in the intent of relevant concepts but does not introduce any new concept. Hence the process stops and RCA returns the family of concept lattices $\{L_1^2, L_2^2\}$.

The result is thus quite different from the $\{L_1^0, L_2^0\}$ that would have been returned by FCA alone.

These operations can be interpreted as generating a description logic T-box from a given A-box. This can be seen in Example 8.

**Example 8 (Relational concept analysis and description logics).** As an example, consider the following ABox:

$$A_{12}^{0} = \{ \top_{1}(a), \top_{1}(b), \top_{1}(c), m_{1}(c), m_{2}(a), m_{2}(b), m_{3}(c), p(a, d), p(b, e), p(c, f), \\ \top_{2}(d), \top_{2}(e), \top_{2}(f), n_{1}(d), n_{1}(e), n_{2}(e), q(d, a), q(e, b), q(f, c) \}$$
<figure><img src="image_4.png" /><figcaption>Figure 1: The three iterations of RCA from the initial contexts $K_1^0$ and $K_2^0$.</figcaption></figure>

This can be encoded as the two context $K_1^0$ and $K_2^0$ (Figure 1) and the two relations $p$ and $q$ between these of Example 7.

From this, RCA generates the lattices $L_1^2$ and $L_2^2$ (Figure 1) which can be interpreted as the description logic T-box:

$$ T_{12}^2 = \{ ABC \sqsubseteq \top_1 \sqcap \exists p.DEF, AB \sqsubseteq ABC \sqcap m_2 \sqcap \exists p.DE, B \sqsubseteq AB \sqcap \exists p.E, \\ C \sqsubseteq ABC \sqcap m_1 \sqcap m_2 \sqcap \exists p.F, AB \sqcap C \sqsubseteq \bot, DEF \sqsubseteq \top_2 \sqcap \exists q.ABC, \\ DE \sqsubseteq DEF \sqcap n_1 \sqcap \exists q.AB, E \sqsubseteq DE \sqcap n_2 \sqcap \exists q.B, F \sqsubseteq DEF \sqcap \exists q.C, \\ DE \sqcap F \sqsubseteq \bot \} $$
with the improved A-box:

$$A_{12}^2 = \{AB(a), B(b), C(c), p(a, d), p(b, e), p(c, f), \\ DE(d), E(e), F(f), q(d, a), q(e, b), q(f, c)\}$$

### 2.4.3 Properties and semantics

A context $K = \langle G, M, I \rangle$ is a subcontext of another $K' = \langle G', M', I' \rangle$ whenever $G \subseteq G'$, $M \subseteq M'$ and $I = I' \cap (G \times M)$ [Ganter and Wille, 1999, p.97]. By abuse of notation, this is noted $K \subseteq K'$. This is generalised to families of contexts $\{K_x\}_{x \in X} \subseteq \{K'_x\}_{x \in X}$ whenever $\forall x \in X, K_x \subseteq K'_x$.

RCA always reaches a closed family of contexts for reason of finiteness [Rouane Hacène et al., 2013a] and the sequence $(K^t)_{t=0}^n$ is non-(intent-)contracting, i.e. $\forall t \ge 0, K^t \subseteq K^{t+1}$ [Rouane Hacène et al., 2013b].

The RCA semantics characterises the set of concepts in resulting RCA lattices as all and only those concepts grounded on the initial family of contexts $(K^0)$ based on relations $(R)$ [Rouane Hacène et al., 2013b]. This can thus be considered as a well-grounded semantics: an attribute is scaled and applied to an object at iteration $t + 1$ only if its condition applies at stage $t$. Hence, everything is ultimately relying on $K^0$.

[Rouane Hacène et al., 2013b] established that RCA indeed finds the $K^n$ satisfying these constraints through correctness (the concepts of FCA$^*(K^n)$ are grounded in $K^0$ through $R$) and completeness (all so-grounded concepts are in $K^n$).

## 2.5 Dependencies and cycles

As can be seen, relations in RCA define a dependency graph between objects (of different or the same context). In turn, this graph of objects induces a dependency graph between concepts through the scaled attributes that refer to other concepts. It also induces a dependency graph between contexts: an edge exists between two contexts if an object of the former is related to an object of the latter.

This report is related to the circular dependencies, i.e. the circuits, that may exist within these graphs. We say that a set $R$ of relations is *hierarchical* if its object dependency graph is not circular.

Circular dependencies create a problem when one wants to define the family of concept lattices that should be returned by relational concept analysis. As will be seen in Section 3, there may exists several such families.

In order to explain some specific phenomena in a clearer way, it is possible to study them in various restrictions of RCA. We introduced some of these that are organised in Figure 2:

- RCA$^n$: RCA with $n$ contexts

- RCA$^1$: RCA with one context

- RCA$^0$: RCA with one *empty* context

- HRCA: RCA with only hierarchical relations.

- HRCA$^1$: FCA: FCA
From such a simple basis, it is possible to consider more complex settings:

- By using more than two contexts;

- By using more than two relations between these contexts;

- By using more than two objects in each context;

- By using more than zero attributes in the contexts.

## 3.1 RCA may accept different families of concept lattices

The simple Example 7 (Figure 1) does not present a result in which each object is identified by a single class. Indeed, *a* has not more attributes than *b*. This result could also be obtained with far more objects *a'*, *a''*, etc. sharing the attributes of *a* and *b*, or duplicating other objects.

However, the lattices $L_1^*$ and $L_2^*$ displayed in Figure 3 seem another good way to describe the data given as input to RCA. There is in fact an objective difference between *AC* and *BC*: *AC* denotes all objects connected by *p* to *DF* and *BC* all objects connected by *p* to *EF*. Reciprocally, *DF* denotes all objects connected by *q* to *AC* and *EF* those connected by *q* to *BC*.

<figure><img src="image_5.png" /><figcaption>Figure 3: Alternative concept lattices for the example of Section 3.1 (★ is simply a way to identify these objects).</figcaption></figure>
The two corresponding T-Box and A-box would be:

$$
T_{12}^{*} = \{ 
\begin{array}{l}
\text{ABC} \sqsubseteq \top_1 \sqcap \exists p.DE, \text{AB} \sqsubseteq \text{ABC} \sqcap m_2 \sqcap \exists p.DE, \text{B} \sqsubseteq \text{AB} \sqcap \exists p.E, \\
\quad \text{C} \sqsubseteq \text{ABC} \sqcap m_1 \sqcap m_2 \sqcap \exists p.F, \text{AB} \sqcap \text{C} \sqsubseteq \perp, \text{DEF} \sqsubseteq \top_2 \sqcap \exists q.ABC, \\
\quad \text{DE} \sqsubseteq \text{DEF} \sqcap n_1 \sqcap \exists q.AB, \text{E} \sqsubseteq \text{DE} \sqcap n_2 \sqcap \exists q.B, \text{F} \sqsubseteq \text{DEF} \sqcap \exists q.C, \\
\quad \text{DE} \sqcap \text{F} \sqsubseteq \perp
\end{array}
\}
$$

$$
A_{12}^{*} = \{ A(a), B(b), C(c), p(a, d), p(b, e), p(c, f), \\
D(d), E(e), F(f), q(d, a), q(e, b), q(f, c) \}
$$

These lattices share many common points with those returned by RCA: they are also

1. valid concept lattices,

2. whose contexts extend $K_1^0$ and $K_2^0$ with attributes of $D_{\exists\{\exists\},\{p\},K^0}$ and $D_{\exists\{\exists\},\{q\},K^0}$ (Example 5),

3. stable for scaling, and

4. such that each attribute refers only to concepts in the lattices.

The only difference with $L_1^0$ and $L_2^0$ is that they are not those returned by RCA. We will
temporarily informally consider lattices sharing these features as *acceptable*.

But, if there exists several acceptable solutions for a given Ω and R, why does RCA
only returns one of these, and which one? To help answering this question, we illustrate
the problem with minimal running examples below.

3.2 Minimal RCA⁰ example

As an RCA⁰ example, consider the following ABox:

$$
A_0^0 = \{ \top_0(a), \top_0(b), \top_0(c), \top_0(d), r(a,b), r(b,a), r(c,d), r(d,c), r(a,a), r(b,b) \}.
$$

It can be encoded as an empty context ($K_0^0$) from which FCA will generate the concept lattice $L_0^0$ as follows:

$$
FCA\left(\frac{
  \begin{array}{c|c}
    K_0^0 \\
    \hline
    a \\
    b \\
    c \\
    d
  \end{array}
}{
  \begin{array}{c}
    K_0^0 \\
    \hline
    a \\
    b \\
    c \\
    d
  \end{array}
}\right) = L_0^0: \left(\frac{
  \begin{array}{c}
    a, b, c, d
  \end{array}
}{
  \begin{array}{c}
    a, b, c, d
  \end{array}
}\right) \quad ABCD
$$

Scaling with $\sigma_{\exists}$ and $r$ provides the attribute $\exists r.ABCD$:

$$
\sigma_{\exists}(\frac{
  \begin{array}{c}
    K_0^0 \\
    \hline
    a \\
    b \\
    c \\
    d
  \end{array}
}{
  \begin{array}{c}
    a \\
    b \\
    c \\
    d
  \end{array}
}) , \quad L_0^0: \left(\frac{
  \begin{array}{c}
    a, b, c, d
  \end{array}
}{
  \begin{array}{c}
    a, b, c, d
  \end{array}
}\right) \quad ) = \quad \frac{
  \begin{array}{c}
    K_0^1 \\
    \hline
    a \\
    b \\
    c \\
    d
  \end{array}
}{
  \begin{array}{c}
    a \\
    b \\
    c \\
    d
  \end{array}
} \quad \left(\frac{
  \begin{array}{c}
    D, B, V, \exists \\
    \hline
    \times \\
    \times \\
    \times \\
    \times
  \end{array}
}{
  \begin{array}{c}
    \times \\
    \times \\
    \times \\
    \times
  \end{array}
}\right)
$$
<figure><img src="image_6.png" /><figcaption>Figure 4: Alternative concept lattices ($L'_0$ and $L_0^*$).</figcaption></figure>

which run through FCA returns:

$$ \text{FCA}( \begin{array}{c|c} K_0^1 & \exists r.ABCD \\ \hline a & \times \\ b & \times \\ c & \times \\ d & \times \end{array} ) = L_0^1: \substack{ \exists r.ABCD \\ \hline a, b, c, d \\ \hline ABCD \end{array} ) $$

Since no new concept has been added, scaling would return $K_0^1$, hence $L_0^1$ is the result returned by RCA⁰ (and RCA).

However, the concept lattices $L'_0$ and $L_0^*$ of Figure 4 are other valid lattices worth considering as acceptable solutions. As in classical RCA, each concept of these lattices is closed with respect to the specific context scaled by $∃$ and $r$ from the concepts of the lattice. Moreover, the lattices are self-supported in the sense that their attributes refer only to their own concepts.

They correspond to different knowledge bases:

$$ T_0^1 = \{ABCD \sqsubseteq \exists r.ABCD\} $$

$$ A_0^1 = \{ABCD(a), ABCD(b), ABCD(c), ABCD(d), r(a, b), r(b, a), r(c, d), r(d, c), r(a, a), r(b, b)\} $$

and

$$ T'_0 = \{AB \sqsubseteq \top_0 \sqcap \exists r.AB, CD \sqsubseteq \top_0 \sqcap \exists r.CD, ABCD \sqsubseteq \exists r.ABCD\} $$

$$ A'_0 = \{AB(a), AB(b), CD(c), CD(d), r(a, b), r(b, a), r(c, d), r(d, c), r(a, a), r(b, b)\} $$
and

$$T_0^* = \{AB \sqsubseteq ABC \sqcap ABD \sqcap \exists r.AB, C \sqsubseteq ABC \sqcap CD \sqcap \exists r.D, D \sqsubseteq ABD \sqcap CD \sqcap \exists r.C, \\ ABC \sqsubseteq ABCD \sqcap \exists r.ABD, ABD \sqsubseteq ABCD \sqcap \exists r.ABC, CD \sqsubseteq ABCD \sqcap \exists r.CD, \\ ABCD \sqsubseteq \exists r.ABCD\}$$

$$A_0^* = \{AB(a), AB(b), C(c), D(d), r(a, b), r(b, a), r(c, d), r(d, c), r(a, a), r(b, b)\}$$

The problem that there exists several acceptable candidate lattices applies to RCA as a whole because RCA⁰ is included in RCA.

## 3.3 Minimal RCA example

As another example, consider the following ABox:

$$A_{34}^{0} = \{\top_{3}(a), \top_{3}(b), \top_{4}(c), \top_{4}(d), p(a, c), p(b, d), q(c, a), q(b, d)\}$$

This can be encoded as the two empty contexts $K_3^0$ and $K_4^0$ of Figure 6 and the two relations $p$ and $q$ of Figure 5.

<table><caption>Figure 5: Relations $p$ and $q$ for RCA.</caption><thead><tr><th>p</th><th>c</th><th>d</th></tr></thead><tbody><tr><td>a</td><td>×</td><td></td></tr><tr><td>b</td><td></td><td>×</td></tr></tbody></table><table><thead><tr><th>q</th><th>a</th><th>b</th></tr></thead><tbody><tr><td>c</td><td>×</td><td></td></tr><tr><td>d</td><td></td><td>×</td></tr></tbody></table>

Applying FCA to the two contexts $K_3^0$ and $K_4^0$ provides the very simple lattices $L_3^0$ and $L_4^0$ of Figure 6. From this, RCA generates new context $K_3^1$ and $K_4^1$ through scaling which provides new lattices $L_3^1$ and $L_4^1$ (Figure 6).

$$\frac{K_3^0}{\begin{array}{c} a \\ b \end{array}}$$

$$L_3^0: \frac{\boxed{\phantom{AB}}}{a, b}$$

$$L_4^0: \frac{\boxed{\phantom{CD}}}{c, d}$$

$$\frac{K_3^1}{\begin{array}{c} a \\ b \end{array}} \xrightarrow{\exists p.CD} \frac{\boxed{\phantom{AB}}}{a, b}$$

$$L_3^1: \frac{\boxed{\exists p.CD}}{\phantom{a, b}}$$

$$L_4^1: \frac{\boxed{\exists q.AB}}{c, d}$$

<caption>Figure 6: The two iterations of RCA from the initial contexts $K_3^0$ and $K_4^0$.</caption>

The lattices $L_3^1$ and $L_4^1$ of Figure 6 are those returned by RCA as applying scaling from them returns the same contexts $K_3^1$ and $K_4^1$.

However, there could be other acceptable solutions such as those displayed in Figure 7. They are all acceptable solutions for $\{K_3^0, K_4^0\}$ (Figure 6) as they satisfy the four conditions of Section 3.1.
<figure><img src="image_7.png" /><figcaption>Figure 7: Alternative pairs of concept lattices covering the contexts of Figure 6.</figcaption></figure>

On the contrary, Figure 8 displays a family of concept lattices {$L_3^#, L_4^#$} which is not an acceptable solution. Although they contain all concepts of {$L_3^0, L_4^0$} and no concept not in {$L_3^*, L_4^*$}, they would generate more attributes through scaling and applying RCA to their contexts {$K_3^#, K_4^#$} would lead to {$L_3^*, L_4^*$}

<figure><img src="image_8.png" /><figcaption>Figure 8: A family of concept lattices {$L_3^#, L_4^#$} which is not an acceptable solution.</figcaption></figure>

Hence the question raised in the previous section: Why does RCA return only one solution, and which one? Answering it requires to reconsider the RCA semantics. More precisely, it requires to define formally which families of concept lattices could be considered as acceptable solutions and which of them is returned by the RCA operation.

The following aims at defining acceptability formally. For that purpose, we first consider the simpler case of RCA⁰. We define expansion functions (Section 4) and contraction functions (Section 5), both from the independent standpoints of contexts and
lattices. Then, because these are in fact dependent, we apply them to context-lattice
pairs (Section 6). These results are then extended to RCA (Section 7) in which accept-
ability is related to the set of fixed points of both extended function. This allows us to
precisely define the fixed-point semantics of RCA (Section 8).

4 A parallel context-lattice fixed-point semantics for RCA⁰

In order to investigate the semantics of relational concept analysis, we adopt a functional
standpoint in which RCA is defined as a function in a precisely defined space. In Sec-
tions 4.1 and 4.2, we provide two alternative, and equivalent, characterisations of that
space, which provide the semantics for RCA⁰. In Section 4.3, we relate the well-grounded
RCA semantics to these two semantics by showing that RCA⁰ computes the least fixed
point of these functions.

In order to investigate the semantics of relational concept analysis, we need to define
the objects on which it applies. They are determined by three elements given once and
for all: $K^0 = \{\langle G_x, M_x^0, I_x^0 \rangle\}_{x \in X}, R, \text{and } \Omega$. Through the application of RCA, only $M_x^t$
and $I_x^t$ change, hence the other may remain implicit.

Although the results of this section aim at RCA⁰, most of it applies to RCA, hence
we use RCA⁰ only when it matters.

**Warning: a nest of fixed points**

RCA is a world of fixed points, hence it is easy to
get lost among the various fixed points involved:

- In description logics, which RCA targets, the semantics of concepts is given by (least) fixed points when circularities occur [Nebel, 1990];

- FCA's goal is to compute fixed points: concepts are the result of a closure operation which is also a fixed point [Belohlávek, 2008];

- finally, the RCA result is the fixed point of the function that grows a family of concept lattices from the previous one through scaling.

The present work is concerned with the fixed points of the latter function taking the
others into account.

4.1 Semantics and properties: the context approach

We first study the semantics of RCA from the standpoint of the contexts. We define
precisely the space of contexts in which RCA⁰ is computed and the functions underlying
RCA in that space.

4.1.1 The lattice 𝓶 of RCA⁰ contexts

The contexts considered by RCA are scaled from the initial context using the scaling
operations. In RCA⁰, they are determined by $K^0 = \langle G, \emptyset, \emptyset \rangle$, $R$, and $\Omega$. But most
of this section will ignore it and consider $K^0 = \langle G, M, I \rangle$. Through the application of
RCA, only $M$ and $I$ change, the latter depending directly from the former (Property 1).
**Property 1** (The incidence relation depends only on the attribute). Given $\varsigma$ a relational scaling operation, $K = \langle G, M, I \rangle$ a formal context and $r$ a relation between $G$ and $G_z$ a possibly different set of objects. Given $L$ and $L'$ two concept lattices on $G_z$, for the scaled attributes $m = \varsigma(r, c) \in D_{\varsigma,r,\eta(L)} \cap D_{\varsigma,r,\eta(L')}$, $\forall g \in G$, $\langle \{r\}, L \rangle \models m(g)$ if and only if $\langle \{r\}, L' \rangle \models m(g)$.

*Proof.* $m = \varsigma(r, c)$ is scaled from a scaling operation $\varsigma$, a relation $r$ and a concept $c$ (possibly a cardinal $n$). From Table 3, $\langle R, L \rangle \models gIm$ only depends on $\varsigma$, $r$ and the extent of $c$. However, $\varsigma$ and $r$ are independent from $L$ and $L'$. The concept $c$ is identified by a name which denotes its extent. Hence, its extent is the same in $L$ and $L'$ to which it belongs. So whether an object of $g \in G_x$ satisfies the attribute $\varsigma(r, c)$ or not depends solely on the attribute $\varsigma(r, c)$ and not on the specific lattice considered. $\square$

Property 1 highlights that the incidence of the scaled attributes does only depend on the relation and not on the concept lattices. This obviously applies to RCA$^0$ with $G_z = G$. This can be extended to the full RCA:

**Property 2** (The incidence relation depends only on the attributes). Given a set $\Omega$ of relational scaling operations, a family $K = \{\langle G_x, M_x, I_x \rangle\}_{x \in X}$ of formal contexts and a set $R$ of relations on $K$. Given $L$ and $L'$ two concept lattices on $G_z$, for all scaled attributes $m = \varsigma(r, c) \in D_{\varsigma,R_{x,z},L} \cap D_{\varsigma,R_{x,z},L'}$, $\forall g \in G_x$, $\langle R, L \rangle \models m(g)$ if and only if $\langle R, L' \rangle \models m(g)$.

*Proof.* For all $\varsigma \in \Omega$, $r \in R$ and $c \in L$, $\varsigma(r, c)$ is defined independently from the rest of $\Omega$, $R$ and $L$ (or $L'$). Hence Property 1 applies to any such combination. $\square$

This means that the interpretation of an attribute never changes: it is given by its syntactic form $\varsigma(r, c)$ and, in particular, the concept name. Hence, when adding or suppressing attributes, through $K_{+M}^{\Sigma}$ or $K_{-M}^{\Sigma}$, $\Sigma$ can be $\langle R, N \rangle$ with $N$ an indexed set of names, and in particular $\eta^*(K^0)$.

In RCA, the set of objects $G_x$ does not change. Property 2 entails that, if $M_x \subseteq M_x'$, then $I_x \subseteq I_x'$. Thus we are justified in using, for RCA, the definition of subcontexts introduced in Section 2.4.3. For comparing two contexts, it suffices to compare their sets of attributes: if $\forall x \in X$, $M_x \subseteq M_x'$, then $K \subseteq K'$.

The attribute language $D_{\Omega,R_x,N}$ that can be generated by scaling depends on the finite set of relations $R$, the scaling operations $\Omega$ and the set of possible concepts identified by their standardised names (§2.2.3 and 2.4.1). Given $N \subseteq \eta^*(K^0)$ an indexed family of names of concepts that can be in the codomain of relations in $R$, the set of contexts that can be obtained by scaling is

$$ \mathcal{K}_{K_x^0, R, \Omega}^N = \{K_{+M}^{\langle R, \eta^*(K^0) \rangle} (K_x^0) \mid M \subseteq D_{\Omega, R_x, N}\}. $$

with $K_{+M}^{\langle R, \eta^*(K^0) \rangle}$ (.) the operation defined in §2.2. Passing $\eta^*(K^0)$ to $K$ allows to interpret the generated attributes and to determine $I$. Below, when we write $\mathcal{K}^N$, the property applies for any $\{N_x\}_{x \in X}$ such that $\forall x \in X$, $N_x \subseteq \eta(K_x^0)$, and in particular for $\eta^*(K^0)$.
In RCA<sup>0</sup>, the set of class names is η(K<sup>0</sup>). Hence the attribute language D<sub>Ω,R,K<sup>0</sup></sub> is fully determined by the non-changing parts: G, the finite set of relations R and the scaling operations Ω.

$$ \mathcal{K}_{K^0, R, \Omega} = \mathcal{K}_{K^0, R, \Omega}^{\eta(K^0)} $$

Contexts may be combined by two operations: meet (∧) and join (∨) on $\mathcal{K}_{K^0, R, \Omega}^N$:

**Definition 1** (Meet and join of contexts). Given K, K' ∈ $\mathcal{K}_{\langle G, M^0, I^0 \rangle, R, \Omega}^N$ such that K = $\langle G, M^0 \cup M, I^0 \cup I \rangle$ and K' = $\langle G, M^0 \cup M', I^0 \cup I' \rangle$, K ∨ K' and K ∧ K' are defined as:

$$ K \lor K' = \langle G, M^0 \cup (M \cup M'), I^0 \cup (I \cup I') \rangle, \quad (\text{join}) $$

$$ K \land K' = \langle G, M^0 \cup (M \cap M'), I^0 \cup (I \cap I') \rangle. \quad (\text{meet}) $$

The set of contexts is closed by meet and join.

**Property 3** ([Euzenat, 2021]). $\forall K, K' \in \mathcal{K}_{K^0, R, \Omega}^N$, $K \land K' \in \mathcal{K}_{K^0, R, \Omega}^N$ and $K \lor K' \in \mathcal{K}_{K^0, R, \Omega}^N$.

*Proof.* Meet and join are defined from the union and intersection of subsets of $D_{Ω,R,K^0}$ (Definition 1). But $\mathcal{K}_{K^0, R, \Omega}^N$ is closed by union and intersection of the sets of attributes to add to $M^0$ and the incidence relation is fully determined by the set of attributes (Property 2). Hence, meet and join of contexts in $\mathcal{K}_{K^0, R, \Omega}^N$ belong to $\mathcal{K}_{K^0, R, \Omega}^N$. □

**Property 4** (Commutativity, associativity and absorption of ∨ and ∧ on $\mathcal{K}$). For all K, K', K'' ∈ $\mathcal{K}$,

$$ K \lor K' = K' \lor K \quad \text{and} \quad K \land K' = K' \land K, \quad (\text{commutativity}) $$

$$ (K \lor K') \lor K'' = K \lor (K' \lor K'') \quad \text{and} \quad (K \land K') \land K'' = K \land (K' \land K''), \quad (\text{associativity}) $$

$$ K \land (K \lor K') = K \quad \text{and} \quad K \lor (K \land K') = K. \quad (\text{absorption}) $$
*Proof.* Proofs are given for $\wedge$, those for $\vee$ follow the exact same pattern.

$$ K \wedge K' = \langle G, M, I \rangle \wedge \langle G, M', I' \rangle \\ = \langle G, M^0 \cup (M \cap M'), I^0 \cup (I \cap I') \rangle \qquad \text{Definition 1} $$

$$ = \langle G, M^0 \cup (M' \cap M), I^0 \cup (I' \cap I) \rangle \qquad \text{Commutativity of } \cap $$

$$ = \langle G, M', I' \rangle \wedge \langle G, M, I \rangle \qquad \text{Definition 1} $$

$$ = K' \wedge K $$

$$ (K \wedge K') \wedge K'' = (\langle G, M, I \rangle \wedge \langle G, M', I' \rangle) \wedge \langle G, M'', I'' \rangle \\ = (\langle G, M^0 \cup (M \cap M'), I^0 \cup (I \cap I') \rangle) \\ \wedge \langle G, M'', I'' \rangle \qquad \text{Definition 1} $$

$$ = \langle G, M^0 \cup ((M \cap M') \cap M''), I^0 \cup ((I \cap I') \cap I'') \rangle \qquad \text{Definition 1} $$

$$ = \langle G, M^0 \cup (M \cap (M' \cap M'')), I^0 \cup (I \cap (I' \cap I'')) \rangle \qquad \text{Associativity of } \cap $$

$$ = \langle G, M^0 \cup M, I^0 \cup I \rangle $$

$$ \wedge \langle G, M^0 \cup (M' \cap M''), I^0 \cup (I' \cap I'') \rangle \qquad \text{Definition 1} $$

$$ = \langle G, M^0 \cup M, I^0 \cup I \rangle $$

$$ \wedge (\langle G, M^0 \cup M', I^0 \cup I' \rangle \wedge \langle G, M^0 \cup M'', I^0 \cup I'' \rangle) \qquad \text{Definition 1} $$

$$ = K \wedge (K' \wedge K'') \qquad \text{Definition 1} $$

$$ K \vee (K \wedge K') = \langle G, M, I \rangle \vee (\langle G, M, I \rangle) \wedge \langle G, M', I' \rangle \\ = \langle G, M, I \rangle \vee \langle G, M^0 \cup (M \cap M'), I^0 \cup (I \cap I') \rangle \qquad \text{Definition 1} $$

$$ = \langle G, M^0 \cup M \cup (M \cap M'), I^0 \cup I \cup (I \cap I') \rangle \qquad \text{Definition 1} $$

$$ = \langle G, M^0 \cup M, I^0 \cup I \rangle \qquad \text{Absorption of } \cup/\cap $$

$$ = \langle G, M, I \rangle $$

$$ = K $$

□

These operations are aligned with context inclusion (Property 5):

**Property 5** ([Euzenat, 2021]). $\forall K, K' \in \mathcal{K}_{K^0, R, \Omega}^N, K \subseteq K' \text{ iff } K = K \wedge K'$.

*Proof.* This property also comes directly from its set theoretic counterpart application to $M$ and $M'$: $K \subseteq K' \Leftrightarrow M \subseteq M' \Leftrightarrow M = M \cap M' \Leftrightarrow K = K \wedge K'$. □

This provides the space of contexts with a complete lattice structure (Property 6):

**Property 6** ([Euzenat, 2021]). $\langle \mathcal{K}_{K^0, R, \Omega}^N, \vee, \wedge \rangle$ is a complete lattice.

*Proof.* $\mathcal{K}_{K^0, R, \Omega}^N$ is closed by meet and join (Property 3). $\vee$ and $\wedge$ satisfy commutativity, associativity and the absorption law (Property 4), so this is a lattice. It is complete because for any subset $S$ of $\mathcal{K}_{K^0, R, \Omega}^N$, $\wedge S = \langle G, M^0 \cup \bigcap_{\langle G, M^0 \cup M, I^0 \cup I \rangle \in S} M, I^0 \cup$
$\bigcap_{\langle G, M^0 \cup M, I^0 \cup I \rangle \in S} I \rangle$ is well-defined and the greatest lower bound, because $\cap$ induces the greatest lower bounds on attributes and incidence relations. The same reasoning is possible for the smallest upper bound. $\square$

The proof extends [Euzenat, 2021] to the non-finite case.

### 4.1.2 The context expansion function F

We reformulate RCA as based on a main single function, $F_{K^0, R, \Omega}$, the context expansion function<fnref n="5" /> attached to a relational context $\langle K^0, R \rangle$ and a set $\Omega$ of scaling operations.

**Definition 2** (Context expansion function [Euzenat, 2021]). Given a relational context $\langle K^0, R \rangle$ and a set $\Omega$ of relational scaling operations, the function $F_{K^0, R, \Omega} : \mathcal{K}_{K^0, R, \Omega} \to \mathcal{K}_{K^0, R, \Omega}$ is defined by:

$$F_{K^0, R, \Omega}(K) = \sigma_{\Omega}(K, R, \text{FCA}(K)).$$

The function expression is independent from $K^0$, $K^0$ is used to restrict the domain of the function so that its elements cover $K^0$. $F_{K^0, R, \Omega}$ is only defined over $\mathcal{K}_{K^0, R, \Omega}$ because scaling is not restricted to an arbitrary $N$. From now on, we will abbreviate $\mathcal{K}_{K^0, R, \Omega}$ as $\mathcal{K}$ and $F_{K^0, R, \Omega}$ as $F$. This is legitimate because, for a given relational context, $K^0$, $R$ and $\Omega$ do not change. $F$ is an extensive and monotone internal operation for $\mathcal{K}$:

**Property 7** ($F$ is internal to $\mathcal{K}$ [Euzenat, 2021]). $\forall K \in \mathcal{K}, F(K) \in \mathcal{K}$.

*Proof.* Scaling only adds attributes from $D_{\Omega, R, K^0}$.

$\square$

**Property 8** ($F$ is extensive and monotone [Euzenat, 2021]). The function $F$, attached to a relational context and a set of scaling operations, satisfies:

$$K \subseteq F(K), \qquad (\text{extensivity})$$

$$K \subseteq K' \Rightarrow F(K) \subseteq F(K'). \qquad (\text{monotony})$$

*Proof.* extensivity holds because $F$ can only add to each context in $K$ new relational attributes scaled from $FCA(K)$. The set of attributes can thus not be smaller. monotony holds because $K \subseteq K'$ means that $M \subseteq M'$. This entails that the set of concepts of $FCA(K)$ is included in that of $FCA(K')$, hence the set of attributes $A$ scaled from $K$ is included in the set $A'$ scaled from $K'$. Since, they are added to $M$ and $M'$, then $M \cup A \subseteq M' \cup A'$, hence $F(K) \subseteq F(K')$. $\square$

Extensivity corresponds to the non-contracting property of the well-grounded semantics [Rouane Hacène et al., 2013b] and monotony is also called order-preservation.

<footnote n="5">⁵Named ‘complete relational extension’ in [Rouane Hacène et al., 2013b].</footnote>
### 4.1.3 Fixed points of F

Given $F$, it is possible to define its sets of fixed points, i.e. the sets of contexts closed for $F$, as:

**Definition 3** (Fixed point [Euzenat, 2021]). A context $K \in \mathcal{K}$ is a fixed point for a context expansion function $F$, if $F(K) = K$. We call $\text{fp}(F)$ the set of fixed points for $F$.

Since $\mathcal{K}^N$ is a complete lattice and $F$ is order-preserving (or monotone) on $\mathcal{K}$, then the Knaster-Tarski theorem applies:

**Theorem 1** (Knaster-Tarski theorem [Tarski, 1955]). Let $\mathcal{K}$ be a complete lattice and let $F: \mathcal{K} \to \mathcal{K}$ be an order-preserving function. Then the set of fixed points of $F$ in $\mathcal{K}$ is also a complete lattice.

In particular, this warrants that there exists least and greatest fixed points of $F$ in $\mathcal{K}$ (called $\text{lfp}(F)$ and $\text{gfp}(F)$) which can be defined as:

$$ \text{lfp}(F) = \bigwedge_{K \in \text{fp}(F)} K \quad \text{and} \quad \text{gfp}(F) = \bigvee_{K \in \text{fp}(F)} K. $$

## 4.2 Semantics and properties: the lattice approach

In formal concept analysis, there is a one-to-one correspondence between contexts and lattices. Hence the results of the previous section could in principle be derived through reasoning on lattices instead of contexts. In this section, we approach RCA from the lattice standpoint and we show, unsurprisingly, the close parallel with the context approach.

### 4.2.1 The lattice $\mathcal{L}$ of RCA$^0$ concept lattices

From $\mathcal{K}_{K^0, R, \Omega}^N$, one can define $\mathcal{L}_{K^0, R, \Omega}^N$ as the set of images of $\mathcal{K}_{K^0, R, \Omega}^N$ by FCA. These are concept lattices obtained by applying FCA on $K^0$ extended with a subset of $D_{\Omega, R, N}$:

$$ \mathcal{L}_{K^0, R, \Omega}^N = \{ \text{FCA}(K_{+M}^{\langle R, \eta(K^0) \rangle}(K^0)) \mid M \subseteq D_{\Omega, R, N} \}. $$

In RCA$^0$, this time again the set of concept names is limited to those of the single context, $\eta(K^0)$:

$$ \mathcal{L}_{K^0, R, \Omega} = \mathcal{L}_{K^0, R, \Omega}^{\eta(K^0)}. $$

For each subset of attributes, the lattice obtained by FCA is necessarily syntactically different as its concepts refer to different attributes in their intents (at least one of them).

There is in fact a bijective correspondence between $\mathcal{L}_{K^0, R, \Omega}$ and $\mathcal{K}_{K^0, R, \Omega}$ [Ganter and Wille, 1999, §1.2]. On the one hand, for any context in $\mathcal{K}_{K^0, R, \Omega}$ corresponds only one
lattice by FCA. On the other hand, to any concept lattice $\langle C, \le \rangle \in \mathcal{L}_{K^0, R, \Omega}$ corresponds a formal context:

$$ \kappa(\langle C, \le \rangle) = \langle \bigcup_{c \in C} \text{extent}(c), \bigcup_{c \in C} \text{intent}(c), \bigcup_{c \in C} \text{extent}(c) \times \text{intent}(c) \rangle. $$

$\kappa(L)$ collects the attributes and objects present in $L$ intents to build the unique $M$ and $G$, from which the corresponding $I$ is obtained.

It is such that $FCA \circ \kappa = \text{id}_{\mathcal{L}}$ and $\kappa \circ FCA = \text{id}_{\mathcal{L}}$ ($\text{id}_{\mathcal{L}}$ and $\text{id}_{\mathcal{L}}$ being the respective identity functions). This may be stated as:

**Property 9.** $K = \kappa(L)$ iff $L = FCA(K)$.

*Proof.* $\Rightarrow$) $K = \langle G, M, I \rangle = \langle \bigcup_{c \in C} \text{extent}(c), \bigcup_{c \in C} \text{intent}(c), \bigcup_{c \in C} \text{extent}(c) \times \text{intent}(c) \rangle = \kappa(\langle C, \le \rangle) = \kappa(L)$. This means that $\langle C, \le \rangle$ is the concept lattice of a context $\langle G', M', I' \rangle$. But since $G = \bigcup_{c \in C} \text{extent}(c)$ and $M = \bigcup_{c \in C} \text{intent}(c)$, then $G = G'$ and $M = M'$. We need to prove that $I = I'$. Consider $I \neq I'$, this could be because there exists at least one $g \in G$ and $m \in M$ such that $\langle g, m \rangle \in I \setminus I'$ (or, but not exclusively, $\langle g, m \rangle \in I' \setminus I$). In this condition, there could not exists $c \in C$ such that $g \in \text{extent}(c)$ and $m \in \text{intent}(c)$ (resp. it exists). Then $\langle g, m \rangle \notin \bigcup_{c \in C} \text{extent}(c) \times \text{intent}(c)$ (resp. on the contrary it is there) and thus $I \neq \bigcup_{c \in C} \text{extent}(c) \times \text{intent}(c)$ which contradicts $\langle G, M, I \rangle = \kappa(\langle C, \le \rangle)$. Hence, $I = I'$ and $L = \langle C, \le \rangle = FCA(\langle G, M, I \rangle) = FCA(K)$

$\Leftarrow$) $L = \langle C, \le \rangle = FCA(\langle G, M, I \rangle) = FCA(K)$ entails $\forall c \in C, \forall g \in \text{extent}(c), \forall m \in \text{intent}(c), g \text{Im},$ i.e. $\text{extent}(c) \times \text{intent}(c) \subseteq I$. In addition, if $g \text{Im}$, then there exists $c \in FCA(\langle G, M, I \rangle) = \langle C, \le \rangle$ such that $g \in \text{extent}(c)$ and $m \in \text{intent}(c)$, thus $I \subseteq \bigcup_{c \in C} \text{extent}(c) \times \text{intent}(c)$. Moreover, $\top = \langle G, G^\top \rangle \in C$ and $\bot = \langle M^\bot, M \rangle \in C$, hence $\bigcup_{c \in C} \text{extent}(c) = G$ and $\bigcup_{c \in C} \text{intent}(c) = M$. Thus $K = \langle G, M, I \rangle = \langle \bigcup_{c \in C} \text{extent}(c), \bigcup_{c \in C} \text{intent}(c), \bigcup_{c \in C} \text{extent}(c) \times \text{intent}(c) \rangle = \kappa(L)$. $\square$

We define a specific type of homomorphisms between two concept lattices when concepts are simply mapped into concepts with the same extent and a possibly increased intent<fnref n="6" />.

**Definition 4** (Lattice homomorphism [Euzenat, 2021]). A concept lattice homomorphism $h: \langle C, \le \rangle \to \langle C', \le' \rangle$ is a function which maps each concept $c \in C$ into a corresponding concept $h(c) \in C'$ such that:

- $\forall c \in C, \text{intent}(c) \subseteq \text{intent}(h(c))$ (or $\text{intent}(c) \supseteq \text{intent}(h(c))$ if these are considered as description logic concept descriptions),

- $\forall c \in C, \text{extent}(c) = \text{extent}(h(c))$, and

- $\forall c, d \in C, c \le d \Rightarrow h(c) \le' h(d)$.

We note $L \preceq L'$ if there exists a homomorphism from $L$ to $L'$. In principle, $L \simeq L'$ if $L \preceq L'$ and $L' \preceq L$, but here, $\simeq$ is simply $=$. This owes to the fact that the

<footnote n="6">⁶The results in the remainder of this section are specific to RCA: $\preceq$ is defined with the equality of extents and $\subseteq$ depends only on $M$ because $G$ is always the same.</footnote>
homomorphism maps concepts of equal extent, hence, if they hold in both ways, there should be as many concepts in each lattice and these concepts will also have the same intent.

**Property 10 (FCA is monotone).** $\forall K = \langle G, M, I \rangle$ and $K' = \langle G, M', I' \rangle$,

$$K \subseteq K' \Rightarrow \mathrm{FCA}(K) \preceq \mathrm{FCA}(K').$$

*Proof.* Any concept $c \in \mathrm{FCA}(K)$ characterises a set of objects $\mathrm{extent}(c)$ by the set of attributes $\mathrm{intent}(c)$ that these objects are the only ones to satisfy. Since both contexts have the same set of objects $G$, there are not more objects satisfying these in $K'$ and since $M \subseteq M'$ these attributes are still in $K'$, thus $c \in \mathrm{FCA}(K')$. Hence, it is always possible to define $h$ such as $h(c) = c$. Then $\mathrm{extent}(h(c)) = \mathrm{extent}(c)$ and $\mathrm{intent}(h(c)) \supseteq \mathrm{intent}(c)$. Moreover, if $c \le d$, then $h(c) \le h(d)$ because $\mathrm{extent}(c) \subseteq \mathrm{extent}(d)$ entails $\mathrm{extent}(h(c)) \subseteq \mathrm{extent}(h(d))$. Hence, $\mathrm{FCA}(K) \preceq \mathrm{FCA}(K')$ (Definition 4). $\square$

If $K \subseteq K'$, then each concept that can be built from $K$ can be built from $K'$. The additional attributes in $M'$ can only be used to separate further objects of existing concepts, introducing additional concepts. All concepts are preserved, possibly with a larger intent, which preserves the homomorphism.

Lattices may be combined by two operations defined from the corresponding operators in $\mathcal{K}_{K^0, R, \Omega}^N$: meet ($\wedge$) and join ($\vee$) on $\mathcal{L}_{K^0, R, \Omega}^N$:

**Definition 5 (Meet and join of lattices).** Given $L, L' \in \mathcal{L}_{\langle G, M^0, I^0 \rangle, R, \Omega}^N$,

$$L \vee L' = \mathrm{FCA}(\kappa(L) \vee \kappa(L')), \qquad (\mathrm{join})$$

$$L \wedge L' = \mathrm{FCA}(\kappa(L) \wedge \kappa(L')), \qquad (\mathrm{meet})$$

The set of lattices is also closed by meet and join:

**Property 11.** $\forall L, L' \in \mathcal{L}_{K^0, R, \Omega}^N, L \wedge L' \in \mathcal{L}_{K^0, R, \Omega}^N$ and $L \vee L' \in \mathcal{L}_{K^0, R, \Omega}^N$.

*Proof.* $\mathcal{L}_{K^0, R, \Omega}^N$ is closed by meet and join since $\mathcal{K}_{K^0, R, \Omega}^N$ is closed by meet and join (Property 3) and $\mathcal{L}_{K^0, R, \Omega}^N$ is the image of $\mathcal{K}_{K^0, R, \Omega}^N$ by FCA. $\square$

**Property 12.** $\langle \mathcal{L}_{K^0, R, \Omega}^N, \vee, \wedge \rangle$ is a complete lattice.

*Proof.* $\mathcal{L}_{K^0, R, \Omega}^N$ is closed by meet and join (Property 11). $\vee$ and $\wedge$ satisfy commutativity, associativity and the absorption laws directly from the union and intersection on contexts (Property 4), so this is a lattice. It is complete because isomorphic, through $\kappa$, to the complete lattices $\mathcal{K}_{K^0, R, \Omega}^N$ (Property 6) and the isomorphism preserves meet and join (consequence of Definition 5). $\square$

**Property 13.** $\forall L, L' \in \mathcal{L}_{K^0, R, \Omega}^N, L \preceq L'$ iff $L = L \wedge L'$.

*Proof.* First, for any $m \in M \cap M'$, the pairs of the incidence relations $I$ and $I'$ for $m$ are the same (Property 2).
<figure><img src="image_9.png" /><figcaption>Figure 9: Relations between F and E through the alternation of FCA and $\sigma_{\Omega}$ (from [Euzenat, 2021]).</figcaption></figure>

⇒ $L \preceq L'$ means that $\forall c \in L, \exists h(c) \in L'$ such that $extent(c) = extent(h(c))$ and $intent(c) \subseteq intent(h(c))$. Given that $M = \bigcup_{c \in L} intent(c) \setminus M^0$ and that $M' = \bigcup_{c \in L'} intent(c) \setminus M^0$, then $M \subseteq M'$ (and $I \subseteq I'$ due to Property 1). Thus, $L = L \wedge L'$ because the contexts on which they are built ($K^0_{+M}$ and $K^0_{+M \cap M'}$) are the same.

$\Leftarrow L = L \wedge L'$ means that $M \subseteq M'$ (and then $I \subseteq I'$ according to Property 1). Hence, $\forall c \in L$, the attributes satisfied by $extent(h(c))$ in $L'$ include those satisfied by $extent(c)$ in $L$ and others belonging to $M' \setminus M$. Thus, $extent(h(c))$ is the extent of a concept in $L'$ because it contains the only objects satisfying these attributes (it is closed). Consequently, $\exists h(c) \in L'$ such that $extent(c) = extent(h(c))$ and $intent(c) \subseteq intent(h(c))$ as $h(c)$ may satisfy additional attributes belonging to $M' \setminus M$, but it satisfies at least all those of $intent(c)$. So, $L \preceq L'$. □

### 4.2.2 The lattice expansion function E

As was done for contexts, it is possible to provide an expansion function for lattices. We define $E_{K^0, R, \Omega}$, the lattice expansion function attached to a relational context $\langle K^0, R \rangle$ and a set $\Omega$ of scaling operations.

**Definition 6** (Lattice expansion function [Euzenat, 2021]). Given a relational context $\langle K^0, R \rangle$ and a set $\Omega$ of relational scaling operations the function $E_{K^0, R, \Omega} : \mathcal{L}_{K^0, R, \Omega} \to \mathcal{L}_{K^0, R, \Omega}$ is defined by:

$$E_{K^0, R, \Omega}(L) = \mathrm{FCA}(\sigma_{\Omega}(\kappa(L), R, L)).$$

Here again, $K^0$ is only used to constrain the domain of the function, not its expression. From now on, we will abbreviate $\mathcal{L}_{K^0, R, \Omega}$ as $\mathcal{L}$ and $E_{K^0, R, \Omega}$ as $E$.

The definition of $E$ first applies scaling and then FCA, though $F$ does the opposite. In consequence, $E$ is the function corresponding to $F$ in the sense that $E \circ \mathrm{FCA} = \mathrm{FCA} \circ F$ (see Figure 9).

$E$ is an extensive and monotone internal operation for $\mathcal{L}$:

**Property 14** ($E$ is internal to $\mathcal{L}$). $\forall L \in \mathcal{L}, E(L) \in \mathcal{L}$.

*Proof.* Given $L \in \mathcal{L}$, $\kappa(L) \in \mathcal{K}$. $K = \sigma_{\Omega}(\kappa(L), R, L)$ adds attributes from $D_{\Omega, R, K^0}$ to $\kappa(L)$, hence $K \in \mathcal{K}$. Consequently, $E(L) = \mathrm{FCA}(K) \in \mathcal{L}$. □
**Property 15** (*E* is monotone and extensive). *The function E, attached to a relational context K<sup>0</sup>, R and a set Ω of scaling operations, satisfies ∀L, L' ∈ L<sub>K<sup>0</sup>,R,Ω</sub>:*

$$L \preceq L' \Rightarrow E(L) \preceq E(L'), \qquad (\text{monotony})$$

$$L \preceq E(L). \qquad (\text{extensivity})$$

*Proof.* (monotony) *L* ≤ *L'* entails that all concepts of *L* are found in *L'* with a larger intent. Consequently, *η*(*L*) ⊆ *η*(*L'* ) and *D*<sub>*Ω*,*R*,*L*</sub> ⊆ *D*<sub>*Ω*,*R*,*L'*</sub>. This entails that *σ*<sub>*Ω*</sub>(*K*, *R*, *L'* ) extends *K* with more attributes than *σ*<sub>*Ω*</sub>(*K*, *R*, *L*). Hence *E*(*L*) ≤ *E*(*L'* ) because *E*(*L*) is the application of FCA to the same context, to which has been added attributes.

(extensivity) For all *K* ∈ K, *L* = FCA(*K*), thus *K* ⊆ *σ*<sub>*Ω*</sub>(*K*, *R*, *L*). But *E*(*L*) = FCA(*σ*<sub>*Ω*</sub>(*K*, *R*, *L*)), so it will have at least all concepts generated by *K* (identified by extents) because *σ* only adds attributes, hence those allowing to generate a concept remain available and FCA can only generate more concepts. Thus, for each concept *c* ∈ *L* there exists *h*(*c*) ∈ *E*(*L*) (with *extent*(*c*) = *extent*(*h*(*c*)) and possibly with a larger intent, i.e. *intent*(*c*) ⊆ *intent*(*h*(*c*))), generated by the new scaled attributes. Hence, *L* ≤ *E*(*L*). □

Monotony is also called order-preservation. It corresponds to the non-(intent-)contracting concept property of [Rouane Hacène et al., 2013b].

### 4.2.3 Fixed points of E

Given *E*, it is possible to define its set of fixed points, i.e. the sets of concept lattices closed for *E*, as:

**Definition 7** (Fixed point). *A concept lattice* *L* ∈ L is a fixed point for a lattice expansion function *E*, if *E*(*L*) ≅ *L*. *We call* fp(*E*) *the set of fixed points for E*.

We can define:

$$\mathrm{lfp}(E) = \bigwedge_{L \in \mathrm{fp}(E)} L \quad \text{and} \quad \mathrm{gfp}(E) = \bigvee_{L \in \mathrm{fp}(E)} L.$$

Since L<sup>*N*</sup> is a complete lattice and *E* is order-preserving (or monotone) on L, then we can apply the Knaster-Tarski theorem. This warrants that there exists least and greatest fixed points of *E* in L.

## 4.3 Well-grounded and least fixed-point semantics

It is now possible to revise the description of Section 2.4.2 by considering that *F*<sup>*∞*</sup>(*K*<sup>0</sup>) = *F*<sup>*n*</sup>(*K*<sup>0</sup>) with *n* the first integer such that *F*<sup>*n*</sup>(*K*<sup>0</sup>) = *F*<sup>*n*+1</sup>(*K*<sup>0</sup>). **RCA** may thus be redefined as

$$\underline{\mathrm{RCA}}_{\Omega}(K^0, R) = \mathrm{FCA}(F^{\infty}(K^0)),$$
Alternatively, one may define $E^\infty(\text{FCA}(K^0)) = F^n(\text{FCA}(K^0))$ with $n$ the first integer $F^n(\text{FCA}(K^0)) = F^{n+1}(\text{FCA}(K^0))$. Then, $\underline{\text{RCA}}$ may be redefined as

$$ \underline{\text{RCA}}_{\Omega}(K^0, R) = E^{\infty}(\text{FCA}(K^0)). $$

It thus seems that $\underline{\text{RCA}}$ returns a fixed point of $F$ or $E$. Hence the question: which fixed point is returned by RCA's well-grounded semantics?

### 4.3.1 The RCA well-grounded semantics is the least fixed-point semantics

Since $K^0$ belongs to $\mathcal{K}$ and $\text{FCA}(K^0)$ belongs to $\mathcal{L}$, then RCA is indeed based on $E$ and $F$ fixed points. These are the least fixed points.

**Proposition 16** (The $\underline{\text{RCA}}$ algorithm on a RCA$^0$ context computes the least fixed point [Euzenat, 2021]). *Given $F$ the context expansion function and $E$ the lattice expansion function associated to $K^0$, $R$ and $\Omega$,*

$$ \underline{\text{RCA}}_{\Omega}(K^0, R) = \text{FCA}(\text{lfp}(F_{K^0, R, \Omega})), $$

and

$$ \underline{\text{RCA}}_{\Omega}(K^0, R) = \text{lfp}(E_{K^0, R, \Omega}). $$

*Proof.* Concerning the first equation, $\underline{\text{RCA}}_{\Omega}(K^0, R) = \text{FCA}(F^n(K^0))$ for some $n$ at which $F(F^n(K^0)) = F^n(K^0)$ [Rouane Hacène et al., 2013a]. Let $K^\infty = F^n(K^0)$, $K^\infty \in \text{fp}(F)$ (Definition 3). $\forall K \in \text{fp}(F)$, $K \in \mathcal{K}$, thus $K^0 \subseteq K$ because all the contexts in $\mathcal{K}$ contain $M^0$. By monotony (Property 8), $K^\infty = F^n(K^0) \subseteq F^n(K) = K$, because $K$ is a fixed point. Thus, $K^\infty$ is a fixed point more specific than all fixed points: it is the least fixed point.

Concerning the second equation, $\underline{\text{RCA}}_{\Omega}(K^0, R) = E^n(K^0)$ for some $n$ at which $E(E^n(K^0)) = E^n(K^0)$ [Rouane Hacène et al., 2013a]. $E(K^0) \in \mathcal{L}$, hence (by Property 14), $E^n(K^0) \in \mathcal{L}$. Moreover, $E(E^n(K^0)) = E^n(K^0)$ thus $E^n(K^0) \in \text{fp}(E)$. In addition, $\forall L \in \text{fp}(E)$, $E(K^0) \preceq L$ because the context from which $L$ is created contains at least all attributes of $K^0$. But if $E^t(K^0) \preceq L$, then $E^{t+1}(K^0) \preceq L$ because by monotony (Property 15), $E^{t+1}(K^0) = E(E^t(K^0)) \preceq E(L)$ and $E$ is idempotent on fixed points (by Definition 7). Thus, $\underline{\text{RCA}}_{\Omega}(K^0, R)$ is a fixed point more specific than all fixed points: it is the least fixed point. $\square$

### 4.3.2 Greatest fixed point

A natural question is how to obtain the greatest fixed point. In fact, under this approach this is (theoretically) surprisingly easy.

**Proposition 17** ([Euzenat, 2021]). $\text{gfp}(F_{K^0, R, \Omega}) = K^{\langle R, \eta(K^0) \rangle}_{+D_{\Omega, R, K^0}}(K^0)$.

*Proof.* This context is the greatest element of $\mathcal{K}$ as it contains all attributes of $M^0 \cup D_{\Omega, R, K^0}$. It is also a fixed point because $F$ is extensive (Property 8) and internal (Property 7). $\square$
The lattice corresponding to the greatest fixed point will be $L = \text{FCA}(\text{gfp}(F_{K^0, R, \Omega}))$.

This result is easy but very uncomfortable. The obtained lattice may contain many non-supported attributes as shown in Example 9. Indeed, $∃r.c$ is well-defined by the incidence relation, but it is of no use to RCA if $c$ does not belong to $L$.

**Example 9** (Greatest fixed point of $F$ in RCA$^0$). In the example of Section 3.2, the attribute $∃p.A$ belongs to $D_{Ω,R,K^0}$ though $A$ does not belong to the maximal lattice $L_0^*$, because it is not a closed concept for FCA. The fact that both a and b satisfy this attribute makes that it will find its place in the intent of AB. If one considers the lattice in isolation, this is perfectly valid because the scaled context is well-defined: $∃p.A$ is just an attribute among others satisfied by a and b. However, if the lattice is transformed in a description logic TBox, this is not correct to refer to an undefined class (here $A$).

On the contrary, there may be cases in which the greatest fixed point is the powerset lattice, i.e. in which all attributes are supported, and the least fixed point of $F$ is directly $\text{FCA}(K^0)$.

This problem is even more embarrassing if one wants to enumerate all acceptable solutions: many of the fixed points of $E$ or $F$ will feature such non-supported attributes.

# 5 Self-supported fixed points in RCA$^0$

In order to define acceptable solutions for RCA, we introduce the notion of self-support. It specifies that a concept lattice is self-supported if the intents of its concepts only refer to concepts in this lattice. We describe a function $Q$ which suppresses non-supported attributes and whose closure yields self-supported lattices. We then identify the acceptable solutions of RCA$^0$ as self-supported fixed points.

## 5.1 Self-supported lattices

Since both $F$ and $E$ are extensive functions, it is possible, starting from anywhere in $\mathcal{K}$ or $\mathcal{L}$, to consider attributes that do not refer to concepts and these attributes will be preserved. As a consequence, there may exist fixed points with these unwanted attributes and they are also found in the greatest fixed point. This is not the result that we expect: we need the results to be self-supported.

One may consider identifying such attributes from the greatest fixed point and forbidding them. However, these meaningless attributes are contextual: a supported attribute in the greatest fixed point, may not be supported in a smaller lattice. This is a difficulty for enumerating these fixed points.

**Example 10** (Non self-supported lattice in RCA$^0$). Figure 10 (p.28) shows a context $K_0^#$ and the associated concept lattice $L_0^#$ that could be a solution for the example of Section 3.2 as it belongs to $\mathcal{L}_{\{∃\}, \{r\}, K_0^0}$. However, the lattice is not self-supported because the concept AB uses the attribute $∃r.B$ in $K_0^#$ which refers to a concept (B) not present in $L_0^#$.
<table><thead><tr><th>K<sub>0</sub><sup>#</sup></th><th>∃r.B</th><th>∃r.C</th><th>∃r.AB</th><th>∃r.ABD</th></tr></thead><tbody><tr><th>a</th><td>×</td><td>×</td><td>×</td><td>×</td></tr><tr><th>b</th><td>×</td><td>×</td><td>×</td><td>×</td></tr><tr><th>c</th><td></td><td></td><td></td><td>×</td></tr><tr><th>d</th><td>×</td><td></td><td></td><td></td></tr></tbody></table>

<figure><img src="image_10.png" /><figcaption>Figure 10: Non self-supported lattice $L_0^#$.</figcaption></figure>

Instead, we consider only self-supported lattices, i.e. lattices whose intents only refer to their own concepts.

**Definition 8** (Self-supported lattices [Euzenat, 2021]). A concept lattice L is self-supported if $\forall c \in L, \text{intent}(c) \subseteq M^0 \cup D_{\Omega,R,L}$.

The definition of self-supported lattices does not provide a direct way to transform a non self-supported lattice into a self-supported one. Simply suppressing non-supported attributes from intents could result in non concepts (with non-closed extents). A possible way to solve this problem consists of extracting only the attributes currently in the lattice and to apply FCA to the resulting context.

For that purpose, we introduce a filtering (or purging) function which suppresses from the induced context ($\kappa(L)$) those attributes non supported by the lattice:

**Definition 9** (Purging function [Euzenat, 2021]). The function $\pi_{K^0,R,\Omega}: \mathscr{L}^N \to \mathscr{H}^N$ returns the context reduced of those attributes not present in a lattice:

$$ \pi_{K^0,R,\Omega}(L) = K_{-(D_{\Omega,R,K^0} \setminus D_{\Omega,R,L})}^{\langle R,N \rangle}(\kappa(L)). $$

When unambiguous, we refer to $\pi_{K^0,R,\Omega}$ as $\pi$. The purging function and the following ones are defined over any $N$, as they only restrict the sets of possible contexts and do not expand them.

Like the scaling function, the purging function is only one step: it suppresses currently unsupported attributes, but this may lead to less concepts to be generated by FCA, and thus to other non-supported attributes. $\pi$ and $\sigma$ are not inverse functions: in particular, $\sigma$ greatly depends on $\Omega$ and $R$ to decide which attributes to scale, through $\pi$ simply suppresses attributes non supported by the lattice(s), independently from $\Omega$, which however determines the attribute language.

**Property 18.** *L is self-supported if and only if FCA($\pi(L)$) = L.*
Proof. (⇒) $L$ is self-supported means that $\forall c \in L$, intent(c) $\subseteq M^0 \cup D_{\Omega,R,L}$ (Definition 8) which means that, in $\kappa(L)$, all attributes belong to $M^0 \cup D_{\Omega,R,L}$. This leads to $\pi(L) = \kappa(L)$. However, by Property 9, $L = \text{FCA}(\kappa(L))$, thus $L = \text{FCA}(\pi(L))$. (⇔) $L = \text{FCA}(\pi(L))$ if and only if $\pi(L) = \kappa(L)$ (Property 9). This means that the attributes of $\kappa(L)$, and thus of $L$, belong to $M^0 \cup D_{\Omega,R,L}$. This is equivalent to being self-supported. $\square$

## 5.2 Contraction functions $Q$ and $P$

Instead of dealing with expansion functions, it is possible to consider contraction functions for contexts or lattices based on $\pi$.

**Definition 10 (Lattice contraction function).** The lattice contraction function $Q: \mathcal{L}^N \to \mathcal{L}^N$ is defined by

$$Q(L) = \text{FCA}(\pi_{K^0, R, \Omega}(L)).$$

As previously, we will abbreviate $Q_{K^0, R, \Omega}$ as $Q$. $Q$ is internal to the space of lattices.

**Property 19** ($Q$ is internal to $\mathcal{L}$). $\forall L \in \mathcal{L}^N$, $Q(L) \in \mathcal{L}^N$.

Proof. $Q(L) = \text{FCA}(\pi(L))$. $\pi(L)$ retracts attributes from $\kappa(L)$. By definition, $\kappa(L) \in \mathcal{K}^N$, hence $\pi(L) \in \mathcal{K}^N$. $\pi$ never suppresses attributes from $M^0$ which are all supported (they do not depend on the existence of specific concepts in $L$). Consequently, $Q(L) = \text{FCA}(\pi(L)) \in \mathcal{L}^N$. $\square$

Contrary to $E$, $Q$ is anti-extensive and monotone:

**Property 20** ($Q$ is anti-extensive and monotone [Euzenat, 2021]). The function $Q$ satisfies:

$$ \begin{gathered} Q(L) \preceq L, \qquad (\text{anti-extensivity}) \\ L \preceq L' \Rightarrow Q(L) \preceq Q(L'). \qquad (\text{monotony}) \end{gathered} $$

Proof. (anti-extensivity) $\pi(L) \subseteq \kappa(L)$ because $\pi$ simply suppresses attributes from $\kappa(L)$. Hence, $\text{FCA}(\pi(L)) \preceq \text{FCA}(\kappa(L))$ because the latter contains all concepts of the former (identified by extent) possibly featuring the removed attributes (Property 10). Moreover, $\text{FCA}(\kappa(L)) = L$ by definition, thus $Q(L) = \text{FCA}(\pi(L)) \preceq \text{FCA}(\kappa(L)) = L$. (monotony) If $L \preceq L'$, then $\kappa(L) \subseteq \kappa(L')$, otherwise FCA would not generate a smaller lattice. In addition, $L \preceq L'$ entails $D_{\Omega,R,L} \subseteq D_{\Omega,R,L'}$ which entails $D_{\Omega,R,K^0} \setminus D_{\Omega,R,L} \supseteq D_{\Omega,R,K^0} \setminus D_{\Omega,R,L'}$, which finally together leads to $M \setminus (D_{\Omega,R,K^0} \setminus D_{\Omega,R,L}) \subseteq M' \setminus (D_{\Omega,R,K^0} \setminus D_{\Omega,R,L'})$. Then, $\pi(L) \subseteq \pi(L')$ because a smaller context supported by a smaller lattice cannot result in a larger context. Hence, $Q(L) = \text{FCA}(\pi(L)) \preceq \text{FCA}(\pi(L')) = Q(L')$ by monotony of FCA (Property 10). $\square$

Similarly, on the context side, the $P$ context contraction function is introduced:

**Definition 11 (Context contraction function).** The context contraction function $P: \mathcal{K}^N \to \mathcal{K}^N$ is defined by

$$P(K) = \pi_{K^0, R, \Omega}(\text{FCA}(K)).$$
<figure><img src="image_11.png" /><figcaption>Figure 11: Relations between P and Q through the alternation of FCA and π (from [Euzenat, 2021]).</figcaption></figure>

Figure 11 displays the relations between these two functions.

P is internal to $\mathcal{K}^N$:

**Property 21** (*P* is internal to *K*). $\forall K \in \mathcal{K}^N, P(K) \in \mathcal{K}^N$.

*Proof.* $P(K) = \pi(\mathrm{FCA}(K))$ (Definition 11). As discussed before (proof of Property 19), $\pi(\mathrm{FCA}(K))$ retracts some attributes from $\kappa(\mathrm{FCA}(K))$, preserving those of $M^0$. By definition, $\kappa(\mathrm{FCA}(K)) \in \mathcal{K}^N$, hence $P(K) = \pi(\mathrm{FCA}(K)) \in \mathcal{K}^N$. $\square$

Contrary to *F* and according to *Q*, *P* is anti-extensive and monotone:

**Property 22** (*P* is anti-extensive and monotone). The function *P* satisfies:

$$P(K) \subseteq K, \qquad (\text{anti-extensivity})$$
$$K \subseteq K' \Rightarrow P(K) \subseteq P(K'). \qquad (\text{monotony})$$

*Proof.* (anti-extensivity) If $P(K) \not\subseteq K$, this means that there exists a non empty set of attributes $M'$ disjoint from $M$ present in $P(K)$. Such attributes cannot have been brought by $\pi$ since it only suppresses attributes. They should come from either FCA or $\kappa$. However, FCA does only include in intents attributes from $M$, and $\kappa$ does only extracts attributes from the intents. Hence, $P(K) \subseteq K$.

(monotony) If $K \subseteq K'$, then $\mathrm{FCA}(K) \subseteq \mathrm{FCA}(K')$ by monotony of FCA (Property 10). This means that there exist a lattice homomorphism between $\mathrm{FCA}(K)$ and $\mathrm{FCA}(K')$ for which the intent of all concepts of $\mathrm{FCA}(K)$ is found in that of those of $\mathrm{FCA}(K')$; moreover, all concepts of $\mathrm{FCA}(K)$, as identified by their extent, are found in $\mathrm{FCA}(K')$ (Definition 4). Hence, necessarily $\kappa(\mathrm{FCA}(K)) \subseteq \kappa(\mathrm{FCA}(K'))$ and the supporting concepts in $\mathrm{FCA}(K)$ are still present in $\mathrm{FCA}(K')$, so $P(K) = \pi(\mathrm{FCA}(K)) \subseteq \pi(\mathrm{FCA}(K')) = P(K')$. $\square$

Like *E* and *F*, *Q* and *P* are not closure operations as they are not idempotent. However, with the same arguments as [Rouane Hacène et al., 2013a], and in particular the finiteness of contexts (see Section 2.4.3), it can be argued that the repeated application of *Q* converges to a self-supported concept lattice.

**Property 23** (Stability of *Q* [Euzenat, 2021]). $\forall L \in \mathcal{L}^N, \exists n; Q^n(L) = Q^{n+1}(L)$.
*Proof.* First, $L$ is a finite concept lattice. Moreover, $Q(L) \preceq L$, hence it not possible to build an infinite chain of non-converging application of $Q$ since at each iteration, either $\pi$ suppresses no attribute (and then a fixed point has been reached), or it suppresses at least one attribute and then a strictly smaller context is reached. Since the number of scalable attributes is finite and attributes of $M^0$ are not purged, then the process will stop after a finite number of applications of $Q$. $\square$

By convention, we note $Q^\infty$ the closure operation$^7$ associated with $Q$ and $\text{fp}(Q)$, the set of fixed points of $Q$.

## 5.3 Fixed points of $Q$

Like with $E$, it is possible to apply the Knaster-Tarski theorem to show that $\langle \text{fp}(Q), \preceq \rangle$ is a complete lattice.

The fixed points of $Q$ are exactly those self-supported lattices in $\mathcal{L}$:

**Property 24.** For any $L \in \mathcal{L}^N$, $L$ is self-supported iff $L \in \text{fp}(Q)$.

*Proof.* $L \in \text{fp}(Q)$ means that $L = \text{FCA}(\pi(L)) = Q(L)$. But, by Property 18, this is equivalent to being self-supported. $\square$

To complete the description of $Q$, it is possible to establish that its least fixed point is $\text{FCA}(K^0)$.

**Property 25.** $\text{lfp}(Q) = \text{FCA}(K^0)$.

*Proof.* $\kappa(\text{FCA}(K^0)) = K^0$ hence $\pi(\text{FCA}(K^0)) = K^0$ because, it is not possible to suppress attributes from $K^0$ which, being a non-scaled context, does not refer to any concept (and in $\text{RCA}^0$ this set of attributes is reduced to $\emptyset$). Thus, $Q(\text{FCA}(K^0)) = \text{FCA}(\pi(\text{FCA}(K^0))) = \text{FCA}(K^0)$. Moreover, $\forall L \in \mathcal{L}^N, \text{FCA}(K^0) \preceq L$. Hence, $\text{FCA}(K^0)$ is a fixed point of $Q$ and all other fixed points are greater. $\square$

## 5.4 Relations between $E$ and $Q$

We end up with two operations, $E$ and $Q$, the former extensive and the latter anti-extensive. If we consider concept lattices from the standpoint of the extents, $Q$ decreases the set of concepts of a lattice and $E$ increases them.

An interesting property of the functions $E$ and $Q$ is that they preserve each other stability: $E$ has the advantage of preserving self-supportivity (Property 26 replaces Proposition 3 of [Euzenat, 2021] due to Property 24):

**Property 26** ($E$ is internal to $\text{fp}(Q)$ [Euzenat, 2021, Prop.3]). $\forall L \in \text{fp}(Q), E(L) \in \text{fp}(Q)$.

<footnote>$^7$Which could be named interior operation as well.</footnote>
<figure><img src="image_12.png" /><figcaption>Figure 12: The $\mathcal{L}$ (resp. $\mathcal{K}$) lattice and effects of $E$ and $Q$ (resp. $F$ and $P$) for characterising $\mathrm{fp}(E)$ and $\mathrm{fp}(Q)$ (resp. $\mathrm{fp}(F)$ and $\mathrm{fp}(P)$) (from [Euzenat, 2021]).</figcaption></figure>

*Proof.* If $L \in \mathrm{fp}(Q)$, all attributes in intents of $L$ are supported by concepts in $L$ (Property 24). $L \preceq E(L)$, so these concepts are still in $E(L)$. Moreover, $E = \sigma_\Omega \circ \mathrm{FCA}$ and $\sigma_\Omega$ first adds to $\kappa(L)$ attributes which are supported by $L$. Hence, the attributes in $\kappa(L)$ and those scaled by $\sigma_\Omega$ are still supported by $E(L). $□

**Property 27** ($Q$ is internal to $\mathrm{fp}(E)$). $\forall L \in \mathrm{fp}(E), Q(L) \in \mathrm{fp}(E)$.

*Proof.* If $L \in \mathrm{fp}(E)$, this means that $E(L) = L$ and, in particular, that $\sigma_\Omega$ does not scale new relational attributes based on the concepts in $L$. $Q(L) \preceq L$, so that $Q(L)$ does not contain more concepts than $L$. $Q(L)$ having not more concepts than $L$, $\sigma_\Omega$ cannot scale new attributes $(\sigma_\Omega(Q(L)) \subseteq \sigma_\Omega(L) = \emptyset)$. Hence, $Q(L) \in \mathrm{fp}(E)$. $\square$

In addition, the closure operations associated with the two functions preserve the extrema of each other.

**Property 28.** $Q^\infty(\mathrm{gfp}(E)) = \mathrm{gfp}(Q)$ and $E^\infty(\mathrm{lfp}(Q)) = \mathrm{lfp}(E)$.

*Proof.* $\forall L \in \mathcal{L}, L \preceq \mathrm{gfp}(E)$ (from Proposition 17) and $Q$ and thus $Q^\infty$ is order preserving (Property 20), hence $Q^\infty(L) \preceq Q^\infty(\mathrm{gfp}(E))$. Moreover, $Q^\infty(\mathrm{gfp}(E)) \in \mathrm{fp}(Q)$, thus $Q^\infty(\mathrm{gfp}(E)) = \mathrm{gfp}(Q)$.

Similarly, $\forall L \in \mathcal{L}$, $\mathrm{lfp}(Q) \preceq L$ (Property 25) and $E$ and thus $E^\infty$ is order preserving (Property 15), hence $E^\infty(\mathrm{lfp}(Q)) \preceq E^\infty(L)$. Moreover, $E^\infty(\mathrm{lfp}(Q)) \in \mathrm{fp}(E)$, thus $E^\infty(\mathrm{lfp}(Q)) = \mathrm{lfp}(E)$. $\square$

The acceptable solutions for RCA$^0$ are the self-supported fixed points of $E$, or said otherwise, the elements of $\mathrm{fp}(E) \cap \mathrm{fp}(Q)$. Such lattices are both saturated and self-supported well-formed elements of $\mathcal{L}$. Moreover, by construction of $\mathcal{K}$ and $\mathcal{L}$, they cover $K^0$, i.e. they contain all attributes in $M^0$.
Proposition 29 establishes that the acceptable solutions are circumscribed to the interval sublattice [lfp(E) gfp(Q)] (see also Figure 12).

**Proposition 29** ([Euzenat, 2021]). lfp(E) and gfp(Q) are the infimun and the supremum of fp(E) ∩ fp(Q) for $\le$.

*Proof.* By definition, $\forall L \in fp(E) \cap fp(Q)$, lfp(E) $\le$ L $\le$ gfp(Q). Moreover, $Q^\infty(lfp(E)) \in fp(E)$ (Property 27) and $Q^\infty(lfp(E)) \le$ lfp(E) (Property 20), but lfp(E) is the least fixed point for E, so $Q^\infty(lfp(E)) = lfp(E)$. Since, by definition, $Q^\infty(lfp(E)) \in fp(Q)$, then lfp(E) $\in$ fp(Q). A similar reasoning applies to E and gfp(Q). □

Thus, the interval sublattice [lfp(E) gfp(Q)] is the smallest interval covering fp(E) ∩ fp(Q). However, fp(E) ∩ fp(Q) does not cover [lfp(E) gfp(Q)] as shown by Example 11.

**Example 11** (Non fixed points of [lfp(E) gfp(Q)] in RCA⁰). The lattice $L_0^\#$ of Figure 10 (p. 41) can be checked to belong to the interval [lfp(E) gfp(Q)] = [$L_0^1$ $L_0^*$], but it does not belong to fp(E) ∩ fp(Q): it is neither a fixed point for Q (not self-supported) because, as Example 10 shows, B does not belong to $L_0^\#$, nor for E (not saturated) because $\exists r.ABC$ does not belong to $K_0^\#$.

The definitions and results of the two past sections have been restricted to RCA⁰ for the sake of clarity. They will now be generalised.

# 6 Unified view of the RCA⁰ space

Although $\mathcal{H}^N$ and $\mathcal{L}^N$ have been presented independently, it is useful to consider the two sets together as, in RCA, lattices in $\mathcal{L}^N$ are an intermediate result of the process which is used for computing the next context. Instead of dealing with two interrelated spaces independently, we tightly connect them. Doing so, we will consider objects which are pairs of contexts and associated concept lattices through FCA. They are called context-lattice pairs.

## 6.1 The lattice $\mathcal{T}$ of context-lattice pairs

From any context in $\mathcal{K}$, it is possible to generate a context-lattice pair using FCA. The T constructor does this.

**Definition 12** (T constructor). Given a context $K \in \mathcal{K}^N$, T : $\mathcal{K}^N \to \mathcal{K}^N \times \mathcal{L}^N$ generates a context-lattice pair, such that:

$$T(K) = \langle K, \text{FCA}(K) \rangle.$$

We consider the set $\mathcal{T}_{K^0, R, \Omega}^N$ of pairs in $\mathcal{K}_{K^0, R, \Omega}^N \times \mathcal{L}_{K^0, R, \Omega}^N$ such that:

$$\mathcal{T}_{K^0, R, \Omega}^N = \{ \langle K, L \rangle \in \mathcal{K}_{K^0, R, \Omega}^N \times \mathcal{L}_{K^0, R, \Omega}^N | L = \text{FCA}(K) \}.$$

Inria
This set is well defined because $\mathcal{H}_{K^0, R, \Omega}^N$ has already been defined and $\mathcal{L}_{K^0, R, \Omega}^N$ are precisely those lattices obtained by FCA from an element of $\mathcal{H}_{K^0, R, \Omega}^N$.

Alternatively, using Property 9, it can be defined from $\kappa$:

$$ \mathcal{T}_{K^0, R, \Omega}^N = \{ \langle K, L \rangle \in \mathcal{H}_{K^0, R, \Omega}^N \times \mathcal{L}_{K^0, R, \Omega}^N | K = \kappa(L) \}. $$

As before, we use $\mathcal{T}_{K^0, R, \Omega} = \mathcal{T}_{K^0, R, \Omega}^{\eta(K^0)}$ and, for any $\langle K, L \rangle \in \mathcal{T}_{K^0, R, \Omega}^N$ we note:

$$ k(\langle K, L \rangle) = K, $$

$$ l(\langle K, L \rangle) = L. $$

It is possible to define the meet and join:

**Definition 13** (Meet and join of context-lattice pairs). Given $T, T' \in \mathcal{T}_{K^0, R, \Omega}^N$ $T \vee T'$ and $T \wedge T'$ are defined as:

$$ T \vee T' = T(k(T) \vee k(T')), \qquad (\text{join}) $$

$$ T \wedge T' = T(k(T) \wedge k(T')), \qquad (\text{meet}) $$

As this definition makes clear, the operations of $\mathcal{T}^N$ only depend on the context part. But the usual relations with the meet and join on contexts and lattices are preserved:

**Property 30.**

$$ T \vee T' = \langle k(T) \vee k(T'), l(T) \vee l(T') \rangle, $$

$$ T \wedge T' = \langle k(T) \wedge k(T'), l(T) \wedge l(T') \rangle. $$

*Proof.* This is a simple consequence on the definition of conjunctions and disjunction on context-lattice pairs (Definition 12) and lattices (Definition 5) as:

$$ L \vee L' = \text{FCA}(K \vee K'), \qquad (\text{join}) $$

$$ L \wedge L' = \text{FCA}(K \wedge K'). \qquad (\text{meet}) $$

□

The set of context-lattice pairs is once again closed by meet and join:

**Property 31.** $\forall T, T' \in \mathcal{T}_{K^0, R, \Omega}^N$, $T \wedge T' \in \mathcal{T}_{K^0, R, \Omega}^N$ and $T \vee T' \in \mathcal{T}_{K^0, R, \Omega}^N$.

*Proof.* $\mathcal{T}_{K^0, R, \Omega}^N$ is closed by meet and join because it is based on $T$ (Definition 13), $T$ builds a context-lattice pair in $\mathcal{T}_{K^0, R, \Omega}^N$ from contexts in $\mathcal{H}_{K^0, R, \Omega}^N$ (Definition 12), and $\mathcal{H}_{K^0, R, \Omega}^N$ itself is closed by meet and join (Property 3). □

**Property 32** (Commutativity, associativity and absorption of $\vee$ and $\wedge$ on $\mathcal{T}$). For all $T, T', T'' \in \mathcal{T}$,

$$ T \vee T' = T' \vee T \qquad \text{and} \qquad T \wedge T' = T' \wedge T, \qquad (\text{commutativity}) $$

$$ (T \vee T') \vee T'' = T \vee (T' \vee T'') \qquad \text{and} \qquad (T \wedge T') \wedge T'' = T \wedge (T' \wedge T''), \qquad (\text{associativity}) $$

$$ T \wedge (T \vee T') = T \qquad \text{and} \qquad T \vee (T \wedge T') = T. \qquad (\text{absorption}) $$
*Proof.* Proofs are given for $\land$, those for $\lor$ follow the exact same pattern.

<table><tr><td>T & T' = T(k(T) & k(T'))</td><td>Definition 13</td></tr><tr><td>= T(k(T') & k(T))</td><td>Property 4</td></tr><tr><td>= T' & T</td><td>Definition 13</td></tr><tr><td>(T & T') & T'' = T(k(T) & k(T')) & T''</td><td>Definition 13</td></tr><tr><td>= T(k(T(k(T) & k(T'))) & k(T''))</td><td>Definition 13</td></tr><tr><td>= T((k(T) & k(T')) & k(T''))</td><td>Definition 12</td></tr><tr><td>= T(k(T) & (k(T') & k(T'')))</td><td>Property 4</td></tr><tr><td>= T(k(T) & k(T((k(T') & k(T''))))</td><td>Definition 12</td></tr><tr><td>= T & T((k(T') & k(T'')))</td><td>Definition 13</td></tr><tr><td>= T & (T' & T'')</td><td>Definition 13</td></tr><tr><td>T & (T & T') = T & T(k(T) & k(T'))</td><td>Definition 13</td></tr><tr><td>= T(k(T) & k(T(k(T) & k(T'))))</td><td>Definition 13</td></tr><tr><td>= T(k(T) & (k(T) & k(T')))</td><td>Definition 12</td></tr><tr><td>= T(k(T))</td><td>Property 4</td></tr><tr><td>= T</td><td>Definition 12.</td></tr></table>

We also define the order between two context-lattice pairs by combining the orders on contexts and lattices:

**Definition 14 (Order).** Given $T, T' \in \mathcal{T}_{K^0, R, \Omega}^N$,

$$T \preceq T' \text{ if } k(T) \subseteq k(T') \text{ and } l(T) \preceq l(T').$$

Figure 13 presents the relations between $\mathcal{K}^N$, $\mathcal{L}^N$ and $\mathcal{T}^N$ and their respective orders. Since FCA is monotone (Property 10), $T \preceq T'$ iff $k(T) \preceq k(T')$. Like before, we note $T \simeq T'$ if $T \preceq T'$ and $T' \preceq T$, and again $\simeq$ is $=$.

This can be applied to the T constructor.

**Property 33.** $\forall K, K' \in \mathcal{K}_{K^0, R, \Omega}^N$, if $K \subseteq K'$ then $T(K) \preceq T(K')$.

*Proof.* (⇒) This is due to monotony of FCA (Property 10). $k(T(K)) = K \subseteq K' = k(T(K'))$ means that $l(T(K)) = \text{FCA}(K) \preceq \text{FCA}(K') = l(T(K'))$. Thus, $T(K) \preceq T(K')$. ( ⇐ ) $T(K) \preceq T(K')$ entails, by Definition 14, that $K \subseteq K'$. □

This has the consequence that $T = T'$ if and only if $k(T) = k(T')$.

This definition complies with that of meet and join.

**Property 34.** $\forall T, T' \in \mathcal{T}_{K^0, R, \Omega}^N, T \preceq T'$ iff $T = T \land T'$.

*Proof.* By Property 5, we have that $k(T) \preceq k(T')$ iff $k(T) = k(T) \land k(T')$ and, by Property 13, that $l(T) \preceq l(T')$ iff $l(T) = l(T) \land l(T')$, consequently $T \preceq T'$ iff $T = T \land T'$ by Property 30. □
<figure><img src="image_13.png" /><figcaption>Figure 13: Relations between $\mathcal{T}$, $\mathcal{K}$ and $\mathcal{L}$.</figcaption></figure>

This makes $\mathcal{T}_{K^0, R, \Omega}^N$ a complete lattice (Property 35).

**Property 35.** $\langle \mathcal{T}_{K^0, R, \Omega}^N, \vee, \wedge \rangle$ is a complete lattice.

*Proof.* $\mathcal{T}_{K^0, R, \Omega}^N$ is closed by meet and join (Property 31). $\vee$ and $\wedge$ satisfy commutativity, associativity and the absorption laws (Property 32), so this is a lattice. It is complete because isomorphic, through $k(\cdot)$ or $l(\cdot)$, to the complete lattices $\mathcal{K}_{K^0, R, \Omega}^N$ (Property 6) or $\mathcal{L}_{K^0, R, \Omega}^N$ (Property 12) and the isomorphisms preserve meet and join (Property 30). $\square$

## 6.2 The expansion function EF

We reformulate RCA as based on a main single function, $EF_{K^0, R, \Omega}$, the expansion function attached to a relational context $\langle K^0, R \rangle$ and a set $\Omega$ of scaling operations.

**Definition 15 (Expansion function).** Given a relational context $\langle K^0, R \rangle$ and a set $\Omega$ of relational scaling operations, the function $EF_{K^0, R, \Omega} : \mathcal{T}_{K^0, R, \Omega} \to \mathcal{T}_{K^0, R, \Omega}$ is defined by:

$$EF_{K^0, R, \Omega}(T) = T(\sigma_{\Omega}(k(T), R, l(T))).$$

This function is an extension of the previous $E$ and $F$:

**Property 36 (EF extends F and E).** $EF(T) = \langle F(k(T)), E(l(T)) \rangle$.

*Proof.* This is the consequence of $F(K) = \sigma_{\Omega}(K, R, FCA(K))$ (Definition 2) and $l(T) = FCA(k(T))$. On the one hand, $F(k(T)) = \sigma_{\Omega}(k(T), R, l(T))$. On the other hand, $E(L) = FCA(\sigma_{\Omega}(\kappa(L), R, L))$ (Definition 6) and $\kappa(l(T)) = k(T)$ (Property 9). Hence, $EF(T) = \langle \sigma_{\Omega}(k(T), R, l(T)), FCA(\sigma_{\Omega}(k(T), R, l(T))) \rangle = \langle F(k(T)), E(l(T)) \rangle$. $\square$
As previously, we will abbreviate $\mathcal{T}_{K^0, R, \Omega}$ as $\mathcal{T}$ and $EF_{K^0, R, \Omega}$ as $EF$. $EF$ is an extensive and monotone internal operation for $\mathcal{T}$:

**Property 37 (EF is internal to $\mathcal{T}$).** $\forall T \in \mathcal{T}$, $EF(T) \in \mathcal{T}$.

*Proof.* $EF(T) \in \mathcal{H}_{K^0, R, \Omega} \times \mathcal{L}_{K^0, R, \Omega}$ because $T \in \mathcal{H}_{K^0, R, \Omega} \times \mathcal{L}_{K^0, R, \Omega}$ and $E$ and $F$ are internal to $\mathcal{H}_{K^0, R, \Omega}$ (Property 7) and $\mathcal{L}_{K^0, R, \Omega}$ (Property 14), respectively. Moreover, $EF(T) = T(F(k(T))) = \langle F(k(T)), \text{FCA}(F(k(T))) \rangle$ (Definition 15 and Property 36), hence $l(EF(T)) = \text{FCA}(k(EF(T)))$. $\square$

**Property 38 (EF is extensive and monotone).** The function $EF$, attached to a relational context and a set of scaling operations, satisfies:

$$T \preceq EF(T), \qquad (\text{extensivity})$$
$$T \preceq T' \Rightarrow EF(T) \preceq EF(T'). \qquad (\text{monotony})$$

*Proof.* extensivity holds because $T \preceq EF(T)$ if and only if $k(T) \preceq k(EF(T))$. However, $k(EF(T)) = F(k(T))$ (Property 36) and $K \preceq F(K)$ (Property 8). monotony relies on the monotony of $F$ (Property 8) and $E$ (Property 15): $T \preceq T'$ if and only if $k(T) \subseteq k'(T)$ and $l(T) \preceq l'(T)$, but this entail $F(k(T)) \preceq F(k'(T))$ (Property 8) and $E(l(T)) \subseteq E(l'(T))$ (Property 15), and so $EF(T) \preceq EF(T')$. $\square$

## 6.3 The contraction function PQ

It is also possible to consider a single contraction function, $PQ_{K^0, R, \Omega}$, attached to a relational context $\langle K^0, R \rangle$ and a set $\Omega$ of scaling operations.

The context-lattice pairs $\langle K, L \rangle$ may contain many unsupported attributes. Unsupported attributes are those which refer to classes non existing in the lattice. Indeed, $\exists r.c$ may be part of the attributes of $K$ well-defined by the incidence relation, but $c$ does not belong to $L$.

$PQ$ may be defined from $\pi$ (§5) and $T$.

**Definition 16 (Contraction function).** Given a relational context $\langle K^0, R \rangle$ and a set $\Omega$ of relational scaling operations, the function $PQ_{K^0, R, \Omega} : \mathcal{T}_{K^0, R, \Omega}^N \to \mathcal{T}_{K^0, R, \Omega}^N$ is defined by:

$$PQ_{K^0, R, \Omega}(T) = T(\pi_{K^0, R, \Omega}(l(T))).$$

As previously, we will abbreviate $PQ_{K^0, R, \Omega}$ as $PQ$. This function is also an extension of the previous $Q$ and $P$:

**Property 39 (PQ extends $P$ and $Q$).** $PQ(T) = \langle P(k(T)), Q(l(T)) \rangle$.

*Proof.* $\forall T \in \mathcal{T}^N$, $l(T) = \text{FCA}(k(T))$, hence $\pi(l(T)) = \pi(\text{FCA}(k(T)))$ and $P(K) = \pi(\text{FCA}(K))$ (Definition 11), thus $\pi(l(T)) = P(k(T))$. Moreover, $Q(L) = \text{FCA}(\pi(L))$ (Definition 10), thus $\text{FCA}(\pi(l(T))) = Q(l(T))$. So, $T(\pi(l(T))) = \langle \pi(l(T)), \text{FCA}(\pi(l(T))) \rangle = \langle P(k(T)), Q(l(T)) \rangle$. $\square$
<figure><img src="image_14.png" /><figcaption>Figure 14: Relations between EF, PQ, E, F, P and Q.</figcaption></figure>

PQ is an anti-extensive and monotone internal operation for $\mathcal{T}^N$:

**Property 40** (PQ is internal to $\mathcal{T}^N$). $\forall T \in \mathcal{T}^N$, $PQ(T) \in \mathcal{T}^N$.

*Proof.* This follows from P and Q being internal to $\mathcal{H}_{K^0, R, \Omega}^N$ and $\mathcal{L}_{K^0, R, \Omega}^N$, respectively (Property 21 and 19) and Property 39. $\square$

**Property 41** (PQ is anti-extensive and monotone). The function PQ, attached to a relational context and a set of scaling operations, satisfies:

$$PQ(T) \preceq T, \qquad (\text{anti-extensivity})$$

$$T \preceq T' \Rightarrow PQ(T) \preceq PQ(T'). \qquad (\text{monotony})$$

*Proof.* anti-extensivity holds because $PQ(T) \preceq T$ if and only if $P(k(T)) = k(PQ(T)) \preceq k(T)$ (Property 39) and $P(K) \preceq K$ (Property 22). monotony relies on the monotony of P and Q: if $T \preceq T'$, then $k(T) \subseteq k(T')$ and $l(T) \preceq l(T')$, hence $P(k(T)) \subseteq P(k(T'))$ (Property 22) and $Q(l(T)) \preceq Q(l(T'))$ (Property 20), hence $PQ(T) \preceq PQ(T')$. $\square$

Joining together contexts and lattices was a preliminary step to consider families of such pairs to represent the behaviour of relational concept analysis as a whole. This is done hereafter.

# 7 Generalisation to full RCA

So far, we have only considered one context independently from the others. We now consider RCA in its entirety.
RCA deals with families of contexts. Its elements are thus simple vectors of the pairs generated by each context. These vectors will be considered as sets indexed by X. All provided definitions can be applied to indexed families of context-lattice pairs, the order between them will be the product of the piece-wise orders. All operations remain monotone and extensive (or anti-extensive) as soon as the selected scaling operations are.

The only important change is the notion of self-supported lattices that has to be replaced by self-supported families of context-lattice pairs (§7.3). Indeed, if $R = \emptyset$ or only contains endorelations, it is sufficient to work on the families as the free product of pairs. However, in RCA, this product is constrained by the relations in $R$ which may provide support for otherwise unsupported concepts, invalidating those solutions which do not consider such concepts. Hence, here the product must be constrained by $R$.

In the following we will thus redefine the objects on which RCA operates (§7.1), and the expansion (§7.2) and contraction functions (§7.4) based on the notion of self-support (§7.3). We will then consider the fixed points of these functions and their relations (§7.5).

## 7.1 The lattice $\mathcal{O}$ of families of context-lattice pairs

The input of RCA is given by a family of contexts: $K^0 = \{K_x^0\}_{x \in X}$, a set $R$ of relations between the objects of these contexts, and a set $\Omega$ of relational scaling operations.

From this, it is possible to characterise the space $\mathcal{O}_{K^0, R, \Omega}$ associated with RCA by the direct product of the sets of context-lattice pairs associated with each context.

**Definition 17** ($\mathcal{O}_{K^0, R, \Omega}$). Given an indexed family of contexts $K^0 = \{\langle G_x, M_x^0, I_x^0 \rangle\}_{x \in X}$, a set $R$ of relations between the objects of these contexts, and a set $\Omega$ of relational scaling operations, the space $\mathcal{O}_{K^0, R, \Omega}$ of indexed families of context-lattice pairs is:

$$ \mathcal{O}_{K^0, R, \Omega} = \prod_{x \in X} \mathcal{T}_{K_x^0, R, \Omega}^{\eta^*(K^0)} $$

As before, $\mathcal{O}_{K^0, R, \Omega}$ will simply be referred to as $\mathcal{O}$.

This is well defined because the set of all possible concept extents across all contexts is determined by the set of objects in the context. This permits us to name unambiguously all the concepts in the family of concept lattices. In turn, since $\eta^*(K^0)$, $R$ and $\Omega$ do not change and $I$ is determined by $\{M_x\}_{x \in X}$ (Property 2), this determines all attributes that can occur in a scaled RCA context.

There is one difference with the RCA$^0$ setting: the scaled attributes depend on $R$ that makes the connection from one context to another, e.g. from $\mathcal{T}_x$ to $\mathcal{T}_z$. But since it is possible to name concepts in the lattices generated by the scaled attributes according to their elements in $G_z$, then, as soon as $G_z$ is finite, the set of scalable attributes in $M_x$ is finite and can be established as $D_{\Omega, R_x, K^0}$ from the beginning.

The previous notations can be extended:

$$ T^*(\{K_x\}_{x \in X}) = \{T(K_x)\}_{x \in X} = \{\langle K_x, \text{FCA}(K_x) \rangle\}_{x \in X}. $$
For any {$T_x$}$_{x \in X} \in \mathcal{O}_{K^0, R, \Omega}$:

$$
\begin{align*}
k(\{T_x\}_{x \in X}) &= \{k(T_x)\}_{x \in X}, \\
l(\{T_x\}_{x \in X}) &= \{l(T_x)\}_{x \in X}, \\
k_z(\{T_x\}_{x \in X}) &= k(T_z), \\
l_z(\{T_x\}_{x \in X}) &= l(T_z).
\end{align*}
$$

Finally, for any indexed family of context-lattice pairs $O \in \bar{\mathcal{O}}$, the family of lattices
$l(O)$ is determined directly from $k(O)$: $l(O) = \text{FCA}^*(k(O))$.

We can define $\wedge$ and $\vee$ on $\mathcal{O}_{K^0, R, \Omega}$.

**Definition 18** (Meet and join of families of context-lattice pairs). Given $O = \{T_x\}_{x \in X}$,
$O' = \{T'_x\}_{x \in X} \in \mathcal{O}_{K^0, R, \Omega}$, $O \vee O'$ and $O \wedge O'$ are defined as:

$$
O \vee O' = \{T_x \vee T'_x\}_{x \in X}, \qquad (\text{join})
$$

$$
O \wedge O' = \{T_x \wedge T'_x\}_{x \in X}. \qquad (\text{meet})
$$

The set of families of context-lattice pairs is once again closed by meet and join:

**Property 42.** $\forall O, O' \in \mathcal{O}_{K^0, R, \Omega}^N$, $O \wedge O' \in \mathcal{O}_{K^0, R, \Omega}^N$ and $O \vee O' \in \mathcal{O}_{K^0, R, \Omega}^N$.

Proof. $\mathcal{O}_{K^0, R, \Omega}$ is closed by meet and join because meet and join are the piecewise meet and join of context-lattice pairs (Definition 18) and for each $x \in X$, $\mathcal{T}_{K_x^{\eta^{(K^0)}}, R, \Omega}$ is closed by meet and join (Property 31). $\square$

Meet and join also satisfies commutativity, associativity and the absorption law.

**Property 43** (Commutativity, associativity and absorption of $\vee$ and $\wedge$ on $\bar{\mathcal{O}}$). For all $O, O', O'' \in \bar{\mathcal{O}}$,

$$
\begin{align*}
& O \vee O' = O' \vee O \quad \text{and} \quad O \wedge O' = O' \wedge O, \quad (\text{commutativity}) \\
& (O \vee O') \vee O'' = O \vee (O' \vee O'') \quad \text{and} \quad (O \wedge O') \wedge O'' = O \wedge (O' \wedge O''), \quad (\text{associativity}) \\
& O \wedge (O \vee O') = O \quad \text{and} \quad O \vee (O \wedge O') = O. \quad (\text{absorption})
\end{align*}
$$
*Proof.* As before, proofs are given for $\wedge$, those for $\vee$ follow the exact same pattern.

<table><tr><td>$O \wedge O' = \{T_x \wedge T'_x\}_{x \in X}$</td><td>Definition 18</td></tr><tr><td>$= \{T'_x \wedge T_x\}_{x \in X}$</td><td>Property 32</td></tr><tr><td>$= O' \wedge O$</td><td>Definition 18</td></tr><tr><td>$(O \wedge O') \wedge O'' = \{T_x \wedge T'_x\}_{x \in X} \wedge O''$</td><td>Definition 18</td></tr><tr><td>$= \{(T_x \wedge T'_x) \wedge T''_x\}_{x \in X}$</td><td>Definition 18</td></tr><tr><td>$= \{T_x \wedge (T'_x \wedge T''_x)\}_{x \in X}$</td><td>Property 32</td></tr><tr><td>$= O \wedge \{T'_x \wedge T''_x\}_{x \in X}$</td><td>Definition 18</td></tr><tr><td>$= O \wedge (O' \wedge O'')$</td><td>Definition 18</td></tr><tr><td>$O \vee (O \wedge O') = O \vee \{T_x \wedge T'_x\}_{x \in X}$</td><td>Definition 18</td></tr><tr><td>$= \{T_x \vee (T_x \wedge T'_x)\}_{x \in X}$</td><td>Definition 18</td></tr><tr><td>$= \{T_x\}_{x \in X}$</td><td>Property 32</td></tr><tr><td>$= O$</td><td>Definition 17</td></tr></table>

We also define the order between two objects by combining the previous definitions.

**Definition 19 (Order).** Given $O = \{T_x\}_{x \in X}$, $O' = \{T'_x\}_{x \in X} \in \mathcal{O}_{K^0, R, \Omega}$, $O \preceq O'$ if $\forall x \in X, T_x \preceq T'_x$.

Like before, we note $O \simeq O'$ if $O \preceq O'$ and $O' \preceq O$, and again $\simeq$ is $=$.

Property 33 can be generalised: the order between families of context-lattice pairs may be reduced to the order between contexts (and ultimately the order between their sets of attributes).

**Property 44.** $\forall O, O' \in \mathcal{O}_{K^0, R, \Omega}$, if $k(O) \subseteq k(O')$ then $O \preceq O'$.

*Proof.* $k(O) \subseteq k(O')$ means that $\forall x \in X, k_x(O) \subseteq k_x(O')$ which is equivalent to $\langle k_x(O), l_x(O) \rangle \preceq \langle k_x(O'), l_x(O') \rangle$ (Property 33) and hence $O \preceq O'$ (Definition 19). $\square$

This order is compatible with meet and join.

**Property 45.** $\forall O, O' \in \mathcal{O}_{K^0, R, \Omega}$, $O \preceq O'$ iff $O = O \wedge O'$.

*Proof.* By Property 34, we have that $T_x \preceq T'_x$ iff $T_x = T_x \wedge T'_x$ and this $\forall x \in X$, consequently $O \preceq O'$ iff $O = O \wedge O'$.

Finally, the set $\mathcal{O}_{K^0, R, \Omega}$ of families of context-lattice pairs is a complete lattice.

**Proposition 46.** $\langle \mathcal{O}_{K^0, R, \Omega}, \vee, \wedge \rangle$ is a complete lattice.

*Proof.* $\mathcal{O}_{K^0, R, \Omega}$ is closed by meet and join (Property 42). $\vee$ and $\wedge$ satisfy commutativity, associativity and the absorption laws (Property 43), so this is a lattice. It is complete because it is the direct product of complete lattices (Property 35). $\square$
## 7.2 The expansion function $EF^*$

We reformulate RCA as based on a main single function, $EF^*_{K^0, R, \Omega}$, the expansion function attached to a relational context $\langle K^0, R \rangle$ and a set $\Omega$ of scaling operations.

**Definition 20 (Expansion function).** Given a relational context $\langle K^0, R \rangle$ and a set $\Omega$, of relational scaling operations the expansion function $EF^*_{K^0, R, \Omega} : \mathcal{O}_{K^0, R, \Omega} \to \mathcal{O}_{K^0, R, \Omega}$ is defined by:

$$EF^*_{K^0, R, \Omega}(O) = T^*(\sigma^*_{\Omega}(k(O), R, l(O))).$$

As previously, we will abbreviate $EF^*_{K^0, R, \Omega}$ as $EF^*$. This function is the basis of RCA: it covers scaling and the application of FCA* embedded in the function $T^*$. Thus, the two steps (3) and (2) of the RCA algorithm (Section 2.4.2) have been merged into one.

A family of context-lattice pairs is called saturated if it is not possible to scale new relational attributes in any of its contexts.

**Definition 21 (Saturated family of context-lattice pairs).** A family of context-lattice pairs $O \in \mathcal{O}$ is saturated if $\forall x \in X, k_x(O) = \sigma_{\Omega}(k_x(O), R, l(O))$.

$EF^*$ is thus not anymore in direct connection with the previous $EF$ but it extends it:

**Property 47.** $\{EF_{K^0, R, \Omega}(T_x)\}_{x \in X} \leq EF^*_{K^0, R, \Omega}(\{T_x\}_{x \in X})$.

*Proof.* $\forall x \in X, l_x(O) \in l(O)$, thus $\sigma_{\Omega}(k_x(O), R, l_x(O)) \subseteq \sigma_{\Omega}(k_x(O), R, l(O))$ because there are less concepts to scale with: only those in $l_x(O)$. Hence, $T(\sigma_{\Omega}(k_x(O), R, l_x(O))) \leq T(\sigma_{\Omega}(k_x(O), R, l(O)))$ (Property 33). Therefore this leads to $\{EF_{K^0, R, \Omega}(T_x)\}_{x \in X} = \{T(\sigma_{\Omega}(k_x(O), R, l_x(O)))\}_{x \in X} \leq \{T(\sigma_{\Omega}(k_x(O), R, l(O)))\}_{x \in X} = EF^*_{K^0, R, \Omega}(O). \quad \square$

$EF^*$ is an extensive and monotone internal operation for $\mathcal{O}$:

**Property 48 (EF$^*$ is internal to $\mathcal{O}$).** $\forall O \in \mathcal{O}, EF^*(O) \in \mathcal{O}$.

*Proof.* $\forall x \in X, \sigma_{\Omega}(k_x(O), R, l(O)) = F(k_x(O)) \in \mathcal{K}^{\eta^*(K^0)}_{K_x, R, \Omega}$ because $\sigma_{\Omega}$ only scales attributes in $D_{\Omega, R_x, K^0}$. Thus, $EF(T) = T(\sigma_{\Omega}(k_x(O), R, l(O))) \in \mathcal{T}^{\eta^*(K^0)}_{K_x, R, \Omega}$. Hence, $EF^*(O) = \{T(\sigma_{\Omega}(k_x(O), R, l(O)))\}_{x \in X} \in \mathcal{O}$ (Definition 17). \quad $\square$

**Property 49 (EF$^*$ is extensive and monotone).** The function $EF^*$ attached to a relational context and a set of scaling operations satisfies:

$$O \leq EF^*(O), \qquad (\text{extensivity})$$

$$O \leq O' \Rightarrow EF^*(O) \leq EF^*(O'). \qquad (\text{monotony})$$

*Proof.* extensivity holds because $EF^*$ can only add to $k(O)$ attributes scaled from $l(O)$, hence $\forall x \in X, k_x(O) \subseteq k_x(EF^*(O))$. Thus, by Property 44, $O \leq EF^*(O)$. monotony holds because $O \leq O'$ means that $\forall x \in X, l_x(O) \leq l_x(O')$ and $k_x(O) \subseteq$
$k_x(O')$. The former entails that $\forall x \in X, \eta(l_x(O)) \subseteq \eta(l_x(O'))$ and consequently, that $D_{\Omega,R_x,l(O)} \subseteq D_{\Omega,R_x,l(O')}$. A smaller context ($k_x(O)$) is extended by a smaller set of attributes ($D_{\Omega,R_x,l(O)}$), thus $k_x(EF^*(O)) \subseteq k_x(EF^*(O'))$. Hence, by Property 44, $EF^*(O) \preceq EF^*(O')$. $\square$

## 7.3 Self-supporting families of context-lattice pairs

In a family of context-lattice pairs $O$, there may be a context $k_x(O)$ containing attributes which refer to concepts non existing in $l(O)$. Such an attribute, e.g. $\exists r.c$, belonging to $k_x(O)$ may belong to $D_{\Omega,R_x,K^0}$ and be well-defined by the incidence relation, but $c$ may not be a concept of $l(O)$. This is illustrated by Example 12.

**Example 12** (Non self-supported families of context-lattice pairs). Figure 8 (p.28) shows a family of contexts $\{K_3^#, K_4^#\}$ and the associated family of concept lattices $\{L_3^#, L_4^#\}$ that could be a solution for the example of Section 3.3 as it belongs to $\mathcal{O}\{\exists\},\{p,q\},\{K_3^0,K_4^0\}$. However, this family is not self-supported because the context $K_3^#$ (and thus concept A) uses the attribute $\exists p.C$ which refers to a concept (C) not present in $L_4^#$ and similarly for $\exists q.B$ in context $K_4^#$.

A family of context-lattice pairs in $\mathcal{O}$ containing such attributes will see them preserved by $EF^*$ which only extends the contexts. This is not the expected result: concepts referred to by attributes are expected to exist in the corresponding lattice.

One may consider identifying such attributes and forbidding them. However, support is contextual: one supported attribute in a large family of context-lattice pairs may not be supported in a smaller one.

In order to define acceptable solutions for RCA, we introduce the notion of context supported by a family of concept lattices, i.e. those contexts whose relational attributes only refer to concepts in the lattices.

**Definition 22** (Supported context). A context $\langle G_x, M_x, I_x \rangle$ is supported by a family of indexed lattices $\{L_z\}_{z \in X}$, with respect to a set $R$ of relations, if $\forall \zeta(r, c) \in M_x$, $r \in R_{x,z}$ and $c \in L_z$.

By extension, an indexed family of context-lattice pairs is said *self-supported* if each context of the family is supported by the family lattices. The support of a single context may use several lattices of the family ($l(O)$).

**Definition 23** (Self-supported families of context-lattice pairs). A family of context-lattice pairs $O \in \mathcal{O}$ is self-supported, with respect to a set $R$ of relations, if $\forall x \in X$, $k_x(O)$ is supported by $l(O)$, with respect to $R$.

As before, the definition of self-supported families of context-lattice pairs does not provide a direct way to transform a non self-supported family into a self-supported one. For that purpose, we extend the purging function $\pi$ (Section 7.3) to take into account families of context-lattice pairs.
**Definition 24** (Purging function). The function

$$ \pi_{K^0, R, \Omega}^* : \prod_{x \in X} \mathcal{L}_{K_x^0, R, \Omega} \to \prod_{x \in X} \mathcal{K}_{K_x^0, R, \Omega} $$

returns the family of contexts reduced of those attributes not present in a family of lattices:

$$ \pi_{K^0, R, \Omega}^*(L) = \{\pi_{K^0, R, \Omega}(L_x, L)\}_{x \in X}, $$

with

$$ \pi_{K^0, R, \Omega}(L_x, L) = K_{-(D_{\Omega, R_x, K^0}) \setminus D_{\Omega, R_x, L}}^{(R, L)}(\kappa(L_x)). $$

When unambiguous, we refer to $\pi_{K^0, R, \Omega}^*$ as $\pi^*$. As for $EF^*$, $\pi^*$ uses the lattices of the whole family $(l(O))$.

$\pi^*$ can be used to determine if a family of context-lattice pairs is self-supported:

**Property 50.** $O$ is self-supported if and only if $k(O) = \pi^*(l(O))$.

*Proof.* $O$ is self-supported means that $\forall x \in X$, $k_x(O)$ is supported by $l(O)$ (Definition 23) which means that, in $k_x(O)$, there is no attribute built from concepts out of $l(O)$, i.e. not belonging to $D_{\Omega, R_x, l(O)}$. By Definition 9, this is equivalent to having $\forall x \in X$, $\pi(l_x(O), l(O)) = \kappa(l_x(O))$. However, by Property 9, $k_x(O) = \kappa(l_x(O))$, thus $k_x(O) = \pi(l_x(O), l(O))$ and then $k(O) = \pi^*(l(O))$. $\square$

Like $\pi$, $\pi^*$ does not necessary provide a self-supported family of context-lattice pairs in one step. Hence, it has to be iterated.

We introduce a contraction function, $PQ_{K^0, R, \Omega}^*$, attached to a relational context $\langle K^0, R \rangle$ and a set $\Omega$ of scaling operations, which suppresses non-supported attributes and whose closure yields self-supported families of context-lattice pairs.

## 7.4 The contraction function $PQ^*$

Similarly to $EF_{K^0, R, \Omega}^*$, it is possible to define $PQ_{K^0, R, \Omega}^*$ the contraction function attached to a relational context $\langle K^0, R \rangle$ and a set $\Omega$ of scaling operations.

**Definition 25** (Contraction function). Given a relational context $\langle K^0, R \rangle$ and a set $\Omega$, of relational scaling operations, the contraction function $PQ_{K^0, R, \Omega}^*$: $\mathcal{O}_{K^0, R, \Omega} \to \mathcal{O}_{K^0, R, \Omega}$ is defined by:

$$ PQ_{K^0, R, \Omega}^*(O) = T^*(\pi_{K^0, R, \Omega}^*(l(O))). $$

This function is thus not anymore in direct connection with the previous $PQ$ but it extends it:

**Property 51.** $\{PQ_{K_x^0, R, \Omega}(T_x)\}_{x \in X} \preceq PQ_{K^0, R, \Omega}^*(\{T_x\}_{x \in X})$.
<figure><img src="image_15.png" /><figcaption>Figure 15: Relations between $\mathcal{O}$, $\mathcal{T}_x$ and $\mathcal{T}_z$. In this figure, $\pi_x$ represents the projection of the objects to their component indexed by $x \in X$.</figcaption></figure>

*Proof.* For any $x \in X$, $l_x(O) \in l(O)$, hence $\pi(k_x(O), l_x(O)) \subseteq \pi(k_x(O), l(O))$ because there are more attributes to preserve from concepts in $l(O)$. Thus, $T(\pi(k_x(O), l_x(O))) \subseteq T(\pi(k_x(O), l(O)))$ (Property 33). This has for consequence that $\{PQ_{K^0, R, \Omega}(T_x)\}_{x \in X} = \{T(\pi(k_x(O), l_x(O)))\}_{x \in X} \subseteq \{T(\pi(k_x(O), l(O)))\}_{x \in X} = PQ^*_{K^0, R, \Omega}(O)$. $\square$

As previously, we will abbreviate $PQ^*_{K^0, R, \Omega}$ as $PQ^*$.

$PQ^*$ is an anti-extensive and monotone internal operation for $\mathcal{O}$:

**Property 52** ($PQ^*$ is internal to $\mathcal{O}$). $\forall O \in \mathcal{O}$, $PQ^*(O) \in \mathcal{O}$.

*Proof.* $PQ^*(O) = T^*(\pi^*(l(O))) = T^*(\{\pi(l_x(O), l(O))\}_{x \in X}) = \{T(\pi(l_x(O), l(O)))\}_{x \in X}$. Hence, $PQ^*(O) \in \mathcal{O}$ if $\pi(l_x(O), l(O)) \in \mathcal{K}_{K_x^0, R, \Omega}^{\eta^*(K^0)}$ (Definition 17). This is the case because (i) $\mathcal{K}_{K_x^0, R, \Omega}^{\eta^*(K^0)}$ contains all contexts extending $K_x^0$ with attributes from $D_{\Omega, R_x, K^0}$, (ii) $k_x(O) \in \mathcal{K}_{K_x^0, R, \Omega}^{\eta^*(K^0)}$, and (iii) $\pi$ only suppresses attributes from $k_x(O)$ preserving those of $K_x^0$. $\square$

**Property 53** ($PQ^*$ is anti-extensive and monotone). The function $PQ^*$ attached to a relational context and a set of scaling operations satisfies:

$$PQ^*(O) \preceq O, \qquad (\text{anti-extensivity})$$

$$O \preceq O' \Rightarrow PQ^*(O) \preceq PQ^*(O'). \qquad (\text{monotony})$$

*Proof.* anti-extensivity holds because $PQ^*$ can only suppress from $k(O)$ attributes not supported by $l(O)$, hence $\forall x \in X, k_x(PQ^*(O)) \subseteq k_x(O)$. Therefore, by Property 44,
$PQ^*(O) \preceq O$. monotony holds because $O \preceq O'$ means that $\forall x \in X, k_x(O) \subseteq k_x(O')$ and $l_x(O) \preceq l_x(O')$. This entails that $\eta^*(l(O)) \subseteq \eta^*(l(O'))$ and thus, $\forall x \in X, D_{\Omega,R_x,l(O)} \subseteq D_{\Omega,R_x,l(O')}$. Because $PQ^*(O)$ suppresses from $k_x(O)$ attributes not in $M_x^0 \cup D_{\Omega,R_x,l(O)}$, this entails that $k_x(PQ^*(O)) \subseteq k_x(PQ^*(O'))$. Hence, by Property 44, $PQ^*(O) \preceq PQ^*(O')$. $\square$

## 7.5 The fixed points of EF* and PQ*

Given $EF^*$ and $PQ^*$, it is possible to define their sets of fixed points, i.e. the sets of families of context-lattice pairs closed for $EF^*$ and $PQ^*$, as:

**Definition 26 (Fixed points).** A family of context-lattice pairs $O \in \mathcal{O}$ is a fixed point for a function $\phi$, if $\phi(O) \simeq O$. We call $\text{fp}(\phi)$ the set of fixed points for $\phi$.

This characterises $\text{fp}(EF^*)$ and $\text{fp}(PQ^*)$.

This may be directly expressed

**Property 54.** $O \in \text{fp}(EF^*)$ iff $\sigma_{\Omega}^*(k(O), R, l(O)) = k(O)$.

*Proof.* $O = T^*(k(O))$ and $EF^*(O) = T^*(\sigma_{\Omega}^*(k(O), R, l(O))).$ ($\Leftarrow$) If $\sigma_{\Omega}^*(k(O), R, l(O)) = k(O)$, then $EF^*(O) = O$ and thus is a fixed point of $EF^*$. ($\Rightarrow$) If $\sigma_{\Omega}^*(k(O), R, l(O)) \neq k(O)$, then $EF^*(O) \neq O$, so it is not a fixed point. $\square$

**Property 55.** $O \in \text{fp}(PQ^*)$ iff $\pi^*(l(O)) = k(O)$.

*Proof.* $O = T^*(k(O))$ and $PQ^*(O) = T^*(\pi^*(l(O))).$ ($\Leftarrow$) If $\pi^*(l(O)) = k(O)$, then $PQ^*(O) = O$ and thus is a fixed point of $PQ^*$. ($\Rightarrow$) If $\pi^*(l(O)) \neq k(O)$, then $PQ^*(O) \neq O$, so it is not a fixed point. $\square$

Since $\mathcal{O}$ is a complete lattice (Proposition 46) and $EF^*$ and $PQ^*$ are order-preserving (or monotone) on $\mathcal{O}$ (Properties 49 and 53), then we can apply the Knaster-Tarski theorem (Theorem 1).

Thus, $\langle \text{fp}(EF^*), \preceq \rangle$ and $\langle \text{fp}(PQ^*), \preceq \rangle$ are complete lattices. This warrants that there exists least and greatest fixed points of $EF^*$ and $PQ^*$ in $\mathcal{O}$. For such a function $\phi$, operating on the set $\mathcal{O}$, their least and greatest fixed points are:

$$ \text{lfp}(\phi) = \bigwedge_{O \in \text{fp}(\phi)} O \quad \text{and} \quad \text{gfp}(\phi) = \bigvee_{O \in \text{fp}(\phi)} O. $$

The fixed points of these two functions may be further characterised. The smallest fixed point of $PQ^*$ is the smallest element of $\mathcal{O}$ which cannot be further reduced. Property 25 (apparently not in [Euzenat, 2021]) can be generalised as:

**Property 56 (Least fixed point of $PQ^*$).**

$$ \text{lfp}(PQ^*) = T^*(K^0). $$
**Proof.** T*(π*(FCA*(K⁰))) = T*(K⁰) because (a) ∀x ∈ X, κ(FCA(Kx⁰)) = Kx⁰ (Property 9), and (b) π(FCA(Kx⁰), FCA*(K⁰)) = Kx⁰ as it is not possible to suppress attributes from Kx⁰ which, being an initial (unscaled) context, does not comprise any attribute referring to concepts. Thus, PQ*(T*(K⁰)) = T*(π*(FCA*(K⁰))) = T*(K⁰). Moreover, ∀O ∈ O, T*(K⁰) ≤ O. Hence, T*(K⁰) is a fixed point of PQ* and all other fixed points are greater. □

The greatest fixed point of EF* is the family that cannot be further extended (generalising Proposition 17 [Euzenat, 2021]):

**Property 57 (Greatest fixed point of EF").**

$$ \text{gfp}(EF_{K^0, R, \Omega}^*) = T^*\{K_{+D_{\Omega, R, K^0}}^{\langle R, \eta^*(K^0) \rangle}(K_x^0)\}_{x \in X}. $$

**Proof.** This family of context-lattice pairs is the greatest element of O as ∀x ∈ X, the context kx(O) contains all attributes of Mx⁰ ∪ DΩ,Rx,K⁰ and due to Property 44. It is also a fixed point because EF* is extensive (Property 49) and internal (Property 48). □

The function EF* and PQ* converge after a finite number of applications.

**Property 58 (Stability of EF").** ∀O ∈ O, ∃n; EF*n*(O) = EF*n+1*(O).

**Proof.** EF* can only increase the contexts when there are new concepts in lattices and increase the lattices when contexts grow. However, the set of attributes that can increase contexts, and the set of concepts that can be in lattices, is finite. Hence, at each step either an attribute is added or n has been reached such that the family of context-lattice pairs is the same. This is the same argument as that of [Rouane Hacène et al., 2013a]. □

This below is an extension of Proposition 5 of [Euzenat, 2021]:

**Property 59 (Stability of PQ").** ∀O ∈ O, ∃n; PQ*n*(O) = PQ*n+1*(O).

**Proof.** PQ* can only decrease the contexts and reduce lattices. Since these are finite (and the decrease does not affect the attributes of K⁰), there exists a n at which the decrease stops. □

The finite application of EF* and PQ* as many times as necessary, i.e. to the first n satisfying Properties 58 and 59, are closure operations denoted by EF*∞ and PQ*∞, respectively.

**Property 60.** EF*∞ and PQ*∞ are closures.

**Proof.** Since EF* is extensive and monotone (Property 49), EF*∞ is also extensive and monotone by transitivity of ≤. In order to be a closure operation it has to be idempotent. This is the case, because ∀O ∈ O, EF*∞(O) = EF*n*(O) = EF*n+1*(O) = EF*(EF*n*(O)). Since EF*n*(O) = EF*(EF*n*(O)), EF* can be applied n times, leading to EF*∞(O) = EF*n*(O) = EF*n*(EF*n*(O)) = EF*∞(EF*∞(O)).

The same can be obtained from PQ*, albeit anti-extensive (Property 53). □
In addition, they are extrema of the sets of fixed points of their respective functions.

**Property 61** ($EF^*$ and $PQ^*$ return the smallest subsuming and greatest subsumed fixed points). $\forall O \in \mathcal{O}$,

$$EF^{*\infty}(O) = \min(\text{fp}(EF^*) \cap \{O'|O \preceq O'\}),$$

$$PQ^{*\infty}(O) = \max(\text{fp}(PQ^*) \cap \{O'|O' \preceq O\}).$$

*Proof.* $EF^{*\infty}(O) \in \text{fp}(EF^*)$ and $PQ^{*\infty}(O) \in \text{fp}(PQ^*)$ as they satisfy Definition 26. Moreover, $EF^{*\infty}(O) \in \{O'|O \preceq O'\}$ and $PQ^{*\infty}(O) \in \{O'|O' \preceq O\}$ as $EF^*$ and $PQ^*$ are respectively extensive and anti-extensive and monotone (Property 49 and 53). There cannot be $O' \in \text{fp}(EF^*) \cap \{O'|O \preceq O'\}$ such that $O' \prec EF^{*\infty}(O)$ because otherwise $k(O') \subset k(EF^{*\infty}(O))$ and $k(O) \subseteq k(O')$. In other terms, $O'$ contains all attributes of $O$ but not all attributes of $EF^{*\infty}(O)$. But, $EF^{*\infty}$ only adds scalable attributes and $k(EF^{*\infty}(O))$ contains only attributes scalable from $O$. Hence, $O'$ is not closed for $EF^*$ ($O' \notin \text{fp}(EF^*)$).

The same holds for $PQ^{*\infty}(O)$, there cannot be $O' \in \text{fp}(PQ^*) \cap \{O'|O' \preceq O\}$ such that $PQ^{*\infty}(O) \prec O'$ because otherwise $k(O') \subseteq k(O)$. In other terms, all attributes of $O'$ are in $O$ but $O'$ contains all attributes of $PQ^{*\infty}(O)$. However, $PQ^{*\infty}$ only suppress attributes not supported by those of $O$. Hence, $O'$ is not closed for $PQ^*$ ($O' \notin \text{fp}(PQ^*)$), as it would contain non-supported attributes. □

The respective relations of these various objects can be summarised by the following property:

**Property 62.** $\forall O \in \mathcal{O}$,

$$\text{lfp}(PQ^*) \preceq PQ^{*\infty}(O) \preceq PQ^*(O) \preceq O \preceq EF^*(O) \preceq EF^{*\infty}(O) \preceq \text{gfp}(EF^*).$$

*Proof.* All the inner equations are consequences of the extensivity of $EF^*$ (Property 49) and anti-extensivity of $PQ^*$ (Property 53). The outer ones owe to the fact that the two closure operations are fixed points (Property 61), thus they are subsumed by, resp. subsuming, their greatest, resp. least, fixed point. □

## 7.6 Acceptable solutions

What is called acceptable solutions in Section 3 is now rephrased in Definition 27.

**Definition 27** (Acceptable family of context-lattice pairs). Given a family $K^0$ of contexts, a set $\Omega$ of scaling operations and a set $R$ of relations, a family of context-lattice pairs $O$ is acceptable if

- $O \in \mathcal{O}_{K^0, R, \Omega}$, (well-formedness)

- $O$ is saturated, (saturation)

- $O$ is self-supported. (self-support)
This can be characterised as those families of context-lattice pairs which are fixed points of both $EF^*$ and $PQ^*$.

The fixed points of $EF^*$ are exactly those saturated elements of $\mathcal{O}$:

**Property 63** (Fixed points of $EF^*$ are saturated). $\forall O \in \mathcal{O}, O$ is saturated iff $O \in \text{fp}(EF^*)$.

*Proof.* $O \in \text{fp}(EF^*)$ means that $k(O) = \sigma_{\Omega}^*(k(O), R, l(O))$ (Property 54) which is equivalent to $\forall x \in X, k_x(O) = \sigma_{\Omega}(k_x(O), R, l(O))$ which, by Definition 21, means that $O$ is saturated. $\square$

The fixed points of $PQ^*$ are exactly those self-supported objects in $\mathcal{O}$:

**Property 64** (Fixed points of $PQ^*$ are self-supported). $\forall O \in \mathcal{O}, O$ is self-supported iff $O \in \text{fp}(PQ^*)$.

*Proof.* $O$ is self-supported iff $k(O) = \pi^*(l(O))$ (Property 50) which is equivalent to $O = PQ^*(O)$ (Property 55), i.e. $O \in \text{fp}(PQ^*)$. $\square$

Hence, the set of acceptable solutions is $\text{fp}(EF^*) \cap \text{fp}(PQ^*)$.

**Proposition 65** (Acceptable solutions are fixed points of both $EF^*$ and $PQ^*$). *Given a family $K^0$ of contexts, a set $\Omega$ of scaling operations and a set $R$ of relations, a family of context-lattice pairs $O$ is acceptable iff $O \in \mathcal{O}_{K^0, R, \Omega}$ and $O \in \text{fp}(EF^*) \cap \text{fp}(PQ^*)$.*

*Proof.* $O$ is well-formed as it belongs to $\mathcal{O}_{K^0, R, \Omega}$. It is saturated if and only if it belongs to $\text{fp}(EF^*)$ (Property 63) and it is self-supported if and only if it belongs to $\text{fp}(PQ^*)$ (Property 64). Hence, $O$ is acceptable (Definition 27). $\square$

Example 13 illustrates this:

**Example 13** (Acceptable solutions). In the example of Section 3.3, it can be checked that the given solutions belong to the expected fixed points:

$$ 
\begin{align*}
EF^* (\{\langle K_3^1, L_3^1 \rangle, \langle K_4^1, L_4^1 \rangle\}) &= \{\langle K_3^1, L_3^1 \rangle, \langle K_4^1, L_4^1 \rangle\} = PQ^* (\{\langle K_3^1, L_3^1 \rangle, \langle K_4^1, L_4^1 \rangle\}), \\
EF^* (\{\langle K_3^*, L_3^* \rangle, \langle K_4^*, L_4^* \rangle\}) &= \{\langle K_3^*, L_3^* \rangle, \langle K_4^*, L_4^* \rangle\} = PQ^* (\{\langle K_3^*, L_3^* \rangle, \langle K_4^*, L_4^* \rangle\}), \\
EF^* (\{\langle K'_3, L'_3 \rangle, \langle K'_4, L'_4 \rangle\}) &= \{\langle K'_3, L'_3 \rangle, \langle K'_4, L'_4 \rangle\} = PQ^* (\{\langle K'_3, L'_3 \rangle, \langle K'_4, L'_4 \rangle\}),
\end{align*}
$$

and

$$ EF^* (\{\langle K_3'', L_3'' \rangle, \langle K_4'', L_4'' \rangle\}) = \{\langle K_3'', L_3'' \rangle, \langle K_4'', L_4'' \rangle\} = PQ^* (\{\langle K_3'', L_3'' \rangle, \langle K_4'', L_4'' \rangle\}). $$

and none of the other elements of $\mathcal{O}$ as displayed in Figure 17 (p.72).

In lattice theory, saturation and self-support would have been easily called closedness. The terms saturation and self-support have been chosen in order to differentiate them.
# 8 The fixed-point semantics of RCA

Now that the acceptable solutions have been characterised structurally and functionally, we can answer our initial question and define the semantics of RCA. RCA returns the smallest acceptable solution. It is also the least fixed point of the $EF^*$ function (§8.1). Another interesting operation is the one that generates the greatest acceptable solution, which is also the greatest fixed point of $PQ^*$ (§8.2).

It is also worth considering obtaining the whole set $fp(EF^*) \cap fp(PQ^*)$. Section 8.3 investigates the structure of $[lfp(EF^*), gfp(PQ^*)]$ and its relation with $fp(EF^*) \cap fp(PQ^*)$ towards that goal. It provides various results that may be exploited to develop efficient algorithms.

## 8.1 Classical RCA computes $EF^*$'s least fixed point

RCA as it has been defined in Section 2.4.2 (p.19) may be redefined as

$$ \underline{\text{RCA}}_{\Omega}(K^0, R) = l(EF_{K^0, R, \Omega}^{*\infty}(T^*(K^0))) $$

i.e. RCA iterates $EF^*$ from $T^*(K^0)$ until reaching a fixed point, and ultimately the corresponding lattices are returned.

It thus seems that RCA returns a fixed point of $EF^*$. Hence the question: which fixed point is returned by RCA's well-grounded semantics? This is the least fixed point.

**Proposition 66** (The RCA algorithm computes the least fixed point of $EF^*$). Given $EF^*$ the expansion function associated to $K^0$, $R$ and $\Omega$,

$$ \underline{\text{RCA}}_{\Omega}(K^0, R) = l(lfp(EF_{K^0, R, \Omega}^*)) $$

*Proof.* $T^*(K^0) \in \mathcal{O}$, thus $EF^{*\infty}(T^*(K^0)) \in \mathcal{O}$ (Property 48). Moreover, $EF^{*\infty}(T^*(K^0)) = \min_{\leq}(fp(EF^*) \cap \{O' | T^*(K^0) \leq O'\})$ (Property 61). But $\forall O' \in \mathcal{O}$, $T^*(K^0) \leq O'$, hence $EF^{*\infty}(T^*(K^0)) = \min_{\leq}(fp(EF^*))$. Thus, $EF_{K^0, R, \Omega}^{*\infty}(T^*(K^0))$ is a fixed point more specific than all fixed points: it is the least fixed point. $l(EF_{K^0, R, \Omega}^{*\infty}(T^*(K^0)))$ is the family of lattices associated with the least fixed point of $EF_{K^0, R, \Omega}^*$.

## 8.2 Greatest fixed-point (of $PQ^*$) semantics

It is possible to define $\overline{\text{RCA}}$ as returning the greatest acceptable solution. The greatest fixed point of $EF^*$ (Property 57) is not necessarily an acceptable solution because it may not be self-supported. Said otherwise, it does not belong to $fp(EF^*) \cap fp(PQ^*)$ because it is not a fixed point for $PQ^*$.

Alternatively, a dual procedure $\overline{\text{RCA}}$ may be defined as:

$$ \overline{\text{RCA}}_{\Omega}(K^0, R) = l(PQ_{K^0, R, \Omega}^{*\infty}(T^*\{K_{+D_{\Omega, R_x, K^0}}^{\langle R, \eta^*(K^0)\rangle}(K_x^0)\}_{x \in X})). $$

and it can be characterised analogously as the greatest fixed point of $PQ_{K^0, R, \Omega}^*$.
<figure><img src="image_16.png" /></figure>

It can be checked that it is a fixed point for EF*: no additional attribute can be scaled.
On the contrary, PQ* can be applied to gfp(EF*) leading to the following result:

$$ \frac{k(PQ^{*\infty}(gfp(EF^*)))}{\begin{array}{c} a \\ b \\ c \\ d \end{array}} \begin{array}{c|cccc} \exists & r.C & & \\ \exists & r.D & & \\ \exists & r.AB & & \\ \exists & r.CD & & \\ \exists & r.ABC & & \\ \exists & r.ABD & & \\ \exists & r.ABCD & & \end{array} $$

<figure><img src="image_17.png" /></figure>

In this case, PQ*(gfp(EF*)) = PQ*∞(gfp(EF*)), this is not necessarily true as some concepts may be supported by attributes which may be retracted from the lattice due to lack of support. When full RCA is considered, this may span from context to context.

**Example 15** (Greatest fixed-point semantics for RCA). In the cases presented in Section 3.1 and 3.3, the greatest (or maximum) elements {$\langle K_1^*, L_1^* \rangle$, $\langle K_2^*, L_2^* \rangle$} and {$\langle K_3^*, L_3^* \rangle$, $\langle K_4^*, L_4^* \rangle$} of $\mathcal{O}$ are fixed points for both EF* and PQ*. Instead, consider the example of Section 3.1 in which the relation $p$ is changed to:

$$ \frac{p \mid d \ e \ f}{\begin{array}{c|ccc} a & \times & \times \\ b & \times & \times \\ c & \times & \times \end{array}} $$

$$ \frac{q \mid a \ b \ c}{\begin{array}{c|ccc} d & \times & \times \\ e & \times & \times \\ f & \times & \times \end{array}} $$

$q$ remaining the same. The effect of changing $p$ is to make $a$ and $b$ non distinguishable and reduce the sets of supported concepts.

By Property 57, gfp(EF*) = T*($\{K_{+D_{\Omega,R_x,K^0}}^{(R,\eta^*(K^0))}\}(K_x^0)\}_{x \in \{1,2\}}$) = {$\langle K_1^\top, L_1^\top \rangle$, $\langle K_2^\top, L_2^\top \rangle$} which is presented below:
<figure><img src="image_18.png" /></figure>

<figure><img src="image_19.png" /></figure>

<figure><img src="image_20.png" /></figure>

It can be checked that $\{\langle K_1^\top, L_1^\top \rangle, \langle K_2^\top, L_2^\top \rangle\}$ is a fixed point for $EF^*$: no additional attribute can be scaled. On the contrary, it is not a fixed point for $PQ^*$ which can be applied to it.

In a first application, it will purge $\langle K_2^\top, L_2^\top \rangle$ to:

<figure><img src="image_21.png" /></figure>

<figure><img src="image_22.png" /></figure>

A second application will purge $\langle K_1^\top, L_1^\top \rangle$ with respect to $\langle K_2^\dagger, L_2^\dagger \rangle$:

<figure><img src="image_23.png" /></figure>

<figure><img src="image_24.png" /></figure>

It can be checked that $\{\langle K_1^\dagger, L_1^\dagger \rangle, \langle K_2^\dagger, L_2^\dagger \rangle\}$ is a fixed point for $PQ^*$, but also for $EF^*$.
It may be interesting, for some applications to check if there is only one acceptable solution. This can easily be characterised by:

**Proposition 68.** $\text{lfp}(EF^*_{K^0, R, \Omega}) = \text{gfp}(PQ^*_{K^0, R, \Omega}) \text{ iff } |\text{fp}(EF^*_{K^0, R, \Omega}) \cap \text{fp}(PQ^*_{K^0, R, \Omega})| = 1$.

The proof of this proposition is given in the next section (8.3) as it relies on further results.

This can be tested using RCA and RCA.

FCA can be described as RCA with $R = \emptyset$. In this case, $\forall x \in X D_{\Omega, R_x, K^0} = \emptyset$. Thus, $\mathcal{O} = \{T^*(K^0)\} = \{\langle K^0, \text{FCA}(K^0) \rangle\}$ and $\text{fp}(EF^*) = \text{fp}(PQ^*) = \{T^*(K^0)\}$. Hence,

$$ \underline{\text{RCA}}_{\Omega}(K^0, \emptyset) = \overline{\text{RCA}}_{\Omega}(K^0, \emptyset) = \text{FCA}(K^0). $$

## 8.3 The structure of fixed points

Besides obtaining the least fixed point of $EF^* (\underline{\text{RCA}}_{\Omega})$ or the greatest fixed point of $PQ^* (\overline{\text{RCA}}_{\Omega})$, an interesting problem is to obtain all acceptable solutions, i.e. those families of context-lattice pairs belonging to the fixed points of both functions ($\text{fp}(EF^*) \cap \text{fp}(PQ^*)$).

A naive algorithm for this consists in enumerating all elements of the interval and testing if they are fixed points. This would not be very efficient. Figure 17 shows that, in our simple Example 3.3, among the 16 elements in the interval only 4 belong to $\text{fp}(EF^*) \cap \text{fp}(PQ^*)$.

One way to try to improve on this situation is to understand the structure of the set of fixed points and its relation with the two functions and their closures. Figure 16 illustrates the structure of $\mathcal{O}$ and how $EF^{*\infty}$ and $PQ^{*\infty}$ and their composition traverse this structure.

An interesting property of the functions $EF^*$ and $PQ^*$ is that they preserve each other stability:

**Property 69** ($EF^*$ is internal to $\text{fp}(PQ^*)$). $\forall O \in \text{fp}(PQ^*)$, $EF^*(O) \in \text{fp}(PQ^*)$.

*Proof.* If $O \in \text{fp}(PQ^*)$, all attributes in intents of $l(O)$ are supported by concepts in $l(O)$ (Property 64 and Definition 23). By Property 49, $O \preceq EF^*(O)$, so these concepts are still in $l(EF^*(O))$. Moreover, $EF^*$ only adds to $k(O)$ attributes which are supported by $l(O)$ (they only refer to concepts in $l(O)$). Hence, the attributes in $k(EF^*(O))$ and those scaled by $\sigma_{\Omega}$ are still supported by $l(EF^*(O))$. $\square$

**Property 70** ($PQ^*$ is internal to $\text{fp}(EF^*)$). $\forall O \in \text{fp}(EF^*)$, $PQ^*(O) \in \text{fp}(EF^*)$.

*Proof.* If $O \in \text{fp}(EF^*)$, this means that $EF^*(O) = O$ and, in particular, that $\sigma_{\Omega}^*$ does not scale new relational attributes based on the concepts in $l(O)$. By Property 53, $PQ^*(O) \preceq O$, so that $l(PQ^*(O))$ does not contain more concepts than $l(O)$, then $\sigma_{\Omega}^*$ cannot scale new attributes $(\sigma_{\Omega}^*(k(PQ^*(O)), R, l(PQ^*(O)))) \subseteq \sigma_{\Omega}^*(k(O), R, l(O)) = \emptyset$. Hence, $PQ^*(O) \in \text{fp}(EF^*)$. $\square$

This shows that $\text{fp}(EF^*) \cap \text{fp}(PQ^*) \neq \emptyset$: acceptable solutions always exist. In addition, the closure operations associated with the two functions preserve their extrema.
**Property 71.** $PQ^{*\infty}(\text{gfp}(EF^*)) = \text{gfp}(PQ^*)$ and $EF^{*\infty}(\text{lfp}(PQ^*)) = \text{lfp}(EF^*)$.

*Proof.* $\forall O \in \mathcal{O}$, $O \preceq \text{gfp}(EF^*)$ (from Property 62), and $PQ^{*\infty}$ is order preserving (Property 60), thus $PQ^{*\infty}(O) \preceq PQ^{*\infty}(\text{gfp}(EF^*))$. Hence, $\forall O \in \text{fp}(PQ^*)$, $O \preceq PQ^{*\infty}(\text{gfp}(EF^*))$. Moreover, $PQ^{*\infty}(\text{gfp}(EF^*)) \in \text{fp}(PQ^*)$, thus $PQ^{*\infty}(\text{gfp}(EF^*)) = \text{gfp}(PQ^*)$.

Similarly, $\forall O \in \mathcal{O}$, $\text{lfp}(PQ^*) \preceq O$ (Property 62), and $EF^{*\infty}$ is order preserving (Property 60), thus $EF^{*\infty}(\text{lfp}(PQ^*)) \preceq EF^{*\infty}(O)$. Hence, $\forall O \in \text{fp}(EF^*)$, $EF^{*\infty}(\text{lfp}(PQ^*)) \preceq O$. Moreover, $EF^{*\infty}(\text{lfp}(PQ^*)) \in \text{fp}(EF^*)$, therefore $EF^{*\infty}(\text{lfp}(PQ^*)) = \text{lfp}(EF^*)$. $\square$

Proposition 72 complements Property 62 for elements of $\text{fp}(EF^*) \cap \text{fp}(PQ^*)$. The elements of $\text{fp}(EF^*) \cap \text{fp}(PQ^*)$ thus belong to the interval $[\text{lfp}(EF^*) \text{ gfp}(PQ^*)]$ (which is more restricted than $[\text{lfp}(PQ^*) \text{ gfp}(EF^*)]$, see Figure 16).

**Proposition 72.** $\forall O \in \text{fp}(EF^*) \cap \text{fp}(PQ^*)$,

$$ \text{lfp}(PQ^*) \preceq \text{lfp}(EF^*) \preceq O \preceq \text{gfp}(PQ^*) \preceq \text{gfp}(EF^*) $$

*Proof.* By Property 71, $PQ^{*\infty}(\text{gfp}(EF^*)) = \text{gfp}(PQ^*)$, but $PQ^*(O) \preceq O$ (Property 53) and $PQ^{*\infty}(O) \preceq PQ^*(O)$ (Property 62), therefore $\text{gfp}(PQ^*) = PQ^{*\infty}(\text{gfp}(EF^*)) \preceq PQ^*(\text{gfp}(EF^*)) \preceq \text{gfp}(EF^*)$. Moreover, by Property 71, $EF^{*\infty}(\text{lfp}(PQ^*)) = \text{lfp}(EF^*)$, but $O \preceq EF^*(O)$ (Property 49) and $EF^*(O) \preceq EF^{*\infty}(O)$ (Property 62), thus $\text{lfp}(PQ^*) \preceq EF^*(\text{lfp}(PQ^*)) \preceq EF^{*\infty}(\text{lfp}(PQ^*)) = \text{lfp}(EF^*)$. Finally, $O \in \text{fp}(EF^*) \cap \text{fp}(PQ^*)$ entails that $\text{lfp}(EF^*) \preceq O$ and $O \preceq \text{gfp}(PQ^*)$. $\square$

It is now possible to prove Proposition 68:

*Proof of Proposition 68.* First, both $\text{lfp}(EF^*_{K^0, R, \Omega})$ and $\text{gfp}(PQ^*_{K^0, R, \Omega})$ are among the acceptable solutions. Indeed, $\text{lfp}(EF^*) = EF^{*\infty}(\text{lfp}(PQ^*))$ (Property 71), but $\text{lfp}(PQ^*) \in \text{fp}(PQ^*)$ thus $EF^{*\infty}(\text{lfp}(PQ^*)) \in \text{fp}(PQ^*)$ (Property 69), hence $\text{lfp}(EF^*) \in \text{fp}(PQ^*)$. The same reasoning can be applied to $\text{gfp}(PQ^*_{K^0, R, \Omega})$ with Property 70.

⇒) Since all acceptable solutions are within the interval between both fixed points (Proposition 72), if these are equal then the interval contains only one object which is the only acceptable solution.

⇔) If there is only one acceptable solution, then $\text{lfp}(EF^*_{K^0, R, \Omega}) = \text{gfp}(PQ^*_{K^0, R, \Omega})$. $\square$

Proposition 72 together with the preamble of the proof of Proposition 68 determine that $[\text{lfp}(EF^*) \text{ gfp}(PQ^*)]$ is the smallest interval in which $\text{fp}(EF^*) \cap \text{fp}(PQ^*)$ is included since its bounds are acceptable solutions. However, acceptable solutions do not cover the whole interval: the converse of Proposition 72 does not hold in general as shown by the counter-example 16.

**Example 16** (Non coverage in RCA). In the example of Section 3.3, $\text{lfp}(EF^*) = \{\langle K_1^1, L_1^1 \rangle, \langle K_2^1, L_2^1 \rangle\}$ and $\text{gfp}(PQ^*) = \{\langle K_1^*, L_1^* \rangle, \langle K_2^*, L_2^* \rangle\}$. The family $\{\langle K_1^#, L_1^# \rangle, \langle K_2^#, L_2^# \rangle\}$ of Figure 8 belongs to $[\text{lfp}(EF^*) \text{ gfp}(PQ^*)]$, but not to $\text{fp}(EF^*) \cap \text{fp}(PQ^*)$ as mentioned in Example 12. Figure 17 shows that 12 out of 16 elements of the interval are in this situation.
The layout of Figures 16 and 18 do not help understanding the situation, but Figure 17 illustrates the presence of non-acceptable objects within the interval.

This interval may be thought of as an approximation of the situation described by the initial context $K^0$. For some purposes, this may be sufficient. However, it may also be interesting to navigate within the set $\mathrm{fp}(EF^*) \cap \mathrm{fp}(PQ^*)$ of fixed points or to compute it.

In order to find the elements of $\mathrm{fp}(EF^*) \cap \mathrm{fp}(PQ^*)$, the closure of $EF^*$ and $PQ^*$, $EF^{*\infty}$ and $PQ^{*\infty}$, can be used as functions which maps elements of $\mathcal{O}$ into families of context-lattice pairs in $\mathrm{fp}(EF^*)$ and $\mathrm{fp}(PQ^*)$, respectively. Moreover, Properties 70 and 69 entail that $PQ^{*\infty} \circ EF^{*\infty}$ and $EF^{*\infty} \circ PQ^{*\infty}$ map any element of $\mathcal{O}$ into an acceptable family of context-lattice pairs in $\mathrm{fp}(EF^*) \cap \mathrm{fp}(PQ^*)$. Hence, the set of acceptable solutions are those elements in the image of $\mathcal{O}$ by the composition of these two closure operations, in any order.

**Property 73.** $\mathrm{Im}(PQ^{*\infty} \circ EF^{*\infty}) = \mathrm{fp}(EF^*) \cap \mathrm{fp}(PQ^*) = \mathrm{Im}(EF^{*\infty} \circ PQ^{*\infty})$.

*Proof.* We show it for $PQ^{*\infty} \circ EF^{*\infty}$, the other part is dual:

$\subseteq$ By definition, $\mathrm{Im}(PQ^{*\infty} \circ EF^{*\infty}) \subseteq \mathrm{Im}(PQ^{*\infty}) = \mathrm{fp}(PQ^*)$. Moreover, $\mathrm{Im}(EF^{*\infty}) = \mathrm{fp}(EF^*)$, but by Property 70, if $O \in \mathrm{fp}(EF^*)$, then $PQ^{*\infty}(O) \in \mathrm{fp}(EF^*)$. Hence, $\mathrm{Im}(PQ^{*\infty} \circ EF^{*\infty}) \subseteq \mathrm{fp}(EF^*) \cap \mathrm{fp}(PQ^*)$.

$\supseteq$ $\forall O \in \mathrm{fp}(PQ^*) \cap \mathrm{fp}(EF^*)$, $O \in \mathrm{fp}(EF^*)$, thus $EF^{*\infty}(O) = O$ and $O \in \mathrm{fp}(PQ^*)$, thus $PQ^{*\infty}(O) = O$. Hence, $O = PQ^{*\infty}(EF^{*\infty}(O)) = PQ^{*\infty} \circ EF^{*\infty}(O) \in \mathrm{Im}(PQ^{*\infty} \circ EF^{*\infty})$ and consequently $\mathrm{fp}(EF^*) \cap \mathrm{fp}(PQ^*) \subseteq \mathrm{Im}(PQ^{*\infty} \circ EF^{*\infty})$. $\square$

In addition, these functions are monotone and idempotent.

**Property 74.** $PQ^{*\infty} \circ EF^{*\infty}$ (resp. $EF^{*\infty} \circ PQ^{*\infty}$) is order-preserving and idempotent:

$$ \forall O, O' \in \mathcal{O}, O \preceq O' \Rightarrow (PQ^{*\infty} \circ EF^{*\infty})(O) \preceq (PQ^{*\infty} \circ EF^{*\infty})(O'), \quad \text{(monotony)} $$

$$ (PQ^{*\infty} \circ EF^{*\infty}) \circ (PQ^{*\infty} \circ EF^{*\infty})(O) = PQ^{*\infty} \circ EF^{*\infty}(O). \quad \text{(idempotence)} $$

*Proof.* We prove it for $PQ^{*\infty} \circ EF^{*\infty}$, the $EF^{*\infty} \circ PQ^{*\infty}$ case is strictly dual.

**monotony** is obtained as the combination of order-preservation of the two functions: $O \preceq O'$, hence $EF^{*\infty}(O) \preceq EF^{*\infty}(O')$, and thus $PQ^{*\infty} \circ EF^{*\infty}(O) \preceq PQ^{*\infty} \circ EF^{*\infty}(O')$ (applying Property 60 twice).

**idempotence** is obtained from Property 73: $\forall O \in \mathcal{O}, PQ^{*\infty} \circ EF^{*\infty}(O) \in \mathrm{fp}(EF^*) \cap \mathrm{fp}(PQ^*)$, hence $PQ^{*\infty} \circ EF^{*\infty}(O) = O$ and $PQ^{*\infty} \circ EF^{*\infty} \circ PQ^{*\infty} \circ EF^{*\infty}(O) = O$, thus $PQ^{*\infty} \circ EF^{*\infty} \circ PQ^{*\infty} \circ EF^{*\infty}(O) = PQ^{*\infty} \circ EF^{*\infty}(O)$. $\square$

The monotony of these functions entails that $\mathrm{fp}(EF^*) \cap \mathrm{fp}(PQ^*)$ is a complete lattice:

**Proposition 75.** $\langle \mathrm{fp}(EF^*) \cap \mathrm{fp}(PQ^*), \preceq \rangle$ is a complete sublattice of $\langle \mathcal{O}, \preceq \rangle$.

*Proof.* $\mathrm{fp}(EF^*) \cap \mathrm{fp}(PQ^*) = \mathrm{Im}(PQ^{*\infty} \circ EF^{*\infty})$ (Property 73) and $\mathrm{Im}(PQ^{*\infty} \circ EF^{*\infty}) = \mathrm{fp}(PQ^{*\infty} \circ EF^{*\infty})$ due to idempotence (Property 74), hence the Knaster-Tarski theorem can be applied based on Property 74 (monotony), concluding that it is a complete lattice. It is included in $\mathcal{O}$, thus this is a sublattice of $\langle \mathcal{O}, \preceq \rangle$. $\square$
<figure><img src="image_25.png" /><figcaption>Figure 16: Illustration of Properties 69, 70, 71, 72, 73, 77 and 78. The figure displays four times $\mathcal{O}$ and the images of gfp$(EF^*)$ (red), a random family of context-lattice pairs (blue) and lfp$(PQ^*) = T^*(K^0)$ (green) through $PQ^{*\infty}$ (left) and $EF^{*\infty}$ (right). fp$(EF^*)$ is drawn in vertical lines; fp$(PQ^*)$ in horizontal lines and the grey area depicts the interval $[lfp(EF^*) \ gfp(PQ^*)]$.</figcaption></figure>
This is illustrated by Example 17.

**Example 17 (Interval lattice).** Figure 17 shows all elements of [lfp(EF*) gfp(PQ*)] for the example of Section 3.3. It can be observed that $\langle \text{fp}(EF^*), \text{fp}(PQ^*), \leq \rangle$ is a proper sublattice of $\emptyset$. Actually only 4 out of 16 possible objects in the interval are acceptable.

In the figure, direct edges corresponding to EF* or PQ*, from lattice pairs of level 2 and 4, are drawn in solid or dashed, respectively. All the objects, of level 3, that are not comparable with the two intermediate fixed points map to the extrema of the interval and thus EF* are PQ* are not displayed.

However, the functions $PQ^{*\infty} \circ EF^{*\infty}$ and $PQ^{*\infty} \circ EF^{*\infty}$ are not necessarily extensive, nor anti-extensive (see Figure 18 and Example 19, p. 74). Hence, they would not be closure operations.

For any family of context-lattice pairs within the fixed points, i.e. $\text{fp}(EF^*)$ or $\text{fp}(PQ^*)$ (the vertically or horizontally stripped area of Figure 18), the two functions are equal.

**Property 76.** $\forall O \in \text{fp}(EF^*) \cup \text{fp}(PQ^*)$, $PQ^{*\infty} \circ EF^{*\infty}(O) = EF^{*\infty} \circ PQ^{*\infty}(O)$.

*Proof.* For any lattice $O$ belonging to $\text{fp}(EF^*) \cap \text{fp}(PQ^*)$, $PQ^*(O) = EF^*(O) = O$, hence $PQ^{*\infty} \circ EF^{*\infty}(O) = EF^{*\infty} \circ PQ^{*\infty}(O) = O$. Similarly, for any lattice $O$ belonging to $\text{fp}(EF^*)$, then $EF^{*\infty}(O) = O$, so $PQ^{*\infty} \circ EF^{*\infty}(O) = PQ^{*\infty}(O)$. However, by Property 69, since $O \in \text{fp}(EF^*)$, $PQ^{*\infty}(O) \in \text{fp}(EF^*)$. This means that $EF^{*\infty} \circ PQ^{*\infty}(O) = PQ^{*\infty}(O)$ as well. The same can be proved for $O \in \text{fp}(PQ^*)$ with Property 70. $\square$

What is actually shown by the proof of Property 76 is that:

$$ \text{if } O \in \text{fp}(EF^*) \text{ then } PQ^{*\infty} \circ EF^{*\infty}(O) = EF^{*\infty} \circ PQ^{*\infty}(O) = PQ^{*\infty}(O), $$

$$ \text{if } O \in \text{fp}(PQ^*) \text{ then } PQ^{*\infty} \circ EF^{*\infty}(O) = EF^{*\infty} \circ PQ^{*\infty}(O) = EF^{*\infty}(O). $$

In particular, this applies to the bounds of $\text{fp}(EF^*) \cup \text{fp}(PQ^*)$:

**Property 77.**

$$ EF^{*\infty} \circ PQ^{*\infty}(\text{gfp}(EF^*)) = PQ^{*\infty} \circ EF^{*\infty}(\text{gfp}(EF^*)) = \text{gfp}(PQ^*), $$

and

$$ PQ^{*\infty} \circ EF^{*\infty}(\text{lfp}(PQ^*)) = EF^{*\infty} \circ PQ^{*\infty}(\text{lfp}(PQ^*)) = \text{lfp}(EF^*). $$

*Proof.* The first part of these equations are consequences of Property 76, since $\text{gfp}(EF^*)$ and $\text{lfp}(PQ^*)$ belong to $\text{fp}(EF^*)$ and $\text{fp}(PQ^*)$, respectively. The second part is due to $PQ^{*\infty} \circ EF^{*\infty}(\text{gfp}(EF^*)) = PQ^{*\infty}(\text{gfp}(EF^*))$ and $EF^{*\infty} \circ PQ^{*\infty}(\text{lfp}(PQ^*)) = EF^{*\infty}(\text{lfp}(PQ^*))$ for the same reason that $\text{gfp}(EF^*) \in \text{fp}(EF^*)$ and $\text{lfp}(PQ^*) \in \text{fp}(PQ^*)$, respectively. Property 71 shows that the second terms correspond to $\text{gfp}(PQ^*)$ and $\text{lfp}(EF^*)$, respectively. $\square$
<figure><img src="image_26.png" /><figcaption>Figure 17: All the families of lattices belonging to [lfp(EF*) gfp(PQ*)] in the example of Section 3.3. Those in fp(EF*) ∩ fp(PQ*) are within solid boxes. As usual, only direct edges are displayed. Solid arrows show direct application of EF* and dashed arrows show direct application of PQ*. Dotted arrows are order relations not corresponding to EF* or PQ* applications.</figcaption></figure>
Examples 18 and 19 show that $EF^{*\infty} \circ PQ^{*\infty}(O^{\#}) \prec O^{\#} \prec PQ^{*\infty} \circ EF^{*\infty}(O^{\#})$
hence that the equality does not hold in general.

**Example 18** (Counterexample to equality in RCA⁰). Consider $O_0^\# = \langle K_0^\#, L_0^\# \rangle$ of Figure 10 (p. 41) in the context of Example 3.2 (p. 25). $O_0^\# \in \mathcal{O}$ because all attributes belong to $M_0^0 \cup D_{\Omega,R,K^0}$ and $L_0^\# = \text{FCA}^*(K_0^\#)$.

In fact, $O_0^\# \in [\text{lfp}(EF^*) \ gfp(PQ^*)] = [\langle K_0^1, L_0^1 \rangle \ \langle K_0^*, L_0^* \rangle]$, but $O_0^\# \not\in \text{fp}(EF^*) \cap \text{fp}(PQ^*)$ as explained in Example 11.

Indeed, applying $EF^{*\infty}$ returns $EF^{*\infty}(O_0^\#)$:

<figure><img src="image_27.png" /></figure>

Applying $PQ^{*\infty}$ returns $PQ^{*\infty}(O_0^\#)$:

<figure><img src="image_28.png" /></figure>

<figure><img src="image_29.png" /></figure>

None of $EF^{*\infty}(O_0^\#)$ nor $PQ^{*\infty}(O_0^\#)$ is a fixed point for $PQ^*$ and $EF^*$, respectively. Indeed, $PQ^{*\infty} \circ EF^{*\infty}(O_0^\#)$ is:

<figure><img src="image_30.png" /></figure>
and $EF^{*\infty} \circ PQ^{*\infty}(O_0^{\#})$:

$$ \frac{k(EF^{*\infty} \circ PQ^{*\infty}(O_0^{\#}))}{\begin{array}{c|c} a & \times \times \\ b & \times \times \\ c & \times \\ d & \times \end{array}} \quad \left| \begin{array}{c} \exists r.AB \\ \exists r.ABCD \end{array} \right. $$

$$ l(EF^{*\infty} \circ PQ^{*\infty}(O_0^{\#})): \left| \begin{array}{c} \exists r.ABCD \\ c, d \\ \exists r.AB \\ a, b \end{array} \right. \quad ABCD $$

Now, $PQ^{*\infty} \circ EF^{*\infty}(O_0^{\#})$ and $EF^{*\infty} \circ PQ^{*\infty}(O_0^{\#})$ belong to $fp(EF^*) \cap fp(PQ^*)$. Yet they are not isomorphic. In fact, $EF^{*\infty} \circ PQ^{*\infty}(O_0^{\#}) \prec PQ^{*\infty} \circ EF^{*\infty}(O_0^{\#})$. This is the result of $\sigma$ which may add needed support (ABD from ABC) and $\pi$ which may suppress unsupported concepts (ABC missing ABD).

**Example 19** (Counterexample to equality in RCA). Consider Example 3.3 (p. 27), $lfp(EF^*) = O_{12}^1 = \{\langle K_1^1, L_1^1 \rangle, \langle K_2^1, L_2^1 \rangle\}$ and $gfp(PQ^*) = O_{12}^* = \{\langle K_1^*, L_1^* \rangle, \langle K_2^*, L_2^* \rangle\}$. $O_{12}^\# = \{\langle K_1^\#, L_1^\# \rangle, \langle K_2^\#, L_2^\# \rangle\}$ belongs to $[lfp(EF^*) \cup gfp(PQ^*)]$ but not to $fp(EF^*) \cap fp(PQ^*)$. It happens that $EF^*(O_{12}^\#) = O_{12}^*$ and $PQ^*(O_{12}^\#) = O_{12}^1$, hence $PQ^{*\infty} \circ EF^{*\infty}(O_{12}^\#) = PQ^* \circ EF^*(O_{12}^\#) = O_{12}^*$ and $EF^{*\infty} \circ PQ^{*\infty}(O_{12}^\#) = EF^* \circ PQ^*(O_{12}^\#) = O_{12}^1$. These two objects are not isomorphic. What can be said, in this case, is that $EF^{*\infty} \circ PQ^{*\infty}(O_{12}^\#) \prec PQ^{*\infty} \circ EF^{*\infty}(O_{12}^\#)$. This is the result of $\sigma$ which may add needed support (for C and B from A and C) and $\pi$ which may suppress unsupported concepts (A missing C and D missing B).

It is not necessary that the results of the closure be the bounds of the interval as is shown for any object of the second and fourth lines of the lattice of Figure 17. Example 18 illustrates this even better.

It may be that, as illustrated by Example 19, when $PQ^{*\infty}$ is first applied, it suppresses non-supported attributes which cannot be recovered by scaling. Conversely, $EF^{*\infty}$ applied first may scale attributes ($\exists p.D$ in Example 19) which generate new concepts (B) supporting previously non-supported concept (D). These will not be suppressed any more.

Property 78 shows that, in addition, there is still a homomorphism between the two resulting objects.

**Property 78.** $\forall O \in \mathcal{O}, EF^{*\infty} \circ PQ^{*\infty}(O) \preceq PQ^{*\infty} \circ EF^{*\infty}(O)$.

*Proof.* $PQ^{*\infty}(O) \preceq O$ by Property 62. But $EF^{*\infty}$ is monotone (Property 60), hence $EF^{*\infty} \circ PQ^{*\infty}(O) \preceq EF^{*\infty}(O)$. $PQ^{*\infty}$ is also monotone (Property 60), thus $PQ^{*\infty} \circ EF^{*\infty} \circ PQ^{*\infty}(O) \preceq PQ^{*\infty} \circ EF^{*\infty}(O)$. However, $PQ^{*\infty} \circ EF^{*\infty}(O) \in fp(EF^*) \cup fp(PQ^*)$ so $PQ^{*\infty} \circ EF^{*\infty}(O) = EF^{*\infty} \circ PQ^{*\infty}(O)$ (Property 76). Thus, $PQ^{*\infty} \circ EF^{*\infty} \circ PQ^{*\infty}(O) = EF^{*\infty} \circ PQ^{*\infty} \circ PQ^{*\infty}(O) = EF^{*\infty} \circ PQ^{*\infty}(O)$. This means that $EF^{*\infty} \circ PQ^{*\infty}(O) \preceq PQ^{*\infty} \circ EF^{*\infty}(O)$. $\square$
<figure><img src="image_31.png" /><figcaption>Figure 18: Illustration of the position of $PQ^{*\infty} \circ EF^{*\infty}(O)$ and $EF^{*\infty} \circ PQ^{*\infty}(O)$ depending on $O$'s origin (in dotted, $\mathcal{O}$, in dashed $fp(EF^*) \cup fp(PQ^*)$, in plain $fp(EF^*) \cap fp(PQ^*)$). Colours correspond to that of Figure 16: green starting from $fp(EF^*)$, red starting from $fp(PQ^*)$, blue starting outside of them.</figcaption></figure>

*Alternative proof.* The same reasoning can be held from $O \preceq EF^{*\infty}(O)$ (Property 62) and $EF^{*\infty}$ and $PQ^{*\infty}$ being monotone (Property 60). Hence, $PQ^{*\infty}(O) \preceq PQ^{*\infty} \circ EF^{*\infty}(O)$ and $EF^{*\infty} \circ PQ^{*\infty}(O) \preceq EF^{*\infty} \circ PQ^{*\infty} \circ EF^{*\infty}(O)$. But, $PQ^{*\infty} \circ EF^{*\infty}(O) \in fp(EF^*) \cup fp(PQ^*)$, so $PQ^{*\infty} \circ EF^{*\infty}(O) = EF^{*\infty} \circ PQ^{*\infty}(O)$ (Property 76). Thus $EF^{*\infty} \circ PQ^{*\infty} \circ EF^{*\infty}(O) = PQ^{*\infty} \circ EF^{*\infty} \circ EF^{*\infty}(O) = PQ^{*\infty} \circ EF^{*\infty}(O)$. Hence, $EF^{*\infty} \circ PQ^{*\infty}(O) \preceq PQ^{*\infty} \circ EF^{*\infty}(O)$. $\square$

The alternative proof is given here to show that starting from the $EF^*$ or $PQ^*$ give the same result.

It is thus unclear what to do with $EF^{*\infty} \circ PQ^{*\infty}$ and $PQ^{*\infty} \circ EF^{*\infty}$ in general. For instance, if one needs an operation to map elements of $\mathcal{O}$ to $fp(EF^*) \cap fp(PQ^*)$, which one is preferable? There may be an interest in studying the interval $[EF^{*\infty} \circ PQ^{*\infty}(O) \preceq PQ^{*\infty} \circ EF^{*\infty}(O)]$. Does it contain only fixed points or no fixed points? Are these the image of other lattices? This question can be answered if $O$ can be compared to these bounds (Proposition 79): the intermediate families are *not* fixed points.

**Proposition 79.** $\forall O \in \mathcal{O} \setminus (fp(EF^*) \cap fp(PQ^*))$:

- if $O \preceq PQ^{*\infty} \circ EF^{*\infty}(O)$, then $\forall O' \in [O \sqsubseteq PQ^{*\infty} \circ EF^{*\infty}(O)][O' \notin fp(EF^*) \cap fp(PQ^*)]$,

- if $EF^{*\infty} \circ PQ^{*\infty}(O) \preceq O$, then $\forall O' \in ]EF^{*\infty} \circ PQ^{*\infty}(O) [O']$, $O' \notin fp(EF^*) \cap fp(PQ^*)$.
*Proof.* Considering the first item of the proposition, $O \preceq PQ^{*\infty} \circ EF^{*\infty}(O)$ can only occur if $EF^{*\infty}(O) \in \text{fp}(PQ^*)$, i.e. $PQ^{*\infty} \circ EF^{*\infty}(O) = EF^{*\infty}(O)$. Indeed, if this were not the case, then $PQ^{*\infty}$ would suppress attributes from $EF^{*\infty}(O)$. However, since $O \preceq PQ^{*\infty} \circ EF^{*\infty}(O)$, these could not be attributes from $O$, but only attributes added by $EF^{*\infty}$. But since $EF^{*\infty}$ only adds attributes if they are supported and it starts with attributes from $O$, this is not possible. Thus, if $O' \in [O PQ^{*\infty} \circ EF^{*\infty}(O)][$ then $O' \in [O EF^{*\infty}(O)][$. However, $O'$ cannot be a fixed point for $EF^*$ because it contains all attributes of $O$ which would scale to generate all those of $EF^{*\infty}(O)$. Hence $O' \notin \text{fp}(EF^*) \cap \text{fp}(PQ^*)$.

The second item has a similar proof: $EF^{*\infty} \circ PQ^{*\infty}(O) \preceq O$ can only occur if $PQ^{*\infty}(O) \in \text{fp}(EF^*)$, i.e. $EF^{*\infty} \circ PQ^{*\infty}(O) = PQ^{*\infty}(O)$. Indeed, if this were not the case, then $EF^{*\infty}$ would generate attributes from $PQ^{*\infty}(O)$. However, since $EF^{*\infty} \circ PQ^{*\infty}(O) \preceq O$, these could only be attributes of $O$ which were suppressed by $PQ^{*\infty}$ due to lack of support. But this is not possible because if they lacked support in $O$, there is not more support for them in $PQ^{*\infty}(O)$, which only reduces $O$. Thus, if $O' \in ]EF^{*\infty} \circ PQ^{*\infty}(O) O]$, then $O' \in ]PQ^{*\infty}(O) O]$. However, $O'$ cannot be a fixed point for $PQ^*$ because it contains less attributes than $O$: if these attributes lacked supports in $O$, they would still lack it in $O'$. Hence, $O' \notin \text{fp}(EF^*) \cap \text{fp}(PQ^*)$. $\square$

This is illustrated by Example 20:

**Example 20.** In Example 19 (p. 74), $O_{34}^{\#} = \{\langle K_3^{\#}, L_3^{\#} \rangle, \langle K_4^{\#}, L_4^{\#} \rangle\}$ is a fixed point for neither $EF^*$ nor $PQ^*$. $PQ^{*\infty} \circ EF^{*\infty}(O_{34}^{\#}) = EF^{*\infty}(O_{34}^{\#}) = O_{34}^{*}$ and $EF^{*\infty} \circ PQ^{*\infty}(O_{34}^{\#}) = PQ^{*\infty}(O_{34}^{\#}) = O_{34}^{1}$. None of the objects in the interval between $O_{34}^{\#}$ and either $O_{34}^{*}$ or $O_{34}^{1}$ belongs to $\text{fp}(EF^*) \cap \text{fp}(PQ^*)$ as can be seen in Figure 17.

This result cannot be generalised to the interval $]EF^{*\infty} \circ PQ^{*\infty}(O) PQ^{*\infty} \circ EF^{*\infty}(O)][$ as shown by Example 21 and Example 22.

**Example 21** (The subinterval may contain fixed points in RCA). Following Example 20, $O'_{34} = \{\langle K'_3, L'_3 \rangle, \langle K'_4, L'_4 \rangle\}$ belongs to $]EF^{*\infty} \circ PQ^{*\infty}(O_{34}^{\#}) PQ^{*\infty} \circ EF^{*\infty}(O_{34}^{\#})[ = ]O_{34}^{1}, O_{34}^{*}[ $ as can be observed in Figure 17. However, $O'_{34} \in \text{fp}(EF^*) \cap \text{fp}(PQ^*)$.

**Example 22** (The subinterval may contain fixed points in RCA$^0$). The family of context-lattice pairs $O_0^{\#}$ of Example 18 (p. 73), is such that: (a) $EF^{*\infty}(O_0^{\#}) \neq PQ^{*\infty} \circ EF^{*\infty}(O_0^{\#})$, (b) $PQ^{*\infty}(O_0^{\#}) \neq EF^{*\infty} \circ PQ^{*\infty}(O_0^{\#})$, and (c) $EF^{*\infty} \circ PQ^{*\infty}(O_0^{\#}) \prec PQ^{*\infty} \circ EF^{*\infty}(O_0^{\#})$.

Note that none of $EF^{*\infty} \circ PQ^{*\infty}(O_0^{\#})$ nor $PQ^{*\infty} \circ EF^{*\infty}(O_0^{\#})$ are the bounds of $\text{fp}(EF^*) \cap \text{fp}(PQ^*)$ ($O_0^{1}$ and $O_0^{*}$) contrary to Example 21.

Moreover, consider $O_0''$ defined as follows:
<figure><img src="image_32.png" /></figure>

$O_0'' \in ]EF^{*\infty} \circ PQ^{*\infty}(O_0^{\#}), PQ^{*\infty} \circ EF^{*\infty}(O_0^{\#})[ \text{ and } O_0'' \in \text{fp}(EF^*) \cap \text{fp}(PQ^*)$.

This counter-example is not sensible to conditions (a) and (b) above: (a) can be relaxed, by simply adding $\exists r.ABCD$ to $K_0^{\#}$, (b) can be relaxed by suppressing $\exists r.B$ from $K_0^{\#}$, and both can be relaxed together. In each of these cases, $EF^{*\infty} \circ PQ^{*\infty}(O_0^{\#})$ and $PQ^{*\infty} \circ EF^{*\infty}(O_0^{\#})$ will not be changed, preventing to discard the presence of acceptable solutions $(O_0'')$ in the interval.

Proposition 79 can however be useful algorithmically. Indeed, if one considers the non-acceptable objects of Figure 17 on the same line as $O_{34}^{\#}$, then this result identifies as non acceptable two objects on the second and fourth line without testing them.

# 9 Conclusion

We addressed the questions of which family of concept lattices was returned by relational concept analysis and, more generally, which such families could be considered acceptable.

This report provides an answer to these questions by characterising the acceptable families of context-lattice pairs that describe a particular initial family of contexts as those families which are well-formed, saturated and self-supported. It identifies the results returned by relational concept analysis as the smallest element of this set. It also defines an alternative operation providing its greatest elements. The structure of the set of acceptable solutions has been further characterised.

To that extent the report defines the set of well-formed objects $\mathcal{O}$, a function $EF^*$, generalising RCA, expanding a family, and a function $PQ^*$ contracting a family. The fixed points of these functions characterise the saturated families and the self-supported families respectively. Hence, the acceptable solutions are those elements of the intersection of the fixed points of both functions ($\text{fp}(EF^*) \cap \text{fp}(PQ^*)$).

These results rely fundamentally on the finiteness of the structure and monotony of the operations. Dealing with infinite structures would jeopardise the construction of the sets of scalable relational attributes (Section 2.4.1), however as soon as the termination of the application of the operations is preserved, this should not be a problem. Non-monotonic operations could be induced by non-monotonic scaling operations. Such operations would prevent relational concept analysis to work properly and would require fully different mechanisms.