=Paper=
{{Paper
|id=Vol-1350/paper-16
|storemode=property
|title=Decidable
Contextualized DLs with Rigid Roles
|pdfUrl=https://ceur-ws.org/Vol-1350/paper-16.pdf
|volume=Vol-1350
|dblpUrl=https://dblp.org/rec/conf/dlog/BohmeL15
}}
==Decidable
Contextualized DLs with Rigid Roles==
https://ceur-ws.org/Vol-1350/paper-16.pdf
Decidable Contextualized DLs with Rigid Roles
Stephan Böhme?? and Marcel Lippmann
Institute for Theoretical Computer Science, Technische Universität Dresden,
{stephan.boehme,marcel.lippmann}@tu-dresden.de
Description logics (DLs) of context can be employed to represent and reason
about contextualized knowledge, which naturally occurs in practice [5,4,7,9,8].
Consider, for instance, the rôles played by a person in different contexts. The
person Bob, who works for the company Siemens, plays the rôle of an employee
of Siemens in the work context, whereas he might play the rôle of a customer
of Siemens in the context of private life. Here, access restrictions to the data of
Siemens might critically depend on Bob’s rôle. Moreover, DLs capable of repre-
senting contexts are vital to integrate distributed knowledge as argued in [5,4].
DLs are well-suited to describe contexts as formal objects with formal prop-
erties that are organized in relational structures, which are fundamental require-
ments for modeling contexts [11,12]. However, classical DLs lack expressive power
to formalize that some individuals satisfy certain concepts and relate to other in-
dividuals depending on a specific context. Therefore, often two-dimensional DLs
are employed [7,9,8]: One DL LM (the meta or outer logic) is used to represent
the contexts and their relationships to each other. LM is combined with a DL LO
(the object or inner logic) that captures the relational structure within each con-
text. Moreover, while some pieces of information depend on the context, other
pieces of information are shared throughout all contexts. For instance, a person’s
name is typically independent of the actual context. To be able to express that,
some concepts and roles a designated to be rigid, i.e. they are required to be
interpreted the same in all contexts. Unfortunately, if rigid roles are admitted,
reasoning in contextualized DLs is usually undecidable [7].
We propose and investigate a family of two-dimensional DLs LM JLO K that
meet the above requirements, but are a restricted form of the one defined in [7]
in the sense that we limit the interaction of LM and LO . More precisely, in our
family of contextualized DLs the outer DL can refer to the internal structure of
each context, but not vice versa. This represents contexts in a top-down perspec-
tive. Interestingly, reasoning in LM JLO K stays decidable with such a restriction,
even in the presence of rigid roles. In some sense our family of contextualized
DLs are similar to temporalized DLs investigated in [2,3,10].
For providing better intuition on how our formalism works, we examine the
above mentioned example a bit further. Consider the following axioms:
> v J∃ worksFor .{Siemens} v ∃ hasAccessRights.{Siemens}K (1)
Work v JworksFor (Bob, Siemens)K (2)
> v J∃ isCustomerOf .> v HasMoneyK (3)
??
Funded by DFG in the Research Training Group “RoSI” (GRK 1907).
Work Private
hasSSN Bob, hasSSN
Bob,
Person Person,
SSN HasMoney SSN
related
hasAccessRights isCustomerOf
worksFor
Siemens, hasCEO
Siemens,
Company .. Person Company
. Person
Fig. 1. Model of Axioms 1–7
J(∃ worksFor .>)(Bob)K v ∃ related .(Private u JHasMoney(Bob)K) (4)
Private v JisCustomerOf (Bob, Siemens)K (5)
Private u Work v ⊥ (6)
¬Work v J∃ worksFor .> v ⊥K (7)
Axiom 1 states that it holds true in all contexts that somebody who works for
Siemens also has access rights to certain data. Axiom 2 states that Bob is an
employee of Siemens in any work context. Axioms 3 and 4 say intuitively that if
Bob has a job, he will earn money, which he can spend as a customer. Axiom 5
formalizes that Bob is a customer of Siemens in any private context. Moreover,
Axiom 6 ensures that private and work contexts are disjoint. Finally, Axiom 7
states that the worksFor relation only exists in work contexts. A fundamental
reasoning task is to decide whether a set of axioms is consistent. For our example,
Figure 1 depicts a model. There, Bob’s social security number is linked to him
using a rigid role hasSSN since it does not change over the contexts.
Our family LM JLO K consists of combinations of two DLs, where we focus on
the cases where LM and LO are EL or DLs between ALC and SHOQ. Let OC ,
OR , and OI be respectively sets of concept, role, and individual names for the
object logic LO . Analogously, we define the sets MC , MR , and MI for the meta
logic LM . Let O = (OC , OR , OI ) and M = (MC , MR , MI ). Concepts, GCIs and
assertions are defined over the respective signatures O and M as usual [1].
Definition 1. Concepts of the object logic (o-concepts) are LO -concepts over O;
o-axioms are LO -axioms over O. Concepts of the meta logic (m-concepts) are de-
fined inductively: each LM -concept over M is an m-concept, and JαK is an m-con-
cept for an o-axiom α; and m-axioms are defined analogously. Boolean LM JLO K-
knowledge bases (LM JLO K-BKBs) are Boolean combinations of m-axioms.
Note that the syntax of the object level is precisely the one of LO , whereas
the syntax of the meta level also allows to put LO -axioms in place of concept
names. The semantics of LM JLO K is defined using nested interpretations, which
consist of O-interpretations (usual DL interpretations for the names in O) for the
Table 1. Complexity results for consistency in LM JLO K
LO no rigid names only rigid concepts rigid roles
LM EL ALC SHOQ EL ALC SHOQ EL ALC SHOQ
EL const Exp Exp const NExp NExp const 2Exp 2Exp
ALC Exp Exp Exp NExp NExp NExp NExp 2Exp 2Exp
SHOQ Exp Exp Exp NExp NExp NExp NExp 2Exp 2Exp
specific contexts and the relational structure between them (M-interpretation),
where all contexts have the same domain. Also, let OCrig ⊆ OC denote the set
of rigid concepts, and let ORrig ⊆ OR denote the set of rigid roles. Moreover, we
assume that individuals of LO are always interpreted the same in all contexts.
C
Definition 2. We call a tuple J = ( , ·J , ∆, (·Ic )c∈C ) a nested interpretation,
C C
where is a non-empty set (called contexts) and ( , ·J ) is an M-interpretation.
C
Moreover, Ic := (∆, ·Ic ) is an O-interpretation for every c ∈ , such that it holds
C
for all c, c0 ∈ that xIc = xIc0 for all x ∈ OI ∪ OCrig ∪ ORrig .
C
Definition 3. Let J = ( , ·J , ∆, (·Ic )c∈C ) be a nested interpretation. The map-
ping ·J is extended as follows: JαKJ := {c ∈ C | Ic |= α}. Moreover, J is a
C
model of the m-axiom β if ( , ·J ) is a model of β. This is extended to LM JLO K-
BKBs inductively as usual. We write J |= B if J is a model of the LM JLO K-
BKB B. We call B consistent if it has a model.
The complexity of consistency in LM JLO K is listed in Table 1. The lower bounds
are obtained using the ideas of [2,3] and hold already for the fragment ELJALCK,
even if only conjunctions of m-axioms are considered instead of BKBs. Without
rigid names, Exp-hardness follows from the complexity of LO . If rigid concept
and role names are allowed, we reduce the word problem for exponentially space-
bounded alternating Turing machines to obtain 2Exp-hardness. If only rigid
concept names are allowed, a reduction of an exponentially bounded version of
the domino problem yields NExp-hardness. For the upper bounds, we proceed
similar to what was done for ALC-LTL in [2,3] and reduce the consistency prob-
lem to two separate decision problems. First, we abstract our LM JLO K-BKB B
by replacing the m-concepts that consist of o-axioms by fresh concept names and
test this abstraction B 0 for consistency. With this abstraction, we loose, however,
the information on the o-axioms. In each model of B 0 , the fresh concept names
have some extensions, and are treated completely independently. The induced
o-axioms, however, may not be independent. It could be that some o-axioms are
inconsistent together. We check this in a separate step.
To conclude, we have proposed novel combinations of two DLs for represent-
ing contextual knowledge and analyzed their complexity. Interestingly, even in
the presence of rigid roles the consistency problem is still decidable. For more
details, see [6]. As future work apart from others, we envision that our deci-
sion procedures can be adapted to deal with temporalized context DLs such as
LT LJALCJALCKK.
References
1. Baader, F., Calvanese, D., McGuinness, D.L., Nardi, D., Patel-Schneider, P.F.
(eds.): The Description Logic Handbook: Theory, Implementation, and Applica-
tions. Cambridge University Press, 2nd edn. (2007)
2. Baader, F., Ghilardi, S., Lutz, C.: LTL over description logic axioms. In: Brewka,
G., Lang, J. (eds.) Proceedings of the 11th International Conference on Principles
of Knowledge Representation and Reasoning (KR 2008). pp. 684–694. AAAI Press,
Sydney, Australia (2008)
3. Baader, F., Ghilardi, S., Lutz, C.: LTL over description logic axioms. ACM Trans-
actions on Computational Logic 13(3) (2012)
4. Bao, J., Voutsadakis, G., Slutzki, G., Honavar, V.: Package-based description log-
ics. In: Stuckenschmidt, H., Parent, C., Spaccapietra, S. (eds.) Modular Ontologies:
Concepts, Theories and Techniques for Knowledge Modularization, Lecture Notes
in Computer Science, vol. 5445, pp. 349–371. Springer (2009)
5. Borgida, A., Serafini, L.: Distributed description logics: Assimilating information
from peer sources. Journal of Data Semantics 2800, 153–184 (2003)
6. Böhme, S., Lippmann, M.: Description logics of context with rigid roles revis-
ited. LTCS-Report 15-04, Chair for Automata Theory, Institute for Theoretical
Computer Science, Technische Universität Dresden (2015), see http://lat.inf.
tu-dresden.de/research/reports.html.
7. Klarman, S., Gutiérrez-Basulto, V.: ALCALC : A context description logic. In: Jan-
hunen, T., Niemelä, I. (eds.) Proceedings of the 12th European Conference on
Logics in Artificial Intelligence (JELIA 2010). Lecture Notes in Computer Science,
vol. 6341, pp. 208–220. Springer (2010)
8. Klarman, S., Gutiérrez-Basulto, V.: Two-dimensional description logics for context-
based semantic interoperability. In: Burgard, W., Roth, D. (eds.) Proceedings of
the 25th AAAI Conference on Artificial Intelligence (AAAI 2011). AAAI Press
(2011)
9. Klarman, S., Gutiérrez-Basulto, V.: Two-dimensional description logics of context.
In: Rosati, R., Rudolph, S., Zakharyaschev, M. (eds.) Proceedings of the 24th
International Workshop on Description Logics (DL 2011). vol. 745. CEUR-WS.org
(2011)
10. Lippmann, M.: Temporalised Description Logics for Monitoring Partially Observ-
able Events. Ph.D. thesis, TU Dresden, Germany (2014)
11. McCarthy, J.: Generality in artificial intelligence. Communications of the ACM
30(12), 1030–1035 (1987)
12. McCarthy, J.: Notes on formalizing context. In: Bajcsy, R. (ed.) Proceedings of the
13th International Joint Conference on Artificial Intelligence (IJCAI 1993). pp.
555–562. Morgan Kaufmann, Los Altos, Chambéry, France (1993)