Rough, Rougher, Roughest Extending β„°β„’ with a Hierarchy of Indiscernibility Relations Rafael PeΓ±aloza1 , Anni-Yasmin Turhan2 1 IKR3 Research Lab, University of Milano-Bicocca, Milan, Italy 2 Knowledge Representation Group, Paderborn University, Germany Abstract Rough sets use a partition of a base set induced by a given indiscernibility relation 𝜌. In practice such partitions can result from clustering the data. DLs with concept operators relying on a single 𝜌 for upper and lower approximations of concepts have been investigated so far. The use of a hierarchy of such equivalence relations as it can result from hierarchical clustering methods is not explored yet in a DL setting. In this paper we extend the rough DL β„°β„’πœŒβŠ₯ with a hierarchy of indiscernibility relations as and develop a decision procedure for testing subsumption. Keywords Rough logics, vagueness, subsumption 1. Introduction Rough description logics extend usual description logics by concept operators that use rough sets to add a qualitative form of vagueness to concepts. In the field of rough sets, the domain is partitioned by an equivalence relation, the so-called the indiscernibility relation 𝜌, that groups indistinguishable elements into equivalence classes, also known as granules. Based on this partition, each set 𝑀 is associated with two additional sets. One is the lower approximation 𝑀 , which contains all elements whose equivalence class is completely contained in 𝑀 . The second set is the upper approximation 𝑀 , which contains all those elements that belong to an equivalence class that has an overlap with 𝑀 . When applied to concepts, the lower approximation 𝐢 models the β€œstrong” or typical instances of 𝐢, while the upper approximation 𝐢 models elements that are at least β€œclose” or similar to instances of 𝐢. Rough description logics have been defined as extensions of several classical DLs ranging from β„°β„’ to π’œβ„’π’ž. Reasoning in those rough DLs has mostly been investigated in relation to subsumption [1, 2, 3, 4, 5] or answering conjunctive queries [6]. Rough DLs are well-behaved in the sense that reasoning in them is usually of the same complexity as for their classical counter parts. Besides simply admitting a controlled form of vagueness in concept descriptions, there are other uses of rough DLs for ontology building and maintenance such as ontology engineering [7] and modeling concept drift [8]. Already rough sets alone have been used to structure data early on [9] as they can cluster the data, and the vagueness they introduce makes them resilient against incomplete or noisy data. There have been indiscernibility relations devised for different application domains in the literature. Varying the β€œdegree” of indiscernibility, admits structuring the data into finer or coarser granules and thus considering the data on different levels of abstraction. There are also methods to obtain indiscernibility relations that give a hierarchy of granulations [7, 10, 11], that result in a linearly ordered set of indiscernibility relations. In more general settings, clustering algorithms are a prime means to structure data as these algorithms group data items according to their homogeneity or proximity into clusters. There is a plethora of such methods and corresponding implementations readily available. A common and well-used type of clustering methods are the hierarchical clustering methods like the classical COBWEB algorithm [12] DL 2024: 37th International Workshop on Description Logics, June 18–21, 2024, Bergen, Norway $ rafael.penaloza@unimib.it (R. PeΓ±aloza); turhan@uni-paderborn (A. Turhan) Β€ https://rpenalozan.github.io/ (R. PeΓ±aloza)  0000-0002-2693-5790 (R. PeΓ±aloza) Β© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR ceur-ws.org Workshop ISSN 1613-0073 Proceedings and its variants. These clustering algorithms partition the data and effectively construct a dendrogram of the data; i.e., they result in a hierarchy of clusters. The corresponding partitions are then a linearly ordered set of equivalence relations. The hierarchy of partitions obtained from hierarchical clustering or from indiscernibility relations motivates the extension of rough DLs by a finite, linearly ordered set of equivalence relations (being used as indiscernibility relations) 𝜌1 , . . . , πœŒπ‘› . The results of clustering the data can be incorporated in the knowledge base by augmenting the ABox with the role assertions for pairs from the same cluster, i.e., from pairs related by πœŒπ‘– . Such an augmentation of the ABox could be achieved by a mapping commonly used in ontology-based data access (OBDA) [13]. The idea to incorporate an indiscernibility relation in the ABox by an ODBA mapping was already described in [14]. In this paper we extend the rough DL β„°β„’πœŒβŠ₯ (originally introduced in [4]), which uses a single granula- 𝜌/lin tion by one indiscernibility relation, to β„°β„’βŠ₯ which uses a finite, linearly ordered set of indiscernibility 𝜌/lin relations, and as such admits the use of a hierarchy of granulations. In this initial study on β„°β„’βŠ₯ , we 𝜌/lin investigate subsumption in β„°β„’βŠ₯ and develop a decision procedure based on a completion algorithm 𝜌/lin that essentially computes canonical models for β„°β„’βŠ₯ TBoxes. This algorithm serves as a starting point for investigating ABox reasoning tasks for this logic. The paper is organised as follows: in the next 𝜌/lin section we introduce the rough DL β„°β„’βŠ₯ . In Section 3 we develop the reasoning algorithm based on a normal form and completion rules. In Section 4 we supply a brief discussion on possible extensions and we end the paper with conclusion and an outlook on future work. 𝜌/lin 2. The Logic β„°β„’βŠ₯ We consider an extension of β„°β„’πœŒβŠ₯ where several equivalence relations (representing indiscernibility at different levels of detail) are used. In our setting, these relations are totally ordered from the coarsest to the most finely-grained. More formally, given 𝑛 β‰₯ 1, we consider 𝑛 equivalence relations ∼1 , . . . , βˆΌπ‘› such that βˆΌπ‘– βŠ† βˆΌπ‘–+1 for all 1 ≀ 𝑖 < 𝑛. That is, ∼1 is the most fine-grained relation, while βˆΌπ‘› is the coarsest. Note that βˆΌπ‘– partitions each equivalence class of βˆΌπ‘–+1 into (possibly) smaller classes. 𝜌/lin Given a fixed but arbitrary 𝑛 ∈ N, the set of β„°β„’βŠ₯ concepts is constructed through the syntactic rule 𝑖 𝐢 ::= 𝐴 | ⊀ | βŠ₯ | 𝐢 βŠ“ 𝐢 | βˆƒπ‘Ÿ.𝐢 | 𝐢 𝑖 | 𝐢 where 𝐴 ∈ NC , π‘Ÿ ∈ NR , and 1 ≀ 𝑖 ≀ 𝑛. Concepts of the form 𝐢 𝑖 are called lower approximation of 𝐢 𝑖 𝜌/lin w.r.t. βˆΌπ‘– and those of the form 𝐢 are called upper approximation of 𝐢 w.r.t. βˆΌπ‘– . As usual, a β„°β„’βŠ₯ TBox 𝜌/lin (or ontology) is a finite set of GCIs of the form 𝐢 βŠ‘ 𝐷, where 𝐢 and 𝐷 are β„°β„’βŠ₯ concepts. The semantics is based on interpretations of the form ℐ = (Δℐ , ·ℐ , {βˆΌπ‘– | 1 ≀ 𝑖 ≀ 𝑛}) where (Δℐ , ·ℐ ) is a standard DL interpretation, and ∼1 , . . . , βˆΌπ‘› are equivalence relations over Δℐ such that βˆΌπ‘– βŠ† βˆΌπ‘–+1 holds for all 1 ≀ 𝑖 < 𝑛. Given an element 𝛿 ∈ Δℐ , we denote as [𝛿]𝑖 the equivalence class of 𝛿 w.r.t. βˆΌπ‘– , which is the class of all objects πœ‚ ∈ Δℐ such that (𝛿, πœ‚) ∈ βˆΌπ‘– . The interpretation function is extended 𝜌/lin to arbitrary β„°β„’βŠ₯ concepts as usual for ⊀, βŠ₯, βŠ“, and βˆƒ, while for the lower and upper approximations, we define (𝐢 𝑖 )ℐ := {𝛿 ∈ Δℐ | [𝛿]𝑖 βŠ† 𝐢 ℐ } and 𝑖 (𝐢 )ℐ := {𝛿 ∈ Δℐ | [𝛿]𝑖 ∩ 𝐢 ℐ ΜΈ= βˆ…}. An interpretation satisfies the GCI 𝐢 βŠ‘ 𝐷 (denoted as ℐ |= 𝐢 βŠ‘ 𝐷) iff 𝐢 ℐ βŠ† 𝐷ℐ . The interpretation ℐ is a model of the TBox 𝒯 (denoted ℐ |= 𝒯 ) iff ℐ |= 𝐢 βŠ‘ 𝐷 holds for all GCIs 𝐢 βŠ‘ 𝐷 ∈ 𝒯 . Note in particular that for every 𝛿 ∈ Δℐ and every 𝑖, with 1 ≀ 𝑖 < 𝑛, it holds that [𝛿]𝑖 βŠ† [𝛿]𝑖+1 , and 𝑖 𝑖+1 hence also (𝐢 𝑖+1 )ℐ βŠ† (𝐢 𝑖 )ℐ βŠ† (𝐢 )ℐ βŠ† (𝐢 )ℐ for all concepts 𝐢. The following proposition is a consequence of these properties. Proposition 1. For all 𝑖, 𝑗 with 1 ≀ 𝑖 ≀ 𝑗 ≀ 𝑛, all concepts 𝐢, and all interpretations ℐ the following equivalences hold: )︀ℐ )︀ℐ 1. (a) (𝐢 𝑖 ) 𝑗 = (𝐢 𝑗 )ℐ ; = (𝐢 𝑗 )ℐ ; (οΈ€ (οΈ€ (b) (𝐢 𝑗 ) 𝑖 (οΈ€ 𝑖 𝑗 )︀ℐ 𝑗 (οΈ€ 𝑗 𝑖 )︀ℐ 𝑗 2. (a) (𝐢 ) = (𝐢 )ℐ ; (b) (𝐢 ) = (𝐢 )ℐ ; 𝑖 )︀ℐ = (𝐢 𝑗 )ℐ ; and (οΈ€ 3. (𝐢 𝑗 ) (οΈ€ 𝑗 )︀ℐ 𝑗 4. (𝐢 ) 𝑖 = (𝐢 )ℐ . Proof. We prove only the claims 1. and 3.; the other two can be shown analogously. For Claim 1.(a), 𝛿 ∈ ((𝐢 𝑖 ) 𝑗 )ℐ iff [𝛿]𝑗 βŠ† (𝐢 𝑖 )ℐ iff (since βˆΌπ‘– βŠ† βˆΌπ‘— ) [𝛿]𝑖 βŠ† [𝛿]𝑗 βŠ† 𝐢 ℐ iff 𝛿 ∈ (𝐢 𝑗 )ℐ . Similarly for 1.(b), 𝛿 ∈ ((𝐢 𝑗 ) )ℐ iff [𝛿]𝑖 βŠ† (𝐢 𝑗 )ℐ iff for every πœ‚ ∈ [𝛿]𝑖 , it holds that [πœ‚]𝑗 βŠ† 𝐢 ℐ iff (since 𝑖 𝛿 βˆΌπ‘– πœ‚ holds and implies that 𝛿 βˆΌπ‘— πœ‚ holds) [𝛿]𝑗 βŠ† 𝐢 ℐ iff 𝛿 ∈ (𝐢 𝑗 )ℐ . 𝑖 For Claim 3., 𝛿 ∈ ((𝐢 𝑗 ) )ℐ iff [𝛿]𝑖 ∩ (𝐢 𝑗 )ℐ ΜΈ= βˆ… iff there exists πœ‚ ∈ [𝛿]𝑖 such that πœ‚ ∈ (𝐢 𝑗 )ℐ iff there is πœ‚ ∈ [𝛿]𝑖 with [πœ‚]𝑗 βŠ† 𝐢 ℐ iff (because 𝛿 βˆΌπ‘– πœ‚ holds and implies that 𝛿 βˆΌπ‘— πœ‚ holds) [𝛿]𝑗 βŠ† 𝐢 ℐ iff 𝛿 ∈ (𝐢 𝑗 )ℐ . If 𝑖 = 𝑗 Claims 1 and 2 from Proposition 1 cover idempotence of both kinds of approximations. This affects the design of the completion rules that treat propagation within the same level of roughness, that is w.r.t. one πœŒπ‘– . For 𝑖 < 𝑗 the claims from Proposition 1 indicate how information is to be propagated or absorbed between different levels of roughness. Other important properties which combine the approximation concept constructors for each given indiscernibility relation are the following, which were originally proven in [4]. 𝜌/lin Proposition 2. For any three β„°β„’βŠ₯ concepts 𝐢, 𝐷, 𝐸 and all 𝑖 with 1 ≀ 𝑖 ≀ 𝑛, the following properties hold: 𝑖 1. 𝒯 |= 𝐢 βŠ‘ 𝐷 iff 𝒯 |= 𝐢 βŠ‘ 𝐷 𝑖 ; and 𝑖 2. if 𝒯 |= 𝐢 βŠ‘ 𝐷 and 𝒯 |= 𝐷 βŠ‘ 𝐸 𝑖 , then 𝒯 |= 𝐢 βŠ‘ 𝐸 𝑖 ; and 𝑖 3. if 𝒯 |= 𝐢 βŠ‘ 𝐷 and 𝒯 |= 𝐷 𝑖 βŠ‘ 𝐸, then 𝒯 |= 𝐢 βŠ‘ 𝐸 𝑖 . These properties indicate how information is to be propagated within the same level of roughness. 𝜌/lin All of these properties will be useful when we design a reasoning algorithm for β„°β„’βŠ₯ in the following section. 𝜌/lin The rough DL β„°β„’πœŒβŠ₯ is the special case of β„°β„’βŠ₯ where 𝑛 = 1; that is, where only one equivalence 1 relation is used. Since β„°β„’βŠ₯ is a particular case of β„°β„’πœŒβŠ₯ , where the GCIs 𝐴 βŠ‘ 𝐴 1 and 𝐴 βŠ‘ 𝐴 are satisfied 𝜌/lin for all 𝐴 ∈ NC , β„°β„’βŠ₯ is obviously a generalisation of the classical DL β„°β„’βŠ₯ . As usual in these logics, we are mainly interested in deciding whether a consequence follows from an ontology; in this case, we consider the problem of deciding subsumption between two concept names. We say that 𝐴 ∈ NC is subsumed by 𝐡 ∈ NC w.r.t. the TBox 𝒯 (𝒯 |= 𝐴 βŠ‘ 𝐡) iff every model of 𝒯 also satisfies the GCI 𝐴 βŠ‘ 𝐡. 𝜌/lin 3. Reasoning in β„°β„’βŠ₯ We are interested in developing a reasoning algorithm capable of deciding subsumption relationships 𝜌/lin between concepts w.r.t. a given β„°β„’βŠ₯ TBox. As this logic is an extension of β„°β„’πœŒβŠ₯ , we extend the known completion algorithm [4] to handle the new cases required by the multiple indiscernibility relations available. As a first step, we need to limit the form that GCIs can take, requiring the TBox to comply with a normal form; that is, that all the axioms are of one of the forms 𝑖 𝐴1 βŠ“ 𝐴2 βŠ‘ 𝐢, 𝐴 βŠ‘ βˆƒπ‘Ÿ.𝐡, βˆƒπ‘Ÿ.𝐴 βŠ‘ 𝐢, 𝐴 𝑖 βŠ‘ 𝐢, 𝐴 βŠ‘ 𝐡 𝑖, π΄βŠ‘π΅ , Table 1 Normalisation rules. Where 𝐴 ∈ NC βˆͺ {⊀}, 𝐢, 𝐷 are complex concepts, and 𝑋 is a new concept name. NF1 𝐹 βŠ“ 𝐢 βŠ‘ 𝐸 βˆ’β†’ {𝐢 βŠ‘ 𝑋, 𝐹 βŠ“ 𝑋 βŠ‘ 𝐸} NF2 βˆƒπ‘Ÿ.𝐢 βŠ‘ 𝐸 βˆ’β†’ {𝐢 βŠ‘ 𝑋, βˆƒπ‘Ÿ.𝑋 βŠ‘ 𝐸} NF3 𝐢 𝑖 βŠ‘ 𝐸 βˆ’β†’ {𝐢 βŠ‘ 𝑋, 𝑋 𝑖 βŠ‘ 𝐸} 𝑖 NF4 𝐢 βŠ‘ 𝐸 βˆ’β†’ {𝐢 βŠ‘ 𝐸 𝑖 } NF5 𝐢 βŠ‘ 𝐷 βˆ’β†’ {𝐢 βŠ‘ 𝑋, 𝑋 βŠ‘ 𝐷} NF6 𝐴 βŠ‘ 𝐸 βŠ“ 𝐹 βˆ’β†’ {𝐴 βŠ‘ 𝐸, 𝐴 βŠ‘ 𝐹 } NF7 𝐴 βŠ‘ βˆƒπ‘Ÿ.𝐢 βˆ’β†’ {𝐴 βŠ‘ βˆƒπ‘Ÿ.𝑋, 𝑋 βŠ‘ 𝐢} NF8 𝐴 βŠ‘ 𝐢 𝑖 βˆ’β†’ {𝐴 βŠ‘ 𝑋 𝑖 , 𝑋 βŠ‘ 𝐢} 𝑖 𝑖 NF9 𝐴 βŠ‘ 𝐢 βˆ’β†’ {𝐴 βŠ‘ 𝑋 , 𝑋 βŠ‘ 𝐢} NF10 βŠ₯ βŠ‘ 𝐸 βˆ’β†’ βˆ… where 𝐴, 𝐡 ∈ NC βˆͺ {⊀}, 𝐢 ∈ NC βˆͺ {⊀, βŠ₯}, and 1 ≀ 𝑖 ≀ 𝑛.1 Any TBox 𝒯 can be transformed into normal form applying the rules from Table 1β€”where NF1 uses the commutativity of conjunctionβ€”until no rule can be applied anymore. The resulting TBox is a conservative extension of 𝒯 which, importantly, is only polynomially larger than 𝒯 as it is found after only a polynomial number of rule applications. Our completion algorithm extends the ideas introduced in [4] to handle lower and upper approxima- tion concepts. Briefly, the completion algorithm for β„°β„’πœŒβŠ₯ preserves, for each concept name 𝐴 appearing in a normalised TBox 𝒯 , a family of completion sets, which preserve the information of how the lower and upper approximations of other concept names relate to 𝐴. This information is needed for an adequate handling of the properties of these concept constructors. In the present case, we must extend this idea to differentiate between the available indiscernibility relations. More formally, for each 𝐴 ∈ NC βˆͺ {⊀} appearing in the normalised TBox 𝒯 , and for each 1 ≀ 𝑖 ≀ 𝑛 𝑖 we preserve two sets called 𝑆 (𝐴) and 𝑆 𝑖 (𝐴). In addition, we keep track of a set 𝑆(𝐴) and for each role name π‘Ÿ ∈ NR appearing in 𝒯 a set 𝑆(𝐴, π‘Ÿ). Hence, for each such 𝐴, we keep 2𝑛 + β„“ + 1 many such completion sets, where β„“ is the number of role names in 𝒯 . With polynomially many 𝐴s in the normalised TBox, the completion algorithm uses polynomially many completion sets. The elements of each completion set all belong to NC βˆͺ {⊀, βŠ₯}. The idea is that these sets are sound w.r.t. subsumption relations among simple concepts. Specifically, throughout the completion algorithm, the application of completion rules preserves the following invariants: 𝑖 𝑖 1. if 𝐡 ∈ 𝑆 (𝐴) then 𝒯 |= 𝐴 βŠ‘ 𝐡 2. if 𝐡 ∈ 𝑆 𝑖 (𝐴) then 𝒯 |= 𝐴 βŠ‘ 𝐡 𝑖 3. if 𝐡 ∈ 𝑆(𝐴) then 𝒯 |= 𝐴 βŠ‘ 𝐡 and 4. if 𝐡 ∈ 𝑆(𝐴, π‘Ÿ) then 𝒯 |= 𝐴 βŠ‘ βˆƒπ‘Ÿ.𝐡 for all 𝐴 ∈ NC βˆͺ {⊀}, 𝐡 ∈ NC βˆͺ {⊀, βŠ₯}, π‘Ÿ ∈ NR , and 1 ≀ 𝑖 ≀ 𝑛. These are essentially the same invariants that were used for β„°β„’πœŒβŠ₯ in [4]. The completion sets are initialized with obvious tautologies; that is, at the beginning of the algorithm the sets are defined as 𝑖 𝑆(𝐴) = 𝑆 (𝐴) := {𝐴, ⊀}, 𝑆 𝑖 (𝐴) := {⊀}, 𝑆(𝐴, π‘Ÿ) := βˆ… for all 𝐴 ∈ NC βˆͺ {⊀}, π‘Ÿ ∈ NR , 1 ≀ 𝑖 ≀ 𝑛. Clearly this initialization preserves the invariants mentioned above. These sets are extended through application of the completion rules described in Table 2. As 1 For brevity, we consider axioms of the form 𝐴 βŠ‘ 𝐡 as ⊀ βŠ“ 𝐴 βŠ‘ 𝐡. Table 2 𝜌/lin Completion rules for β„°β„’βŠ₯ . cr1 if {𝐡1 , 𝐡2 } βŠ† 𝑆(𝐴) and 𝐡1 βŠ“ 𝐡2 βŠ‘ 𝐢 ∈ 𝒯 , then add 𝐢 to 𝑆(𝐴) cr2 if 𝐡 ∈ 𝑆(𝐴) and 𝐡 βŠ‘ βˆƒπ‘Ÿ.𝐢 ∈ 𝒯 , then add 𝐢 to 𝑆(𝐴, π‘Ÿ) cr3 if 𝐡 ∈ 𝑆(𝐴, π‘Ÿ), 𝐢 ∈ 𝑆(𝐡) and βˆƒπ‘Ÿ.𝐢 βŠ‘ 𝐷 ∈ 𝒯 , then add 𝐷 to 𝑆(𝐴) cr4 if {𝐡1 , 𝐡2 } ∈ 𝑆 𝑖 (𝐴) and 𝐡1 βŠ“ 𝐡2 βŠ‘ 𝐢 ∈ 𝒯 , then add 𝐢 to 𝑆 𝑖 (𝐴) 𝑖 𝑖 cr5 if 𝐡1 ∈ 𝑆 𝑖 (𝐴), 𝐡2 ∈ 𝑆 (𝐴) and 𝐡1 βŠ“ 𝐡2 βŠ‘ 𝐢 ∈ 𝒯 , then add 𝐢 to 𝑆 (𝐴) cr6 if 𝐡 ∈ 𝑆 𝑖 (𝐴) and 𝐡 𝑖 βŠ‘ 𝐢 ∈ 𝒯 , then add 𝐢 to 𝑆 𝑖 (𝐴) 𝑖 cr7 if 𝐡 ∈ 𝑆 (𝐴) and 𝐡 βŠ‘ 𝐢 𝑖 ∈ 𝒯 , then add 𝐢 to 𝑆 𝑖 (𝐴) 𝑖 𝑖 𝑖 cr8 if 𝐡 ∈ 𝑆 (𝐴) and 𝐡 βŠ‘ 𝐢 ∈ 𝒯 , then add 𝐢 to 𝑆 (𝐴) cr9 if 𝐡 ∈ 𝑆 𝑖 (𝐴), then add 𝐡 to 𝑆(𝐴) 𝑖 cr10 if 𝐡 ∈ 𝑆(𝐴), then add 𝐡 to 𝑆 (𝐴) cr11 if 𝐡 ∈ 𝑆 𝑗 (𝐴) and 𝑖 < 𝑗, then add 𝐡 to 𝑆 𝑖 (𝐴) 𝑖 𝑗 cr12 if 𝐡 ∈ 𝑆 (𝐴) and 𝑖 < 𝑗, then add 𝐡 to 𝑆 (𝐴) cr13 if 𝐡 ∈ 𝑆 𝑖 (𝐴) and 𝐢 ∈ 𝑆(𝐡), then add 𝐢 to 𝑆 𝑖 (𝐴) 𝑖 𝑖 𝑖 cr14 if 𝐡 ∈ 𝑆 (𝐴) and 𝐢 ∈ 𝑆 (𝐡), then add 𝐢 to 𝑆 (𝐴) cr15 if 𝐡 ∈ 𝑆 𝑖 (𝐴) and 𝐢 ∈ 𝑆 𝑖 (𝐡), then add 𝐢 to 𝑆 𝑖 (𝐴) cr16 if 𝐡 ∈ 𝑆(𝐴, π‘Ÿ) and βŠ₯ ∈ 𝑆(𝐡), then add βŠ₯ to 𝑆(𝐴) 𝑖 𝑖 cr17 if 𝐡 ∈ 𝑆 (𝐴) and βŠ₯ ∈ 𝑆 (𝐡), then add βŠ₯ to 𝑆 𝑖 (𝐴) 𝑖 cr18 if βŠ₯ ∈ 𝑆 (𝐴), then add βŠ₯ to 𝑆 𝑖 (𝐴) usual for these kinds of algorithms, the rules are only applied if they add an element to one of the sets involved; that is, if the concept to be added is not already present in the set. The completion algorithm applies rules until no rule is applicable anymore; at that point, we say that the algorithm is saturated. Note that this algorithm becomes saturated after at most polynomially many rule applications (in 𝑛 and the size of 𝒯 ). Indeed, there are (2𝑛 + β„“ + 1)π‘š sets, where β„“ is the number of role names in 𝒯 and π‘š is the number of concept names in 𝒯 . Each of this sets contains at most π‘š + 2 elements (the concept names in 𝒯 plus ⊀ and βŠ₯). Since each rule application adds one element to one of the sets, at most (2𝑛 + β„“ + 1)(π‘š + 2)π‘š rule applications are needed before reaching saturation. In addition, the conditions for the application of a rule require only a lookup between the sets and the GCIs in 𝒯 , which can also be performed in polynomial time. Thus, overall the algorithm needs only polynomial time to be saturated. The result of the completion algorithm can be used to decide all the atomic subsumption relations entailed by the TBox 𝒯 . That is, for every 𝐴, 𝐡 ∈ NC we get that 𝒯 |= 𝐴 βŠ‘ 𝐡 iff 𝐡 ∈ 𝑆(𝐴). Soundness is a consequence of the invariants described above. Lemma 3. The completion algorithm preserves the four invariants, throughout all rule applications. Proof. The proof is by induction on rule applications. The induction base is satisfied by the initialization. For rules without rough constructors (cr1-cr3 and cr16) soundness was shown already in [15]. For rules cr6 to cr15, cr17, and cr18 soundness is a consequence of Propositions 1 and 2. Since the rules cr11 and cr12 treat the interaction of different indiscernibility relations, we give a detailed proof of them. For cr11, suppose 𝒯 |= 𝐴 βŠ‘ 𝐡 𝑖 and 𝑖 < 𝑗. For every model ℐ and every 𝛿 ∈ Δℐ , if 𝛿 ∈ 𝐴ℐ , then 𝛿 ∈ 𝐡 𝑗 ℐ and thus [𝛿]𝑗 βŠ† 𝐡 ℐ . Since from 𝑖 < 𝑗 follows that [𝛿]𝑖 βŠ† [𝛿]𝑗 , we obtain [𝛿]𝑖 βŠ† 𝐡 ℐ holds and thus 𝛿 ∈ 𝐡 𝑖 ℐ . This implies 𝒯 |= 𝐴 βŠ‘ 𝐡 𝑖 . The proof for cr12 is analogous. The only remaining rules are cr4 and cr5. For the rule cr4, suppose that 𝒯 |= 𝐴 βŠ‘ 𝐡1 𝑖 and 𝐴 βŠ‘ 𝐡𝑖 𝐴𝐷 βˆΌπ‘– 𝐴∼ 𝑖 𝐡 π΄βŠ‘π΅ 𝑖 𝐷 𝐴, 𝐡, 𝐢 𝐡 π΄βŠ‘π΅ 𝐴 𝐢 π΄βŠ‘πΆ 𝑖 π΄βŠ‘πΆ 𝐢 𝐡 𝑖 π΄βŠ‘π· 𝐷 𝐴𝐢 βˆΌπ‘– 𝐴𝐡 βˆΌπ‘– Figure 1: The construction of the model for the proof of Lemma 4. Each gray box is an equivalence class for βˆΌπ‘– . The details of [𝐴]βˆΌπ‘– are given, relative to the derived subsumptions depicted on the left. 𝒯 |= 𝐴 βŠ‘ 𝐡2 𝑖 . For every model ℐ and every 𝛿 ∈ Δℐ , if 𝛿 ∈ 𝐴ℐ then [𝛿]𝑖 βŠ† 𝐡1ℐ ∩ 𝐡2ℐ and hence (as ℐ |= 𝐡1 βŠ“ 𝐡2 βŠ‘ 𝐢) [𝛿]𝑖 βŠ† 𝐢 ℐ , which implies 𝒯 |= 𝐴 βŠ‘ 𝐢 𝑖 . Rule cr5 can be treated analogously. For the converse directionβ€”completenessβ€”we follow the usual approach of building a sort of canonical model of 𝒯 that serves as a counterexample for all the atomic subsumption relations which do not appear explicitly in the generated sets. The domain Δℐ of the canonical model is composed of three kinds of elements. First, as usual for the β„°β„’ family of DLs, it includes one domain element for each satisfiable concept name 𝐴 appearing in 𝒯 , which stands for a standard instance representing that concept; i.e., it is a minimal representative of 𝐴. Hence, it will belong to each concept 𝐡 that subsumes 𝐴 w.r.t. 𝒯 . The two other kinds of domain elements handle the lower and upper approximations of named concepts in the interpretation domain. For the lower approximation, we include, for each βˆΌπ‘– , with 1 ≀ 𝑖 ≀ 𝑛, an element π΄βˆΌπ‘– that belongs to all concepts 𝐡 such that 𝒯 |= 𝐴 βŠ‘ 𝐡 𝑖 . In other words, π΄βˆΌπ‘– keeps information about all the concept names 𝐡 such that all objects indiscernible from instances of 𝐴 are necessarily in 𝐡. Dealing with the upper approximations requires a more nuanced construction, as a single element cannot fully witness the existence of indiscernible elements belonging to different concepts. We handle 𝑖 this with the help of different objects. Specifically, for each concept name 𝐡 such that 𝒯 |= 𝐴 βŠ‘ 𝐡 , we create an element 𝐴𝐡 βˆΌπ‘– which is a representative instance of 𝐡 (i.e., belongs to 𝐡 and all its subsumers), but exists only through its connection to the representative of 𝐴. To handle the indiscernibility relations, these elements 𝐴, π΄βˆΌπ‘– , and 𝐴𝐡 βˆΌπ‘– all belong to the same βˆΌπ‘– -equivalence class. As this is not a trivial 𝑖 structure, we explain it in more detail here. Note that 𝒯 |= 𝐴 βŠ‘ 𝐡 means that every element of 𝐴 must be associated (via βˆΌπ‘– ) with some element of 𝐡. In particular, the representative of 𝐴 must have such an association as well. But we cannot connect 𝐴 to the representative of 𝐡 because the symmetry of βˆΌπ‘– 𝑖 would then entail that 𝐡 βŠ‘ 𝐴 , which is not necessarily a consequence of 𝒯 . We can also not choose only one representative, as we did for the lower approximations, because (again) we cannot guarantee that the representative belongs to other concepts that are not known subsumers of 𝐡. Figure 1 describes this intuition graphically. Each gray box is an equivalence class for βˆΌπ‘– . There can be more elements than those shown, in each class, but the figure zooms into some relevant elements of [𝐴]βˆΌπ‘– , given by the derivations shown at the left of the figure. Since 𝐴 βŠ‘ 𝐡 𝑖 , the object π΄βˆΌπ‘– belongs to the concept 𝐡. 𝑖 𝑖 𝑖 On the other hand, since 𝐴 is subsumed by 𝐡 , 𝐢 , and 𝐷 , we create the three objects 𝐴𝐡 𝐢 βˆΌπ‘– , π΄βˆΌπ‘– , and π΄π·βˆΌπ‘– , respectively. Importantly, these objects belong to the concepts 𝐡, 𝐢, and 𝐷 (respectively), but not to [𝐡]βˆΌπ‘– , [𝐢]βˆΌπ‘– , or [𝐷]βˆΌπ‘– , represented as the three boxes on the right. Before formalising this construction, we recall that βŠ₯ requires a special treatment when it appears as a subsumer of a concept name. If 𝒯 |= 𝐴 βŠ‘ βŠ₯, we know that every model makes 𝐴 empty, and hence 𝐴 is subsumed by all concepts. Rather than making all these relations explicit, we simply handle this special case separately. 𝜌/lin Lemma 4. Let 𝐴, 𝐡 be two concept names appearing in the normalised β„°β„’βŠ₯ TBox 𝒯 , and 𝑆(𝐴) the set obtained after saturation of the completion algorithm. If {𝐡, βŠ₯} ∩ 𝑆(𝐴) = βˆ…, then 𝒯 ΜΈ|= 𝐴 βŠ‘ 𝐡. Proof. We build a model ℐ of 𝒯 such that 𝐴ℐ ΜΈβŠ† 𝐡 ℐ . The domain of this interpretation is Δℐ := {𝐢, πΆβˆΌπ‘– , 𝐢∼ 𝐷 𝑖 | 1 ≀ 𝑖 ≀ 𝑛, and 𝐢, 𝐷 are concept names appearing in 𝒯 }. For each 𝑖, with 1 ≀ 𝑖 ≀ 𝑛, the equivalence relation βˆΌπ‘– is the transitive, symmetric, and reflexive closure of the relation 𝐷 {(𝐢, πΆβˆΌπ‘– ), (𝐢, 𝐢∼ 𝑖 ) | 𝐢, 𝐷 are concept names appearing in 𝒯 }. Note that all objects in Δℐ are of the form 𝐢, πΆβˆΌπ‘– , or 𝐢∼ 𝐷 . By the definition of the equivalence relations 𝑖 βˆΌπ‘– , for every 𝛿 ∈ Δℐ there exists some concept name 𝐢 such that 𝛿 βˆΌπ‘– 𝐢. In particular, this means that every equivalence class of βˆΌπ‘– contains at least one concept name or, in other terms, that for every 𝛿 ∈ Δℐ there exists some 𝐸 ∈ NC such that [𝛿]𝑖 = [𝐸]𝑖 . To define the interpretation function ·ℐ , we set for each concept name 𝐢 appearing in 𝒯 𝐢 ℐ := {𝐷 | 𝐢 ∈ 𝑆(𝐷)} βˆͺ {π·βˆΌπ‘– | 𝐢 ∈ 𝑆 𝑖 (𝐷)} βˆͺ 𝐸 𝑖 {𝐷∼ 𝑖 | 𝐢 ∈ 𝑆(𝐸), 𝐸 ∈ 𝑆 (𝐷)} βˆͺ 𝐸 {𝐷∼ 𝑖 | 𝐢 ∈ 𝑆 𝑖 (𝐷), 𝐸 ∈ NC } and for each role name π‘Ÿ π‘Ÿβ„ := {(𝐢, 𝐷) | 𝐷 ∈ 𝑆(𝐢, π‘Ÿ)} βˆͺ {(πΆβˆΌπ‘– , 𝐷) | 𝐷 ∈ 𝑆(𝐸, π‘Ÿ), 𝐸 ∈ 𝑆 𝑖 (𝐢)} βˆͺ 𝐸 𝑖 {(πΆβˆΌπ‘– , 𝐷) | 𝐷 ∈ 𝑆(𝐸, π‘Ÿ), 𝐸 ∈ 𝑆 (𝐢)} βˆͺ 𝐸 {(πΆβˆΌπ‘– , 𝐷) | 𝐷 ∈ 𝑆(𝐹, π‘Ÿ), 𝐹 ∈ 𝑆 𝑖 (𝐢), 𝐸 ∈ NC }. By construction 𝐴 ∈ 𝐴ℐ and since 𝐡 ∈ / 𝑆(𝐴) we know that 𝐴 ∈ / 𝐡 ℐ . It remains to show that this is indeed a model of 𝒯 . This is shown through a case distinction over the possible types of axioms admitted in the normal form. We show only the cases involving rough constructors. [Case 𝐢 𝑖 βŠ‘ 𝐷] If 𝛿 ∈ (𝐢 𝑖 )ℐ , then by definition [𝛿]𝑖 βŠ† 𝐢 ℐ . Let 𝐸 ∈ NC be such that [𝛿]𝑖 = [𝐸]𝑖 . Then πΈβˆΌπ‘– ∈ 𝐢 ℐ and hence 𝐢 ∈ 𝑆 𝑖 (𝐸). As the algorithm has finished, the rule cr6 is not applicable, this means that 𝐷 ∈ 𝑆 𝑖 (𝐸) and by cr9 𝐷 ∈ 𝑆(𝐸). Consider now an arbitrary 𝐸∼ 𝐹 ∈ [𝐸] . Since 𝑖 𝑖 𝐷 ∈ 𝑆 𝑖 (𝐸), by construction we know that 𝐸∼ 𝐹 ∈ 𝐷 ℐ . Overall, this means that 𝛿 ∈ [𝐸] βŠ† 𝐷 ℐ , which 𝑖 𝑖 proves the result. [Case 𝐢 βŠ‘ 𝐷 𝑖 ] If 𝛿 ∈ 𝐢 ℐ and [𝛿]𝑖 = [𝐸]βˆΌπ‘– for some 𝐸 ∈ NC , then by the rules cr9, cr10, and 𝑖 𝑖 cr14 it follows that 𝐢 ∈ 𝑆 (𝐸) which, by rule cr7 implies that 𝐷 ∈ 𝑆 𝑖 (𝐸) βŠ† 𝑆(𝐸) βŠ† 𝑆 (𝐸). Then, [𝛿]𝑖 = [𝐸]𝑖 βŠ† 𝐷ℐ ; that is, 𝛿 ∈ (𝐷 𝑖 )ℐ . 𝑖 𝑖 [Case 𝐢 βŠ‘ 𝐷 ] As in the previous case, if 𝛿 ∈ 𝐢 ℐ with [𝛿]𝑖 = [𝐸]𝑖 , then 𝐢 ∈ 𝑆 (𝐸). Rule cr8 𝑖 𝐷 ∈ 𝐷 ℐ . By construction, 𝐸 𝐷 ∈ [𝛿] , which implies that then implies that 𝐷 ∈ 𝑆 (𝐸) and hence πΈβˆΌπ‘– βˆΌπ‘– 𝑖 𝑖 [𝛿]𝑖 ∩ 𝐷ℐ ΜΈ= βˆ…, and hence 𝛿 ∈ (𝐷 )ℐ . Thus we have a decision procedure for subsumption in β„°β„’πœŒβŠ₯ . Overall, we get the main result from this paper. 𝜌/lin Theorem 5. Subsumption between concept names w.r.t. β„°β„’βŠ₯ TBoxes can be decided in polynomial time. Note that the completion algorithm can be used also to check TBox consistency and concept satis- fiability. For the latter, we have from Lemma 4 that 𝐴 is unsatisfiable w.r.t. 𝒯 iff βŠ₯ ∈ 𝑆(𝐴). For the former, we can add the GCI ⊀ βŠ‘ 𝑋 and check whether 𝑋 is unsatisfiable. 4. Discussions 𝜌/lin Admitting Nominals. Extending β„°β„’βŠ₯ with nominals would effectively give a means to identify 𝑖 and address a particular granule in the TBox by using the concept {π‘Ž} . This might be useful for some applications. The subsumption algorithm for rough β„°β„’++ in [4] even admits nominals, so that a 𝜌/lin completion algorithm for β„°β„’βŠ₯ extended by nominals would simply need to combine the techniques. However, admitting nominals in the TBox would also admit to change the clustering results by GCIs that add a nominal to a granule such as 𝑖 𝑖 𝑖 {π‘Ž} βŠ‘ 𝐢 or {π‘Ž} ≑ {𝑏} , 𝑖 or could remove individuals from a granule by disjointness axioms like π‘Ž 𝑖 βŠ“ 𝐢 βŠ‘ βŠ₯. This is not compatible with the idea of having the granules populated by a mapping from the results of a clustering algorithm. The TBox could then even contradict such a clustering. Nevertheless, it might be useful to admit nominals and their approximations in the query language to reason over a knowledge base. Partial Orders of Indiscernibility Relations. For this paper, we focused on a family of indiscerni- bility relations that form a total order, from the most fine-grained (least rough) to the roughest. A natural question is whether it is possible to relax the conditions to allow for partial orders between these equivalence relations. This remains an open problem at the time, yet we argue that it is as hard as the general case, where arbitrary equivalence relations (without any ordering between them) are chosen, even if we require the partial order to be connected. Indeed, if we have 𝑛 arbitrary equivalence relations, we can always represent them as a connected partial order of 𝑛 + 1 relations where the new relation ∼0 is contained in all others. The reason why arbitrary classes of indiscernibility relations is problematic is that there is no way to predict the relationships between objects. For instance, we can have 𝛼 ∼1 𝛽 ∼2 𝛾 and there be no relation between 𝛼 and 𝛾. A construction akin to our completion algorithm would need to preserve at least 2𝑛 different objects to keep track of this information. Yet, we still do not know whether another strategy could reduce the overall complexity to remain in polynomial time, or in a sub-exponential class. 5. Conclusions and Future Work In this paper we have extended the β„°β„’ family by another rough member, that admits a (linear) hierarchy of indiscernibility relations to be used in upper and lower approximation concepts. The resulting DL 𝜌/lin β„°β„’βŠ₯ can facilitate reasoning w.r.t. clustering results for data that vary in granularity. For the DL 𝜌/lin β„°β„’βŠ₯ , we have devised a subsumption algorithm based on completion rules. This algorithm runs in polynomial time and can also be employed to test satisfiability of concepts. 𝜌/lin The next thing to investigate for β„°β„’βŠ₯ would be reasoning problems that answer queries over the TBox together with an ABox. Instance checking and answering of conjunctive queries are so far only studied to a small extent for rough DLs. Usually, completion algorithms for subsumption readily extend to algorithms for instance checking, while their extension to algorithms for answering conjunctive queries is more challenging. Rough DLs have been employed for instance unification [16]. A similar task is solved in entity resolution. Here, sometimes also information on non-equivalence of entities is given to avoid unifi- cation. Likewise, some applications of rough sets consider a discernibility relation in addition to the indiscernibility relation. It would be interesting to extend rough DLs by a discernibility relation that can express that two elements are not members of the same equivalence class. As such a relation introduces a form of negation, it is not immediately clear how to extend the reasoning algorithms. Acknowledgments Partially supported by the MUR for the Department of Excellence DISCo at the University of Milano- Bicocca and under the PRIN project PINPOINT Prot. 2020FNEB27, CUP H45E21000210001; and by the European Union – Next Generation EU within the project NRPP M4C2, Investment 1.,3 DD. 341 - 15 march 2022 – FAIR – Future Artificial Intelligence Research – Spoke 4 - PE00000013 - D53C22002380006 References [1] C.-J. Liau, On rough terminological logics, in: Proc. of the 4th Int. Workshop on Rough Sets, Fuzzy Sets and machine Discovery (RSFD’96), 1996, pp. 47–54. [2] S. Schlobach, M. C. Klein, L. Peelen, Description logics with approximate definitions - precise modeling of vague concepts, in: Proc. of 19th Int. Joint Conference on Artificial Intelligence (IJCAI 2007), 2007, pp. 557–562. [3] C. M. Keet, Rough subsumption reasoning with rOWL, in: Proc. of the 2011 Ann. Conf. of the South African Inst. of Computer Scientists and Information Technologists, SAICSIT 2011, ACM, 2011, pp. 133–140. [4] R. PeΓ±aloza, T. Zou, Roughening the β„°β„’ envelope, in: Proc. of Int. Symposium on Frontiers of Combining Systems (FroCoS 2013), volume 8152 of LNCS, Springer, 2013, pp. 71–86. [5] C. d’Amato, N. Fanizzi, F. Esposito, T. Lukasiewicz, Representing uncertain concepts in rough description logics via contextual indiscernibility relations, in: Int. Workshop on Uncertainty Reasoning for the Semantic Web, volume 7123 of LNCS, Springer, 2013, pp. 300–314. [6] R. PeΓ±aloza, V. Thost, A.-Y. Turhan, Query answering for rough β„°β„’ ontologies, in: M. Thielscher, F. Toni (Eds.), Proceedings of the 16th International Conference on Principles of Knowledge Representation and Reasoning (KR’18), AAAI Press, 2018. [7] C. M. Keet, From granulation hierarchy to granular perspective, in: The 2009 IEEE International Conference on Granular Computing (GrC), IEEE Computer Society, 2009, pp. 306–311. doi:10. 1109/GRC.2009.5255108. [8] N. Fanizzi, C. d’Amato, F. Esposito, Conceptual clustering and its application to concept drift and novelty detection, in: S. Bechhofer, M. Hauswirth, J. Hoffmann, M. Koubarakis (Eds.), The Semantic Web: Research and Applications, 5th European Semantic Web Conference, ESWC, Proceedings, volume 5021 of Lecture Notes in Computer Science, Springer, 2008, pp. 318–332. doi:10.1007/978-3-540-68234-9_25. [9] Z. Pawlak, Reasoning about data - A rough set perspective, in: Proc. of First Int. Conf. on Rough Sets and Current Trends in Computing (RSCTC’98), volume 1424 of LNCS, Springer, 1998, pp. 25–34. [10] C. M. Keet, Granulation with indistinguishability, equivalence, or similarity, in: 2007 IEEE International Conference on Granular Computing (GrC 2007), IEEE Computer Society, 2007, pp. 11–16. doi:10.1109/GRC.2007.29. [11] S. Hirano, S. Tsumoto, Hierarchical clustering of non-euclidean relational data using indiscernibility-level, in: G. Wang, T. Li, J. W. Grzymala-Busse, D. Miao, A. Skowron, Y. Yao (Eds.), Rough Sets and Knowledge Technology, Third International Conference, RSKT, Pro- ceedings, volume 5009 of Lecture Notes in Computer Science, Springer, 2008, pp. 332–339. doi:10.1007/978-3-540-79721-0_47. [12] D. H. Fisher, Knowledge acquisition via incremental conceptual clustering, Mach. Learn. 2 (1987) 139–172. doi:10.1007/BF00114265. [13] G. Xiao, D. Calvanese, R. Kontchakov, D. Lembo, A. Poggi, R. Rosati, M. Zakharyaschev, Ontology- based data access: A survey, in: J. Lang (Ed.), Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, ijcai.org, 2018, pp. 5511–5519. URL: https: //doi.org/10.24963/ijcai.2018/777. doi:10.24963/IJCAI.2018/777. [14] C. M. Keet, Ontology engineering with rough concepts and instances, in: Proc. of 17th International Conference on Knowledge Engineering and Management by the Masses EKAW 2010, volume 6317 of LNCS, Springer, 2010, pp. 503–513. [15] F. Baader, S. Brandt, C. Lutz, Pushing the β„°β„’ envelope, in: Proc. of 18th Int. Joint Conference on Artificial Intelligence (IJCAI 2005), 2005. [16] M. C. Klein, P. Mika, S. Schlobach, Rough description logics for modeling uncertainty in instance unification, in: Proc. of 3rd ISWC Workshop on Uncertainty Reasoning for the Semantic Web, volume 327 of CEUR Workshop Notes, 2007.