SCIENCE@home

Adding the Power-Set to Description Logics

Laura Giordano,A. Policriti

Published 2019 in Theoretical Computer Science

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.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-31 of 31 references · Page 1 of 1

CITED BY