# the_fixedpoint_semantics_of_relational_concept_analysis__ef09bcf7.pdf

The Fixed-Point Semantics of Relational Concept Analysis

JÉRÔME EUZENAT, Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, F-38000 Grenoble, France

Background: 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. Objectives: This paper aims at defining precisely the semantics of RCA and identifying alternative solutions. Methods: We first characterise the 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. In this context, the acceptable solutions are the common fixed points of both functions. Results: 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.

JAIR Associate Editor: Ivan José Varzinczak

JAIR Reference Format: Jérôme Euzenat. 2025. The Fixed-Point Semantics of Relational Concept Analysis. Journal of Artificial Intelligence Research 83, Article 1 (June 2025), 38 pages. doi: 10.1613/jair.1.17882

1 Introduction Formal concept analysis (FCA) is a well-defined and widely used operation for extracting concept lattices from binary data tables [16]. 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.

Author s Contact Information: Jérôme Euzenat, orcid: 0000-0002-5014-4411, Jerome.Euzenat@inria.fr, Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, F-38000 Grenoble, Grenoble, France.

This work is licensed under a Creative Commons Attribution International 4.0 License.

2025 Copyright held by the owner/author(s). doi: 10.1613/jair.1.17882

Journal of Artificial Intelligence Research, Vol.83, Article 1. Publication date: June 2025.

1:2 Euzenat

Formal concept analysis has been put to work in a variety of applications [15, 22], 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 [26]. 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 theses 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 [19], it has been generalised to more varied description logic constructors [26]. Relational concept analysis has been used for instance for analysing the ecological and sanitary quality of water courses [24]. 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 [1].

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 paper 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

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

The Fixed-Point Semantics of Relational Concept Analysis 1:3

developers add artificial identifiers in their data in order to constrain the returned solution to include more concepts [8, 6].

To understand why such concepts are not provided, and which concepts are returned by RCA, this paper questions its semantics. The semantics of relational concept analysis has, so far, been provided in a rather operational way [27]. 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 paper 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 28): 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 29). 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 30). The structure of the set of fixed points is further characterised to support algorithmic developments.

This paper extends the results obtained for the RCA0 restriction of RCA [10], which contains a single formal context, hence a single concept lattice, and no attribute, only relations. In spite of the simplicity of RCA0, the main arguments of this work were already present and it remains a good introduction to the considered problems. A specific research report [11] builds on the results established in [10] and extends them step-by-step to RCA. It also explains the legacy names used here for functions. The present paper offers a direct and more synthetic formulation of the fixed-point semantics of RCA and the space of alternative acceptable solutions. We first present the work on which this one builds (relational concept analysis) and relevant related work (Section 2). Then, simple examples are provided to illustrate that relational concept analysis may accept concept lattices which are not those provided by the RCA operation (Section 3). In order to determine which could be the acceptable solutions of relational concept analysis, Section 4 circumscribes the space of objects that it considers. Two functions, an expansive function, corresponding to the operations of RCA, and a contractive function, aiming at finding self-supported solutions, are defined on this space (Section 5). The fixed points of these functions are discussed leading to a redefinition of acceptable solutions as those objects of the space which are fixed points for both functions (Section 6). In consequence, solutions returned by RCA are precisely characterised as the smallest acceptable solution, a dual operation returning the greatest acceptable solution can be defined, and the structure of the set of acceptable solutions is investigated (Section 7).

2 Preliminaries and Related Work We mix preliminaries with related work for reasons of space, but also because the paper directly builds on this related work.

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

1:4 Euzenat

2.1 Basics of Formal Concept Analysis

This paper relies only on the most basic results of formal concept analysis expressed as order-preserving functions. Formal Concept Analysis (FCA) [16] starts with a formal context (hereafter context) 𝐺, 𝑀, 𝐼 such that 𝐺 denotes a set of objects, 𝑀a set of attributes, and 𝐼 𝐺 𝑀a binary relation between 𝐺and 𝑀, called the incidence relation. The statement 𝑔𝐼𝑚is interpreted as object𝑔has attribute𝑚 , also noted𝑚(𝑔). Two operators

and define a Galois connection between the powersets 2𝐺, and 2𝑀, , with 𝐴 𝐺and 𝐵 𝑀:

𝐴 = {𝑚 𝑀| 𝑔𝐼𝑚for all 𝑔 𝐴},

𝐵 = {𝑔 𝐺| 𝑔𝐼𝑚for all 𝑚 𝐵}.

The operators and are decreasing, i.e. if 𝐴1 𝐴2 then 𝐴 2 𝐴 1 and if 𝐵1 𝐵2 then 𝐵 2 𝐵 1. 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 𝐴 𝐴 and that 𝐵 𝐵 , that 𝐴 = 𝐴 and that 𝐵 = 𝐵 . A pair 𝐴, 𝐵 2𝐺 2𝑀, such that 𝐴 = 𝐵and 𝐵 = 𝐴, is called a formal concept (hereafter concept), where 𝐴= 𝑒𝑥𝑡𝑒𝑛𝑡( 𝐴, 𝐵 ) is the extent and 𝐵= 𝑖𝑛𝑡𝑒𝑛𝑡( 𝐴, 𝐵 ) the intent of 𝐴, 𝐵 . Moreover, for a formal concept 𝐴, 𝐵 , 𝐴and 𝐵are closed for the closure operations and , respectively, i.e. 𝐴 = 𝐴and 𝐵 = 𝐵. Concepts are partially ordered by 𝐴1, 𝐵1 𝐴2, 𝐵2 𝐴1 𝐴2 or equivalently 𝐵2 𝐵1. With respect to this partial order, the set of all formal concepts is a complete lattice called the concept lattice of 𝐺, 𝑀, 𝐼 . It has for supremum the concept = 𝐺,𝐺 and for infimum the concept = 𝑀 , 𝑀 .

Example 1 (Formal concept analysis). Starting from a context 𝐾0 1 = 𝐺1, 𝑀0 1, 𝐼0 1 with 𝐺1 = {𝑎,𝑏,𝑐}, 𝑀0 1 = {𝑚1,𝑚2,𝑚3} and 𝐼0 1 as the incidence relation whose table is given below, the application of FCA results in the lattice made of the concepts 𝐴𝐵𝐶, 𝐴𝐵, 𝐶and as:

𝐾0 1 𝑚1 𝑚2 𝑚3 𝑎 𝑏 𝑐

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 intents 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, 𝐴𝐵𝐶= {𝑎,𝑏,𝑐}, and = , {𝑚1,𝑚2,𝑚3} .

Formal concept analysis can be considered as a function that associates to a context 𝐺, 𝑀, 𝐼 its concept lattice 𝐶, = FCA( 𝐺, 𝑀, 𝐼 ) (or 𝔅(𝐺, 𝑀, 𝐼) [16]). This is illustrated by Example 1. By abuse of language, when a variable 𝐿denotes a concept lattice 𝐶, , 𝐿will also be used to denote 𝐶. The concepts that can be created from a context can be identified by their extent. Hence, 𝜂( 𝐺, 𝑀, 𝐼 ) = 2𝐺

is the set of all concept names that may be used in any such concept lattice1. 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 𝐿= FCA(𝐾), the subset 𝜂(𝐿) of 𝜂(𝐾) is the set of names of concepts in this lattice according to this convention as illustrated in Example 2.

1A similar remark is made in [29, 4.1.2].

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

The Fixed-Point Semantics of Relational Concept Analysis 1:5

Example 2 (Concept names). Consider the context 𝐾0 1 of Example 1. The set of objects of 𝐾0 1 being 𝐺1 = {𝑎,𝑏,𝑐}, the set of concept names that can be created for them in any concept lattice is 𝜂(𝐾0 1) = {𝐴𝐵𝐶,𝐴𝐵,𝐴𝐶, 𝐵𝐶,𝐴, 𝐵,𝐶, }. In the specific lattice obtained in Example 1, the set of concept names is 𝜂(𝐿0 1) = {𝐴𝐵𝐶,𝐴𝐵,𝐶, }. Throughout the paper, 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.

2.2.1 Scaling: a Generalisation. Scaling is one kind of extension of type (𝑎). It is a way to encode a more complex structure Σ into FCA. For that purpose, a scaling operation 𝜍determines a set 𝐷𝜍,Σ of Boolean attributes to be added to a context 𝐾from a structure Σ. In scaled contexts, these attributes can be interpreted so that the incidence relation 𝐼is immediately derived from the attribute 𝑚 𝐷𝜍,Σ following:

Σ |= 𝑔𝐼𝑚or Σ |= 𝑚(𝑔).

Hence, adding attributes 𝑀 to a context under such a structure Σ consists of adding the attributes and extending the incidence relation according to this interpretation. It may be performed as:

KΣ +𝑀 ( 𝐺, 𝑀, 𝐼 ) = 𝐺, 𝑀 𝑀 , 𝐼 { 𝑔,𝑚 𝐺 𝑀 | Σ |= 𝑚(𝑔)} ,

and suppressing them as:

KΣ 𝑀 ( 𝐺, 𝑀, 𝐼 ) = 𝐺, 𝑀\ 𝑀 , 𝐼\ { 𝑔,𝑚 𝐺 𝑀 } .

Applying a scaling operation 𝜍to a context 𝐾following a structure Σ can thus be decomposed into (i) determining the set of attributes 𝐷𝜍,Σ to add, and (ii) extending the context with these attributes:

𝜎𝜍(𝐾, Σ) = KΣ +𝐷𝜍,Σ (𝐾).

This unified view of scaling may be applied to many available scaling operations, including the initial conceptual scaling [16] and logical scaling [25]. RCA relies on relational scaling.

2.2.2 Relational Scaling. Relational scaling operations (𝜍) considered in [26] create relational attributes from a binary relation 𝑟 𝐺 𝐺 between two sets of objects 𝐺= dom(𝑟) and 𝐺 = cod(𝑟) and a concept lattice 𝐿 on 𝐺 . 𝜍(𝑟,𝑐) provides the syntactic form of the attribute. For example, qualified existential scaling (𝜍= ) is expressed by (𝑟,𝑐) = 𝑟.𝑐. 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 employer.School may be scaled and holds for all people employed by a school. Thus, the set of qualified existential attributes are:

𝐷 , 𝑟,𝐿 = { 𝑟.𝑐| 𝑐 𝜂(𝐿)}.

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

𝑟, 𝐿 |= 𝑔𝐼 𝑟.𝑐iff 𝑔 ; 𝑔,𝑔 𝑟 𝑔 𝑒𝑥𝑡𝑒𝑛𝑡(𝑐).

This is illustrated in Example 3.

Example 3 (Relational scaling). Consider that the relation 𝑞is given by the table:

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

1:6 Euzenat

between 𝐺1 = {𝑎,𝑏,𝑐} and 𝐺2 = {𝑑,𝑒, 𝑓} and consider the concept lattice 𝐿0 1 corresponding to the context 𝐾0 1 of Example 1. The concepts in 𝐿0 1 have names in 𝜂(𝐿0 1) = {𝐴𝐵𝐶,𝐴𝐵,𝐶, } (Example 2) hence scaling by 𝜎 will provide the attribute set { 𝑞.𝐴𝐵𝐶, 𝑞.𝐴𝐵, 𝑞.𝐶, 𝑞. }. The description of the relation 𝑞allows to uncover the incidence relation for these (the incidence relation for is always empty for so never displayed in the examples):

If, in addition, the context 𝐾0 2 of 𝐺2 had two other attributes 𝑛1 and 𝑛2 whose incidence relation is given as 𝐼0 2 displayed below, then the scaling operation would correspond to:

𝐾0 2 𝑛1 𝑛2 𝑑 𝑒 𝑓

When generating relational attributes, scaling only relies on the names of the concepts in 𝐿. It is thus possible to define the sets of attributes from the set of names. The set of relational attributes that can be scaled from 𝜍and 𝑟against a set of concept of names 𝑁is 𝐷𝜍,𝑟,𝑁= {𝜍(𝑟,𝑐) | 𝑐 𝑁}. This can be used with 𝜂(𝐿), i.e. the names of concepts actually in 𝐿, or with 𝜂(𝐾), i.e. the names of all possible concepts to be generated from a context 𝐾. Example 4 illustrates this.

Example 4 (Set of relational attributes). For the context 𝐾0 2 of Example 3, if there is only one relation 𝑞, whose codomain is 𝐾0 1 of Example 1, and the existential scaling operation , then the set of possibly scalable relational attributes is: 𝐷 ,𝑞,𝜂(𝐾0 1 ) = { 𝑞.𝐴𝐵𝐶, 𝑞.𝐴𝐵, 𝑞.𝐴𝐶, 𝑞.𝐵𝐶, 𝑞.𝐴, 𝑞.𝐵, 𝑞.𝐶, 𝑞. }.

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

𝐷 ,𝑞,𝜂(𝐿0 1) = { 𝑞.𝐴𝐵𝐶, 𝑞.𝐴𝐵, 𝑞.𝐶, 𝑞. }.

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 [3] under the closed-world assumption (see Table 1). The set of relational attributes obtained from a relation 𝑟by relational scaling may be large but remains finite as long as 𝐺 = cod(𝑟) is finite. Cardinality constraints, relying on integers, may entail infinite sets of concepts in theory, but in practice, when 𝐺 is finite, the set of meaningful cardinality attributes is bounded by |𝐺 |. 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 [6, 1, 29].

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

The Fixed-Point Semantics of Relational Concept Analysis 1:7

Table 1. Relational scaling operations (inspired from [26, 6]) and additional link key condition scaling operations [1].

name language (𝐷) Σ condition (𝑚(𝑔))

existential 𝑟 𝑅 𝑟(𝑔) universal (wide) 𝑟.𝑐 𝑅, 𝐿 𝑟(𝑔) 𝑒𝑥𝑡𝑒𝑛𝑡(𝑐) strict universal 𝑟.𝑐 𝑅, 𝐿 𝑟(𝑔) 𝑟(𝑔) 𝑒𝑥𝑡𝑒𝑛𝑡(𝑐) contains (wide) 𝑐.𝑟 𝑅, 𝐿 𝑒𝑥𝑡𝑒𝑛𝑡(𝑐) 𝑟(𝑔) strict contains 𝑐.𝑟 𝑅, 𝐿 𝑒𝑥𝑡𝑒𝑛𝑡(𝑐) 𝑒𝑥𝑡𝑒𝑛𝑡(𝑐) 𝑟(𝑔) qualified existential 𝑟.𝑐 𝑅, 𝐿 𝑟(𝑔) 𝑒𝑥𝑡𝑒𝑛𝑡(𝑐) qualified min cardinality 𝑛𝑟.𝑐 𝑅, 𝐿 |𝑟(𝑔) 𝑒𝑥𝑡𝑒𝑛𝑡(𝑐)| 𝑛 qualified max cardinality 𝑛𝑟.𝑐 𝑅, 𝐿 |𝑟(𝑔) 𝑒𝑥𝑡𝑒𝑛𝑡(𝑐)| 𝑛 -condition 𝑟,𝑟 𝑘 𝑅 𝑅 , 𝐿𝐶 𝐶 𝑟(𝑔) =𝑘𝑟 (𝑔 ) -condition 𝑟,𝑟 𝑘 𝑅 𝑅 , 𝐿𝐶 𝐶 𝑟(𝑔) 𝑘𝑟 (𝑔 )

2.3 Other Extensions

There are other extensions [7, 13, 14] providing formal concept analysis with more expressiveness in the expression of intents without scaling (type 𝑏extension). Instead of scaling, they change the structure of the set of attributes, staying within the scope of Galois lattices. However, these extensions are not directly affected by the problem of context dependencies considered here as the attributes do not refer to concepts. On the contrary, other approaches [21, 12] aim at extracting conceptual structures from 𝑛-ary relations without resorting 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 [12] the incidence relation is a hypergraph between objects, and produce more expressive representations. A comparison of RCA and Graph-FCA is provided in [20]. 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. Finally, description logic base mining [4, 18] 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, where description logic base mining does not introduce new names but uses new concept descriptions inspired from Duquenne-Guigues implication bases [17]. Where, in Example 3, relational scaling would use attribute 𝑞.𝐴𝐵, base mining would use the description 𝑞. 𝑚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 EL𝑔𝑓𝑝. However, led by complexity considerations, work has focused on extracting minimal bases in EL through unravelling [4, 18]. The problem raised in this paper 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) [26] extends FCA to the processing of relational datasets and allows interobject relations to be materialised and incorporated into formal concept intents. It may also be thought of as a general way to deal with circular references using different scaling operations.

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

1:8 Euzenat

RCA applies

a set of relational scaling operations Ω on a family of contexts 𝐾0 = { 𝐺𝑥, 𝑀0 𝑥, 𝐼0 𝑥 }𝑥 𝑋indexed by a finite set 𝑋, such that, if 𝑥 𝑧, 𝐺𝑥 𝐺𝑧= , and a finite set of binary relations 𝑅, i.e. relations 𝑟 𝐺𝑥 𝐺𝑧(with 𝑥,𝑧 𝑋). 𝐾0, 𝑅 is called a relational context2. Each context of the family 𝐾𝑡may be abbreviated as 𝐾𝑡 𝑥= 𝐺𝑥, 𝑀𝑡 𝑥, 𝐼𝑡 𝑥 . The use of the ordinal superscript 𝑡will become clearer in a few lines and can be ignored at that stage. We note 𝑅𝑥= {𝑟 𝑅| dom(𝑟) = 𝐺𝑥} and 𝑅𝑥,𝑧= {𝑟 𝑅𝑥| cod(𝑟) = 𝐺𝑧}.

2.4.1 Concept Names and Relational Attributes. The notation used for expressing sets of relational attributes can be generalised. For RCA, 𝜂 (𝐾0) = {𝜂(𝐾0 𝑥)}𝑥 𝑋is the indexed set of all concept names induced from all contexts in 𝐾0. Similarly, for an indexed set of concept lattices 𝐿= {𝐿𝑥}𝑥 𝑋, 𝜂 (𝐿) = {𝜂(𝐿𝑥)}𝑥 𝑋. Then, given a set of relational scaling operations Ω, a set of relations 𝑅, the set of scalable relational attributes for a concept with respect to an indexed family of sets of concept names 𝑁is:

𝑟 𝑅𝑥,𝑧 𝐷𝜍,𝑟,𝑁𝑧.

This notation is used for identifying the relational attributes that can be scaled for a context 𝐾𝑥from a set of concept lattices: 𝐷Ω,𝑅𝑥,𝐿= 𝐷Ω,𝑅𝑥,𝜂 (𝐿), or the set of all the possible relational attributes that can be scaled for a context 𝐾𝑥given a family of formal contexts 𝐾0 as 𝐷Ω,𝑅𝑥,𝐾0 = 𝐷Ω,𝑅𝑥,𝜂 (𝐾0).

Since 𝑧 𝑋, 𝜂(𝐿𝑧) 𝜂(𝐾0 𝑧), then 𝐷Ω,𝑅𝑥,{𝐿𝑧}𝑧 𝑋 𝐷Ω,𝑅𝑥,𝐾0. This is illustrated by Example 5.

Example 5 (Set of relational attributes (cont d)). Following Example 4, if 𝐾0 2, whose objects are {𝑑,𝑒, 𝑓}, is also linked to itself (𝐾0 2) by the relation 𝑠and the current set of concept names is 𝜂(𝐿0 2) = {𝐷𝐸𝐹, 𝐷𝐸, 𝐸}, then it would additionally scale the relational attributes: 𝐷{ },{𝑠},{𝐿0 2 } = 𝐷 ,𝑠,𝜂(𝐿0 2) = { 𝑠.𝐷𝐸𝐹, 𝑠.𝐷𝐸, 𝑠.𝐸}. If, in addition, the strict contains scaling operation ( 𝐶.𝑟, see Table 1) is used, then new relational attributes would be:

𝐷{ , },{𝑞,𝑠},{𝐿0 1,𝐿0 2 } = { 𝑞.𝐴𝐵𝐶, 𝑞.𝐴𝐵, 𝑞.𝐶, 𝑞. , 𝑠.𝐷𝐸𝐹, 𝑠.𝐷𝐸, 𝑠.𝐸,

𝐴𝐵𝐶.𝑞, 𝐴𝐵.𝑞, 𝐶.𝑞, .𝑞, 𝐷𝐸𝐹.𝑠, 𝐷𝐸.𝑠, 𝐸.𝑠}.

The semantics of these attributes is provided in the same way as above and noted 𝑅, 𝐿 |= 𝑔𝐼𝜍(𝑟,𝑐).

2.4.2 Operations and Algorithm. Hereafter, we will consider relational scaling with the structure Σ = 𝑅, 𝐿 made of a set of binary relations 𝑅between two sets of objects from 𝐾0, and a family 𝐿𝑡= {𝐿𝑡 𝑥}𝑥 𝑋of concept lattices obtained from 𝐾𝑡. RCA applies relational scaling operations from a set Ω to each 𝐾𝑡 𝑥 𝐾𝑡and all relations 𝑟 𝑅𝑥,𝑧from the set of concepts in the corresponding 𝐿𝑡 𝑧= FCA(𝐾𝑡 𝑧). Such scaling is defined as:

𝜎Ω(𝐾𝑥, 𝑅, 𝐿) = K 𝑅,𝐿 +𝐷Ω,𝑅𝑥,𝐿(𝐾𝑥).

The classical RCA algorithm, that is called here RCA, thus relies on FCA and 𝜎Ω. More precisely, it applies these in parallel on all contexts. Hence, FCA and 𝜎 Ω are defined as:

FCA ({𝐾𝑥}𝑥 𝑋) = {FCA(𝐾𝑥)}𝑥 𝑋,

𝜎 Ω({𝐾𝑥}𝑥 𝑋, 𝑅, 𝐿) = {𝜎Ω(𝐾𝑥, 𝑅, 𝐿)}𝑥 𝑋.

2We use the term relational context instead of relational context family .

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

The Fixed-Point Semantics of Relational Concept Analysis 1:9

such that 𝐿is a family of concept lattices. The whole family of concepts lattices needs to be passed to 𝜎. RCA starts from the initial family of contexts 𝐾0 and iterates the application of the two operations:

𝐾𝑡+1 = 𝜎 Ω(𝐾𝑡, 𝑅, FCA (𝐾𝑡))

until reaching a fixed point, i.e. reaching 𝑛such that 𝐾𝑛+1 = 𝐾𝑛. Then, RCAΩ(𝐾0, 𝑅) = FCA (𝐾𝑛). Thus, the RCA algorithm proceeds in the following way: (1) Initial contexts: 𝑡 0; { 𝐺𝑥, 𝑀𝑡 𝑥, 𝐼𝑡 𝑥 }𝑥 𝑋 { 𝐺𝑥, 𝑀𝑥, 𝐼𝑥 }𝑥 𝑋. (2) {𝐿𝑡 𝑥}𝑥 𝑋 FCA ({ 𝐺𝑥, 𝑀𝑡 𝑥, 𝐼𝑡 𝑥 }𝑥 𝑋) (or, for each context, 𝐺𝑥, 𝑀𝑡 𝑥, 𝐼𝑡 𝑥 the corresponding concept lattice 𝐿𝑡 𝑥= FCA( 𝐺𝑥, 𝑀𝑡 𝑥, 𝐼𝑡 𝑥 ) is created using FCA). (3) { 𝐺𝑥, 𝑀𝑡+1 𝑥 , 𝐼𝑡+1 𝑥 }𝑥 𝑋 𝜎 Ω({ 𝐺𝑥, 𝑀𝑡 𝑥, 𝐼𝑡 𝑥 }𝑥 𝑋, 𝑅, {𝐿𝑡 𝑥}𝑥 𝑋) (i.e. relational scaling is applied, for each relation 𝑟whose codomain lattice has new concepts, generating new contexts 𝐺𝑥, 𝑀𝑡+1 𝑥 , 𝐼𝑡+1 𝑥 including both plain and relational attributes in 𝑀𝑡+1 𝑥 ). (4) If 𝑥 𝑋such that 𝑀𝑡+1 𝑥 𝑀𝑡 𝑥(scaling has occurred), then 𝑡 𝑡+ 1; go to Step 2. (5) Return {𝐿𝑡 𝑥}𝑥 𝑋. This is illustrated by Example 6.

Example 6 (Relational concept analysis). Consider two relations 𝑝and 𝑞defined as:

and applying on the contexts 𝐾0 1 of Example 1 and 𝐾0 2 of Example 3 (Figure 1). Applying FCA to the two contexts 𝐾0 1 and 𝐾0 2, provides the very simple lattices 𝐿0 1 and 𝐿0 2 of Figure 1 with concepts 𝐴𝐵𝐶, 𝐴𝐵, 𝐶and , and 𝐷𝐸𝐹, 𝐷𝐸and 𝐸, respectively. Applying scaling, as seen partially in Example 3, provides the context 𝐾1 1 with new attributes 𝑝.𝐷𝐸𝐹, 𝑝.𝐷𝐸, 𝑝.𝐸and 𝐾1 2 with 𝑞.𝐴𝐵𝐶, 𝑞.𝐴𝐵, 𝑞.𝐶(Example 4). Applying FCA to these contexts provides the lattices 𝐿1 1 and 𝐿1 2 with additional concepts 𝐵and 𝐹. These can in turn go through scaling and unveil new attributes 𝑝.𝐹and 𝑞.𝐵added to 𝐾1 1 and 𝐾1 2 to give 𝐾2 1 and 𝐾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 {𝐿2 1, 𝐿2 2}. The result is thus quite different from the {𝐿0 1, 𝐿0 2} that would have been returned by FCA alone.

2.4.3 Properties and Semantics. A context 𝐾= 𝐺, 𝑀, 𝐼 is a subcontext of another 𝐾 = 𝐺 , 𝑀 , 𝐼 whenever 𝐺 𝐺 , 𝑀 𝑀 and 𝐼= 𝐼 (𝐺 𝑀) [16, 3.1]. By abuse of notation, this is noted 𝐾 𝐾 . This is generalised to families of contexts {𝐾𝑥}𝑥 𝑋 {𝐾 𝑥}𝑥 𝑋whenever 𝑥 𝑋, 𝐾𝑥 𝐾 𝑥. RCA always reaches a closed family of contexts for reason of finiteness [26] and the sequence (𝐾𝑡)𝑛 𝑡=0 is non-(intent-)contracting, i.e. 𝑡 0, 𝐾𝑡 𝐾𝑡+1 [27]. The RCA semantics characterises the set of concepts in resulting RCA lattices as all and only those concepts grounded on the initial family (𝐾0) based on relations (𝑅) [27]. This can thus be considered as a well-grounded semantics: an attribute is scaled and applied to an object at iteration 𝑡+ 1 only if its condition applies at stage 𝑡. Hence, everything is ultimately relying on 𝐾0. [27] established that RCA indeed finds the 𝐾𝑛satisfying these constraints through correctness (the concepts of FCA (𝐾𝑛) are grounded in 𝐾0 through 𝑅) and completeness (all so-grounded concepts are in 𝐾𝑛).

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

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

1:10 Euzenat

𝐾0 1 𝑚1 𝑚2 𝑚3 𝑎 𝑏 𝑐

𝐾0 2 𝑛1 𝑛2 𝑑 𝑒 𝑓

Fig. 1. The three iterations of RCA from the initial contexts 𝐾0 1 and 𝐾0 2.

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 paper is related to the circular dependencies, i.e. the circuits, that may exist within these graphs. 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.

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

The Fixed-Point Semantics of Relational Concept Analysis 1:11

3 Motivating Examples

In order to illustrate the weakness of the RCA semantics, we first carry on the introductory Examples 1 6 ( 3.1). We then display it on a more minimal example that will be carried over the paper ( 3.2). 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 6 (Figure 1) does not present a result in which each object is identified by a single class. Indeed, 𝑎has not more attributes than 𝑏. This result could also be obtained with far more objects 𝑎 , 𝑎 , etc. sharing the attributes of 𝑎and 𝑏, or duplicating other objects. However, the lattices 𝐿 1 and 𝐿 2 displayed in Figure 2 seem another good way to describe the data given as input to RCA. There is in fact an objective difference between 𝐴𝐶and 𝐵𝐶: 𝐴𝐶denotes all objects connected by 𝑝 to 𝐷𝐹and 𝐵𝐶all objects connected by 𝑝to 𝐸𝐹. Reciprocally, 𝐷𝐹denotes all objects connected by 𝑞to 𝐴𝐶and 𝐸𝐹 those connected by 𝑞to 𝐵𝐶.

𝐾 1 𝑚1 𝑚2 𝑚3

𝑚2, 𝑝.𝐷𝐸 𝑝.𝐷𝐹 𝑝.𝐸𝐹

𝑛1, 𝑝.𝐴𝐵 𝑝.𝐴𝐶 𝑝.𝐵𝐶

Fig. 2. Alternative concept lattices for the example of Section 3.1 ( is simply a way to identify these objects).

These lattices share many common points with those returned by RCA: they are also (i) valid concept lattices, (ii) whose contexts extend 𝐾0 1 and 𝐾0 2 with attributes of 𝐷{ },{𝑝},𝐾0 and 𝐷{ },{𝑞},𝐾0 (Example 4), (iii) stable for scaling, and (iv) such that each attribute refers only to concepts in the lattices. The only difference with 𝐿2 1 and 𝐿2 2 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 𝑅, why does RCA only returns one of these, and which one? To help answering this question, we illustrate the problem with a minimal running example below.

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

1:12 Euzenat

3.2 Minimal RCA Example As another example, consider the following two empty contexts 𝐾0 3 and 𝐾0 4 of Figure 4 and the two relations 𝑝 and 𝑞of Figure 3.

Fig. 3. Relations 𝑝and 𝑞for RCA.

Applying FCA to the two contexts 𝐾0 3 and 𝐾0 4 provides the very simple lattices 𝐿0 3 and 𝐿0 4 of Figure 4. From this, RCA generates new context 𝐾1 3 and 𝐾1 4 through scaling which provides new lattices 𝐿1 3 and 𝐿1 4 (Figure 4).

𝐾0 4 𝑐 𝑑 𝑎,𝑏 𝐴𝐵 𝐿0 3: 𝑐,𝑑 𝐶𝐷 𝐿0 4:

Fig. 4. The two iterations of RCA from the initial contexts 𝐾0 3 and 𝐾0 4.

The lattices 𝐿1 3 and 𝐿1 4 of Figure 4 are those returned by RCA as applying scaling from them returns the same contexts 𝐾1 3 and 𝐾1 4. However, there could be other acceptable solutions such as those displayed in Figure 5. They are all acceptable solutions for {𝐾0 3, 𝐾0 4 } (Figure 4) as they satisfy the four conditions of Section 3.1. On the contrary, Figure 6 displays a family of concept lattices {𝐿# 3, 𝐿# 4} which is not an acceptable solution. Although they contain all concepts of {𝐿0 3, 𝐿0 4} and no concept not in {𝐿 3 , 𝐿 4 }, they would generate more attributes through scaling and applying RCA to their contexts {𝐾# 3, 𝐾# 4 } would lead to {𝐿 3 , 𝐿 4 } 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.

We will thus redefine the objects on which RCA operates ( 4), precising well-formedness, and introduce two functions on this space ( 5) from whose fixed points acceptability can be defined ( 6), offering a fixed-point semantics for relational concept analysis ( 7).

4 Dual Context-Lattice Space 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: 𝐾0 = { 𝐺𝑥, 𝑀0 𝑥, 𝐼0 𝑥 }𝑥 𝑋, 𝑅, and Ω. Through the application of 𝑅𝐶𝐴, only 𝑀𝑡 𝑥and 𝐼𝑡 𝑥change, hence the other may remain implicit.

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

The Fixed-Point Semantics of Relational Concept Analysis 1:13

Fig. 5. Alternative pairs of concept lattices covering the contexts of Figure 4.

Fig. 6. A family of concept lattices {𝐿# 3, 𝐿# 4} which is not an acceptable solution.

These objects are introduced progressively by considering in a row: contexts ( 4.1), lattices ( 4.2), context-lattice pairs ( 4.3) and indexed families of context-lattice pairs ( 4.4). The first three subsections will only consider one context 𝐾𝑥, one concept lattice 𝐿𝑥and one context-lattice pair 𝑇𝑥at a time; the fourth section will consider them together. Hereafter, we use a simple and regular notation: 𝐾denotes contexts, 𝐿lattices, 𝑇context-lattice pairs and 𝑂families of context-lattice pairs. In addition, 𝑅is used for relations, 𝑁for names and 𝐷for attributes. Greek letters are devoted to some auxiliary functions (𝜂, 𝜅, 𝜎, 𝜋). 𝐸, 𝐹, 𝑃and 𝑄are used for functions names and is used for distinguishing the parallel application of such functions.

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

1:14 Euzenat

4.1 The Space of Contexts 𝒦 We first study the semantics of RCA from the standpoint of the contexts. The contexts considered by RCA are scaled from an initial context using the scaling operations. Property 1 highlights that the incidence of the scaled attributes does only depend on the relation and not on the concept lattices.

Property 1 (The incidence relation depends only on the attributes). Given a set Ω of relational scaling operations, a family 𝐾= { 𝐺𝑥, 𝑀𝑥, 𝐼𝑥 }𝑥 𝑋of formal contexts and a set 𝑅of relations on 𝐾. Given 𝐿𝑧and 𝐿 𝑧two concept lattices on 𝐺𝑧, for all scaled attributes 𝑚 𝐷Ω,𝑅𝑥,𝑧,𝐿𝑧 𝐷Ω,𝑅𝑥,𝑧,𝐿 𝑧, 𝑔 𝐺𝑥, 𝑅, 𝐿𝑧 |= 𝑚(𝑔) if and only if 𝑅, 𝐿 𝑧 |= 𝑚(𝑔).

Proof. 𝑚= 𝜍(𝑟,𝑐) is scaled from a scaling operation 𝜍, a relation 𝑟and a concept 𝑐(possibly a cardinal 𝑛). From Table 1, 𝑅, 𝐿𝑧 |= 𝑔𝐼𝑚only depends on 𝜍, 𝑟and the extent of 𝑐. However, 𝜍and 𝑟are independent from 𝐿𝑧 and 𝐿 𝑧. The concept 𝑐is identified by a name which denotes its extent. Hence, its extent is the same in 𝐿𝑧and 𝐿 𝑧. So whether an object of 𝑔 𝐺𝑥satisfies the attribute 𝜍(𝑟,𝑐) or not depends solely on the attribute 𝜍(𝑟,𝑐) and not on the specific lattice considered.

This means that the interpretation of an attribute never changes: it is given by its syntactic form 𝜍(𝑟,𝑐) and, in particular, the concept name. Hence, when adding or suppressing attributes, through KΣ +𝑀or KΣ 𝑀, Σ can be 𝑅, 𝑁 with 𝑁an indexed set of names, and in particular 𝜂 (𝐾0). In RCA, the set of objects 𝐺𝑥does not change and for any object and attribute, either the object satisfies the attribute or not. Property 1 entails that, if 𝑀𝑥 𝑀 𝑥, then 𝐼𝑥 𝐼 𝑥. 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 𝑀𝑥 𝑀 𝑥, then 𝐾𝑥 𝐾 𝑥. The attribute language 𝐷Ω,𝑅𝑥,𝑁that can be generated by scaling depends on the finite set of relations 𝑅, the scaling operations Ω and the set of possible concepts identified by their standardised names ( 2.2.2 and 2.4.1). Given 𝑁 𝜂 (𝐾0) an indexed family of names of concepts that can be in the codomain of relations in 𝑅, the set of contexts that can be obtained by scaling is

𝒦𝑁 𝐾0𝑥,𝑅,Ω = {K 𝑅,𝜂 (𝐾0) +𝑀 (𝐾0 𝑥) | 𝑀 𝐷Ω,𝑅𝑥,𝑁}

with K 𝑅,𝜂 (𝐾0) +𝑀 (.) the operation defined in 2.2. Passing 𝜂 (𝐾0) to K allows to interpret the generated attributes and to determine 𝐼. Below, when we write 𝒦𝑁, the property applies for any {𝑁𝑥}𝑥 𝑋such that 𝑥 𝑋, 𝑁𝑥 𝜂(𝐾0 𝑥), and in particular for 𝜂 (𝐾0). We can define two operations, and on 𝒦𝑁 𝐾0𝑥,𝑅,Ω.

Definition 1 (Meet and join of contexts). Given 𝐾, 𝐾 𝒦𝑁 𝐺,𝑀0,𝐼0 ,𝑅,Ω, such that 𝐾= 𝐺, 𝑀0 𝑀, 𝐼0 𝐼 and 𝐾 = 𝐺, 𝑀0 𝑀 , 𝐼0 𝐼 , 𝐾 𝐾 and 𝐾 𝐾 are defined as:

𝐾 𝐾 = 𝐺, 𝑀0 (𝑀 𝑀 ), 𝐼0 (𝐼 𝐼 ) , (join)

𝐾 𝐾 = 𝐺, 𝑀0 (𝑀 𝑀 ), 𝐼0 (𝐼 𝐼 ) . (meet)

The set of contexts is closed by meet and join.

Property 2 ([10]). 𝐾, 𝐾 𝒦𝑁 𝐾0𝑥,𝑅,Ω, 𝐾 𝐾 𝒦𝑁 𝐾0𝑥,𝑅,Ω and 𝐾 𝐾 𝒦𝑁 𝐾0𝑥,𝑅,Ω.

Proof. Meet and join are defined from the union and intersection of subsets of 𝐷Ω,𝑅𝑥,𝐾0 (Definition 1). But 𝒦𝑁 𝐾0𝑥,𝑅,Ω is closed by union and intersection of the sets of attributes to add to 𝑀0 and the incidence relation is

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

The Fixed-Point Semantics of Relational Concept Analysis 1:15

fully determined by the set of attributes (Property 1). Hence, meet and join of contexts in 𝒦𝑁 𝐾0𝑥,𝑅,Ω belong to

𝒦𝑁 𝐾0𝑥,𝑅,Ω.

4.2 The Space of Lattices ℒ

From 𝒦𝑁 𝐾0𝑥,𝑅,Ω, one can define ℒ𝑁 𝐾0𝑥,𝑅,Ω as the set of images of 𝒦𝑁 𝐾0𝑥,𝑅,Ω by FCA. These are concept lattices obtained

by applying FCA on 𝐾0 𝑥extended with a subset of 𝐷Ω,𝑅𝑥,𝑁:

ℒ𝑁 𝐾0𝑥,𝑅,Ω = {FCA(𝐾 𝑅,𝜂 (𝐾0) +𝑀 (𝐾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 ℒ𝐾0𝑥,𝑅,Ω and 𝒦𝐾0𝑥,𝑅,Ω [16, 1.2]. On the one hand, to any context in 𝒦𝐾0𝑥,𝑅,Ω corresponds only one lattice by FCA. On the other hand, to any concept lattice 𝐶, ℒ𝐾0𝑥,𝑅,Ω corresponds a formal context:

𝜅( 𝐶, ) = Ø

𝑐 𝐶 𝑒𝑥𝑡𝑒𝑛𝑡(𝑐), Ø

𝑐 𝐶 𝑖𝑛𝑡𝑒𝑛𝑡(𝑐), Ø

𝑐 𝐶 𝑒𝑥𝑡𝑒𝑛𝑡(𝑐) 𝑖𝑛𝑡𝑒𝑛𝑡(𝑐) .

𝜅(𝐿) collects the attributes and objects present in 𝐿intents to build the unique 𝑀and 𝐺, from which the corresponding 𝐼is obtained. It is such that FCA 𝜅= 𝑖𝑑𝒦and 𝜅 FCA = 𝑖𝑑ℒ(𝑖𝑑𝒦and 𝑖𝑑ℒbeing the respective identity functions). This may be stated as:

Property 3. 𝐾= 𝜅(𝐿) iff 𝐿= FCA(𝐾).

Proof. ) 𝐾= 𝐺, 𝑀, 𝐼 = Ð 𝑐 𝐶𝑒𝑥𝑡𝑒𝑛𝑡(𝑐), Ð 𝑐 𝐶𝑖𝑛𝑡𝑒𝑛𝑡(𝑐), Ð 𝑐 𝐶𝑒𝑥𝑡𝑒𝑛𝑡(𝑐) 𝑖𝑛𝑡𝑒𝑛𝑡(𝑐) = 𝜅( 𝐶, ) = 𝜅(𝐿). This means that 𝐶, is the concept lattice of a context 𝐺 , 𝑀 , 𝐼 . But since 𝐺= Ð 𝑐 𝐶𝑒𝑥𝑡𝑒𝑛𝑡(𝑐) and 𝑀= Ð 𝑐 𝐶𝑖𝑛𝑡𝑒𝑛𝑡(𝑐), then 𝐺= 𝐺 and 𝑀= 𝑀 . We need to prove that 𝐼= 𝐼 . Consider 𝐼 𝐼 , this could be because there exists at least one 𝑔 𝐺and 𝑚 𝑀such that 𝑔,𝑚 𝐼\ 𝐼 (or, but not exclusively, 𝑔,𝑚 𝐼 \ 𝐼). In this condition, there could not exists 𝑐 𝐶such that 𝑔 𝑒𝑥𝑡𝑒𝑛𝑡(𝑐) and 𝑚 𝑖𝑛𝑡𝑒𝑛𝑡(𝑐) (resp. it exists). Then 𝑔,𝑚 Ð 𝑐 𝐶𝑒𝑥𝑡𝑒𝑛𝑡(𝑐) 𝑖𝑛𝑡𝑒𝑛𝑡(𝑐) (resp. on the contrary it is there) and thus 𝐼 Ð 𝑐 𝐶𝑒𝑥𝑡𝑒𝑛𝑡(𝑐) 𝑖𝑛𝑡𝑒𝑛𝑡(𝑐) which contradicts 𝐺, 𝑀, 𝐼 = 𝜅( 𝐶, ). Hence, 𝐼= 𝐼 and 𝐿= 𝐶, = FCA( 𝐺, 𝑀, 𝐼 ) = FCA(𝐾)

) 𝐿= 𝐶, = FCA( 𝐺, 𝑀, 𝐼 ) = FCA(𝐾) entails 𝑐 𝐶, 𝑔 𝑒𝑥𝑡𝑒𝑛𝑡(𝑐), 𝑚 𝑖𝑛𝑡𝑒𝑛𝑡(𝑐), 𝑔𝐼𝑚, i.e. 𝑒𝑥𝑡𝑒𝑛𝑡(𝑐) 𝑖𝑛𝑡𝑒𝑛𝑡(𝑐) 𝐼. In addition, if 𝑔𝐼𝑚, then there exists 𝑐 FCA( 𝐺, 𝑀, 𝐼 ) = 𝐶, such that 𝑔 𝑒𝑥𝑡𝑒𝑛𝑡(𝑐) and 𝑚 𝑖𝑛𝑡𝑒𝑛𝑡(𝑐), thus 𝐼 Ð 𝑐 𝐶𝑒𝑥𝑡𝑒𝑛𝑡(𝑐) 𝑖𝑛𝑡𝑒𝑛𝑡(𝑐). Moreover, = 𝐺,𝐺 𝐶and = 𝑀 , 𝑀 𝐶, hence Ð 𝑐 𝐶𝑒𝑥𝑡𝑒𝑛𝑡(𝑐) = 𝐺and Ð 𝑐 𝐶𝑖𝑛𝑡𝑒𝑛𝑡(𝑐) = 𝑀. Thus 𝐾= 𝐺, 𝑀, 𝐼 = Ð 𝑐 𝐶𝑒𝑥𝑡𝑒𝑛𝑡(𝑐), Ð 𝑐 𝐶𝑖𝑛𝑡𝑒𝑛𝑡(𝑐), Ð 𝑐 𝐶𝑒𝑥𝑡𝑒𝑛𝑡(𝑐) 𝑖𝑛𝑡𝑒𝑛𝑡(𝑐) = 𝜅(𝐿).

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 intent3.

Definition 2 (Lattice homomorphism [10]). A concept lattice homomorphism ℎ: 𝐶, 𝐶 , is a function which maps each concept 𝑐 𝐶into a corresponding concept ℎ(𝑐) 𝐶 such that:

𝑐 𝐶, 𝑖𝑛𝑡𝑒𝑛𝑡(𝑐) 𝑖𝑛𝑡𝑒𝑛𝑡(ℎ(𝑐)), 𝑐 𝐶, 𝑒𝑥𝑡𝑒𝑛𝑡(𝑐) = 𝑒𝑥𝑡𝑒𝑛𝑡(ℎ(𝑐)), and 𝑐,𝑑 𝐶, 𝑐 𝑑 ℎ(𝑐) ℎ(𝑐).

3The results in the remainder of this section are specific to RCA: is defined with the equality of extents and depends only on 𝑀because 𝐺is always the same.

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

1:16 Euzenat

We note 𝐿 𝐿 if there exists a homomorphism from 𝐿to 𝐿 . In principle, 𝐿 𝐿 if 𝐿 𝐿 and 𝐿 𝐿, but here, is simply =. This owes to the fact that the 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 4 (FCA is monotone). 𝐾= 𝐺, 𝑀, 𝐼 and 𝐾 = 𝐺, 𝑀 , 𝐼 ,

𝐾 𝐾 FCA(𝐾) FCA(𝐾 ).

Proof. Any concept 𝑐 FCA(𝐾) characterises a set of objects 𝑒𝑥𝑡𝑒𝑛𝑡(𝑐) by the set of attributes 𝑖𝑛𝑡𝑒𝑛𝑡(𝑐) that these objects are the only ones to satisfy. Since both contexts have the same set of objects 𝐺, there are not more objects satisfying these in 𝐾 and since 𝑀 𝑀 these attributes are still in 𝐾 , thus 𝑐 FCA(𝐾 ). Hence, it is always possible to define ℎsuch as ℎ(𝑐) = 𝑐. Then 𝑒𝑥𝑡𝑒𝑛𝑡(ℎ(𝑐)) = 𝑒𝑥𝑡𝑒𝑛𝑡(𝑐) and 𝑖𝑛𝑡𝑒𝑛𝑡(ℎ(𝑐)) 𝑖𝑛𝑡𝑒𝑛𝑡(𝑐). Moreover, if 𝑐 𝑑, then ℎ(𝑐) ℎ(𝑑) because 𝑒𝑥𝑡𝑒𝑛𝑡(𝑐) 𝑒𝑥𝑡𝑒𝑛𝑡(𝑑) entails 𝑒𝑥𝑡𝑒𝑛𝑡(ℎ(𝑐)) 𝑒𝑥𝑡𝑒𝑛𝑡(ℎ(𝑑)). Hence, FCA(𝐾) FCA(𝐾 ) (Definition 2).

If 𝐾 𝐾 , then each concept that can be built from 𝐾can be built from 𝐾 . The additional attributes in 𝑀 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. We can define and on ℒ𝑁 𝐾0𝑥,𝑅,Ω from the corresponding operators in 𝒦𝑁 𝐾0𝑥,𝑅,Ω.

Definition 3 (Meet and join of lattices). Given 𝐿, 𝐿 ℒ𝑁 𝐾0𝑥,𝑅,Ω,

𝐿 𝐿 = FCA(𝜅(𝐿) 𝜅(𝐿 )), (join)

𝐿 𝐿 = FCA(𝜅(𝐿) 𝜅(𝐿 )). (meet)

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

Property 5. 𝐿, 𝐿 ℒ𝑁 𝐾0𝑥,𝑅,Ω, 𝐿 𝐿 ℒ𝑁 𝐾0𝑥,𝑅,Ω and 𝐿 𝐿 ℒ𝑁 𝐾0𝑥,𝑅,Ω.

Proof. ℒ𝑁 𝐾0𝑥,𝑅,Ω is closed by meet and join since 𝒦𝑁 𝐾0𝑥,𝑅,Ω is closed by meet and join (Property 2) and ℒ𝑁 𝐾0𝑥,𝑅,Ω is

the image of 𝒦𝑁 𝐾0𝑥,𝑅,Ω by FCA.

4.3 The Lattice 𝒯of Context-Lattice Pairs Although 𝒦𝑁and ℒ𝑁have been presented independently, it is useful to consider the two sets together as, in RCA, lattices in ℒ𝑁are an intermediate result of the process which is used for computing the next contexts. 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. From any context in 𝒦, it is possible to generate a context-lattice pair using FCA. The T constructor does this.

Definition 4 (T constructor). Given a context 𝐾 𝒦𝑁, T : 𝒦𝑁 𝒦𝑁 ℒ𝑁generates a context-lattice pair, such that: T(𝐾) = 𝐾, FCA(𝐾) .

We consider the set 𝒯𝑁 𝐾0𝑥,𝑅,Ω of pairs in 𝒦𝑁 𝐾0𝑥,𝑅,Ω ℒ𝑁 𝐾0𝑥,𝑅,Ω such that:

𝒯𝑁 𝐾0𝑥,𝑅,Ω = { 𝐾, 𝐿 𝒦𝑁 𝐾0𝑥,𝑅,Ω ℒ𝑁 𝐾0𝑥,𝑅,Ω|𝐿= FCA(𝐾)}.

This set is well defined because 𝒦𝑁 𝐾0𝑥,𝑅,Ω has already been defined and ℒ𝑁 𝐾0𝑥,𝑅,Ω are precisely those lattices obtained

by FCA from an element of 𝒦𝑁 𝐾0𝑥,𝑅,Ω.

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

The Fixed-Point Semantics of Relational Concept Analysis 1:17

Alternatively, using Property 3, it can be defined from 𝜅:

𝒯𝑁 𝐾0𝑥,𝑅,Ω = { 𝐾, 𝐿 𝒦𝑁 𝐾0𝑥,𝑅,Ω ℒ𝑁 𝐾0𝑥,𝑅,Ω|𝐾= 𝜅(𝐿)}.

As before, we use 𝒯𝐾0𝑥,𝑅,Ω = 𝒯𝜂 (𝐾0) 𝐾0𝑥,𝑅,Ω and, for any 𝐾, 𝐿 𝒯𝑁 𝐾0𝑥,𝑅,Ω we note:

𝑘( 𝐾, 𝐿 ) = 𝐾,

𝑙( 𝐾, 𝐿 ) = 𝐿.

It is possible to define the meet and join:

Definition 5 (Meet and join of context-lattice pairs). Given𝑇,𝑇 𝒯𝑁 𝐾0𝑥,𝑅,Ω 𝑇 𝑇 and𝑇 𝑇 are defined as:

𝑇 𝑇 = T(𝑘(𝑇) 𝑘(𝑇 )), (join)

𝑇 𝑇 = T(𝑘(𝑇) 𝑘(𝑇 )). (meet)

As this definition makes clear, the operations of 𝒯𝑁only depend on the context part. But the usual relations with the meet and join on contexts and lattices are preserved:

Property 6.

𝑇 𝑇 = 𝑘(𝑇) 𝑘(𝑇 ),𝑙(𝑇) 𝑙(𝑇 ) ,

𝑇 𝑇 = 𝑘(𝑇) 𝑘(𝑇 ),𝑙(𝑇) 𝑙(𝑇 ) .

Proof. This is a simple consequence on the definition of conjunction and disjunction on context-lattice pairs (Definition 4) and lattices (Definition 3) as:

𝐿 𝐿 = FCA(𝐾 𝐾 ), (join)

𝐿 𝐿 = FCA(𝐾 𝐾 ). (meet)

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

Property 7. 𝑇,𝑇 𝒯𝑁 𝐾0𝑥,𝑅,Ω, 𝑇 𝑇 𝒯𝑁 𝐾0𝑥,𝑅,Ω and 𝑇 𝑇 𝒯𝑁 𝐾0𝑥,𝑅,Ω.

Proof. 𝒯𝑁 𝐾0𝑥,𝑅,Ω is closed by meet and join because it is based on T (Definition 5), T builds a context-lattice pair

in 𝒯𝑁 𝐾0𝑥,𝑅,Ω from contexts in 𝒦𝑁 𝐾0𝑥,𝑅,Ω (Definition 4), and 𝒦𝑁 𝐾0𝑥,𝑅,Ω itself is closed by meet and join (Property 2).

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

Definition 6 (Order). Given 𝑇, 𝑇 𝒯𝑁 𝐾0𝑥,𝑅,Ω,

𝑇 𝑇 if 𝑘(𝑇) 𝑘(𝑇 ) and 𝑙(𝑇) 𝑙(𝑇 ).

Figure 7 presents the relations between 𝒦𝑁, ℒ𝑁and 𝒯𝑁and their respective orders. Since FCA is monotone (Property 4), 𝑇 𝑇 iff 𝑘(𝑇) 𝑘(𝑇 ). Like before, we note 𝑇 𝑇 if 𝑇 𝑇 and 𝑇 𝑇, and again is =. This can be applied to the T constructor.

Property 8. 𝐾, 𝐾 𝒦𝑁 𝐾0𝑥,𝑅,Ω, 𝐾 𝐾 iff T(𝐾) T(𝐾 ).

Proof. ( ) This is due to monotony of FCA (Property 4). 𝑘(T(𝐾)) = 𝐾 𝐾 = 𝑘(T(𝐾 )) means that 𝑙(T(𝐾)) = FCA(𝐾) FCA(𝐾 ) = 𝑙(T(𝐾 )). Thus, T(𝐾) T(𝐾 ). ( ) T(𝐾) T(𝐾 ) entails, by Definition 6, that 𝐾 𝐾 .

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

1:18 Euzenat

𝑘(𝑇 ) 𝑙(𝑇 )

Fig. 7. Relations between 𝒯, 𝒦and ℒ.

This has the consequence that 𝑇= 𝑇 if and only if 𝑘(𝑇) = 𝑘(𝑇 ). 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.

4.4 The Lattice 𝒪of Families of Context-Lattice Pairs

So far, we have only considered one context independently from the others. We now consider relational concept analysis 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 𝑋. 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. The only important change is that 𝑁will be frozen to the set of concept names in all the different contexts in 𝐾0. The input of RCA is given by a family of contexts: 𝐾0 = {𝐾0 𝑥}𝑥 𝑋, a set 𝑅of relations between the objects of these contexts, and a set Ω of relational scaling operations. From this, it is possible to characterise the space 𝒪𝐾0,𝑅,Ω associated with RCA by the direct product of the sets of context-lattice pairs associated with each context.

Definition 7 (𝒪𝐾0,𝑅,Ω). Given an indexed family of contexts 𝐾0 = { 𝐺𝑥, 𝑀0 𝑥, 𝐼0 𝑥 }𝑥 𝑋, a set 𝑅of relations between the objects of these contexts, and a set Ω of relational scaling operations, the space 𝒪𝐾0,𝑅,Ω of indexed families of context-lattice pairs is:

𝒪𝐾0,𝑅,Ω = Ö

𝑥 𝑋 𝒯𝜂 (𝐾0) 𝐾0𝑥,𝑅,Ω .

As usual, 𝒪𝐾0,𝑅,Ω will simply be referred to as 𝒪. 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 𝜂 (𝐾0), 𝑅and Ω do not change and 𝐼is determined by {𝑀𝑥}𝑥 𝑋(Property 1), this determines all attributes that can occur in a scaled RCA context. Contrary to RCA0 [10], the scaled attributes depend on 𝑅that makes the connection from one context to another, e.g. from 𝒯𝑥to 𝒯𝑧. But since it is possible to name concepts in the lattices generated by the scaled

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

The Fixed-Point Semantics of Relational Concept Analysis 1:19

attributes according to their elements in 𝐺𝑧, then, as soon as 𝐺𝑧is finite, the set of scalable attributes in 𝑀𝑥is finite and can be established as 𝐷Ω,𝑅𝑥,𝐾0 from the beginning. The previous notations can be extended:

T ({𝐾𝑥}𝑥 𝑋) = {T(𝐾𝑥)}𝑥 𝑋= { 𝐾𝑥, FCA(𝐾𝑥) }𝑥 𝑋.

For any {𝑇𝑥}𝑥 𝑋 𝒪𝐾0,𝑅,Ω:

𝑘({𝑇𝑥}𝑥 𝑋) = {𝑘(𝑇𝑥)}𝑥 𝑋,

𝑙({𝑇𝑥}𝑥 𝑋) = {𝑙(𝑇𝑥)}𝑥 𝑋,

𝑘𝑧({𝑇𝑥}𝑥 𝑋) = 𝑘(𝑇𝑧),

𝑙𝑧({𝑇𝑥}𝑥 𝑋) = 𝑙(𝑇𝑧).

Finally, for any indexed family of context-lattice pairs 𝑂 𝒪, the family of lattices 𝑙(𝑂) is determined directly from 𝑘(𝑂): 𝑙(𝑂) = FCA (𝑘(𝑂)). We can define and on 𝒪𝐾0,𝑅,Ω.

Definition 8 (Meet and join of families of context-lattice pairs). Given 𝑂= {𝑇𝑥}𝑥 𝑋, 𝑂 = {𝑇 𝑥}𝑥 𝑋 𝒪𝐾0,𝑅,Ω, 𝑂 𝑂 and 𝑂 𝑂 are defined as:

𝑂 𝑂 = {𝑇𝑥 𝑇 𝑥}𝑥 𝑋, (join)

𝑂 𝑂 = {𝑇𝑥 𝑇 𝑥}𝑥 𝑋. (meet)

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

Property 9. 𝑂,𝑂 𝒪𝑁 𝐾0,𝑅,Ω, 𝑂 𝑂 𝒪𝑁 𝐾0,𝑅,Ω and 𝑂 𝑂 𝒪𝑁 𝐾0,𝑅,Ω.

Proof. 𝒪𝐾0,𝑅,Ω is closed by meet and join because meet and join are the piecewise meet and join of context-

lattice pairs (Definition 8) and for each 𝑥 𝑋, 𝒯𝜂 (𝐾0) 𝐾0𝑥,𝑅,Ω is closed by meet and join (Property 7).

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

Definition 9 (Order). Given 𝑂= {𝑇𝑥}𝑥 𝑋, 𝑂 = {𝑇 𝑥}𝑥 𝑋 𝒪𝐾0,𝑅,Ω,

𝑂 𝑂 if 𝑥 𝑋,𝑇𝑥 𝑇 𝑥.

Like before, we note 𝑂 𝑂 if 𝑂 𝑂 and 𝑂 𝑂, and again is =. Property 8 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 10. 𝑂,𝑂 𝒪𝐾0,𝑅,Ω, if 𝑘(𝑂) 𝑘(𝑂 ) then 𝑂 𝑂 .

Proof. 𝑘(𝑂) 𝑘(𝑂 ) means that 𝑥 𝑋,𝑘𝑥(𝑂) 𝑘𝑥(𝑂 ) which is equivalent, by Property 8, to 𝑘𝑥(𝑂),𝑙𝑥(𝑂) 𝑘𝑥(𝑂 ),𝑙𝑥(𝑂 ) and hence 𝑂 𝑂 (Definition 9).

Finally, the set 𝒪𝐾0,𝑅,Ω of families of context-lattice pairs is a complete lattice.

Proposition 11. 𝒪𝐾0,𝑅,Ω, , is a complete lattice.

Proof. 𝒪𝐾0,𝑅,Ω is closed by meet and join (Property 9). The commutativity, associativity and the absorption law of and ultimately rely on these properties holding for the same operators on contexts. They are satisfied because these are properties of union and intersection on sets. Hence, 𝒪𝐾0,𝑅,Ω, , is a lattice. It is complete because and are well-defined (Definition 8) and 𝑆 𝒪, 𝑂 𝑆, Ó 𝑂 𝑆𝑂 𝑂 Ô 𝑂 𝑆𝑂 (due to the completeness of powerset lattices which apply to those of attributes).

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

1:20 Euzenat

The set 𝒪of families of context-lattice pairs arguably contains all possible solutions that can be returned by relational concept analysis. However, they have been defined on independent contexts, taking into account the scalable attributes but not the coherence between the considered concepts. This will now be achieved through specific functions.

5 A Functional Standpoint on RCA Here we adopt a functional standpoint on operations on the space of families of context-lattice pairs. We first define an expansion function 𝐸𝐹 which corresponds to the internal operations of RCA ( 5.1). We then consider the notion of support which eliminates potential solutions referring to non-available concepts ( 5.2). This allows us to define a contraction function reducing the non-supported part of a family of context-lattice pairs ( 5.3).

5.1 The Expansion Function 𝐸𝐹

The solutions are now characterised as elements of 𝒪𝐾0,𝑅,Ω. In the following, a function on this set is defined to reformulate RCA. This is 𝐸𝐹 𝐾0,𝑅,Ω, the expansion function attached to a relational context 𝐾0, 𝑅 and a set Ω of scaling operations.

Definition 10 (Expansion function). Given a relational context 𝐾0, 𝑅 and a set Ω of relational scaling operations, the expansion function 𝐸𝐹 𝐾0,𝑅,Ω : 𝒪𝐾0,𝑅,Ω 𝒪𝐾0,𝑅,Ω is defined by:

𝐸𝐹 𝐾0,𝑅,Ω(𝑂) = T (𝜎 Ω(𝑘(𝑂), 𝑅,𝑙(𝑂))).

As previously, we will abbreviate 𝐸𝐹 𝐾0,𝑅,Ω as 𝐸𝐹 . 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 11 (Saturated family of context-lattice pairs). A family of context-lattice pairs 𝑂 𝒪is saturated if 𝑥 𝑋, 𝑘𝑥(𝑂) = 𝜎Ω(𝑘𝑥(𝑂), 𝑅,𝑙(𝑂)).

𝐸𝐹 is an extensive and monotone internal operation for 𝒪:

Property 12 (𝐸𝐹 is internal to 𝒪). 𝑂 𝒪, 𝐸𝐹 (𝑂) 𝒪.

Proof. 𝑥 𝑋, 𝜎Ω(𝑘𝑥(𝑂), 𝑅,𝑙(𝑂)) 𝒦𝜂 (𝐾0) 𝐾0𝑥,𝑅,Ω because 𝜎Ω only scales attributes in 𝐷Ω,𝑅𝑥,𝐾0. Therefore,

T(𝜎Ω(𝑘𝑥(𝑂), 𝑅,𝑙(𝑂))) 𝒯𝜂 (𝐾0) 𝐾0𝑥,𝑅,Ω . Hence, 𝐸𝐹 (𝑂) = {T(𝜎Ω(𝑘𝑥(𝑂), 𝑅,𝑙(𝑂)))}𝑥 𝑋 𝒪𝐾0𝑥,𝑅,Ω (Definition 7).

Property 13 (𝐸𝐹 is extensive and monotone). The function 𝐸𝐹 attached to a relational context and a set of scaling operations satisfies:

𝑂 𝐸𝐹 (𝑂), (Extensivity)

𝑂 𝑂 𝐸𝐹 (𝑂) 𝐸𝐹 (𝑂 ). (Monotony)

Proof. Extensivity holds because 𝐸𝐹 can only add to 𝑘(𝑂) attributes scaled from 𝑙(𝑂), hence 𝑥 𝑋,𝑘𝑥(𝑂) 𝑘𝑥(𝐸𝐹 (𝑂)). Thus, by Property 10, 𝑂 𝐸𝐹 (𝑂). Monotony holds because 𝑂 𝑂 means that 𝑥 𝑋, 𝑙𝑥(𝑂) 𝑙𝑥(𝑂 ) and 𝑘𝑥(𝑂) 𝑘𝑥(𝑂 ). The former entails that 𝑥 𝑋, 𝜂(𝑙𝑥(𝑂)) 𝜂(𝑙𝑥(𝑂 )) and consequently, that 𝐷Ω,𝑅𝑥,𝑙(𝑂) 𝐷Ω,𝑅𝑥,𝑙(𝑂 ). A smaller context (𝑘𝑥(𝑂)) is extended by a smaller set of attributes (𝐷Ω,𝑅𝑥,𝑙(𝑂)), thus 𝑘𝑥(𝐸𝐹 (𝑂)) 𝑘𝑥(𝐸𝐹 (𝑂 )). Hence, by Property 10, 𝐸𝐹 (𝑂) 𝐸𝐹 (𝑂 ).

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

The Fixed-Point Semantics of Relational Concept Analysis 1:21

5.2 Self-Supported Lattices

In a family of context-lattice pairs 𝑂, there may be a context 𝑘(𝑂𝑥) containing attributes which refer to concepts non existing in 𝑙(𝑂). Such an attribute, e.g. 𝑟.𝑐, belonging to 𝑘(𝑂𝑥) may belong to 𝐷Ω,𝑅𝑥,𝐾0 and be well-defined by the incidence relation, but 𝑐may not be a concept of 𝑙(𝑂). This is illustrated by Example 7.

Example 7 (Non self-supported families of context-lattice pairs). Figure 6 (p.13) shows a familly of contexts {𝐾# 3, 𝐾# 4 } and the associated family of concept lattices {𝐿# 3, 𝐿# 4} that could be a solution for the example of Section 3.2 as it belongs to 𝒪{ },{𝑝,𝑞},{𝐾0 3,𝐾0 4 }. However, this family is not self-supported because the context 𝐾# 3 (and thus concept 𝐴) uses the attribute 𝑝.𝐶which refers to a concept (𝐶) not present in 𝐿# 4 and similarly for 𝑞.𝐵in context 𝐾# 4.

A family of context-lattice pairs in 𝒪containing such attributes will see them preserved by 𝐸𝐹 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: a 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 12 (Supported context). A context 𝐺𝑥, 𝑀𝑥, 𝐼𝑥 is supported by a family of indexed lattices {𝐿𝑧}𝑧 𝑋, with respect to a set 𝑅of relations, if 𝜍(𝑟,𝑐) 𝑀𝑥, 𝑟 𝑅𝑥,𝑧and 𝑐 𝐿𝑧.

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 (𝑙(𝑂)).

Definition 13 (Self-supported families of context-lattice pairs). A family of context-lattice pairs 𝑂 𝒪 is self-supported, with respect to a set 𝑅of relations, if 𝑥 𝑋, 𝑘𝑥(𝑂) is supported by 𝑙(𝑂), with respect to 𝑅.

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. 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 contexts (𝜅(𝐿𝑥)) induced by the lattices 𝐿𝑥in 𝐿those attributes non supported by 𝐿:

Definition 14 (Purging function). The function 𝜋 𝐾0,𝑅,Ω : Î 𝑥 𝑋ℒ𝐾0𝑥,𝑅,Ω Î 𝑥 𝑋𝒦𝐾0𝑥,𝑅,Ω returns the family of contexts reduced of those attributes not present in a family of lattices:

𝜋 𝐾0,𝑅,Ω(𝐿) = {𝜋𝐾0,𝑅,Ω(𝐿𝑥, 𝐿)}𝑥 𝑋

𝜋𝐾0,𝑅,Ω(𝐿𝑥, 𝐿) = K 𝑅,𝐿 (𝐷Ω,𝑅𝑥,𝐾0)\𝐷Ω,𝑅𝑥,𝐿) (𝜅(𝐿𝑥)).

When unambiguous, we refer to 𝜋𝐾0,𝑅,Ω (resp. 𝜋 𝐾0,𝑅,Ω) as 𝜋(resp. 𝜋 ). This extends the purging function of [10]. The purging function only restricts the sets of possible contexts and does not expand them. 𝜋and 𝜎are not inverse functions: in particular, 𝜎greatly depends on Ω and 𝑅to decide which attributes to scale, through 𝜋simply suppresses attributes non supported by the lattices, independently from Ω, which however determines the attribute language. 𝜋 can be used to determine if a family of context-lattice pairs is self-supported:

Property 14. 𝑂is self-supported if and only if 𝑘(𝑂) = 𝜋 (𝑙(𝑂)).

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

1:22 Euzenat

Proof. 𝑂is self-supported means that 𝑥 𝑋, 𝑘𝑥(𝑂) is supported by 𝑙(𝑂) (Definition 13) which means that, in 𝑘𝑥(𝑂), there is no attribute built from concepts out of 𝑙(𝑂), i.e. not belonging to 𝐷Ω,𝑅𝑥,𝑙(𝑂). By Definition 14, this is equivalent to having 𝑥 𝑋, 𝜋(𝑙𝑥(𝑂),𝑙(𝑂)) = 𝜅(𝑙𝑥(𝑂)). However, by Property 3, 𝑘𝑥(𝑂) = 𝜅(𝑙𝑥(𝑂)), thus 𝑘𝑥(𝑂) = 𝜋(𝑙𝑥(𝑂),𝑙(𝑂)) and then 𝑘(𝑂) = 𝜋 (𝑙(𝑂)).

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. Hence, it has to be iterated. We introduce a contraction function, 𝑃𝑄 𝐾0,𝑅,Ω, attached to a relational context 𝐾0, 𝑅 and a set Ω of scaling operations, which suppresses non-supported attributes and whose closure yields self-supported families of context-lattice pairs.

5.3 The Contraction Function 𝑃𝑄

Similarly to 𝐸𝐹 𝐾0,𝑅,Ω, it is possible to define 𝑃𝑄 𝐾0,𝑅,Ω the contraction function attached to a relational context 𝐾0, 𝑅 and a set Ω of scaling operations.

Definition 15 (Contraction function). Given a relational context 𝐾0, 𝑅 and a set Ω of relational scaling operations, the contraction function 𝑃𝑄 𝐾0,𝑅,Ω : 𝒪𝐾0,𝑅,Ω 𝒪𝐾0,𝑅,Ω is defined by:

𝑃𝑄 𝐾0,𝑅,Ω(𝑂) = T (𝜋 𝐾0,𝑅,Ω(𝑙(𝑂))).

As previously, we will abbreviate 𝑃𝑄 𝐾0,𝑅,Ω as 𝑃𝑄 . 𝑃𝑄 is an anti-extensive and monotone internal operation for 𝒪:

Property 15 (𝑃𝑄 is internal to 𝒪). 𝑂 𝒪, 𝑃𝑄 (𝑂) 𝒪.

Proof. 𝑃𝑄 (𝑂) = T (𝜋 (𝑙(𝑂))) = T ({𝜋(𝑙𝑥(𝑂),𝑙(𝑂))}𝑥 𝑋) = {T(𝜋(𝑙𝑥(𝑂),𝑙(𝑂)))}𝑥 𝑋. So, 𝑃𝑄 (𝑂) 𝒪if 𝜋(𝑙𝑥(𝑂),𝑙(𝑂)) 𝒦𝜂 (𝐾0) 𝐾0𝑥,𝑅,Ω (Definition 7). This is the case because (i) 𝒦𝜂 (𝐾0) 𝐾0𝑥,𝑅,Ω contains all contexts extending 𝐾0 𝑥

with attributes from 𝐷Ω,𝑅𝑥,𝐾0, (ii) 𝑘𝑥(𝑂) 𝒦𝜂 (𝐾0) 𝐾0𝑥,𝑅,Ω , and (iii) 𝜋only suppresses attributes from 𝑘𝑥(𝑂) preserving

those of 𝐾0 𝑥.

Property 16 (𝑃𝑄 is anti-extensive and monotone). The function 𝑃𝑄 attached to a relational context and a set of scaling operations satisfies:

𝑃𝑄 (𝑂) 𝑂, (Anti-extensivity)

𝑂 𝑂 𝑃𝑄 (𝑂) 𝑃𝑄 (𝑂 ). (Monotony)

Proof. Anti-extensivity holds because 𝑃𝑄 can only suppress from 𝑘(𝑂) attributes not supported by 𝑙(𝑂), hence 𝑥 𝑋,𝑘𝑥(𝑃𝑄 (𝑂)) 𝑘𝑥(𝑂). Thus, by Property 10, 𝑃𝑄 (𝑂) 𝑂. Monotony holds because 𝑂 𝑂 means that 𝑥 𝑋,𝑘𝑥(𝑂) 𝑘𝑥(𝑂 ) and 𝑙𝑥(𝑂) 𝑙𝑥(𝑂 ). This entails that 𝜂 (𝑙(𝑂)) 𝜂 (𝑙(𝑂 )) and thus, 𝑥 𝑋, 𝐷Ω,𝑅𝑥,𝑙(𝑂) 𝐷Ω,𝑅𝑥,𝑙(𝑂 ). Because 𝑃𝑄 (𝑂) suppresses from 𝑘𝑥(𝑂) attributes not in 𝑀0 𝑥 𝐷Ω,𝑅𝑥,𝑙(𝑂), this entails that 𝑘𝑥(𝑃𝑄 (𝑂)) 𝑘𝑥(𝑃𝑄 (𝑂 )). Hence, by Property 10, 𝑃𝑄 (𝑂) 𝑃𝑄 (𝑂 ).

6 The Fixed Points of 𝐸𝐹 and 𝑃𝑄

We end up with two functions, 𝐸𝐹 and 𝑃𝑄 , over families of context-lattice pairs, the former extensive and the latter anti-extensive. We consider the fixed points of these functions as saturated and self-supported families of context-lattice pairs ( 6.1). Closure functions are defined which return the smallest subsuming and greatest subsumed fixed points of a family ( 6.2). This allows us to precisely define acceptable solutions as those families of context-lattice pairs which are fixed points for both functions ( 6.3).

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

The Fixed-Point Semantics of Relational Concept Analysis 1:23

6.1 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 [23]; FCA s goal is to compute fixed points: concepts are the result of a closure operation which is also a fixed point [5]; 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. Given 𝐸𝐹 and 𝑃𝑄 , it is possible to define their sets of fixed points, i.e. the sets of families of context-lattice pairs closed for 𝐸𝐹 and 𝑃𝑄 , as:

Definition 16 (Fixed points). A family of context-lattice pairs 𝑂 𝒪is a fixed point for a function 𝜙, if 𝜙(𝑂) 𝑂. We call fp(𝜙) the set of fixed points for 𝜙.

This characterises fp(𝐸𝐹 ) and fp(𝑃𝑄 ). This may be directly expressed

Property 17. 𝑂 fp(𝐸𝐹 ) iff 𝜎 Ω(𝑘(𝑂), 𝑅,𝑙(𝑂)) = 𝑘(𝑂).

Proof. 𝑂= T (𝑘(𝑂)) and 𝐸𝐹 (𝑂) = T (𝜎 Ω(𝑘(𝑂), 𝑅,𝑙(𝑂))). ( ) If 𝜎 Ω(𝑘(𝑂), 𝑅,𝑙(𝑂)) = 𝑘(𝑂), then 𝐸𝐹 (𝑂) = 𝑂and thus 𝑂is a fixed point of 𝐸𝐹 . ( ) If 𝜎 Ω(𝑘(𝑂), 𝑅,𝑙(𝑂)) 𝑘(𝑂), then 𝐸𝐹 (𝑂) 𝑂, so it is not a fixed point.

Property 18. 𝑂 fp(𝑃𝑄 ) iff 𝜋 (𝑙(𝑂)) = 𝑘(𝑂).

Proof. 𝑂= T (𝑘(𝑂)) and 𝑃𝑄 (𝑂) = T (𝜋 (𝑙(𝑂))). ( ) If 𝜋 (𝑙(𝑂)) = 𝑘(𝑂), then 𝑃𝑄 (𝑂) = 𝑂and thus is a fixed point of 𝑃𝑄 . ( ) If 𝜋 (𝑙(𝑂)) 𝑘(𝑂), then 𝑃𝑄 (𝑂) 𝑂, so it is not a fixed point.

Since 𝒪is a complete lattice (Proposition 11) and 𝐸𝐹 and 𝑃𝑄 are order-preserving (or monotone) on 𝒪 (Properties 13 and 16), then we can apply the Knaster-Tarski theorem.

Theorem (Knaster-Tarski theorem [28]). Let 𝒪be a complete lattice and let𝜙: 𝒪 𝒪be an order-preserving function. Then the set of fixed points of 𝜙in 𝒪is also a complete lattice.

Thus, fp(𝐸𝐹 ), and fp(𝑃𝑄 ), are complete lattices. This warrants that there exists least and greatest fixed points of 𝐸𝐹 and 𝑃𝑄 in 𝒪. For such a function 𝜙, operating on the set 𝒪, their least and greatest fixed points are: lfp(𝜙) = Û

𝑂 fp(𝜙) 𝑂and gfp(𝜙) = Ü

The fixed points of these two functions may be further characterised. The smallest fixed point of 𝑃𝑄 is the smallest element of 𝒪which cannot be further reduced:

Property 19 (Least fixed point of 𝑃𝑄 ).

lfp(𝑃𝑄 ) = T (𝐾0).

Proof. T (𝜋 (FCA (𝐾0))) = T (𝐾0) because (a) 𝑥 𝑋, 𝜅(FCA(𝐾0 𝑥)) = 𝐾0 𝑥(Property 3), and (b) 𝜋(FCA(𝐾0 𝑥), FCA (𝐾0)) = 𝐾0 𝑥as it is not possible to suppress attributes from 𝐾0 𝑥which, being an initial (unscaled) context, does not comprise any attribute referring to concepts. Thus, 𝑃𝑄 (T (𝐾0)) = T (𝜋 (FCA (𝐾0))) = T (𝐾0). Moreover, 𝑂 𝒪, T (𝐾0) 𝑂. Hence, T (𝐾0) is a fixed point of 𝑃𝑄 and all other fixed points are greater.

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

1:24 Euzenat

The greatest fixed point of 𝐸𝐹 is the family that cannot be further extended (generalising Proposition 2 of [10]):

Property 20 (Greatest fixed point of 𝐸𝐹 ).

gfp(𝐸𝐹 𝐾0,𝑅,Ω) = T ({K 𝑅,𝜂 (𝐾0) +𝐷Ω,𝑅𝑥,𝐾0 (𝐾0 𝑥)}𝑥 𝑋).

Proof. This family of context-lattice pairs is the greatest element of 𝒪as 𝑥 𝑋, the context 𝑘𝑥(𝑂) contains all attributes of 𝑀0 𝑥 𝐷Ω,𝑅𝑥,𝐾0 and due to Property 10. It is also a fixed point because 𝐸𝐹 is extensive (Property 13) and internal (Property 12).

6.2 Closure Functions (𝐸𝐹 and 𝑃𝑄 )

𝐸𝐹 and 𝑃𝑄 are not closure operations as they are not idempotent. However, with the same arguments as [26], and in particular the finiteness of contexts (see Section 2.4.3), it can be argued that their repeated application converges to a fixed point.

Property 21 (Stability of 𝐸𝐹 ). 𝑂 𝒪, 𝑛; 𝐸𝐹 𝑛(𝑂) = 𝐸𝐹 𝑛+1(𝑂).

Proof. 𝐸𝐹 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 𝑛has been reached such that the family of context-lattice pairs is the same. This is the same argument as that of [26].

This below is an extension of Proposition 5 of [10]:

Property 22 (Stability of 𝑃𝑄 ). 𝑂 𝒪, 𝑛; 𝑃𝑄 𝑛(𝑂) = 𝑃𝑄 𝑛+1(𝑂).

Proof. 𝑃𝑄 can only decrease the contexts and reduce lattices. Since these are finite (and the decrease does not affect the attributes of 𝐾0), there exists a 𝑛at which the decrease stops.

The finite application of 𝐸𝐹 and 𝑃𝑄 as many times as necessary, i.e. to the first 𝑛satisfying Properties 21 and 22, are closure operations denoted by 𝐸𝐹 and 𝑃𝑄 , respectively.

Property 23. 𝐸𝐹 and 𝑃𝑄 are closures.

Proof. Since 𝐸𝐹 is extensive and monotone (Property 13), 𝐸𝐹 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 𝑂 𝒪, 𝐸𝐹 (𝑂) = 𝐸𝐹 𝑛(𝑂) = 𝐸𝐹 𝑛+1(𝑂) = 𝐸𝐹 (𝐸𝐹 𝑛(𝑂)). Since 𝐸𝐹 𝑛(𝑂) = 𝐸𝐹 (𝐸𝐹 𝑛(𝑂)), 𝐸𝐹 can be applied 𝑛times, leading to 𝐸𝐹 (𝑂) = 𝐸𝐹 𝑛(𝑂) = 𝐸𝐹 𝑛(𝐸𝐹 𝑛(𝑂)) = 𝐸𝐹 (𝐸𝐹 (𝑂)). The same can be obtained from 𝑃𝑄 , albeit anti-extensive (Property 16).

In addition, they are extrema of the sets of fixed points of their respective functions.

Property 24 (𝐸𝐹 and 𝑃𝑄 return the smallest subsuming and greatest subsumed fixed points). 𝑂 𝒪,

𝐸𝐹 (𝑂) = min (fp(𝐸𝐹 ) {𝑂 |𝑂 𝑂 }),

𝑃𝑄 (𝑂) = max (fp(𝑃𝑄 ) {𝑂 |𝑂 𝑂}).

Proof. 𝐸𝐹 (𝑂) fp(𝐸𝐹 ) and 𝑃𝑄 (𝑂) fp(𝑃𝑄 ) as they satisfy Definition 16. Moreover, 𝐸𝐹 (𝑂) {𝑂 |𝑂 𝑂 } and 𝑃𝑄 (𝑂) {𝑂 |𝑂 𝑂} as 𝐸𝐹 and 𝑃𝑄 are respectively extensive and anti-extensive and monotone (Property 13 and 16). There cannot be 𝑂 fp(𝐸𝐹 ) {𝑂 |𝑂 𝑂 } such that 𝑂 𝐸𝐹 (𝑂) because

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

The Fixed-Point Semantics of Relational Concept Analysis 1:25

otherwise 𝑘(𝑂 ) 𝑘(𝐸𝐹 (𝑂)) and 𝑘(𝑂) 𝑘(𝑂 ). In other terms, 𝑂 contains all attributes of 𝑂but not all attributes of 𝐸𝐹 (𝑂). But, 𝐸𝐹 only adds scalable attributes and 𝑘(𝐸𝐹 (𝑂)) contains only attributes scalable from 𝑂. Hence, 𝑂 is not closed for 𝐸𝐹 (𝑂 fp(𝐸𝐹 )). The same holds for 𝑃𝑄 (𝑂), there cannot be 𝑂 fp(𝑃𝑄 ) {𝑂 |𝑂 𝑂} such that 𝑃𝑄 (𝑂) 𝑂

because otherwise 𝑘(𝑂 ) 𝑘(𝑂). In other terms, all attributes of 𝑂 are in 𝑂but 𝑂 contains all attributes of 𝑃𝑄 (𝑂). However, 𝑃𝑄 only suppress attributes not supported by those of 𝑂. Hence, 𝑂 is not closed for 𝑃𝑄

(𝑂 fp(𝑃𝑄 )), as it would contain non-supported attributes.

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

Property 25. 𝑂 𝒪,

lfp(𝑃𝑄 ) 𝑃𝑄 (𝑂) 𝑃𝑄 (𝑂) 𝑂 𝐸𝐹 (𝑂) 𝐸𝐹 (𝑂) gfp(𝐸𝐹 ).

Proof. All the inner equations are consequences of the extensivity of 𝐸𝐹 (Property 13) and anti-extensivity of 𝑃𝑄 (Property 16). The outer ones owe to the fact that the two closure operations are fixed points (Property 24), thus they are subsumed by, resp. subsuming, their greatest, resp. least, fixed point.

6.3 Acceptable Solutions

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

Definition 17 (Acceptable family of context-lattice pairs). Given a family 𝐾0 of contexts, a set Ω of scaling operations and a set 𝑅of relations, a family of context-lattice pairs 𝑂is acceptable if

𝑂 𝒪𝐾0,𝑅,Ω, (well-formedness) 𝑂is saturated, (saturation) 𝑂is self-supported. (self-support)

This can be characterised as those families of context-lattice pairs which are fixed points of both 𝐸𝐹 and 𝑃𝑄 . The fixed points of 𝐸𝐹 are exactly those saturated elements of 𝒪:

Property 26 (Fixed points of 𝐸𝐹 are saturated). 𝑂 𝒪, 𝑂is saturated iff 𝑂 fp(𝐸𝐹 ).

Proof. 𝑂 fp(𝐸𝐹 ) means that𝑘(𝑂) = 𝜎 Ω(𝑘(𝑂), 𝑅,𝑙(𝑂)) (Property 17) which is equivalent to 𝑥 𝑋,𝑘𝑥(𝑂) = 𝜎Ω(𝑘𝑥(𝑂), 𝑅,𝑙(𝑂)) which, by Definition 11, means that 𝑂is saturated.

The fixed points of 𝑃𝑄 are exactly those self-supported objects in 𝒪:

Property 27 (Fixed points of 𝑃𝑄 are self-supported). 𝑂 𝒪, 𝑂is self-supported iff 𝑂 fp(𝑃𝑄 ).

Proof. 𝑂is self-supported iff 𝑘(𝑂) = 𝜋 (𝑙(𝑂)) (Property 14) which is equivalent to 𝑂= 𝑃𝑄 (𝑂) (Property 18), i.e. 𝑂 fp(𝑃𝑄 ).

Hence, the set of acceptable solutions is fp(𝐸𝐹 ) fp(𝑃𝑄 ).

Proposition 28 (Acceptable solutions are fixed points of both 𝐸𝐹 and 𝑃𝑄 ). Given a family 𝐾0 of contexts, a set Ω of scaling operations and a set 𝑅of relations, a family of context-lattice pairs 𝑂is acceptable iff 𝑂 𝒪𝐾0,𝑅,Ω and 𝑂 fp(𝐸𝐹 ) fp(𝑃𝑄 ).

Proof. 𝑂is well-formed as it belongs to 𝒪𝐾0,𝑅,Ω. It is saturated if and only if it belongs to fp(𝐸𝐹 ) (Property 26) and it is self-supported if and only if it belongs to fp(𝑃𝑄 ) (Property 27). Hence,𝑂is acceptable (Definition 17).

Example 8 illustrates this:

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

1:26 Euzenat

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

𝐸𝐹 ({ 𝐾1 3, 𝐿1 3 , 𝐾1 4, 𝐿1 4 }) = { 𝐾1 3, 𝐿1 3 , 𝐾1 4, 𝐿1 4 } = 𝑃𝑄 ({ 𝐾1 3, 𝐿1 3 , 𝐾1 4, 𝐿1 4 }),

𝐸𝐹 ({ 𝐾 3 , 𝐿 3 , 𝐾 4 , 𝐿 4 }) = { 𝐾 3 , 𝐿 3 , 𝐾 4 , 𝐿 4 } = 𝑃𝑄 ({ 𝐾 3 , 𝐿 3 , 𝐾 4 , 𝐿 4 }),

𝐸𝐹 ({ 𝐾 3, 𝐿 3 , 𝐾 4, 𝐿 4 }) = { 𝐾 3, 𝐿 3 , 𝐾 4, 𝐿 4 } = 𝑃𝑄 ({ 𝐾 3, 𝐿 3 , 𝐾 4, 𝐿 4 }),

𝐸𝐹 ({ 𝐾 3 , 𝐿 3 , 𝐾 4 , 𝐿 4 }) = { 𝐾 3 , 𝐿 3 , 𝐾 4 , 𝐿 4 } = 𝑃𝑄 ({ 𝐾 3 , 𝐿 3 , 𝐾 4 , 𝐿 4 }).

and none of the other elements of 𝒪as displayed in Figure 9 (p.32).

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.

7 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 𝐸𝐹 function ( 7.1). Another interesting operation is the one that generates the greatest acceptable solution, which is also the greatest fixed point of 𝑃𝑄 ( 7.2). It is also worth considering obtaining the whole set fp(𝐸𝐹 ) fp(𝑃𝑄 ). Section 7.3 investigates the structure of [lfp(𝐸𝐹 ), gfp(𝑃𝑄 )] and its relation with fp(𝐸𝐹 ) fp(𝑃𝑄 ) towards that goal. It provides various results that may be exploited to develop efficient algorithms.

7.1 Classical RCA Computes 𝐸𝐹 s Least Fixed Point

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

RCAΩ(𝐾0, 𝑅) = 𝑙(𝐸𝐹 𝐾0,𝑅,Ω(T (𝐾0)))

i.e. RCA iterates 𝐸𝐹 from T (𝐾0) until reaching a fixed point, and ultimately the corresponding lattices are returned. It thus seems that RCA returns a fixed point of 𝐸𝐹 . Hence the question: which fixed point is returned by RCA s well-grounded semantics? This is the least fixed point.

Proposition 29 (The RCA algorithm computes the least fixed point of 𝐸𝐹 ). Given 𝐸𝐹 the expansion function associated to 𝐾0, 𝑅and Ω, RCAΩ(𝐾0, 𝑅) = 𝑙(lfp(𝐸𝐹 𝐾0,𝑅,Ω)).

Proof. T (𝐾0) 𝒪, hence 𝐸𝐹 (T (𝐾0)) 𝒪(by Property 12). Moreover, 𝐸𝐹 (T (𝐾0)) = min (fp(𝐸𝐹 ) {𝑂 | T (𝐾0) 𝑂 }) (Property 24). But 𝑂 𝒪, T (𝐾0) 𝑂 , hence 𝐸𝐹 (T (𝐾0)) = min (fp(𝐸𝐹 )). Thus, 𝐸𝐹 𝐾0,𝑅,Ω(T (𝐾0)) is a fixed point more specific than all fixed points: it is the least fixed point. RCAΩ(𝐾0, 𝑅) = 𝑙(𝐸𝐹 𝐾0,𝑅,Ω(T (𝐾0))) returns the family of lattices associated with the least fixed point of 𝐸𝐹 𝐾0,𝑅,Ω.

7.2 Greatest Fixed-Point (of 𝑃𝑄 ) Semantics

It is possible to define RCA as returning the greatest acceptable solution. The greatest fixed point of 𝐸𝐹

(Property 20) is not necessarily an acceptable solution because it may not be self-supported. Said otherwise, it does not belong to fp(𝐸𝐹 ) fp(𝑃𝑄 ) because it is not a fixed point for 𝑃𝑄 .

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

The Fixed-Point Semantics of Relational Concept Analysis 1:27

Alternatively, a dual procedure RCA may be defined as:

RCAΩ(𝐾0, 𝑅) = 𝑙(𝑃𝑄 𝐾0,𝑅,Ω(T ({K 𝑅,𝜂 (𝐾0) +𝐷Ω,𝑅𝑥,𝐾0 (𝐾0 𝑥)}𝑥 𝑋)))

and it can be characterised analogously as the greatest fixed point of 𝑃𝑄 𝐾0,𝑅,Ω.

Proposition 30 (RCA determines the greatest fixed point of 𝑃𝑄 ). Given 𝑃𝑄 the contraction function associated to 𝐾0, 𝑅and Ω,

RCAΩ(𝐾0, 𝑅) = 𝑙(gfp(𝑃𝑄 𝐾0,𝑅,Ω)).

Proof. 𝑂 = T ({K 𝑅,𝜂 (𝐾0) +𝐷Ω,𝑅𝑥,𝐾0 (𝐾0 𝑥)}𝑥 𝑋) 𝒪, hence 𝑃𝑄 𝐾0,𝑅,Ω(𝑂 ) 𝒪(by Property 15). Moreover, 𝑃𝑄 (𝑂 ) = max (fp(𝑃𝑄 ) {𝑂 |𝑂 𝑂 }) (Property 24). But 𝑂 𝒪, 𝑂 𝑂 , hence 𝑃𝑄 (𝑂 ) = max (fp(𝑃𝑄 )). Thus, 𝑃𝑄 𝐾0,𝑅,Ω(𝑂 ) is a fixed point more general than all fixed points: it is the greatest fixed point.

RCAΩ(𝐾0, 𝑅) = 𝑙(𝑃𝑄 𝐾0,𝑅,Ω(𝑂 )) returns the family of lattices associated with the greatest fixed point of 𝑃𝑄 𝐾0,𝑅,Ω.

In order to find gfp(𝑃𝑄 ), the process starts with T ({K 𝑅,𝜂 (𝐾0) +𝐷Ω,𝑅𝑥,𝐾0 (𝐾0 𝑥)}𝑥 𝑋), the largest family of context-lattice pairs, and iterates the application of 𝑃𝑄 , i.e. the two operations 𝜋 and FCA , until reaching a fixed point, i.e. reaching 𝑛such that 𝑂𝑛+1 = 𝑂𝑛. Thus, the RCA algorithm proceeds in the following way:

(1) Initial contexts: 𝑡 0; { 𝐺𝑥, 𝑀𝑡 𝑥, 𝐼𝑡 𝑥 }𝑥 𝑋 {K 𝑅,𝜂 (𝐾0) +𝐷Ω,𝑅𝑥,𝐾0 (𝐾0 𝑥)}𝑥 𝑋 (2) {𝐿𝑡 𝑥}𝑥 𝑋 FCA ({ 𝐺𝑥, 𝑀𝑡 𝑥, 𝐼𝑡 𝑥 }𝑥 𝑋) (or, for each context, 𝐺𝑥, 𝑀𝑡 𝑥, 𝐼𝑡 𝑥 the corresponding concept lattice 𝐿𝑡 𝑥= FCA( 𝐺𝑥, 𝑀𝑡 𝑥, 𝐼𝑡 𝑥 ) is created using FCA). (3) { 𝐺𝑥, 𝑀𝑡+1 𝑥 , 𝐼𝑡+1 𝑥 }𝑥 𝑋 𝜋 ({𝐿𝑡 𝑥}𝑥 𝑋) (i.e. suppressing from 𝐾𝑡 𝑥each attribute in 𝐿𝑡 𝑥referring through a relation 𝑟 𝑅𝑥,𝑧to a concept 𝑐𝑧not appearing in 𝐿𝑡 𝑧). (4) If 𝑥 𝑋; 𝑀𝑡+1 𝑥 𝑀𝑡 𝑥(purging has occurred), then 𝑡 𝑡+ 1; go to Step 2. (5) Return: {𝐿𝑡 𝑥}𝑥 𝑋.

This algorithm is the dual of the RCA procedure. Example 9 shows how this is processed.

Example 9 (Greatest fixed-point semantics). In the cases presented in Section 3.1 and 3.2, the greatest (or maximum) elements { 𝐾 1 , 𝐿 1 , 𝐾 2 , 𝐿 2 } and { 𝐾 3 , 𝐿 3 , 𝐾 4 , 𝐿 4 } of 𝒪are fixed points for both 𝐸𝐹 and 𝑃𝑄 . Instead, consider the example of Section 3.1 in which the relation 𝑝is changed to:

𝑞remaining the same. The effect of changing 𝑝is to make 𝑎and 𝑏non distinguishable and reduce the sets of supported concepts. Then (Property 20), gfp(𝐸𝐹 ) = T ({K 𝑅,𝜂 (𝐾0) +𝐷Ω,𝑅𝑥,𝐾0 (𝐾0 𝑥)}𝑥 {1,2}) = { 𝐾 1 , 𝐿 1 , 𝐾 2 , 𝐿 2 } is presented below:

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

1:28 Euzenat

𝐾 1 𝑚1 𝑚2 𝑚3

𝑝.𝐷𝐸𝐹, 𝑝.𝐷𝐹, 𝑝.𝐸𝐹

𝑚2, 𝑝.𝐷, 𝑝.𝐸, 𝑝.𝐷𝐸

𝑛1, 𝑝.𝐴𝐵 𝑝.𝐴𝐶 𝑝.𝐵𝐶

It can be checked that { 𝐾 1 , 𝐿 1 , 𝐾 2 , 𝐿 2 } is a fixed point for 𝐸𝐹 : no additional attribute can be scaled. On the contrary, it is not a fixed point for 𝑃𝑄 which can be applied to it. In a first application, it will purge 𝐾 2 , 𝐿 2 to:

A second application will purge 𝐾 1 , 𝐿 1 with respect to 𝐾 2, 𝐿 2 :

𝐾 1 𝑚1 𝑚2 𝑚3

𝑚2, 𝑝.𝐸, 𝑝.𝐷𝐸

It can be checked that { 𝐾 1, 𝐿 1 , 𝐾 2, 𝐿 2 } is a fixed point for 𝑃𝑄 , but also for 𝐸𝐹 .

It may be interesting, for some applications to check if there is only one acceptable solution. This can easily be characterised by:

Proposition 31. lfp(𝐸𝐹 𝐾0,𝑅,Ω) = gfp(𝑃𝑄 𝐾0,𝑅,Ω) iff |fp(𝐸𝐹 𝐾0,𝑅,Ω) fp(𝑃𝑄 𝐾0,𝑅,Ω)| = 1.

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

The Fixed-Point Semantics of Relational Concept Analysis 1:29

The proof of this proposition is given in the next section (7.3) as it relies on further results. This can be tested using RCA and RCA. FCA can be described as RCA with 𝑅= . In this case, 𝑥 𝑋, 𝐷Ω,𝑅𝑥,𝐾0 = . Thus, 𝒪= {T (𝐾0)} = { 𝐾0, FCA(𝐾0) } and fp(𝐸𝐹 ) = fp(𝑃𝑄 ) = {T (𝐾0)}. Hence,

RCAΩ(𝐾0, ) = RCAΩ(𝐾0, ) = FCA(𝐾0).

7.3 The Structure of Fixed Points Besides obtaining the least fixed point of 𝐸𝐹 (RCAΩ) or the greatest fixed point of 𝑃𝑄 (RCAΩ), 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 (fp(𝐸𝐹 ) fp(𝑃𝑄 )). A naive algorithm for this consists in enumerating all elements of 𝒪and testing if they are fixed points. This would not be very efficient. 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 8 illustrates the structure of 𝒪 and how 𝐸𝐹 and 𝑃𝑄 and their composition traverse this structure. An interesting property of the functions 𝐸𝐹 and 𝑃𝑄 is that they preserve each other stability:

Property 32 (𝐸𝐹 is internal to fp(𝑃𝑄 )). 𝑂 fp(𝑃𝑄 ), 𝐸𝐹 (𝑂) fp(𝑃𝑄 ).

Proof. If 𝑂 fp(𝑃𝑄 ), all attributes in intents of 𝑙(𝑂) are supported by concepts in 𝑙(𝑂) (Property 27 and Definition 13). By Property 13, 𝑂 𝐸𝐹 (𝑂), so these concepts are still in 𝑙(𝐸𝐹 (𝑂)). Moreover, 𝐸𝐹 only adds to 𝑘(𝑂) attributes which are supported by 𝑙(𝑂) (they only refer to concepts in 𝑙(𝑂)). Hence, the attributes in 𝑘(𝐸𝐹 (𝑂)) and those scaled by 𝜎Ω are still supported by 𝑙(𝐸𝐹 (𝑂)).

Property 33 (𝑃𝑄 is internal to fp(𝐸𝐹 )). 𝑂 fp(𝐸𝐹 ), 𝑃𝑄 (𝑂) fp(𝐸𝐹 ).

Proof. If 𝑂 fp(𝐸𝐹 ), this means that 𝐸𝐹 (𝑂) = 𝑂and, in particular, that 𝜎 Ω does not scale new attributes based on the concepts in 𝑙(𝑂). By Property 16, 𝑃𝑄 (𝑂) 𝑂, so that 𝑙(𝑃𝑄 (𝑂)) does not contain more concepts than 𝑙(𝑂), then 𝜎 Ω cannot scale new attributes (𝜎 Ω(𝑘(𝑃𝑄 (𝑂)), 𝑅,𝑙(𝑃𝑄 (𝑂))) 𝜎 Ω(𝑘(𝑂), 𝑅,𝑙(𝑂)) = ). Hence, 𝑃𝑄 (𝑂) fp(𝐸𝐹 ).

This shows that fp(𝐸𝐹 ) fp(𝑃𝑄 ) : acceptable solutions always exist. In addition, the closure operations associated with the two functions preserve their extrema.

Property 34. 𝑃𝑄 (gfp(𝐸𝐹 )) = gfp(𝑃𝑄 ) and 𝐸𝐹 (lfp(𝑃𝑄 )) = lfp(𝐸𝐹 ).

Proof. 𝑂 𝒪,𝑂 gfp(𝐸𝐹 ) (from Property 25), and 𝑃𝑄 is order preserving (Property 23), thus 𝑃𝑄 (𝑂) 𝑃𝑄 (gfp(𝐸𝐹 )). Hence, 𝑂 fp(𝑃𝑄 ), 𝑂 𝑃𝑄 (gfp(𝐸𝐹 )). Moreover, 𝑃𝑄 (gfp(𝐸𝐹 )) fp(𝑃𝑄 ), thus 𝑃𝑄 (gfp(𝐸𝐹 )) = gfp(𝑃𝑄 ). Similarly, 𝑂 𝒪, lfp(𝑃𝑄 ) 𝑂(Property 25), and 𝐸𝐹 is order preserving (Property 23), thus 𝐸𝐹 (lfp(𝑃𝑄 )) 𝐸𝐹 (𝑂). Hence, 𝑂 fp(𝐸𝐹 ), 𝐸𝐹 (lfp(𝑃𝑄 )) 𝑂. Moreover, 𝐸𝐹 (lfp(𝑃𝑄 )) fp(𝐸𝐹 ), therefore 𝐸𝐹 (lfp(𝑃𝑄 )) = lfp(𝐸𝐹 ).

Proposition 35 complements Property 25 for elements of fp(𝐸𝐹 ) fp(𝑃𝑄 ). The elements of fp(𝐸𝐹 ) fp(𝑃𝑄 ) thus belong to the interval [lfp(𝐸𝐹 ) gfp(𝑃𝑄 )] (which is more restricted than [lfp(𝑃𝑄 ) gfp(𝐸𝐹 )], see Figure 8).

Proposition 35. 𝑂 fp(𝐸𝐹 ) fp(𝑃𝑄 ),

lfp(𝑃𝑄 ) lfp(𝐸𝐹 ) 𝑂 gfp(𝑃𝑄 ) gfp(𝐸𝐹 ).

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

1:30 Euzenat

fp(𝐸𝐹 ) = Im(𝐸𝐹 )

𝒪 fp(𝑃𝑄 ) = Im(𝑃𝑄 )

T (𝐾0) = lfp(𝑃𝑄 )

Fig. 8. Illustration of Properties 32, 33, 35, 34, 36, 40 and 41. The figure displays four times 𝒪and the images of gfp(𝐸𝐹 ) (red), a random family of context-lattice pairs (blue) and lfp(𝑃𝑄 ) = T (𝐾0) (green) through 𝑃𝑄 (left) and 𝐸𝐹 (right). fp(𝐸𝐹 ) is drawn in vertical lines; fp(𝑃𝑄 ) in horizontal lines and the grey area depicts the interval [lfp(𝐸𝐹 ), gfp(𝑃𝑄 )].

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

The Fixed-Point Semantics of Relational Concept Analysis 1:31

Proof. By Property 34, 𝑃𝑄 (gfp(𝐸𝐹 )) = gfp(𝑃𝑄 ), but 𝑃𝑄 (𝑂) 𝑂(Property 16) and 𝑃𝑄 (𝑂) 𝑃𝑄 (𝑂) (Property 25), thus gfp(𝑃𝑄 ) = 𝑃𝑄 (gfp(𝐸𝐹 )) 𝑃𝑄 (gfp(𝐸𝐹 )) gfp(𝐸𝐹 ). Moreover, by Property 34, 𝐸𝐹 (lfp(𝑃𝑄 )) = lfp(𝐸𝐹 ), but 𝑂 𝐸𝐹 (𝑂) (Property 13) and 𝐸𝐹 (𝑂) 𝐸𝐹 (𝑂) (Property 25), thus lfp(𝑃𝑄 ) 𝐸𝐹 (lfp(𝑃𝑄 )) 𝐸𝐹 (lfp(𝑃𝑄 )) = lfp(𝐸𝐹 ). Finally, 𝑂 fp(𝐸𝐹 ) fp(𝑃𝑄 ) entails that lfp(𝐸𝐹 ) 𝑂and 𝑂 gfp(𝑃𝑄 ).

It is now possible to prove Proposition 31:

Proof of Proposition 31. First, both lfp(𝐸𝐹 𝐾0,𝑅,Ω) and gfp(𝑃𝑄 𝐾0,𝑅,Ω) are among the acceptable solutions. Indeed, lfp(𝐸𝐹 ) = 𝐸𝐹 (lfp(𝑃𝑄 )) (Property 34), but lfp(𝑃𝑄 ) fp(𝑃𝑄 ) thus 𝐸𝐹 (lfp(𝑃𝑄 )) fp(𝑃𝑄 ) (Property 32), hence lfp(𝐸𝐹 ) fp(𝑃𝑄 ). The same reasoning can be applied to gfp(𝑃𝑄 𝐾0,𝑅,Ω) with Property 33. ) Since all acceptable solutions are within the interval between both fixed points (Proposition 35), 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 lfp(𝐸𝐹 𝐾0,𝑅,Ω) = gfp(𝑃𝑄 𝐾0,𝑅,Ω).

Proposition 35 together with the preamble of the proof of Proposition 31 determine that [lfp(𝐸𝐹 ) gfp(𝑃𝑄 )] is the smallest interval in which fp(𝐸𝐹 ) fp(𝑃𝑄 ) is included since its bounds are acceptable solutions. However, acceptable solutions do not cover the whole interval: the converse of Proposition 35 does not hold in general as shown by the counter-example 10.

Example 10 (Non coverage in RCA). In the example of Section 3.2, lfp(𝐸𝐹 ) = { 𝐾1 1, 𝐿1 1 , 𝐾1 2, 𝐿1 2 } and gfp(𝑃𝑄 ) = { 𝐾 1 , 𝐿 1 , 𝐾 2 , 𝐿 2 }. The family { 𝐾# 1, 𝐿# 1 , 𝐾# 2, 𝐿# 2 } of Figure 6 belongs to [lfp(𝐸𝐹 ) gfp(𝑃𝑄 )], but not to fp(𝐸𝐹 ) fp(𝑃𝑄 ) as mentioned in Example 7. Figure 9 shows that 12 out of 16 elements of the interval are in this situation: only 4 belong to fp(𝐸𝐹 ) fp(𝑃𝑄 ).

This interval may be thought of as an approximation of the situation described by the initial context 𝐾0. For some purposes, this may be sufficient. However, it may also be interesting to navigate within the set fp(𝐸𝐹 ) fp(𝑃𝑄 ) of fixed points or to compute it. In order to find the elements of fp(𝐸𝐹 ) fp(𝑃𝑄 ), the closure of 𝐸𝐹 and 𝑃𝑄 , 𝐸𝐹 and 𝑃𝑄 , can be used as functions which maps elements of 𝒪into families of context-lattice pairs in fp(𝐸𝐹 ) and fp(𝑃𝑄 ), respectively. Moreover, Properties 33 and 32 entail that 𝑃𝑄 𝐸𝐹 and 𝐸𝐹 𝑃𝑄 map any element of 𝒪into an acceptable family of context-lattice pairs in fp(𝐸𝐹 ) fp(𝑃𝑄 ). Hence, the set of acceptable solutions are those elements in the image of 𝒪by the composition of these two closure operations, in any order.

Property 36. Im(𝑃𝑄 𝐸𝐹 ) = fp(𝐸𝐹 ) fp(𝑃𝑄 ) = Im(𝐸𝐹 𝑃𝑄 ).

Proof. We show it for 𝑃𝑄 𝐸𝐹 , the other part is dual: By definition, Im(𝑃𝑄 𝐸𝐹 ) Im(𝑃𝑄 ) = fp(𝑃𝑄 ). Moreover, Im(𝐸𝐹 ) = fp(𝐸𝐹 ), but by Property 33, if 𝑂 fp(𝐸𝐹 ), then 𝑃𝑄 (𝑂) fp(𝐸𝐹 ). Hence, Im(𝑃𝑄 𝐸𝐹 ) fp(𝐸𝐹 ) fp(𝑃𝑄 ). 𝑂 fp(𝑃𝑄 ) fp(𝐸𝐹 ), 𝑂 fp(𝐸𝐹 ), thus 𝐸𝐹 (𝑂) = 𝑂and 𝑂 fp(𝑃𝑄 ), thus 𝑃𝑄 (𝑂) = 𝑂. Hence, 𝑂= 𝑃𝑄 (𝐸𝐹 (𝑂)) = 𝑃𝑄 𝐸𝐹 (𝑂) Im(𝑃𝑄 𝐸𝐹 ) and consequently fp(𝐸𝐹 ) fp(𝑃𝑄 ) Im(𝑃𝑄 𝐸𝐹 ).

In addition, these functions are monotone and idempotent.

Property 37. 𝑃𝑄 𝐸𝐹 (resp. 𝐸𝐹 𝑃𝑄 ) is order-preserving and idempotent:

𝑂,𝑂 𝒪,𝑂 𝑂 (𝑃𝑄 𝐸𝐹 )(𝑂) (𝑃𝑄 𝐸𝐹 )(𝑂 ), (Monotony)

(𝑃𝑄 𝐸𝐹 ) (𝑃𝑄 𝐸𝐹 )(𝑂) = 𝑃𝑄 𝐸𝐹 (𝑂). (Idempotence)

Proof. We prove it for 𝑃𝑄 𝐸𝐹 , the 𝐸𝐹 𝑃𝑄 case is strictly dual.

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

1:32 Euzenat

Fig. 9. All the families of lattices belonging to [lfp(𝐸𝐹 ) gfp(𝑃𝑄 )] in the example of Section 3.2. Those in fp(𝐸𝐹 ) fp(𝑃𝑄 ) are within solid boxes. As usual, only direct edges are displayed. Solid arrows show direct application of 𝐸𝐹 and dashed arrows show direct application of 𝑃𝑄 . Dotted arrows are order relations not corresponding to 𝐸𝐹 or 𝑃𝑄 applications.

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

The Fixed-Point Semantics of Relational Concept Analysis 1:33

Monotony is obtained as the combination of order-preservation of the two functions: 𝑂 𝑂 , hence 𝐸𝐹 (𝑂) 𝐸𝐹 (𝑂 ), and thus 𝑃𝑄 𝐸𝐹 (𝑂) 𝑃𝑄 𝐸𝐹 (𝑂 ) (applying Property 23 twice). Idempotence is obtained from Property 36: 𝑂 𝒪, 𝑃𝑄 𝐸𝐹 (𝑂) fp(𝐸𝐹 ) fp(𝑃𝑄 ), hence 𝑃𝑄 𝐸𝐹 (𝑂) = 𝑂and 𝑃𝑄 𝐸𝐹 𝑃𝑄 𝐸𝐹 (𝑂) = 𝑂, thus 𝑃𝑄 𝐸𝐹 𝑃𝑄 𝐸𝐹 (𝑂) = 𝑃𝑄 𝐸𝐹 (𝑂).

The monotony of these functions entails that fp(𝐸𝐹 ) fp(𝑃𝑄 ) is a complete lattice:

Proposition 38. fp(𝐸𝐹 ) fp(𝑃𝑄 ), is a complete sublattice of 𝒪, .

Proof. fp(𝐸𝐹 ) fp(𝑃𝑄 ) = Im(𝑃𝑄 𝐸𝐹 ) (Property 36) and Im(𝑃𝑄 𝐸𝐹 ) = fp(𝑃𝑄 𝐸𝐹 ) due to idempotence (Property 37), hence the Knaster-Tarski theorem can be applied based on Property 37 (monotony), concluding that it is a complete lattice. It is included in 𝒪, thus this is a sublattice of 𝒪, .

This is illustrated by Example 11.

Example 11 (Interval lattice). Figure 9 shows all elements of [lfp(𝐸𝐹 ) gfp(𝑃𝑄 )] for the example of Section 3.2. It can be observed that fp(𝐸𝐹 ) fp(𝑃𝑄 ), is a proper sublattice of 𝒪. Actually only 4 out of 16 possible objects in the interval are acceptable. In the figure, direct edges corresponding to 𝐸𝐹 or 𝑃𝑄 , 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 𝐸𝐹 are 𝑃𝑄 are not displayed.

However, the functions 𝑃𝑄 𝐸𝐹 and 𝑃𝑄 𝐸𝐹 are not necessarily extensive, nor anti-extensive (see Figure 10 and Example 12, p. 34). Hence, they would not be closure operations. For any family of context-lattice pairs within the fixed points, i.e. fp(𝐸𝐹 ) or fp(𝑃𝑄 ) (the vertically or horizontally stripped area of Figure 10), the two functions are equal.

Property 39. 𝑂 fp(𝐸𝐹 ) fp(𝑃𝑄 ), 𝑃𝑄 𝐸𝐹 (𝑂) = 𝐸𝐹 𝑃𝑄 (𝑂).

Proof. For any lattice 𝑂belonging to fp(𝐸𝐹 ) fp(𝑃𝑄 ), 𝑃𝑄 (𝑂) = 𝐸𝐹 (𝑂) = 𝑂, hence 𝑃𝑄 𝐸𝐹 (𝑂) = 𝐸𝐹 𝑃𝑄 (𝑂) = 𝑂. Similarly, for any lattice 𝑂belonging to fp(𝐸𝐹 ), then 𝐸𝐹 (𝑂) = 𝑂, so 𝑃𝑄 𝐸𝐹 (𝑂) = 𝑃𝑄 (𝑂). However, by Property 32, since 𝑂 fp(𝐸𝐹 ), 𝑃𝑄 (𝑂) fp(𝐸𝐹 ). This means that 𝐸𝐹 𝑃𝑄 (𝑂) = 𝑃𝑄 (𝑂) as well. The same can be proved for 𝑂 fp(𝑃𝑄 ) with Property 33.

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

if 𝑂 fp(𝐸𝐹 ) then 𝑃𝑄 𝐸𝐹 (𝑂) = 𝐸𝐹 𝑃𝑄 (𝑂) = 𝑃𝑄 (𝑂),

if 𝑂 fp(𝑃𝑄 ) then 𝑃𝑄 𝐸𝐹 (𝑂) = 𝐸𝐹 𝑃𝑄 (𝑂) = 𝐸𝐹 (𝑂).

In particular, this applies to the bounds of fp(𝐸𝐹 ) fp(𝑃𝑄 ):

Property 40.

𝐸𝐹 𝑃𝑄 (gfp(𝐸𝐹 )) = 𝑃𝑄 𝐸𝐹 (gfp(𝐸𝐹 )) = gfp(𝑃𝑄 ),

𝑃𝑄 𝐸𝐹 (lfp(𝑃𝑄 )) = 𝐸𝐹 𝑃𝑄 (lfp(𝑃𝑄 )) = lfp(𝐸𝐹 ).

Proof. The first part of these equations are consequences of Property 39, since gfp(𝐸𝐹 ) and lfp(𝑃𝑄 ) belong to fp(𝐸𝐹 ) and fp(𝑃𝑄 ), respectively. The second part is due to 𝑃𝑄 𝐸𝐹 (gfp(𝐸𝐹 )) = 𝑃𝑄 (gfp(𝐸𝐹 )) and 𝐸𝐹 𝑃𝑄 (lfp(𝑃𝑄 )) = 𝐸𝐹 (lfp(𝑃𝑄 )) for the same reason that gfp(𝐸𝐹 ) fp(𝐸𝐹 ) and lfp(𝑃𝑄 ) fp(𝑃𝑄 ), respectively. Property 34 shows that the second terms correspond to gfp(𝑃𝑄 ) and lfp(𝐸𝐹 ), respectively.

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

1:34 Euzenat

Example 12 shows that 𝐸𝐹 𝑃𝑄 (𝑂#) 𝑂# 𝑃𝑄 𝐸𝐹 (𝑂#) hence that the equality does not hold in general.

Example 12 (Counterexample to eqality in RCA). Consider Example 3.2 (p. 12), lfp(𝐸𝐹 ) =𝑂1 12 = { 𝐾1 1, 𝐿1 1 , 𝐾1 2, 𝐿1 2 } and gfp(𝑃𝑄 ) = 𝑂 12 = { 𝐾 1 , 𝐿 1 , 𝐾 2 , 𝐿 2 }. 𝑂# 12 = { 𝐾# 1 , 𝐿# 1 , 𝐾# 2, 𝐿# 2 } belongs to [lfp(𝐸𝐹 ) gfp(𝑃𝑄 )] but not to fp(𝐸𝐹 ) fp(𝑃𝑄 ). It happens that 𝐸𝐹 (𝑂# 12) = 𝑂 12 and 𝑃𝑄 (𝑂# 12) = 𝑂1 12, hence 𝑃𝑄 𝐸𝐹 (𝑂# 12) = 𝑃𝑄 𝐸𝐹 (𝑂# 12) = 𝑂 12 and 𝐸𝐹 𝑃𝑄 (𝑂# 12) = 𝐸𝐹 𝑃𝑄 (𝑂# 12) = 𝑂1 12. These two objects are not isomorphic. What can be said, in this case, is that 𝐸𝐹 𝑃𝑄 (𝑂# 12) 𝑃𝑄 𝐸𝐹 (𝑂# 12). This is the result of 𝜎which may add needed support (for 𝐶and 𝐵from 𝐴and 𝐷) and 𝜋which may suppress unsupported concepts (𝐴missing 𝐶and 𝐷 missing 𝐵). 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 9.

It may be that, as illustrated by Example 12, when 𝑃𝑄 is first applied, it suppresses non-supported attributes which cannot be recovered by scaling. Conversely, 𝐸𝐹 applied first may scale attributes ( 𝑝.𝐷in Example 12) which generate new concepts (𝐵) supporting previously non-supported concept (𝐷). These will not be suppressed any more. Property 41 shows that, in addition, there is still a homomorphism between the two resulting objects.

Property 41. 𝑂 𝒪, 𝐸𝐹 𝑃𝑄 (𝑂) 𝑃𝑄 𝐸𝐹 (𝑂).

Proof. 𝑃𝑄 (𝑂) 𝑂by Property 25. But 𝐸𝐹 is monotone (Property 23), hence 𝐸𝐹 𝑃𝑄 (𝑂) 𝐸𝐹 (𝑂). 𝑃𝑄 is also monotone (Property 23), thus 𝑃𝑄 𝐸𝐹 𝑃𝑄 (𝑂) 𝑃𝑄 𝐸𝐹 (𝑂). However, 𝑃𝑄 𝐸𝐹 (𝑂) fp(𝐸𝐹 ) fp(𝑃𝑄 ) so 𝑃𝑄 𝐸𝐹 (𝑂) = 𝐸𝐹 𝑃𝑄 (𝑂) (Property 39). Thus, 𝑃𝑄 𝐸𝐹 𝑃𝑄 (𝑂) = 𝐸𝐹 𝑃𝑄 𝑃𝑄 (𝑂) = 𝐸𝐹 𝑃𝑄 (𝑂). This means that 𝐸𝐹 𝑃𝑄 (𝑂) 𝑃𝑄 𝐸𝐹 (𝑂).

Alternative proof. The same reasoning can be held from 𝑂 𝐸𝐹 (𝑂) (Property 25) and 𝐸𝐹 and 𝑃𝑄

being monotone (Property 23). Hence, 𝑃𝑄 (𝑂) 𝑃𝑄 𝐸𝐹 (𝑂) and 𝐸𝐹 𝑃𝑄 (𝑂) 𝐸𝐹 𝑃𝑄 𝐸𝐹 (𝑂). But, 𝑃𝑄 𝐸𝐹 (𝑂) fp(𝐸𝐹 ) fp(𝑃𝑄 ), so 𝑃𝑄 𝐸𝐹 (𝑂) = 𝐸𝐹 𝑃𝑄 (𝑂) (Property 39). Thus 𝐸𝐹 𝑃𝑄 𝐸𝐹 (𝑂) = 𝑃𝑄 𝐸𝐹 𝐸𝐹 (𝑂) = 𝑃𝑄 𝐸𝐹 (𝑂). Hence, 𝐸𝐹 𝑃𝑄 (𝑂) 𝑃𝑄 𝐸𝐹 (𝑂).

The alternative proof is given here to show that starting from the 𝐸𝐹 or 𝑃𝑄 give the same result. It is thus unclear what to do with 𝐸𝐹 𝑃𝑄 and 𝑃𝑄 𝐸𝐹 in general. For instance, if one needs an operation to map elements of 𝒪to fp(𝐸𝐹 ) fp(𝑃𝑄 ), which one is preferable? There may be an interest in studying the interval [𝐸𝐹 𝑃𝑄 (𝑂) 𝑃𝑄 𝐸𝐹 (𝑂)]. Does it contain only fixed points or no fixed points? Are these the image of other lattices? This question can be answered if 𝑂can be compared to these bounds (Proposition 42): the intermediate families are not fixed points.

Proposition 42. 𝑂 𝒪\ (fp(𝐸𝐹 ) fp(𝑃𝑄 )):

if 𝑂 𝑃𝑄 𝐸𝐹 (𝑂), then 𝑂 [𝑂𝑃𝑄 𝐸𝐹 (𝑂)[, 𝑂 fp(𝐸𝐹 ) fp(𝑃𝑄 ), if 𝐸𝐹 𝑃𝑄 (𝑂) 𝑂, then 𝑂 ]𝐸𝐹 𝑃𝑄 (𝑂),𝑂], 𝑂 fp(𝐸𝐹 ) fp(𝑃𝑄 ).

Proof. Considering the first item of the proposition, 𝑂 𝑃𝑄 𝐸𝐹 (𝑂) can only occur if 𝐸𝐹 (𝑂) fp(𝑃𝑄 ), i.e. 𝑃𝑄 𝐸𝐹 (𝑂) = 𝐸𝐹 (𝑂). Indeed, if this were not the case, then 𝑃𝑄 would suppress attributes from 𝐸𝐹 (𝑂). However, since 𝑂 𝑃𝑄 𝐸𝐹 (𝑂), these could not be attributes from 𝑂, but only attributes added by 𝐸𝐹 . But since 𝐸𝐹 only adds attributes if they are supported and it starts with attributes from 𝑂, this is not possible. Thus, if 𝑂 [𝑂𝑃𝑄 𝐸𝐹 (𝑂)[ then 𝑂 [𝑂𝐸𝐹 (𝑂)[. However, 𝑂 cannot be a fixed point for 𝐸𝐹 because it contains all attributes of 𝑂which would scale to generate all those of 𝐸𝐹 (𝑂). Hence 𝑂 fp(𝐸𝐹 ) fp(𝑃𝑄 ).

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

The Fixed-Point Semantics of Relational Concept Analysis 1:35

𝑃𝑄 𝐸𝐹 (𝑂) = 𝐸𝐹 𝑃𝑄 (𝑂) 𝑂

Property 39

𝑂 𝑃𝑄 𝐸𝐹 (𝑂) = 𝐸𝐹 𝑃𝑄 (𝑂)

Property 39

𝑃𝑄 𝐸𝐹 (𝑂) = 𝑂= 𝐸𝐹 𝑃𝑄 (𝑂)

𝐸𝐹 𝑃𝑄 (𝑂) 𝑃𝑄 𝐸𝐹 (𝑂)

Property 41

Fig. 10. Illustration of the position of 𝑃𝑄 𝐸𝐹 (𝑂) and 𝐸𝐹 𝑃𝑄 (𝑂) depending on 𝑂 s origin (in dotted, 𝒪, in dashed fp(𝐸𝐹 ) fp(𝑃𝑄 ), in plain fp(𝐸𝐹 ) fp(𝑃𝑄 )). Colours correspond to that of Figure 8: green starting from fp(𝐸𝐹 ), red starting from fp(𝑃𝑄 ), blue starting outside of them.

The second item has a similar proof: 𝐸𝐹 𝑃𝑄 (𝑂) 𝑂can only occur if 𝑃𝑄 (𝑂) fp(𝐸𝐹 ), i.e. 𝐸𝐹 𝑃𝑄 (𝑂) = 𝑃𝑄 (𝑂). Indeed, if this were not the case, then 𝐸𝐹 would generate attributes from 𝑃𝑄 (𝑂). However, since 𝐸𝐹 𝑃𝑄 (𝑂) 𝑂, these could only be attributes of 𝑂which were suppressed by 𝑃𝑄 due to lack of support. But this is not possible because if they lacked support in 𝑂, there is not more support for them in 𝑃𝑄 (𝑂), which only reduces 𝑂. Thus, if 𝑂 ]𝐸𝐹 𝑃𝑄 (𝑂) 𝑂], then 𝑂 ]𝑃𝑄 (𝑂) 𝑂]. However, 𝑂 cannot be a fixed point for 𝑃𝑄 because it contains less attributes than 𝑂: if these attributes lacked supports in 𝑂, they would still lack it in 𝑂 . Hence, 𝑂 fp(𝐸𝐹 ) fp(𝑃𝑄 ).

This is illustrated by Example 13:

Example 13. In Example 12 (p. 34), 𝑂# 34 = { 𝐾# 3, 𝐿# 3 , 𝐾# 4, 𝐿# 4 } is a fixed point for neither 𝐸𝐹 nor 𝑃𝑄 . 𝑃𝑄 𝐸𝐹 (𝑂# 34) = 𝐸𝐹 (𝑂# 34) = 𝑂 34 and 𝐸𝐹 𝑃𝑄 (𝑂# 34) = 𝑃𝑄 (𝑂# 34) = 𝑂1 34. None of the objects in the interval between 𝑂# 34 and either 𝑂 34 or 𝑂1 34 belongs to fp(𝐸𝐹 ) fp(𝑃𝑄 ) as can be seen in Figure 9.

This result cannot be generalised to the interval ]𝐸𝐹 𝑃𝑄 (𝑂) 𝑃𝑄 𝐸𝐹 (𝑂)[ as shown by Example 14.

Example 14 (The subinterval may contain fixed points). Following Example 13, 𝑂 34 = { 𝐾 3, 𝐿 3 , 𝐾 4, 𝐿 4 } belongs to ]𝐸𝐹 𝑃𝑄 (𝑂# 34) 𝑃𝑄 𝐸𝐹 (𝑂# 34)[ = ]𝑂1 34, 𝑂 34[ as can be observed in Figure 9. However, 𝑂 34 fp(𝐸𝐹 ) fp(𝑃𝑄 ).

Proposition 42 can however be useful algorithmically. Indeed, if one considers the non-acceptable objects of Figure 9 on the same line as 𝑂# 34, then this result identifies as non acceptable two objects on the second and fourth line without testing them.

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

1:36 Euzenat

8 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 paper 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 paper defines the set of well-formed objects 𝒪, a function 𝐸𝐹 , generalising RCA, expanding a family, and a function 𝑃𝑄 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 (fp(𝐸𝐹 ) fp(𝑃𝑄 )). 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. In FCA, conceptual scaling is considered as a human-driven analysis tool: a knowledgeable person could provide attributes to be scaled for describing better the data to be analysed. In RCA, scaling is used as an extraction tool, with the drawback to potentially generate many attributes. By only extracting the least fixed point, RCA avoids generating too many of them. This is useful when generating a description logic TBox because all concepts are well-defined and necessary, but other contexts may benefit from exploiting other solutions. Beyond the minimal common acceptable lattices returned by RCA and the most detailed ones that RCA returns, algorithms may be developed for returning all acceptable solutions [2]. The characterisation of the structure of the space of acceptable solutions aims at contributing to this goal. However, our work does not provide an efficient way to obtain all elements of this set. This work also opens perspectives for helping users to identify the acceptable solution that they prefer. Beyond generating all solutions, another option is to offer users the opportunity to guide the navigation among them. The structure of admissible solutions and the associated functions may be fruitfully exploited in order to help users finding an acceptable solution featuring the concepts and attributes that they want and not unnecessary ones. An anonymous reviewer remarked that variations of RCA, such as those based on AOC-posets [9], may receive the same treatment. This is a perspective worth pursuing, that may lead to generalise the results presented here. Finally, the position of relational concept analysis with respect to formal concept analysis and Galois connections would be worth investigating. On the one hand, this work shows that, contrary to other extensions that use scaling to encode a problem within FCA, RCA cannot be encoded in FCA. Indeed, RCA admits various fixed points contrary to FCA. RCA is not just the application of a product or sequence of FCA, but relations between contexts introduce constraints between them leading to the possibility of alternative fixed points. Hence, an encoding would not be direct, so that it provides RCA solutions directly. On the other hand, other generalisations of FCA get closer to general Galois connections by extending the structure of attributes. The open question is whether RCA is another instance of a Galois connection extending FCA or if these two need a common generalisation.

Acknowledgments

This work has been partially funded by the ANR Elker project (ANR-17-CE23-0007-01). The author thanks Petko Valtchev for comments and suggestions on an earlier version of this work, Marianne Huchard for taking the pain to describe the trick used for forcing discrimination, Amedeo Napoli for explaining me RCA (and so many other

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

The Fixed-Point Semantics of Relational Concept Analysis 1:37

things), Jérôme David for reviewing the text, and Philippe Besnard for pointing to the Knaster-Tarski theorem. Anonymous reviews helped clarifying the paper.

[1] M. Atencia, J. David, J. Euzenat, A. Napoli, and J. Vizzini. 2020. Link key candidate extraction with relational concept analysis. Discrete applied mathematics, 273, 2 20. doi: 10.1016/J.DAM.2019.02.012. [2] M. Atencia, J. David, J. Euzenat, A. Napoli, and J. Vizzini. 2021. Relational concept analysis for circular link key extraction. Deliverable 1.2. Elker. 57 pp. https://moex.inria.fr/files/reports/elker-1.2.pdf. [3] F. Baader, D. Calvanese, D. Mc Guinness, D. Nardi, and P. Patel-Schneider, (Eds.) 2007. The description logic handbook: theory, implementations and applications. (2nd ed.). Cambridge University Press, Cambridge (UK). doi: 10.1017/cbo9780511711787. [4] F. Baader and F. Distel. 2008. A finite basis for the set of ℰℒ-implications holding in a finite model. In Proc. 6th International Conference on Formal Concept Analysis (ICFCA), Montréal (CA) (Lecture notes in computer science). Vol. 4933, 46 61. doi: 10.1007/978-3-540-7813 7-0_4. [5] R. Belohlávek. 2008. Introduction to formal concept analysis. Tech. rep. Univerzita Palackého, Olomouc (CZ). http://belohlavek.inf.upo l.cz/vyuka/Intro FCA.pdf. [6] A. Braud, X. Dolques, M. Huchard, and F. Le Ber. 2018. Generalization effect of quantifiers in a classification based on relational concept analysis. Knowledge-based systems, 160, 119 135. doi: 10.1016/J.KNOSYS.2018.06.011. [7] L. Chaudron and N. Maille. 2000. Generalized formal concept analysis. In Proc. 8th International Conference on Conceptual Structures (ICCS), Darmstadt (DE) (Lecture notes in computer science). Vol. 1867, 357 370. doi: 10.1007/10722280_25. [8] X. Dolques, M. Huchard, C. Nebut, and P. Reitz. 2012. Fixing generalization defects in UML use case diagrams. Fundamenta informaticae, 115, 4, 327 356. doi: 10.3233/FI-2012-658. [9] X. Dolques, F. Le Ber, and M. Huchard. 2013. AOC-posets: a scalable alternative to concept lattices for relational concept analysis. In Proc. of the 10th international conference on concept lattices and their applications (CLA), La Rochelle (FR), 129 140. https://ceur-ws.org /Vol-1062/paper11.pdf. [10] J. Euzenat. 2021. Fixed-point semantics for barebone relational concept analysis. In Proc. 16th international conference on formal concept analysis (ICFCA), Strasbourg (FR) (Lecture notes in computer science). Vol. 12773, 20 37. doi: 10.1007/978-3-030-77867-5_2. [11] J. Euzenat. 2023. Stepwise functional refoundation of relational concept analysis. Research report 9518. INRIA. doi: 10.48550/ar Xiv.231 0.06441. [12] S. Ferré and P. Cellier. 2020. Graph-FCA: an extension of formal concept analysis to knowledge graphs. Discrete applied mathematics, 273, 81 102. doi: 10.1016/J.DAM.2019.03.003. [13] S. Ferré and O. Ridoux. 2000. A logical generalization of formal concept analysis. In Proc. 8th International Conference on Conceptual Structures (ICCS), Darmstadt (DE) (Lecture notes in computer science). Vol. 1867, 371 384. doi: 10.1007/10722280_26. [14] B. Ganter and S. Kuznetsov. 2001. Pattern structures and their projections. In Proc. 9th International conference on conceptual structures (ICCS), Stanford (CA US) (Lecture Notes in Computer Science). Vol. 2120, 129 142. doi: 10.1007/3-540-44583-8_10. [15] B. Ganter, G. Stumme, and R. Wille, (Eds.) 2005. Formal concept analysis: foundations and applications. Springer, Heildelberg (DE). doi: 10.1007/978-3-540-31881-1. [16] B. Ganter and R. Wille. 1999. Formal Concept Analysis: mathematical foundations. Springer, Berlin (DE). doi: 10.1007/978-3-642-59830-2. [17] J.-L. Guigues and V. Duquenne. 1986. Familles minimales d implications informatives résultant d un tableau de données binaires. Mathématiques et sciences humaines, 95, 5 18. https://www.numdam.org/item/MSH_1986__95__5_0/. [18] R. Guimarães, A. Ozaki, C. Persia, and B. Sertkaya. 2023. Mining ℰℒ bases with adaptable role depth. Journal of artificial intelligence research, 76, 119 135. doi: 10.1613/jair.1.13777. [19] M. Huchard, M. Rouane Hacène, C. Roume, and P. Valtchev. 2007. Relational concept discovery in structured datasets. Annals of Mathematics and Artificial Intelligence, 49, 1, 39 76. doi: 10.1007/s10472-007-9056-3. [20] P. Keip, S. Ferré, A. Gutierrez, M. Huchard, P. Silvie, and P. Martin. 2020. Practical comparison of FCA extensions to model indeterminate value of ternary data. In Proc. 15th International Conference on Concept Lattices and Their Applications (CLA), Tallinn (EE) (CEUR Workshop Proceedings). Vol. 2668, 197 208. https://ceur-ws.org/Vol-2668/paper15.pdf. [21] J. Kötters. 2013. Concept lattices of a relational structure. In Proc. 20th International Conference on Conceptual Structures (ICCS), Mumbay (IN) (Lecture Notes in Computer Science). Vol. 7735, 301 310. doi: 10.1007/978-3-642-35786-2_23. [22] R. Missaoui, L. Kwuida, and T. Abdessalem, (Eds.) 2022. Complex data analytics with formal concept analysis. Springer, Cham (CH). doi: 10.1007/978-3-030-93278-7. [23] B. Nebel. 1990. Reasoning and revision in hybrid representation systems. Lecture Notes in Artificial Intelligence. Vol. 422. Springer, Berlin (DE). doi: 10.1007/BFB0016445. [24] A. Ouzerdine, A. Braud, X. Dolques, M. Huchard, and F. Le Ber. 2019. Adjusting the exploration flow in relational concept analysis an experience on a watercourse quality dataset. In Advances in Knowledge Discovery and Management (Studies in Computational

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.

1:38 Euzenat

Intelligence). R. Jaziri, A. Martin, M.-C. Rousset, L. Boudjeloud-Assala, and F. Guillet, (Eds.) Vol. 1004. Springer, 175 198. doi: 10.1007/978-3-030-90287-2_9. [25] S. Prediger. 1997. Logical scaling in formal concept analysis. In Proc. 5th International Conference on Conceptual Structures (ICCS), Seattle (WA US) (Lecture Notes in Computer Science). Vol. 1257, 332 341. doi: 10.1007/BFB0027881. [26] M. Rouane Hacène, M. Huchard, A. Napoli, and P. Valtchev. 2013. Relational concept analysis: mining concept lattices from multirelational data. Annals of Mathematics and Artificial Intelligence, 67, 1, 81 108. doi: 10.1007/S10472-012-9329-3. [27] M. Rouane Hacène, M. Huchard, A. Napoli, and P. Valtchev. 2013. Soundness and completeness of relational concept analysis. In Proc. 11th International Conference on Formal Concept Analysis (ICFCA), Dresden (DE) (Lecture notes in computer science). Vol. 7880, 228 243. doi: 10.1007/978-3-642-38317-5_15. [28] A. Tarski. 1955. A lattice-theoretical fixpoint theorem and its applications. Pacific journal of mathematics, 5, 2, 285 309. doi: 10.2140/pj m.1955.5.285. [29] M. Wajnberg. 2020. Analyse relationnelle de concepts: une méthode polyvalente pour l extraction de connaissance. Ph.D. Dissertation. Université du Québec à Montréal & Université de Lorraine. https://hal.science/tel-03042085.

Received 18 December 2023; revised 18 December 2024; accepted 26 April 2025

Journal of Artificial Intelligence Research, Vol. 83, Article 1. Publication date: June 2025.