Adding the power-set to description logics

DOI10.1016/J.TCS.2019.10.049MaRDI QIDQ1989328zbMATH OpenOpenAlexWikidataFDO

Authors Laura Giordano, Alberto Policriti

Publication date 21 April 2020

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

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)

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.

Recommendations

• A new description logic with set constraints and cardinality constraints on role successors
• On the relative expressiveness of description logics and predicate logics
• On the expressive power of description logics with cardinality constraints on finite and infinite sets
• Web ontology representation and reasoning via fragments of set theory
• scientific article; zbMATH DE number 1980927

Cites work

• scientific article; zbMATH DE number 3142195 (Why is no real title available?)
• scientific article; zbMATH DE number 4148058 (Why is no real title available?)
• scientific article; zbMATH DE number 42735 (Why is no real title available?)
• scientific article; zbMATH DE number 67503 (Why is no real title available?)
• scientific article; zbMATH DE number 1989660 (Why is no real title available?)
• A set-theoretic approach to ABox reasoning services
• A set-theoretic translation method for polymodal logics
• 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
• Modal logic
• On sets and graphs. Perspectives on logic and combinatorics
• Set Theory
• The Description Logic Handbook

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)