The Expressive Power of DL-Lite

2014/12/18 by Camilo Thorne, Thorne, Camilo
Computer Science · #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #cs.LO

paper · pdf · doi:10.48550/arxiv.1412.5795

7pp

arxiv created 2015/02/18 · arxiv updated 2015/02/19

Abstract

Description logics are knowledge representation formalisms that provide the formal underpinning of the semantic web and in particular of the OWL Ontology Web Language. In this paper we investigate the expressive power of logic DL-Lite_R,\sqcap, and some of its computational properties. We rely on simulations to characterize the absolute expressive power of DL-Lite_R,\sqcap as a concept language, and to show that disjunction is not expressible. We also show that no simulation-based closure property exists for DL-Lite_R,\sqcap assertions. Finally, we show that query answering of unions of conjunctive queries is NP-complete.

Related

• Web ontology representation and reasoning via fragments of set theory
• An Experiment on the Connection between the DLs' Family DL<ForAllPiZero> and the Real World
• On Expansion and Contraction of DL-Lite Knowledge Bases
• Frontiers and Exact Learning of ELI Queries under DL-Lite Ontologies
• The Completeness of Reasoning Algorithms for Clause Sets in Description Logic ALC