Role-Value Maps and General Concept Inclusions in the Minimal Description Logic with Value Restrictions or Revisiting Ol
- PDF / 2,270,229 Bytes
- 11 Pages / 595.276 x 790.866 pts Page_size
- 15 Downloads / 179 Views
TECHNICAL CONTRIBUTION
Role‑Value Maps and General Concept Inclusions in the Minimal Description Logic with Value Restrictions or Revisiting Old Skeletons in the DL Cupboard Franz Baader1 · Clément Théron2 Received: 31 October 2019 / Accepted: 6 March 2020 © The Author(s) 2020
Abstract We investigate the impact that general concept inclusions and role-value maps have on the complexity and decidability of reasoning in the description logic FL0 . On the one hand, we give a more direct proof for ExpTime-hardness of subsumption w.r.t. general concept inclusions in FL0 . On the other hand, we determine restrictions on role-value maps that ensure decidability of subsumption, but we also show undecidability for the cases where these restrictions are not satisfied. Keywords Description logic · Value restrictions · Role-value maps · FL0 · Decidability and complexity
1 Introduction Description logics (DLs) [6] are a well-investigated family of logic-based knowledge representation formalisms, which are used to define ontologies in applications domains such as the semantic web [9, 19] and in biology and medicine [20]. DLs are descended from semantic networks [28, 29] and frames [26] via the knowledge representation system KL-ONE [17]. The design goal of KL-ONE was, on the one hand, to provide its users with a knowledge representation (KR) language that is equipped with a well-defined syntax and a formal, unambiguous semantics, which was not always true for early KR approaches such as semantic networks and frames. On the other hand, reasoning over knowledge bases written in this language was supposed to be tractable (i.e., realizable by polynomial-time inference procedures) [15]. Thus, it came as a considerable shock to the community when it was shown that the second requirement is not satisfied by the language employed by KL-ONE for two independent reasons.
* Franz Baader franz.baader@tu‑dresden.de Clément Théron clement.theron@ens‑paris‑saclay.fr 1
TU Dresden, Dresden, Germany
ENS Paris-Saclay, Cachan, France
2
On the one hand, KL-ONE provided its users with the concept constructor role-value maps (RVMs), which can be employed to link role successor sets. For example, the concept described by the RVM
(𝖼𝗁𝗂𝗅𝖽◦𝖿𝗋𝗂𝖾𝗇𝖽 ⊆ 𝗄𝗇𝗈𝗐𝗌) collects all individuals that know all the friends of their children. The general form of such an RVM is (r1 ◦ ⋯ ◦rm ⊆ s1 ◦ ⋯ ◦sn ) , where r1 , … , sn are roles (i.e., binary predicates). It was shown in [30] that the presence of RVMs actually makes reasoning in KL-ONE undecidable. As a consequence, general RVMs were removed from KL-ONE-based KR languages, and are not available in any of the DLs employed by today’s DL systems. One possibility for avoiding the undecidability caused by RVMs is to restrict the roles occurring in them to being functional. This approach was employed by the CLASSIC system [14], where the corresponding constructor is called the same-as constructor. However, using same-as in place of RVMs only overcomes the undecidability problem if no general concept inclusions (G
Data Loading...
