Towards Description Logic on Concept Lattices?

Abstract

In this position paper we start with a motivation of our study of modal/description logics with values in concept lattices. Then we give a brief survey of approaches to lattice-valued modal and/or description logics. After that we study some methods of context symmetrization, because the description logic on concept lattices is defined for symmetric co ntexts only. We conclude with a list of problems related to comparison of different lattice-valued modal/description logics, different variants of context symmetrization and resulting description logics, decidability and axiomatization of these logics.

Introduction

c paper author(s), 2013. Published in Manuel Ojeda-Aciego, Jan Outrata (Eds.): CLA 2013, pp. 287{292, ISBN 978{2{7466{6566{8, Laboratory L3i, University of La Rochelle, 2013. Copying permitted only for private and academic purposes. represents derivative in the formal context T = (U RL, Key, F ). Recall that U RLSh&Ga = {Shilov, Garanina}0 in KG, U RLGr = {Grebeneva}0 in KY . So we can not write the following equality

U RLSh&Ga\Gr = {Shilov, Garanina}0 \ {Grebeneva}000, but have to write another one

U RLSh&Ga\Gr = {Shilov, Garanina}↓F \ {Grebeneva}↓S↑T ↓T , where ‘↓F ’ represents the lower derivative in the context F, ‘↓S’ — the lower derivative in the context S, and ‘↓T ’ and ‘ ↑T ’ — the lower and upper derivatives in the context T. We believe that it would be nice to process queries like this one but (unfortunately) modern search engines can not do it; a part of the reason for this inability is due to lack of theory for processing such multi-context queries.

At the same time polymodal and/or descriptive logics (DL) [1] provide language for presentation of queries as above. In particular, if T d denotes the inverse of the binary relation T , then Sh&Ga \ Gr may be represented in syntax of a polymodal logic by the following formula

[F ](Shilov&Garanina) & ¬[T ][T d][S]Grebeneva or in syntax of a description logic as the following concept term

∀F.(Shilov u Garanina) u ¬∀T.∀T d.∀S.Grebeneva.

An interpretation of FCA constructs in DL has been studied in [7]. In these studies DL has been extended by FCA-derivatives and provided with Kripke semantics; as a result all concept terms are interpreted by sets of objects, not by concepts (or their extents), a lattice-theoretic structure of formal concepts (that is so important advantage of FCA) is lost.

A variant of description logic (namely ALC, Attribute Language with Complements) with values in concept lattices was defined in [8] but without a concept negation; the concept negation was defined only in concept lattices for symmetric contexts (i.e. in contexts where sets of objects and attributes are equal and the binary relation is symmetric). It implies that if we would like to define concept lattice semantics for the DL concept term above, we have to symmetrize contexts F, S and T in some manner. In this position paper we present some preliminary results of our studies of ways of context symmetrization, formulate and discuss some topics that need more research. 2

Lattice-valued Modal and Description Logics

Modal and Description Logic are closely related but different research paradigms: they have different syntax and pragmatic, but very closely related semantics (in spite of different terminology). Lattice-valued modal logics were introduced in [3, 2] by M.C. Fitting. They were studied in the cited papers from a prooftheoretic point of view. Later several authors attempted study of these logics from algebraic perspective [5, 6, 9]. Basic definitions related to modal logics on lattices and completeness theorems can be found in [5].

Description Logic (DL) is a logic for reasoning about concepts. But there is also an algebraic formalism developed around concepts in terms of concept lattices, namely Formal Concept Analysis (FCA). In this section we recall in brief definition of description logic ALC on concept lattices of (symmetric) contexts and some properties that follow from this definition, please refer [8] for full details. We use notation and definitions for Description Logics from [1]1. For the basics and notation of Formal Concept Analysis, please, refer to [4].

Semantics of description logics on concept lattices comes from lattice-theoretic characterization of ‘positive’ (i.e. without negation) concept constructs (for close world semantics) that is given in the following proposition [8]. Proposition 1. Let (Δ, Υ ) be a terminological interpretation and P (Δ) = (2Δ, ∅, ⊆, Δ, ∪, ∩) be the complete lattice of subsets of Δ. Then semantics of ALC positive concept constructs >, ⊥, t, u, ∀, and ∃ enjoys the following properties in P (Δ): ( 1 ) Υ (>) = sup P (Δ), and Υ (⊥) = inf P (Δ); ( 2 ) Υ (X t Y ) = sup(Υ (X), Υ (Y )), and Υ (X uY ) = inf(Υ (X), Υ (Y )); ( 3 ) Υ (∀R. X) = sup{S ∈ P (Δ) : ∀s ∈ S∀t ∈ Δ((s, t) ∈ Υ (R) ⇒ t ∈ Υ (X))}, ( 4 ) Υ (∃R. X) = sup{S ∈ P (Δ) : ∀s ∈ S∃t ∈ Δ((s, t) ∈ Υ (R) & t ∈ Υ (X))}.

Conceptual interpretation is a formal context provided by an interpretation function.

Definition 1.

Conceptual interpretation is a four-tuple (G, M, I, Υ ) where (G, M, I) is a formal context, and an interpretation function Υ = ICS ∪ IRS, where CS and RS are standard concept and role symbols, and ( 1 ) ICS : CS → B(G, M, I) maps concept symbols to formal concepts, ( 2 ) IRS : RS → 2(G×G)∪(M×M) maps role symbols to binary relations. A formal context (G, M, I) or conceptual interpretation (G, M, I, Υ ) is said to be homogeneous (symmetric) if G = M (and binary relation I is symmetric in addition).

Semantics of ALC positive concept constructs >, ⊥, t, u, ∀, and ∃ as well as semantics of negative construct ¬ are defined in [8] as follows.

Definition 2.

Let (G, M, I, Υ ) be a conceptual interpretation, K be a formal context (G, M, I), and B = (K) be the concept lattice of K. The interpretation function Υ can be extended to all role terms in a terminological interpretation ((G ∪ M ), Υ ) in the standard manner so that Υ (R) is a binary relation on (G ∪ M ) for every role term R. The interpretation function Υ can be extended to all positive ALC concept terms as follows. ( 1 ) Υ (>) = sup B and Υ (⊥) = inf B; ( 2 ) Υ (X t Y ) = sup(Υ (X), Υ (Y )), and Υ (X u Y ) = inf(Υ (X), Υ (Y )); ( 3 ) Let Υ (X) = 1 But we use Υ instead of ‘·’ for terminological interpretation function for readability. (Ex0, In0) ∈ B. Then (a) Υ (∀R. X) = supK {(Ex, In) ∈ B : ∀o ∈ Ex ∀a ∈ In ∀o0 ∈ G ∃a0 ∈ M ((o, o0) ∈ Υ (R) ⇒ o0 ∈ Ex0, (a, a0) ∈ Υ (R), and a0 ∈ In0)}, (b) I(∃R. X) = supK {(Ex, In) ∈ B : ∀o ∈ Ex ∀a ∈ In ∃o0 ∈ G ∀a0 ∈ M ((a, a0) ∈ Υ (R) ⇒ (o, o0) ∈ Υ (R), o0 ∈ Ex0, and a0 ∈ In0)}. In addition, if K is a symmetric context and Υ (X) = (Ex, In) ∈ B, then Υ (¬X) = (In, Ex). The following proposition [8] states that for any conceptual interpretation every positive ALC concept term is an element of concept lattice; in addition, if an interpretation is symmetric then this fact holds for all ALC concept terms. Proposition 2. For any conceptual interpretation (G, M, I, Υ ), for every positive ALC concept term X, semantics Υ (X) is an element of B(G, M, I). For any symmetric conceptual interpretation (D, D, I, Υ ), for every ALC concept term X, semantics Υ (X) is an element of B(D, D, I). 3

Ways to Build a Symmetric Context

The above proposition 2 leads to the following idea: to define semantics of ALC with values in an arbitrary concept lattice by isomorphic embedding of the background context into a symmetric one in such a way that for the positive fragment of ALC the original semantics and the induced semantics equal each other. Below we examine some opportunities how to “symmetrize” a given context, i.e. to build a symmetric context from an arbitrary given background context. Below we are going to study how to build a symmetric context from a given one by set-theoretic and algebraic manipulations with a binary relation of the context. Without loss of generality we may assume that the background context is reduced [4] and has disjoint sets of objects and attributes.

Let K := (G, M, I) be a reduced context where G ∩ M = ∅ and Kd = (M, G, I−) be its dual context. Let also use the following notation for binary relations (on M and/or G): ( 1 ) ∅ be the empty binary relation, ( 2 ) × be a total binary relation, ( 3 ) E be the identity binary relation, ( 4 ) Ec be the complement for E. We would like to combine the cross-tables of K and the dual context G M Kd into the symmetric one in the following way: G ? I . Let us represent M I−1 ? the above cross-table in a shorter way as K?d K? and denote the corresponding symmetric context by K◦ := (G◦, M◦, I◦). Recall that B(G, M, I) is the concept lattice of the context K, B(G◦, M◦, I◦) is the concept lattice of the context K◦. Let us use the standard notation ‘0’ for derivatives in the background context K but (for distinction) the notation ‘◦’ for derivatives in the symmetric one. We are going to fill question quadrants by different combinations of ∅, ×, E and Ec. Below we study 9 of these 16 combinations.

Case 1. K∅d K∅ . It is the disjoint union of K and Kd. The concept lattice .

B(K◦) = B(K ∪ Kd) is a horizontal sum [4], i.e. the union of two sublattices B(K) and B(Kd), such that B(K) ∩ B(Kd) = {⊥, >}.

Case 2. K×d K∅ . The concept lattice of this context is isomorphic to the vertical sum [4] of the concept lattices B(Kd) and B(K) (where the concept lattice B(Kd) is upper than B(K)).

Case 3. (∅,×). This case is the same like a previous, but we have to swap components of the vertical sum.

Case 4. K×d ×K . We have here the direct sum K + Kd of contexts K and Kd [4] and the concept lattice of the sum is isomorphic to the product of the concept lattices B(K) × B(Kd). A pair (A, B) is a concept of the direct sum (K + Kd) iff (A ∩ G, B ∩ M ) is a concept of K and (A ∩ M, B ∩ G) is a concept of Kd. It implies that isomorphism is given by (A, B) 7→ ((A ∩ G, B ∩ M ), (A ∩ M, B ∩ G)).

Case 5. KEd EK . Let (X, Y ) ∈ B(K◦) be a concept and let X = A ∪. B where A ⊆ G, B ⊆ M . We have the following cases: ( 1 ) B = ∅. Let X = A. If |A| = 1, then (X, Y ) = ({a}, {a} ∪ A0), and (X, Y ) = (A, A0) otherwise. ( 2 ) A = ∅. Let X = B. If |B| = 1, then (X, Y ) = ({b}, {b} ∪ B0), and (X, Y ) = (B, B0) otherwise. ( 3 ) |B| = 1 and A 6= ∅. Let X = A ∪ {b}. If {b} ∈ A0 and |A| = 1, then (X, Y ) = ( a A { } ∪ {b}, {a} ∪ {b}), and if {b} ∈ A0 | | > 1, then (X, Y ) = (A ∪ {b}, {b}). ( 4 ) |B| > 1 and A 6= ∅. Let |B| > 1, then X = A ∪ B. If B ⊆ {a}0 and | | = 1, A then (X, Y ) = ({a} ∪ B, {a}).

Case 6. K∅d EK . This case is a very similar to the previous one. ( 1 ) B = ∅. (X, Y ) = (A, A0). ( 2 ) A = ∅. If |B| = 1 then (X, Y ) = ({b}, {b} ∪ B0) else (X, Y ) = (B, B0). ( 3 ) |B| = 1. If {b} ∈ A0, we have (X, Y ) = (A ∪ {b}, {b}). ( 4 ) |B| > 1. All the concepts in this case will be either > or ⊥.

Case 7. (E,∅). This case is similar to the previous.

Case 8. K×d EK . Let us use subcases as in the case 5. ( 1 ) B = ∅. (X, Y ) = (A, G ∪ A0). ( 2 ) A = ∅. If |B| = 1, then (X, Y ) = ({b}, {b} ∪ B0), and (X, Y ) = (B, B0) otherwise. ( 3 ) |B| = 1. If {b} ∈ A0, then (X, Y ) = (A ∪ {b}, {b} ∪ {b}0), else (X, Y ) = (A ∪ {b}, {b}0). ( 4 ) |B| > 1. (X, Y ) = (A ∪ B, B0).

Case 9. (E,×). This case is similar to the case 8. 4

Conclusion

Now we are ready to formulate several topics and problems that we consider natural and important for further research.

In [5] the definition for modal logics with values in a given finite distributive lattice L is presented. This definition is easy to expand on polymodal logics. In section 2 we represented the definition for description logic ALC (that can be considered as a polymodal version of K) with values in concept lattices of symmetric contexts. Assume that K is a finite symmetric context; then B(K) is a finite lattice, but it may not be a distributive lattice. Question: Assuming that B(K) is a finite distributive lattice, whether ALC with values in B(K) is a polymodal B(K)-ML?

In section 2 we represented the definition for description logic ALC with values in concept lattices of symmetric contexts and for positive fragment of ALC with values in arbitrary concept lattices. Questions: ( 1 ) Is decidable or axiomatizable the positive fragment of ALC with values in concept lattices? ( 2 ) Is decidable or axiomatizable ALC with values in concept lattices of symmetric contexts?

In the section 3 we examine 9 of 16 variants of context symmetrization. Topics for further research are following: ( 1 ) to study the remaining 7 cases of context symmetrization and isomorphic embedding with Ec in one or two free quadrants; ( 2 ) to examine under which embedding from these in these 16 the induced semantics of the positive fragment of ALC is equal to the original semantics.

References

1. Baader F., D. Calvanese , D. Nardi D.McGuinness , and P. Patel-Schneider (editors). The Description Logic Handbook: Theory,Implementation and Applications . Cambridge University Press, 2003 .

2. Fitting M.C. Many-valued modal logics II. Fund . Inform., 1992 , v. 17 , p. 5573 .

3. Fitting M.C. Many-valued modal logics . Fund . Inform., 1991 , v. 15 , p. 235254 .

4. Ganter B. , Wille R . Formal Concept Analysis . Mathematical Foundations . Springer Verlag, 1996 .

5. Maruyama Y. Algebraic Study of Lattice-Valued Logic and Lattice-Valued Modal Logic . In ICLA'09 Proceedings of the 3rd Indian Conference on Logic and Its Applications. Lecture Notes in Computer Science . Springer-Verlag Berlin, Heidelberg 2009, v. 5378 , p. 170 - 184 .

6. Maruyama Y. Reasoning about Fuzzy Belief and Common Belief: With Emphasison Incomparable Beliefs . In Proceedings of the 22nd International Joint Conference on Artificial Intelligence. AAAI Press/International Joint Conferences on Artificial Intelligence , Menlo Park, California, 2011 , Vol. 2 , p. 1008 - 1013 .

7. Shilov N.V. Garanina N.O. , Anureev I.S. Combining Two Formalism for Reasoning about Concepts . Proceedings of the 2007 International Workshop on Description Logics (DL2007) , Brixen Italy , 2007 . CEUR Workshop Proceedings v. 250 . p. 459 - 466 .

8. Shilov N.V. , Han S . -Y. A proposal of Description Logic on Concept Lattices . Proceedings of the Fifth International Conference on Concept Lattices and their Applications , 2007 . CEUR Workshop Proceedings, v. 331 , 2008 , p. 165 - 176 .

9. Shi H.-X. , Wang G . -J. Lattice-valued modal propositional logic and its completeness . Science China, Information Sciences . 2010 , v. 53 ( 11 ), p. 2230 - 2239 .