Adding the power-set to description logics

DOI10.1016/J.TCS.2019.10.049zbMATH Open1433.68420arXiv1902.09844OpenAlexW2988960511WikidataQ126831231 ScholiaQ126831231MaRDI QIDQ1989328FDOQ1989328

Alberto Policriti, Laura Giordano

Publication date: 21 April 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: We explore the relationships between Description Logics and Set Theory. The study is carried on using, on the set-theoretic side, a very rudimentary axiomatic set theory Omega, consisting of only four axioms characterizing binary union, set difference, inclusion, and the power-set. An extension of ALC, ALC^Omega, is then defined in which concepts are naturally interpreted as sets living in Omega-models. In ALC^Omega not only membership between concepts is allowed---even admitting circularity---but also the power-set construct is exploited to add metamodeling capabilities. We investigate translations of ALC^Omega into standard description logics as well as a set-theoretic translation. A polynomial encoding of ALC^Omega in ALCIO proves the validity of the finite model property as well as an ExpTime upper bound on the complexity of concept satisfiability. We develop a set-theoretic translation of ALC^Omega in the theory Omega, exploiting a technique originally proposed for translating normal modal and polymodal logics into Omega. Finally, we show that the fragment LC^Omega of ALC^Omega, which does not admit roles and individual names, is as expressive as ALC^Omega.

Full work available at URL: https://arxiv.org/abs/1902.09844

zbMATH Keywords

description logicknowledge representationset theory

Mathematics Subject Classification ID

Knowledge representation (68T30) Logic in artificial intelligence (68T27) Nonclassical and second-order set theories (03E70) Applications of set theory (03E75)

Cites Work

• Modal logic
• Title not available (Why is that?)
• Title not available (Why is that?)
• Set Theory
• The Description Logic Handbook
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Decision procedures for elementary sublanguages of set theory. VI. Multi-level syllogistic extended by the powerset operator
• Decision procedures for elementary sublanguages of set theory: X. Multilevel syllogistic extended by the singleton and powerset operators
• Formative processes with applications to the decision problem in set theory. I: Powerset and singleton operators
• A set-theoretic translation method for polymodal logics
• A Set-Theoretic Approach to ABox Reasoning Services
• On Sets and Graphs

This page was built for publication: Adding the power-set to description logics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1989328)